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

《数据结构课程设计集合的交并差运算》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

桂林电子科技大学数据结构课程设计说明书编号：730数据结构与算法课程设计说明书集合的交并差运算学　　院：海洋信息工程学院专业：网络工程学生姓名：xx20 桂林电子科技大学数据结构课程设计说明书学号：xx指导教师：xx2017年12月21日目录目录2概述3程序说明31实验内容41.1实验目的41.2实验任务41.3要求42数据结构设计及流程图52.1抽象数据结构类型定义52.2本程序包含四个模块720 桂林电子科技大学数据结构课程设计说明书3测试数据83.1源程序83.2测试数据及程序运行情况144总结15参考文献15概述本演示程序的编写，主要运用的我们学的第二章《线性表》中的知识。线性结构的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。本程序需要两个抽象数据类型：有序表和集合。而且采用了单链表来实现。一、程序说明本程序主要利用单链表及函数，实现集合的交集、并集和差集运算。运行程序说明：20 桂林电子科技大学数据结构课程设计说明书菜单执行的命令包括<0-7>：<1>“请输入A集合的个数与A集合元素”<2>“请输入B集合个数与B集合的元素”<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<7>“AB集合的差集”<0>“退出”注：展示程序中，集合元素限定为小写字母数据，以“回车键”束标志。1、实验内容1.1实验目的：设计一个演示集合的交、并、差的运算程序1.2实验任务1）使用单链表来表示集合，完成集合的交集、并集、差等操作。2）采用链表等数据结构。3）集合的元素限定为数字和小写的英文字母20 桂林电子科技大学数据结构课程设计说明书1.3实验要求：1.初步完成总体设计，建立头文件，确定函数个数。2.完成以下条件:1)界面清楚，函数功能划分好2)总体设计应画流程图3)程序要加必要的注释4)提供测试方案注：程序多次测试，弥补漏洞。要求：1）展示程序中，集合元素限定为小写字母数据。集合输入的形式为一以“回车键”束标志。2）展示程序以用户和计算机的对话方式执行，即在程序输出显示“提示信息”之后，然后再输入命令；相应的输入数据和运算结果显示在其后。3）程序执行的命令包括<0-7>：<1>“请输入A集合的个数与A集合元素”<2>“请输入B集合个数与B集合的元素”<3>“A集合的有序集合”20 桂林电子科技大学数据结构课程设计说明书<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<7>“AB集合的差集”<0>“退出”程序功能：计算两个的集合的交、并、差以及重新输入集合功能。一、数据结构设计及流程图实现功能：集合的交集合的并为了实现上述程序的功能，应以有序单链表表示集合。为此，需要抽象数据类型：有序表和集合2.1数据类型定义20 桂林电子科技大学数据结构课程设计说明书1、//线性表的单链表存储结构typedefstructLNode{ElemTypedata;structLNode*next;}LinkList;1、实现输出功能的函数voidDispList()//输出函数2、输入n个元素的值，建立带表头结点的单链线性表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)20 桂林电子科技大学数据结构课程设计说明书8、销毁表LvoidDestroyList(LinkList*&L)1、主程序模块（）{初始化；定义变量；While（）{选择菜单Switch（）{case1：……case2:……case3：……}}Return0；}2.2本程序包含四个模块20 桂林电子科技大学数据结构课程设计说明书1）主菜单模块2）输入集合单元模块：运用单链表输入；3）集合运算单元模块：实现集合的抽象数据类型；4）有序表单元模块：实现有序表的抽象数据类型；模块关系：3.1测试数据：集合A={dop}，B={dli}，运算其交集、并集、差集。3.2源程序：源程序代码如下：20 桂林电子科技大学数据结构课程设计说明书#include#include#include#includeusingnamespacestd;typedefcharElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LinkList;voidDispList(LinkList*L)//输出函数{LinkList*p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf(" ");}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;20 桂林电子科技大学数据结构课程设计说明书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->datadata)pre=pre->next;p->next=pre->next;pre->next=p;p=q;}}voidUnion(LinkList*ha,LinkList*hb,LinkList*&hc)//求集合的并20 桂林电子科技大学数据结构课程设计说明书{LinkList*pa=ha->next,*pb=hb->next,*pc,*s;hc=(LinkList*)malloc(sizeof(LinkList));pc=hc;while(pa!=NULL&&pb!=NULL){if(pa->datadata){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)20 桂林电子科技大学数据结构课程设计说明书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->datadata)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;20 桂林电子科技大学数据结构课程设计说明书}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->datadata)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<<" tt—集合的简单运算— ";cout<<"ttt菜单 ";cout<<"ttt—————————— ";cout<<"ttt1.请输入A集合个数与A集合的元素 ";20 桂林电子科技大学数据结构课程设计说明书cout<<"ttt2.请输入B集合个数与B集合的元素 ";cout<<"ttt3.A集合的有序集合 ";cout<<"ttt4.B集合的有序集合 ";cout<<"ttt5.AB集合的并集 ";cout<<"ttt6.AB集合的交集 ";cout<<"ttt7.AB集合的差集 ";cout<<"ttt0.退出 ";cout<<"ttt——————————— ";cout<<"ttt请选择(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<<" A的有序集合为：";DispList(ha);break;case4:sort(hb);cout<<" B的有序集合为：";DispList(hb);break;case5:Union(ha,hb,hc);cout<<" AB集合的并集为：";DispList(hc);break;case6:InterSect(ha,hb,hc);cout<<" AB集合的交集为：";DispList(hc);break;case7:Subs(ha,hb,hc);cout<<" AB集合的差集为：";DispList(hc);break;case0:cout<<" ttt------谢谢使用！------- ";cout<<" ttt按任意键退出...... ";return0;}//switch}//whileDestroyList(ha);DestroyList(hb);DestroyList(hc);20 桂林电子科技大学数据结构课程设计说明书return0;}3.3测试数据及运行情况(1)选择功能<0-7>(2)输入A集合的个数与A集合的元素{dop}(3)输入B集合的个数与B集合的元素{dli}20 桂林电子科技大学数据结构课程设计说明书(1)A集合的有序集合(2)B集合的有序集合(3)AB集合的并集20 桂林电子科技大学数据结构课程设计说明书(1)AB集合的交集(2)AB集合的差集(3)退出程序20 桂林电子科技大学数据结构课程设计说明书在测试过程中出现过许多小问题，如：交集并集两者运算结果颠倒、菜单文字错误、菜单较长等问题，在认真查看修改后，这些问题得到了解决。4.总结：在完成此次的课程设计的过程中，通过自己的思考和努力，培养了自学能力和动手能力。并且由原先的被动的接受知识转换为主动的寻求知识，这可以说是学习方法上的一个很大的突破。在以往的传统的学习模式下，我们可能会记住很多的书本知识，但是通过课程设计，我们学会了如何将学到的知识转化为自己的东西，学会了怎么更好的处理知识和实践相结合的问题。通过编程实践，不仅开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力，更充分锻炼了我们的编程能力。在设计报告的写作过程中，我也学到了做任何事情都要有的心态，首先我明白了，出现的任何问题都不要轻视，要通过正确的途径去解决，在做事情的过程中要有耐心和毅力，不要一遇到困难就打退堂鼓，只要坚持下去就可以找到思路去解决问题的。20 桂林电子科技大学数据结构课程设计说明书在这次课程设计中我也知道了自己的编码能力不强，有待于进一步提高，但在老师和同学的帮助下，我坚持到了最后。我在这次课程设计中学到很多。在今后的学习中，我一定勤于思考，并灵活运用所学知识，多进行编程实践。在总结反思和编程训练中，不断提升自己的编程能力。相信在我的努力下，我的程序设计水平一定会不断提高。参考文献清华大学计算机系教材：数据结构（c语言版）严蔚敏、吴伟民编著20