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

课 程 设 计 报 告课程名称 数据结构 课题名称 集合的并、交和差运算 专 业 通信工程 班 级 通信1101 学 号 201103020127 姓 名 皮锋 指导教师 张鏖烽 田娟秀 李杰君 2013 年6月29日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 集合的并、交和差运算 专业班级 通信1101 学生姓名 皮锋 学 号 201103020127 指导老师 张鏖烽 田娟秀 李杰君 审 批 任务书下达日期 2013 年 6 月 23 日任 务 完成日期 2013 年 6 月 29 日目录 1. 需求分析11.1. 问题描述11.2. 基本要求11.3. 测试数据11.4. 实现提示12. 概要设计12.1. 有序表的抽象数据类型定义为12.2. 集合的定义为12.3. 基本操作22.4. 调用关系23. 详细设计43.1. 具体算法流程43.2. 具体的程序功能实现43.3. 伪码算法54. 调试分析94.1. 调试过程中遇到的问题94.2. 算法的时空分析95. 用户使用说明106. 测试结果116.1. 做完一次运算后按回车键继续下一次运算116.2. 做完运算后输入字母“e”退出运算127. 总结128. 附录138.1. 程序源代码13集合的并、交和差运算1. 需求分析1.1. 问题描述编制一个能演示执行集合的并、交和差运算的程序。1.2. 基本要求(1) 集合的元素限定为小写字母字符 a.z 。(2) 演示程序以用户和计算机的对话方式执行。1.3. 测试数据(1)Set1=magazine，Set2=paper，Set1Set2=aegimnprz，Setl Set2=ae，Set1-Set2=gimnz。(2)Set1= 012oper4a6tion89，Set2=error data，Set1Set2=adeinoprt，Setl Set2=aeort，Set1-Set2=inp。1.4. 实现提示以有序链表表示集合。2. 概要设计为实现上述程序功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。2.1. 有序表的抽象数据类型定义为typedef struct LNodechar data;struct LNode *next;LinkList;2.2. 集合的定义为char set1maxsize,set2maxsize;2.3. 基本操作void GreatListR(LinkList *&L,char a,int n) /尾插法建表void InitList(LinkList *&L)/初始化线性表void DestroyList(LinkList *&L)/销毁线性表void DispList(LinkList *L)/输出线性表void sort(LinkList *&L)/元素排序void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集运算void dels(LinkList *&M) /删除相同元素 仅留一个void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集运算void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差运算int main()/为设计程序主页面的函数，并且使用了所有的函数2.4. 调用关系InitList(L);InitList(N);GreatListR(L,set1,i);GreatListR(U,set1,i);sort(U);/元素排序dels(U);/删除相同元素 仅留一个sort(L);/元素排序dels(L);/删除相同元素 仅留一个printf(请输入集合set2=);for(j=0;jmaxsize;j+)scanf(%c,&set2j);if(set2j=n)break; GreatListR(N,set2,j); sort(N);/元素排序dels(N);/删除相同元素 仅留一个bingji(L,N,M);/集合合并dels(M);/删除相同元素 仅留一个DispList(M); jiaoji(M,L,N);/交集运算DispList(M); chayunsuan(U,M,K);/集合差运算DispList(K);char n;printf(n是否退出运算？n);scanf(%c,&n);if(n=e)exit(0);DestroyList(L);DestroyList(N);DestroyList(U);DestroyList(M);DestroyList(K);system(PAUSE);3. 详细设计3.1. 具体算法流程 图3-1 具体算法流程3.2. 具体的程序功能实现(1)利用c+引用类型，对线性表LinkList *L,*N进行初始化，并用for循环将将集合set1maxsize,set2maxsize分别存入线性表L和K。(2)用sort()函数对两个线性表里的元素进行排序，得到两个有序表。(3)用dels()函数分别删除两个有序表里相同元素，仅留一个。(4)用函数bingji(L,N,M)合并两个有序表，得到有序表M，并再次调用函数dels(M)删除有序表里相同的元素，仅留下一个，从而得到集合的并集。(5)调用函数jiaoji(M,L,N)，进行交集运算，从而得到一个新的有序表M，存着两个集合的交集。(6)利用交集运算得到的结果M进行集合差运算，调用函数chayunsuan(U,M,K)，得到两个集合差集为有序表K。(7)调用函数DispList()输出并集，交集和差集的结果。 (8)用代码char n;printf(n是否退出运算？n);scanf(%c,&n);if(n=e)exit(0);判断是否进行下一次运输，如果进行下一次运算按回车键继续，否则输入字母“e”退出运算。(9)最后利用函数DestroyList()销毁所有线性表。(10)加上头文件#include 和语句system(color B5)对界面进行颜色设置，得到自己喜欢的颜色。3.3. 伪码算法(1)并集运算void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集运算LinkList *pa=L-next,*pb=N-next,*r,*s;/时归并算法M=(LinkList *)malloc(sizeof(LinkList);r=M;while(pa!=NULL&pb!=NULL)/集合合并if(pa-datadata)s=(LinkList *)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;elses=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;pb=pb-next;while(pa!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;pb=pb-next;r-next=NULL;printf(两个集合的并集为set1set2:);void dels(LinkList *&M) /删除相同元素 仅留一个LinkList *p=M-next,*q;while(p-next!=NULL)if(p-data=p-next-data)q=p-next;p-next=q-next;free(q);elsep=p-next;(2) 交集运算void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集运算LinkList *pa=L-next,*pb=N-next,*q,*r;/以单链表M的头节点创建一个空单链表M-next=NULL;r=M;/r指向这个新链表的最后一个节点while(pa!=NULL)/以pa扫描单链表M的数据节点，判断是否在单链表L和N中while(pb!=NULL&pa-datapb-data)pb=pb-next;if(pa!=NULL&pb!=NULL&pa-data=pb-data)r-next=pa;r=pa;pa=pa-next;elseq=pa;pa=pa-next;free(q);r-next=NULL;printf(两个集合的交集为set1set2=);(3) 差集运算void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差运算LinkList *p1=L-next,*p2=M-next,*s,*r;K=(LinkList *)malloc(sizeof(LinkList);r=K;r-next=NULL;while(p1!=NULL)p2=M-next;while(p2!=NULL&p2-data!=p1-data)p2=p2-next;if(p2=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=p1-data;r-next=s;r=s;p1=p1-next;r-next=NULL;printf(两个集合的差集为set1 - set2=);4. 调试分析4.1. 调试过程中遇到的问题(1)由于对集合的三种运算的算法推敲不足,在有序链表类型的早期版本未设置尾指针操作,导致算法低效。(2)由于首先没设置数组最大值，导致数组不能正确输入，后来定义了#define maxsize 100才解决这个问题。(3)在子函数中线性表的创建不正确，导致在输入数组后不能正确执行，出现下图结果，经过多次调试才得到正确结果。(4)在进行差运算的算法设计时出现逻辑上的错误，导致结果不正确，集合的首元素未能正确参与运算。进过仔细的推敲才发现没有创建一个空的头结点就直接把pa=pa-next，使第一个数据元素未参加运算。(5)程序首先只能进行一次运算就退出了，不能人性化的进行多次运算，后来在主函数中加入for语句，进行循环，才能进行多次运算，并在for语句里加入if条件语句，进行是否进行下一次运算的判断，使程序更加优化。(6)首先把删除相同元素的算法写在交集，并集和差集的算法运算里面，使程序代码冗长，后来为了使代码更加简洁，就另外单独写了一个删除相同元素的算法，只要在各个运算中调用即可。4.2. 算法的时空分析(1)void GreatListR(LinkList *&L,char a,int n) /尾插法建表本算法的时间复杂度为O(n)，其中n为单链表中数据节点的个数。(2) void InitList(LinkList *&L)/初始化线性表本算法的时间复杂度为O(1)。(3) void DestroyList(LinkList *&L)本算法的时间复杂度为O(n)，其中n为单链表中数据节点的个数。(4) void DispList(LinkList *L)/输出线性表本算法的时间复杂度为O(n)，其中n为单链表中数据节点的个数。(6) void sort(LinkList *&L)/元素排序本算法的时间复杂度为O(n)，其中n为单链表中数据节点的个数。(7) void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集运算本算法的时间复杂度为O(ListLength(L)+ListLength(N)。(8) void dels(LinkList *&M) /删除相同元素 仅留一个本算法的时间复杂度为O(n)，其中n为单链表中数据节点的个数。(9) void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集运算本算法的时间复杂度为O(m+n+p)。(10) void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差运算本算法的时间复杂度为O(n*n)，其中n为单链表中数据节点的个数。5. 用户使用说明用户在使用时首先输入要进行运算的两个集合，然后按回车键则会出现运算结果。只能进行小写字母a到z的运算，如果输入其他以外的数字、字母或字符，则不会在运算结果中显示！若用户需要在进行下一次运算，则按回车键继续，否则按字母“e”退出计算！6. 测试结果6.1. 做完一次运算后按回车键继续下一次运算图6-1运算完一次进行第二次运算图6-2 进行多次运算6.2. 做完运算后输入字母“e”退出运算图6-1 运算完按字母“e”退出7. 总结数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。 数据结构课设使我们巩固了以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我们在这门课程的实际应用上也有了一个提高。 首先这两周的学习，使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。另外，让我们进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我们数据结构的学习和提高很有益处，并且使我们明白了程序设计过程，如解决一些实际问题，从解决实际问题的角度。 课程设计让我们受益匪浅。我们深深认识到，要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。 8. 附录8.1. 程序源代码#include#include using namespace std;#define maxsize 100typedef struct LNodechar data;struct LNode *next;LinkList;void GreatListR(LinkList *&L,char a,int n) /尾插法建表LinkList *s,*r;int i;L=(LinkList *)malloc(sizeof(LinkList);/创建头节点r=L;for(i=0;idata=ai;r-next=s;r=s;r-next=NULL;void InitList(LinkList *&L)/初始化线性表L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;void DestroyList(LinkList *&L)LinkList *pre=L,*p=L-next;while(p!=NULL)free(pre);pre=p;p=pre-next;free(pre);void DispList(LinkList *L)/输出线性表LinkList *p=L-next;while(p!=NULL)if(p-data=a)&(p-datadata);p=p-next;printf(n);void sort(LinkList *&L)/元素排序LinkList *p,*pre,*q;p=L-next-next;/p指向L的第2个数据节点L-next-next=NULL;/构件只含一个数据节点的有序表while(p!=NULL)q=p-next;while(p!=NULL)q=p-next;/q保存*p节点没后继节点的指针pre=L;/从有序表开头进行比较，pre指向插入*p的前驱节点while(pre-next!=NULL&pre-next-datadata)pre=pre-next;p-next=pre-next;pre-next=p;p=q;void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集运算LinkList *pa=L-next,*pb=N-next,*r,*s;/时归并算法M=(LinkList *)malloc(sizeof(LinkList);r=M;while(pa!=NULL&pb!=NULL)/集合合并if(pa-datadata)s=(LinkList *)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;elses=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;pb=pb-next;while(pa!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=pa-data;r-next=s;r=s;pa=pa-next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=pb-data;r-next=s;r=s;pb=pb-next;r-next=NULL;printf(两个集合的并集为set1set2:);void dels(LinkList *&M) /删除相同元素 仅留一个LinkList *p=M-next,*q;while(p-next!=NULL)if(p-data=p-next-data)q=p-next;p-next=q-next;free(q);elsep=p-next;void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集运算LinkList *pa=L-next,*pb=N-next,*q,*r;/以单链表M的头节点创建一个空单链表M-next=NULL;r=M;/r指向这个新链表的最后一个节点while(pa!=NULL)/以pa扫描单链表M的数据节点，判断是否在单链表L和N中while(pb!=NULL&pa-datapb-data)pb=pb-next;if(pa!=NULL&pb!=NULL&pa-data=pb-data)r-next=pa;r=pa;pa=pa-next;elseq=pa;pa=pa-next;free(q);r-next=NULL;printf(两个集合的交集为set1set2=);void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差运算LinkList *p1=L-next,*p2=M-next,*s,*r;K=(LinkList *)malloc(sizeof(LinkList);r=K;r-next=NULL;while(p1!=NULL)p2=M-next;while(p2!=NULL&p2-data!=p1-data)p2=p2-next;if(p2=NULL)s=(LinkList *)malloc(sizeof(LinkList);s-data=p1-data;r