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

编号： 730 数据结构和算法课程设计说明书集合交并差运算 学院： 海洋信息工程学院 专 业： 网络工程 学生姓名： xx 学 号： xx 指导老师： xx 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）存在唯一一个被称做“最终一个”数据元素；（3）除第一个之外，集合中每个数据元素均只有一个前驱；（4）除最终一个之外，集合中每个数据元素均只有一个后继。本程序需要两个抽象数据类型：有序表和集合。而且采取了单链表来实现。一、程序说明本程序关键利用单链表及函数，实现集合交集、并集和差集运算。运行程序说明：菜单实施命令包含：“请输入A集合个数和A集合元素”“请输入B集合个数和B集合元素”“A集合有序集合”“B集合有序集合”“AB集合并集”“AB集合交集”“AB集合差集”“退出”注：展示程序中，集合元素限定为小写字母数据，以“回车键”束标志。1、 试验内容1.1试验目标：设计一个演示集合交、并、差运算程序1.2试验任务1） 使用单链表来表示集合，完成集合交集、并集、差等操作。2） 采取链表等数据结构。3） 集合元素限定为数字和小写英文字母1.3试验要求：1. 初步完成总体设计，建立头文件，确定函数个数。2. 完成以下条件:1) 界面清楚，函数功效划分好2) 总体设计应画步骤图3) 程序要加必需注释4) 提供测试方案注：程序数次测试，填补漏洞。要求：1） 展示程序中，集合元素限定为小写字母数据。集合输入形式为一以“回车键”束标志。2）展示程序以用户和计算机对话方法实施，即在程序输出显示“提醒信息”以后，然后再输入命令；对应输入数据和运算结果显示在其后。3）程序实施命令包含：“请输入A集合个数和A集合元素”“请输入B集合个数和B集合元素”“A集合有序集合”“B集合有序集合”“AB集合并集”“AB集合交集”“AB集合差集”“退出”程序功效：计算两个集合交、并、差和重新输入集合功效。一、数据结构设计及步骤图实现功效： 集合交 集合并为了实现上述程序功效，应以有序单链表表示集合。为此，需要抽象数据类型：有序表和集合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集合并集，并放到新单链表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（）选择菜单Switch（）case1：case2:case3：Return 0； 2.2本程序包含四个模块1）主菜单模块2）输入集合单元模块：利用单链表输入；3）集合运算单元模块：实现集合抽象数据类型；4）有序表单元模块：实现有序表抽象数据类型；模块关系： 3.1测试数据：集合A=dop，B=dli，运算其交集、并集、差集。3.2源程序：源程序代码以下：#include #include#include#includeusing namespace std;typedef char ElemType;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=(LinkList*)malloc(sizeof(LinkList); L-next=NULL; q=L; for(int i=n;i0;-i) p=(LinkList*)malloc(sizeof(LinkList);/生成新结点 cinp-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-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-datadata) pre=pre-next; p-next=pre-next; pre-next=p; p=q; void Union(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-datadata) s=(LinkList*)malloc(sizeof(LinkList); s-data=pa-data; pc-next=s; pc=s; pa=pa-next; else if(pa-datapb-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;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-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;void Subs(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;int main()LinkList *ha,*hb,*hc; int n,k; while(1) coutntt 集合简单运算nn; coutttt 菜单 n; coutttt n;coutttt 1. 请输入A集合个数和A集合元素 n;coutttt 2. 请输入B集合个数和B集合元素 n; coutttt 3. A集合有序集合 n; coutttt 4. B集合有序集合 n; coutttt 5. AB集合并集 n; coutttt 6. AB集合交集 n; coutttt 7. AB集合差集 n; coutttt 0. 退出 n; coutttt n; coutk; switch(k) case 1: coutn; CreateList_L1(ha,n);break;case 2:coutn;CreateList_L1(hb,n); break;case 3:sort(ha);coutn A有序集合为：;DispList(ha);break;case 4:sort(hb);coutn B有序集合为：;DispList(hb);break;case 5:Union(ha,hb,hc);coutn AB集合并集为：;DispList(hc);break;case 6:InterSect(ha,hb,hc);coutn AB集合交集为：; DispList(hc);break;case 7:Subs(ha,hb,hc);coutn AB集合差集为：;DispList(hc);break;case 0: coutnttt- 谢谢使用！-n;coutnttt按任意键退出.n; return 0; / switch /while DestroyList(ha); DestroyList(hb); DestroyList(hc); return 0;3.3测试数据及运行情况(1) 选择功效(2) 输入A集合个数和A集合元素dop(3) 输入B集合个数和B集合元素dli(4) A集合有序集合(5) B集合有序集合(6) AB集合并集(7) AB集合交集(8) AB集合差集(9) 退出程序在测试过程中出现过很多小问题，如：交集并集二者运算结果颠倒、菜单文字错误、菜单较长等问题，在认真查看修改后，这些问题得到了处理。4.总结：在完成此次课程设计过程中，经过自己思索和努力，培养了自学能力和动手能力。而且由原先被动接收知识转换为主动寻求知识，这能够说是学习方法上一个很大突破。在以往传统学习模式下，我们可能会记住很多书本知识，不过经过课程设计，我们学会了怎样将学到知识转化为自己东西，学会了怎么愈加好处理知识和实践相结合问题。经过编程实践，不仅开发了自己逻辑思维能力，培养了分析问题、处理问题能力，更充足锻炼了我们编程能力。在设计汇报写作过程中，我也学到了做任何事情全部要有心态，首先我明白了，出现任何问题全部不要轻视，要经过正确路径去处理，在做事情过程中要有耐心和毅力，不要一碰到困难就打退堂鼓，只要坚持下去就能够找到思绪去处理问题。在这次课程设计中我也知道了自己编码能力不强，有待于深入提升，但在老师和同学帮助下，我坚持到了最终。我在这次课程设计中学到很多。在以后学习中，我一定勤于思索，并灵活利用所学知识，多进行编程实践。在总结反思和编程训练中，不停提升自己编程能力。相信在我努力下，我程序设计水平一定会不停提升。参考文件清华大学计算机系教材：数据结构（c语言版）严蔚敏、吴伟民编著