数据结构课程设计集合的交并差运算

1、编号： 730 数据结构与算法课程设计说明书集合的交并差运算 学院： 海洋信息工程学院 专 业： 网络工程 学生姓名： xx 学 号： xx 指导教师： xx 2017年 12 月 21 日目录目录2概述3程序说明31 实验内容41.1实验目的41.2实验任务41.3要求42数据结构设计及流程图52.1抽象数据结构类型定义52.2本程序包含四个模块73测试数据83.1源程序83.2测试数据及程序运行情况144总结15参考文献15概述本演示程序的编写，主要运用的我们学的第二章线性表中的知识。线性结构的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一

2、的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。本程序需要两个抽象数据类型：有序表和集合。而且采用了单链表来实现。一、程序说明本程序主要利用单链表及函数，实现集合的交集、并集和差集运算。运行程序说明：菜单执行的命令包括<0-7>：<1>“请输入A集合的个数与A集合元素”<2>“请输入B集合个数与B集合的元素”<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<

3、;7>“AB集合的差集”<0>“退出”注：展示程序中，集合元素限定为小写字母数据，以“回车键”束标志。1、 实验内容1.1实验目的：设计一个演示集合的交、并、差的运算程序1.2实验任务1） 使用单链表来表示集合，完成集合的交集、并集、差等操作。2） 采用链表等数据结构。3） 集合的元素限定为数字和小写的英文字母1.3实验要求：1. 初步完成总体设计，建立头文件，确定函数个数。2. 完成以下条件:1) 界面清楚，函数功能划分好2) 总体设计应画流程图3) 程序要加必要的注释4) 提供测试方案注：程序多次测试，弥补漏洞。要求：1） 展示程序中，集合元素限定为小写字母数据。集合输入

4、的形式为一以“回车键”束标志。2）展示程序以用户和计算机的对话方式执行，即在程序输出显示“提示信息”之后，然后再输入命令；相应的输入数据和运算结果显示在其后。3）程序执行的命令包括<0-7>：<1>“请输入A集合的个数与A集合元素”<2>“请输入B集合个数与B集合的元素”<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<7>“AB集合的差集”<0>“退出”程序功能：计算两个的集合的交、并、差以及重新输入集合功能。一、数据结构设计及流程图

5、实现功能： 集合的交 集合的并为了实现上述程序的功能，应以有序单链表表示集合。为此，需要抽象数据类型：有序表和集合2.1数据类型定义1、/线性表的单链表存储结构typedef struct LNode ElemType data; struct LNode *next; LinkList;1、 实现输出功能的函数void DispList()/输出函数2、 输入n个元素的值，建立带表头结点的单链线性表Lvoid CreateList_L1(LinkList *&L,int n)4、实现集合元素由小到大排序功能void sort(LinkList *&L)5、实现了将A、B集合的

6、并集，并放到新的单链表C中void Union(LinkList *ha,LinkList*hb,LinkList*&hc)6、实现了将A、B集合的交集，并放到新的单链表C中void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc)7、实现了将A、B集合的差集，并放到新的单链表C中void Subs(LinkList *ha,LinkList*hb,LinkList*&hc)8、销毁表Lvoid DestroyList(LinkList *&L)3、 主程序模块（）初始化；定义变量；While（）选择菜单Switc

7、h（）case1：case2:case3：Return 0； 2.2本程序包含四个模块1）主菜单模块2）输入集合单元模块：运用单链表输入；3）集合运算单元模块：实现集合的抽象数据类型；4）有序表单元模块：实现有序表的抽象数据类型；模块关系： 3.1测试数据：集合A=dop，B=dli，运算其交集、并集、差集。3.2源程序：源程序代码如下：#include <iostream>#include<stdio.h>#include<malloc.h>#include<cstdio>using namespace std;typedef char Ele

