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

编号：730 氧;）技林电孑科蕊火容GUILINUNIVERSITYOFELECTRONICTECHNOLOGY数据结构与算法课程设计说明书集合的交并差运算学院： 海洋信息工程学院专业:网络工程TOC\o"1-5"\h\z学生姓名： xx学号： xx指导教师：XX2017年12月21日目录\o"CurrentDocument"目录 2概述 3程序说明 3\o"CurrentDocument"1实验内容 41。1实验目的 4\o"CurrentDocument"1.2实验任务 41.3要求 42数据结构设计及流程图 52。 1抽象数据结构类型定义 5\o"CurrentDocument"2.2本程序包含四个模块 73测试数据 8\o"CurrentDocument"3.1源程序 8\o"CurrentDocument"3。 2测试数据及程序运行情况 144总结 15参考文献 15本演示程序的编写，主要运用的我们学的第二章《线性表》中的知识。线性结构的特点是:在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继.本程序需要两个抽象数据类型：有序表和集合。而且采用了单链表来实现。一、程序说明本程序主要利用单链表及函数，实现集合的交集、并集和差集运算.运行程序说明：菜单执行的命令包括〈0-7>：〈1〉“请输入A集合的个数与A集合元素”〈2〉“请输入8集合个数与B集合的元素〃〈3〉“A集合的有序集合”<4〉“B集合的有序集合”〈5〉“AB集合的并集〃<6>“AB集合的交集”〈7>“AB集合的差集”<0〉“退出〃注：展示程序中，集合元素限定为小写字母数据，以“回车键〃束标志。1、 实验内容1。1实验目的：设计一个演示集合的交、并、差的运算程序1。2实验任务1） 使用单链表来表示集合，完成集合的交集、并集、差等操作。2） 采用链表等数据结构。3） 集合的元素限定为数字和小写的英文字母1。3实验要求：初步完成总体设计，建立头文件，确定函数个数。完成以下条件：1） 界面清楚，函数功能划分好2） 总体设计应画流程图3） 程序要加必要的注释4） 提供测试方案注：程序多次测试，弥补漏洞。要求：1） 展示程序中，集合元素限定为小写字母数据。集合输入的形式为一以“回车键”束标志。2） 展示程序以用户和计算机的对话方式执行，即在程序输出显示“提示信息'之

后，然后再输入命令；相应的输入数据和运算结果显示在其后。3）程序执行的命令包括〈0-7〉：<1〉“请输入A集合的个数与A集合元素”<2>“请输入B集合个数与B集合的元素”〈3〉“A集合的有序集合”<4〉“B集合的有序集合”〈5>“AB集合的并集”<6〉“AB集合的交集〃〈7〉“AB集合的差集〃<0〉“退出”程序功能：计算两个的集合的交、并、差以及重新输入集合功能。一、数据结构设计及流程图实现功能:C=A+B：A.Add(l);C=A+B：A.Add(l);A.Add⑵：8.Addt3):⑵:A.Add(4):A.Add(9):B.Addt?): cout«C«wndl；町3〔8)；SetA:SetB；SetC:A,Add⑴；B.Add(3)；C=A*8；A.Add{2):B.Add(2);A.Add{4):日.Ad出7）：coul«C«endlA,Add(9)；e.Addifl};6集合的并集合的交集合的并为了实现上述程序的功能，应以有序单链表表示集合。为此，需要抽象数据类型：有序表和集合2.1数据类型定义1、//线性表的单链表存储结构typedefstructLNode{ElemTypedata；structLNode大next;}LinkList；1、 实现输出功能的函数voidDispList()//输出函数2、 输入门个元素的值，建立带表头结点的单链线性表LvoidCreateList_L1(LinkList大&L,intn)4、实现集合元素由小到大排序功能voidsort(LinkList大&L)5、 实现了将A、B集合的并集，并放到新的单链表C中voidUnion(LinkList*ha，LinkList*hb,LinkList大&hc)6、 实现了将A、B集合的交集，并放到新的单链表C中voidInterSect(LinkList*ha,LinkList*hb,LinkList大&hc)7、 实现了将A、B集合的差集，并放到新的单链表C中voidSubs(LinkList*ha,LinkList大hb,LinkList大&hc)8、 销毁表LvoidDestroyList(LinkList*&L)3、 主程序模块(){初始化；定义变量；While(){选择菜单Switch(){casel: case2： case3： }}Return0；}2.2本程序包含四个模块1） 主菜单模块2） 输入集合单元模块：运用单链表输入；3） 集合运算单元模块：实现集合的抽象数据类型;4） 有序表单元模块：实现有序表的抽象数据类型；模块关系：3.1测试数据：集合A={dop}，B={dli},运算其交集、并集、差集。3.2源程序：源程序代码如下：include〈iostream>include〈stdio.h>#include<malloc。h〉#include〈cstdio>usingnamespacestd；typedefcharElemType；typedefstructLNode(ElemTypedata；structLNode*next；}LinkList；voidDispList(LinkList*L)//输出函数{LinkList*p=L—>next;while(p!=NULL){printf("%c",p->data)；p=p-〉next;}printf("\n");}voidCreateList_L1(LinkList大&L,intn){//输入n个元素的值，建立带表头结点的单链线性表LLinkList*p,*q;L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL；q=L;for(inti=n；i>0； i){p=(LinkList*)malloc(sizeof(LinkList))；//生成新结点cin>>p->data；//输入元素值p—>next=NULL;q-〉next=p;//插入到表尾q=p;}}voidDestroyList(LinkList大&L){LinkList*p=L—>next，*pre=L;while(p!二NULL)(free(pre)；pre=p；p=pre一>next；}free(pre)；}voidsort(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;}}voidUnion(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=pa->next；}elseif(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!=NULL)(s=(LinkList*)malloc(sizeof(LinkList));s一〉data=pa—>data；pc—〉next=s；pc=s；pa=pa-〉next；}pc—〉next=NULL；}voidInterSect(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—>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;}voidSubs(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->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;}intmain()(LinkList*ha,大hb,*hc;

