数据结构课程设计-集合的运算.doc

集合的运算集合的运算摘要随着计算机的普及、IT产业和Internet获得了飞速的发展，计算机应用已经渗透到各个领域，引起信息管理的革命，实现了信息的自动化处理，提高了处理的及时性和正确性。计算机应用到数学运算中之后大大提高了运算的速度和正确性。集合论是现代数学中重要的基础理论。它的概念和方法已经渗透到代数、拓扑和分析等许多数学分支以及物理学和质点力学等一些自然科学部门，为这些学科提供了奠基的方法，改变了这些学科的面貌。几乎可以说，如果没有集合论的观点，很难对现代数学获得一个深刻的理解。所以集合论的创立不仅对数学基础的研究有重要意义，而且对现代数学的发展也有深远的影响。本文描述了如何编制一个能演示执行集合的并、交、差和布尔和（对称差）运算的程序，并对结果排序，其中集合用有序链表表示。集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符a.z；演示程序以用户和计算机的对话方式执行；对四种运算的结果分别用不同的排序方法进行排序。其中运用了编程软件Microsoft Visual C+ 6.0创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算，并且对结果进行排序。最终实现了编写出实现上述内容的程序。关键词：布尔和；集合运算；拓扑；排序； OPERATIONS OF SETABSTRACTWith the popularity of computer, IT industry and Internet develop rapidly. Computer application has penetrated into every field, which causes the revolution of the information management, realizes the automatic processing of the information and improves the timeliness and accuracy of the processing. Since the computer has applied to the operation of the mathematics, the speed and accuracy has much increased. Set theory plays an important role in modern mathematics basic theory. Its concept and method has penetrated into many branches of mathematics such as algebra, topology and analysis, and some natural science like physics and particle mechanics, providing these subjects the foundation methods and changing their feathers. Almost can say, without set theory, it is difficult to get a profound understanding on modern mathematics. So set theory not only has an important significance on the foundation research of mathematics, but also has profound and lasting effects on the development of modern mathematics.This essay talks about how the program is made in order to demonstrate how to perform the operations of Union, Intersection, Difference、and Boolean sum(also called Symmetric Difference) and to sort the results in which sets are symbolized with sequenced chains. The elements of the sets must include the structure of two data fields: one contains integers, the other contains small letters (from “a” to “z”). The Demonstration Program is carried out through the dialogues between the users and the computers. The results of four operations are sorted with different sorting methods. During it, the sets are signaled by the chains which are created by the programming software, Microsoft Visual C+ 6.0. The chains can realize the four operations and the sorting results with the functions of finding, deleting, inserting and so on. At last the program which can realize the above contents can be programmed.Key words: Boolean sum; operations of set; Topology ; sorting; 目 录 1 需求分析.1 1.1 设计任务11.2功能要求.12 概要设计. .12. 1 链表表的抽象数据类型定义.13 详细分析.23. 1 元素类型、结点类型和指针类型.33. 2 结点中元素大小的比较函数.33. 3 元素个数输入的合法性检查.43. 4 集合元素输入的合法性检查.53. 5 创建链表，用来存储元素，以表示集合63. 6 求集合的并集.73. 7 求A、B集合的交集.93. 8 求差集.103. 9 求布尔和.114 调试分析.11 4. 1 调试过程中遇到的问题.11 4. 2 算法的时间复杂度和空间复杂度分析.13 4. 3 经验与体会.13 5 用户使用说明.146 测试数据与测试结果.18参考文献.20附录.2 集合的运算1 需求分析1.1 设计任务集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符a.z；演示程序以用户和计算机的对话方式执行；其中运用了编程软件Microsoft Visual C+ 6.0创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算。1.2 功能要求集合输入的形式为一个以回车符为结束标志的字符串，元素中字符顺序为先整数后字母，否则程序提示重新输入,若出现重复元素或非法字符，不符合集合的定义,程序提示重新输入。本段程序旨在对输入的元素进行并集,交集,差集和布尔和运算。 2 概要设计2.1链表表的抽象数据类型定义1为实现上述程序功能，并要求以有序链表表示集合。所以，抽象数据类型就是单链表ADT OrderedLinkList数据对象：D=( ai, bi)|aiInteger，biCharSet, i=1,2,.,n, n 0数据关系：Rl=| ( ai-1, bi-1), ( ai, bi)D, ( ai-1, bi-1)e)return 1;elseif(enode2.c)return 1;elseif(ode2.c)return -1;elsereturn 0;3.3元素个数输入的合法性检查这个函数完全是为了程序的健壮性准备的，当用户错误输入时，程序提示用户输入正确的整数，直到输入正确后才可以进行下一步操作。如果用户输入的有多余的字符，存在输入输入缓冲却，将会被函数中调用的fflush(stdin) 6函数处理掉，消除了缓冲区残留信息对下一步操作的影响。函数如下：Status input1(int n)while(1)if(scanf(%d,&n)=1)fflush(stdin);/清除输入缓冲区break;elsecout请正确输入整数：endl;fflush(stdin);/退出循环就输入正确了return n;/返回正确输入的整数3.4 集合元素输入的合法性检查即归为结点数据输入的正确性检查。当输入不正确时，程序提示用户具体的输入操作，直到用户输入正确后，才可以把输入的值赋值给结点的两个数据成员，否则提示用户重新输入该元素。具体函数如下：Status input(LinkList &s)int a,x;char c;/scanf()函数的返回值5进行条件判断if(scanf(%d,&a)=1 & scanf(%c,&c)=1)/控制字符为小写字母if(c=97)s-inte=a;s-c=c;fflush(stdin);/清除缓冲区的一个输入流x=1;elsecout输入失败,第二部分是小写字母endl;fflush(stdin);x=-1;elsecout集合元素是先一个整数后一个小写字母！nex=NULL。如用重复，则需要重新输入。直到元素的个数等于用户第一步输入的元素个数时函数调用结束。函数如下：Status createLinkList(LinkList &L,int n)cout输入集合元素时，整数与字母之间没有任何符号，endl并且多余的字符将被程序处理掉，元素之间用回车键next=NULL;for(int i=0;inext)& datacompare(*p-next,*s)!=0)/调用元素大小比较函数p=p-next;if(p-next)/检查到重复元素cout元素有重复next=s;p=p-next;p-next=NULL;x=OK;elsei-;/为下一次循环显示元素的ID号x=-1;return x;3.6求集合的并集2求集合的并集，根据课题要求，转化为合并两个链表的的问题。先把链表A的元素拷贝到链表C中，然后对链表B从头开始检索，依次和链表C中的每一个元素进行比较，如果该元素不存在于链表C中，就将该元素用尾插法插入链表C。直到链表B为空，就完成了两个集合的并集运算。函数如下：Status unionset(LinkList &A,LinkList &B,LinkList &C)LinkList pa=A-next,pb=B-next,s,r;/pb指向B的第一个结点，s为要插入的结点，r为扫描指针C=(LinkList)malloc(sizeof(LNode);r=C;while(pa!=NULL)/复制链表A的结点到链表C中s=(LinkList)malloc(sizeof(LNode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;while(pb!=NULL)/依次检索链表Bpa=A-next;while(pa!=NULL & datacompare(*pa,*pb)/检查元素是否重复pa=pa-next;if(pa=NULL)/说明该元素不存在于A中/尾插法插入该结点s=(LinkList)malloc(sizeof(LNode);s-inte=pb-inte;s-c=pb-c;r-next=s;r=s;pb=pb-next;r-next=NULL;return OK;3.7 求A、B集合的交集3转化为求两个链表中相同元素的算法。先创建空链表C，外层循环对链表A首元结点开始检索，内层循环是将外层循环的结点的数据域与链表B中的非表头结点的数据域依次进行比较，当外循环的节点数据与内循环结点数据相等时，就得到交集的一个元素，用尾插法插入链表C中，当两层循环都结束时，就完成了集合的交集运算。函数如下：Status interset(LinkList &A,LinkList &B,LinkList &D)LinkList pa=A-next,pb,s,r;/pb指向B的第一个结点，s为要插入的结点，r为扫描指针D=(LinkList)malloc(sizeof(LNode);r=D;while(pa!=NULL)/外层循环，对A中元素检索pb=B-next;while(pb!=NULL& datacompare(*pb,*pa)内层循环，找相等元素pb=pb-next;if(pb!=NULL)/此元素在A中s=(LinkList)malloc(sizeof(LNode);s-c=pa-c;s-inte=pa-inte;r-next=s;r=s;pa=pa-next;r-next=NULL;return OK;3.8求差集2转化为求两表中，存在于前一个表中而不存在于后一个表中的元素的组成，即为差集。具体思路是先创建空链表C，外层循环从首元结点检索A表中的元素，内层循环就是将A中的该元素从首元结点开始与表B中的元素依次作比较，如不等，则为差集的一个元素，用尾插法插入链表C中。当这两层循环结束时，集合A、B的差集运算就结束了，便得到了差集C。函数如下：Status diffence(LinkList &A,LinkList &B,LinkList &E)LinkList pa=A-next,pb,s,r;/pb指向B的第一个结点，s为要插入的结点，r为扫描指针E=(LinkList)malloc(sizeof(LNode);r=E;while(pa!=NULL)/外层循环，从首元结点开始检索表Apb=B-next;while(pb!=NULL& datacompare(*pb,*pa)/相应元素作比较pb=pb-next;if(pb=NULL)/此元素在A中/尾插法插入找到的结点s=(LinkList)malloc(sizeof(LNode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;/外层循环的指针后移r-next=NULL;return OK;3.9 求布尔和。依据数学上的定义，布尔和即为两集合的对称差，其实质是（A-B）U（B-A），再次转化为（AUB）-（A B ）。所以只需要对并集和交集调用求差集函数即可。4 调试分析4.1 调试过程中遇到的问题死循环问题1. 在输入合法性检查中，输入整数时，如果不合法，带有其他字符，产生死循环。这种问题产生于循环体的条件是永真式，而循环体内没有用break语句或者其他跳出语句；2. 同样是在输入时造成的死循环，在while(1)中，用了break语句，但是仍然出现的死循环。比如用scanf(“%d”,n)=1来判断是否输入一个整数时，在输入的不是合理整数的情况下，就死循环。其原因是输入的字符存为整数不成功，它将留在输入缓冲区，进入下一次存储，也不成功，就形成死循环。查阅资料可以找到一个清除输入缓冲区的库函数fflush(stdin)，这个函数很有效，在每次有可能在输入缓冲区残留信息的地方调用一次该函数就可以了（部分程序如下）：while(1)if(scanf(%d,&n)=1)fflush(stdin);break;elsecout请正确输入整数：endl;fflush(stdin);但是据网友细说，此函数在linux下不管用，由于本人及周边人没有用linux，所以未得试验。另一种解决方案，就是自己定义一个字符数组，把多余的字符接收掉，这样就不会影响下一次输入。3. 对于链表，条件判定后，指针未后移引起的死循环。这种主要是判断条件永真，而漏写指针后移的语句，检查程序可以解决。参数传递问题1. 如果参数是一个数组，那么形参处就写明数组类型和数组名即可，应为数组名本来就是指向该数组首地址的一个指针。2. 如果传递的是二维数组，如二维字符数组，其前面的一维就是数组如 char a5，那么a1指的是一个字符数组。3. cannot convert parameter 1 from struct LNode * to struct LNode；这种问题是参数类型不一致引起的，如果类型是明显的基本类型时一般不会出现这类错误，但是如果是自己定义的类型时，很容忽视类型而引起这类错误。字符串数组长度问题。我曾花了很多时间在网上搜索关于求字符串长度的问题，试验过不少网友提供的方法，大部分人提供的是使用库函数strlen(数组名)，但经我试验，这种方法是错误的，如：char *a=111,222,3, ,fjdkal;执行printf(“%d”,strlen(a);将得到3。这不是字符串数组的长度，其得到的是字符串数组中第一个字符串的字符个数，后来继续搜索才找到了正确答案：sizeof(数组名)/sizeof(数组元素类型)。这个真是正确答案，我试验过多次，下面是一个样例:void main() char *a=111,222,3, ,fjdkal; cout sizeof(a)/sizeof(char*) endl; cout a0 endl;运行结果如下：指针问题1. 如果指针指向的结点没有数据，而执行输出语句时却用了该指针指向的结点，则会输出一个很小的负数，一看就明白不是想要的结果。2. 指针未初始化，当程序执行过程遇到指针未初始化语句时，将无法继续执行而不正常退出，典型错误就是把一个空指针赋值给一个空指针。4.2 算法的时间复杂度和空间复杂度分析如果不改变指针本身的值时，就不要用指向指针的指针。算法复杂度（n，m为元素个数）创建链表时，正确输入的情况下，检查元素是否重复为O(n2)；求并集、交集，差集和布尔和时，时间复杂度为O(m*n);由于是用链表来作运算的，空间上都比较合理。4.3经验与体会遇到问题时，可以自己改动程序，然后编译和运行，这样可以找到错误的原因；网络是较好的资源，但是部分东西还需要我们自己验证。程序出现问题时，可以自己在程序中加入标记，观察程序执行过程，找出错误。这次课程设计让我的这方面的只是得到了扩充，程序设计思路更为清楚，同时也强化了基础，学到了不少新的知识。5 用户使用说明1 编译后，点击运行，出现如图5-1所示的运行界面；图5-12 在图5-1的情况下，用户输入两个集合中第一集合的元素的个数，输入的数必须为正整数或者0。如果用户输入的不是整数，系统会提示用户正确输入整数，直到用户输入正确后方能进入下一步（如图5-2）；如图5-23 用户输入正确后得到如图5-3所示界面，提示用户输入第一个集合的元素，元素必须含有两个部分-整数和字符，之间没有任何其他符号，对于用户输入的多余的字母，程序将自动处理掉，元素之间用回车键，并提示用户输入第一个元素；图5-34 用户输入一个元素，如果是按要求先整数后小写字母，系统就提示输入下一个元素（如图5-4所示），否则提示用户输入正确的元素（如图5-5所示），如过程中有重复的元素，系统会提示用户重新输入（如图5-6所示），直到正确输入用户在前面输入的元素个数，系统提示用户输入第二个集合的元素（如图5-7），其要求和规则同第一个集合完全一样；图5-4图5-5图5-6图5-75 当用户正确完成两个集合的元素的输入后，系统将直接输出两个集合的并集、交集、差集和布尔和，其顺序依次为集合、集合、并集、用直接插入法排序后的并集、交集、用直接选择法排序后的交集、差集、用冒泡法排序后的差集、布尔和、用希尔排序后的布尔和（如图5-8所示），之后主程序调用destroyLinkList() 销毁所有链表，程序到此结束。 图5-86 测试数据与测试结果请输入集合A的元素个数：7依次输入：98f 56d23b78h21z98q2b请输入集合B的元素个数：8依次输入：56d21z78h98f36j8w1l0x得到结果：（为了尽可能显示界面，输入元素提示处没有换行）参考文献1 严蔚敏，吴伟民. 数据结构(C语言版). 北京：清华大学出版社，1997.042 数据结构习题与解析B级 第3版 清华大学出版社 李春葆 喻丹丹 编著3 数据结构教程（第2版）清华大学出版社 李春葆 等 编著4 Data Structures & Program Drsign in C,Second Edition 数据结构与程序设计C语言（第二版） 清华大学出版社5 C语言程序设计 复旦大学出版社 主编 孟爱国6 /view/1390039.htm7 /t/20051018/15/4334095.html附录 源程序#include#include#include#define NULL 0 #define OK 1#define ERROR 0typedef int Status;typedef struct LNode/定义结构体，数据域两种类型int inte;char c;struct LNode *next;LNode,*LinkList;/比较元素大小Status datacompare(LNode node1,LNode node2)/元素大小的比较：结点作参数，先比整数域，再比字母域/用点运算取结构体的成员变量if(e)return 1;elseif(enode2.c)return 1;elseif(ode2.c)return -1;elsereturn 0;/输入的合法性（检查输入元素个数与input的区分）Status input1(int n)while(1)if(scanf(%d,&n)=1)fflush(stdin);break;elsecout请正确输入整数：endl;fflush(stdin);return n;/输入合法性检查Status input(LinkList &s)int a,x;char c;/scanf()函数的返回值进行条件判断if(scanf(%d,&a)=1 & scanf(%c,&c)=1)/控制字符为小写字母if(c=97)s-inte=a;s-c=c;fflush(stdin);/清除缓冲区的一个输入流x=1;elsecout输入失败,第二部分是小写字母endl;fflush(stdin);x=-1;elsecout集合元素是先一个整数后一个小写字母！endl;fflush(stdin);x=-1;return x;/创建链表Status createLinkList(LinkList &L,int n)cout输入集合元素时，整数与字母之间没有任何符号，endl并且多余的字符将被程序处理掉，元素之间用回车键next=NULL;for(int i=0;inext)& datacompare(*p-next,*s)!=0)p=p-next;if(p-next)cout元素有重复next=s;p=p-next;p-next=NULL;x=OK;elsei-;x=-1;return x;/求集合并集Status unionset(LinkList &A,LinkList &B,LinkList &C)LinkList pa=A-next,pb=B-next,s,r;/pb指向B的第一个结点，s为要插入的结点，r为扫描指针C=(LinkList)malloc(sizeof(LNode);r=C;while(pa!=NULL)s=(LinkList)malloc(sizeof(LNode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;while(pb!=NULL)pa=A-next;while(pa!=NULL & datacompare(*pa,*pb)pa=pa-next;if(pa=NULL)s=(LinkList)malloc(sizeof(LNode);s-inte=pb-inte;s-c=pb-c;r-next=s;r=s;pb=pb-next;r-next=NULL;return OK;/求交集Status interset(LinkList &A,LinkList &B,LinkList &D)LinkList pa=A-next,pb,s,r;/pb指向B的第一个结点，s为要插入的结点，r为扫描指针D=(LinkList)malloc(sizeof(LNode);r=D;while(pa!=NULL)pb=B-next;while(pb!=NULL& datacompare(*pb,*pa)pb=pb-next;if(pb!=NULL)/此元素在A中s=(LinkList)malloc(sizeof(LNode);s-c=pa-c;s-inte=pa-inte;r-next=s;r=s;pa=pa-next;r-next=NULL;return OK;/求集合差集Status diffence(LinkList &A,LinkList &B,LinkList &E)LinkList pa=A-next,pb,s,r;/pb指向B的第一个结点，s为要插入的结点，r为扫描指针E=(LinkList)malloc(sizeof(LNode);r=E;while(pa!=NULL)pb=B-next;while(pb!=NULL& datacompare(*pb,*pa)pb=pb-next;if(pb=NULL)/此元素在A中s=(LinkList)malloc(sizeof(LNode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;r-next=NULL;return OK;/直接插入排序Status insertsort(LinkList L)LinkList p,r,s;p=L-next;/p扫描无序表段，r为扫描有序表段，s指向要插入的结点while(p-next)r=L;while(r-next!=p-next & datacompare(*p-next,*r-next)0)r=r-next;if(r-next=p-next)p=p-next;elseif(r=L)/如果是在表头后插入，则需要移动表头指针s=p-next; p-next=p-next-next;s-next=r-next;L-next=s;else /不是在表头插入s=p-next;p-next=p-next-next;s-next=r-next;r-next=s;return OK;/直接选择排序Status selectsort(LinkList L)LinkList r,s,p;/r为扫描指针，s为选中的最小结点，p指向有序段的尾指针int tempinte;char tempc;p=L;while(p-next)r=p;s=p-next;while(r-next)if(datacompare(*s,*(r-next)0)s=r-next;r=r-next;elser=r-next;if(s)/交换结点的数据即可tempinte=s-inte;tempc=s-c;s-inte=p-next-inte;s-c=p-next-c;p-next-inte=tempinte;p-next-c=tempc;p=p-next;return OK;/冒泡排序（大的往下沉）Status bubblesort(LinkList L)int tempinte;char tempc;LinkList p,r;/p为扫描指针，r指向有序段得头指针r=NULL;for(r=NULL;r!=L-next;p=L-next)for(p=L-next;p-next!=NULL&p-next!=r;)if(datacompare(*p,*(p-next)0)tempinte=p-inte;tempc=p-c;p-inte=p-next-inte;p-c=p-next-c;p-next-inte=tempinte;p-next-c=tempc;else;p=p-next;r=p;return OK;/希尔排序Status shellsort(LinkList L)int i=0,flag=0;LinkList p,r,s;int count=0,d;/count为结点总数，d为步长p=L;while