8、mType;typedef struct LNodeElemType data; struct LNode *next; LinkList;void DispList(LinkList*L)/输出函数LinkList *p=L->next; while(p!=NULL) printf("%c ",p->data); p=p->next; printf("n");void CreateList_L1(LinkList *&L,int n) /输入n个元素的值，建立带表头结点的单链线性表L LinkList *p,*q; L=(Li

9、nkList*)malloc(sizeof(LinkList); L->next=NULL; q=L; for(int i=n;i>0;-i) p=(LinkList*)malloc(sizeof(LinkList);/生成新结点 cin>>p->data;/输入元素值 p->next=NULL; q->next=p;/插入到表尾 q=p; void DestroyList(LinkList *&L)LinkList*p=L->next,*pre=L; while(p!=NULL) free(pre); pre=p; p=pre->

10、next; free(pre);void sort(LinkList *&L) /从小到大排序LinkList *pre,*p,*q; p=L->next->next; L->next->next=NULL; while(p!=NULL) q=p->next; pre=L; while(pre->next!=NULL&&pre->next->data<p->data) pre=pre->next; p->next=pre->next; pre->next=p; p=q; void Uni

11、on(LinkList *ha,LinkList*hb,LinkList*&hc) /求集合的并LinkList *pa=ha->next,*pb=hb->next,*pc,*s; hc=(LinkList*)malloc(sizeof(LinkList); pc=hc; while(pa!=NULL &&pb!=NULL ) if(pa->data<pb->data) s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=

12、pa->next; else if(pa->data>pb->data) s=(LinkList*)malloc(sizeof(LinkList); s->data=pb->data; pc->next=s; pc=s; pb=pb->next; else s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pb=pb->next; if(pb!=NULL) pa=pb; while(pa!=NU

13、LL) s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pc->next=NULL;void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc)/求两个有序集合的交用尾插法LinkList *pa=ha->next,*pb,*pc,*s; hc=(LinkList*)malloc(sizeof(LinkList); pc=hc; while(pa!=NULL) pb=hb->

14、next; while(pb!=NULL&&pb->data<pa->data) pb=pb->next;if(pb!=NULL &&pb->data=pa->data)/B节点在A节点中复制A节点 s=(LinkList*)malloc(sizeof(LinkList); s->data=pa->data; pc->next=s; pc=s; pa=pa->next; pc->next=NULL;void Subs(LinkList *ha,LinkList*hb,LinkList*&h

15、c) /求两个有序集合的差 LinkList *pa=ha->next,*pb,*pc,*s; hc=(LinkList*)malloc(sizeof(LinkList); pc=hc; while(pa!=NULL) pb=hb->next; while(pb!=NULL&&pb->data<pa->data) pb=pb->next;if(!(pb!=NULL &&pb->data=pa->data)/B节点不在A节点中复制A节点 s=(LinkList*)malloc(sizeof(LinkList); s-

16、>data=pa->data; pc->next=s; pc=s; pa=pa->next; pc->next=NULL;int main()LinkList *ha,*hb,*hc; int n,k; while(1) cout<<"ntt 集合的简单运算nn" cout<<"ttt 菜单 n" cout<<"ttt n"cout<<"ttt 1. 请输入A集合个数与A集合的元素 n"cout<<"ttt 2. 请

17、输入B集合个数与B集合的元素 n" cout<<"ttt 3. A集合的有序集合 n" cout<<"ttt 4. B集合的有序集合 n" cout<<"ttt 5. AB集合的并集 n" cout<<"ttt 6. AB集合的交集 n" cout<<"ttt 7. AB集合的差集 n" cout<<"ttt 0. 退出 n" cout<<"ttt n" cout

18、<<"ttt 请选择(0-7):" cin>>k; switch(k) case 1: cout<<"请输入A集合的个数与A集合元素："cin>>n; CreateList_L1(ha,n);break;case 2:cout<<"请输入B集合的个数与B集合元"cin>>n;CreateList_L1(hb,n); break;case 3:sort(ha);cout<<"n A的有序集合为："DispList(ha);break;

19、case 4:sort(hb);cout<<"n B的有序集合为："DispList(hb);break;case 5:Union(ha,hb,hc);cout<<"n AB集合的并集为："DispList(hc);break;case 6:InterSect(ha,hb,hc);cout<<"n AB集合的交集为：" DispList(hc);break;case 7:Subs(ha,hb,hc);cout<<"n AB集合的差集为："DispList(hc);break;case 0: cout<<"nttt- 谢谢使用！-n"cout<<"nttt按任意键退出.n" return 0; / switch /while DestroyList(ha); DestroyList(hb); DestroyList(hc); return 0;3.3测试数据及运行情况(1) 选择功能<0-7>(2) 输入A集合的个数与A集合的元素dop(3) 输入