intn,k;while(1)(cout〈<”\n\t\t一集合的简单运算一\n\n〃;cout<〈"\t\t\t菜单\n”；cout<<”\t\t\t\n”；cout<<”\t\t\t1.请输入A集合个数与A集合的元素\n";cout<〈"\t\t\t 2.请输入Bintn,k;while(1)(cout〈<”\n\t\t一集合的简单运算一\n\n〃;cout<〈"\t\t\t菜单\n”；cout<<”\t\t\t\n”；cout<<”\t\t\t1.请输入A集合个数与A集合的元素\n";cout<〈"\t\t\t 2.请输入B集合个数与B集合的元素\n”；cout<〈”\t\t\t3。A集合的有序集合\n”；cout<<”\t\t\t4.B集合的有序集合\n"；cout〈〈”\t\t\t5。AB集合的并集\n";cout〈〈”\t\t\t6。AB集合的交集\n”；cout<<”\t\t\t7.AB集合的差集\n”;\n";\n"；cout〈<”\t\t\t 0.退出\n";\n"；cout<<"\t\t\tcout<〈”\t\t\t请选择(0—7):"；cin>>k；switch(k){case1:cout〈<”请输入A集合的个数与A集合元素："；cin>〉n;CreateList_L1(ha,n);break;case2:cout<〈”请输入B集合的个数与B集合元”；cin>〉n；CreateList_L1(hb,n);break；case3：sort(ha);cout<<"\nA的有序集合为：";DispList(ha)；break;case4：sort(hb)；cout<<"\nB的有序集合为："；DispList(hb);break；case5:Union(ha,hb,hc)；cout〈〈"\nAB集合的并集为："；DispList(hc);break;case6:InterSect(ha,hb,hc);cout〈〈"\nAB集合的交集为："；DispList(hc);break;桂林电子科技大学数据结构课程设计说明书case7:Subs(ha,hb,hc);cout<<”\nAB集合的差集为："；DispList(hc);break;case0：cout<<〃\n\t\t\t 谢谢使用！ \n〃；cout<<"\n\t\t\t按任意键退出。..°..\n"；return0；}//switch}//whileDestroyList(ha);DestroyList(hb);DestroyList(hc);return0;}3。3测试数据及运行情况选择功能<0—7〉23■156■23■156■.rr与与••X..-■-,■.IT-rp顷邙_"=一BBBnEJAhnL请选择输入A集合的个数与A集合的元素{dop}土至不=•=■芝二.H.B.呆MA@与与,TT*里乓杉杉弟3一fiBJ-ruvr-日白白mz.Z.-AA12J4SLVM请:1诸初W集合的个数与嶂合元素;3dDP输入B集合的个数与B集合的元素{dli}一-.■■'M-.-:.一-.■■'M-.-:..:Wg-B..-ftnB-上_•**一|-|B勺.Jzr1£n.日.日妃L、■B白土n二n二nA饨择＜0-?＞：2请输入蝶合的佛与B集合元素，3MA集合的有序集合—集合的简单运其一1

234

5固7

0请选择E-gD的有序集合为：dovB集合的有序集合与」••1元元的的?■1.TTiK靠哭4.一■sH・L•E±JBiIL:r-宕砂I--r二■-I舞AIIAIIABin12345670AB集合的并集宣口sAH-与与救蓍台耳禁nJr_AflEII1234E670清A；±<0-7>：5AB集合的交集打.卫打.卫请旅择CH6W集•含b•土桌7［，“AB集合的差集r5-—'.■'□_=r".g-“■w.身hr」一」一拓帝l:.nsi并交差•?■•1.H1Afl