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

1 需求分析1.1 设计任务集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符a.z；演示程序以用户和计算机的对话方式执行；其中运用了编程软件Microsoft Visual C+ 6.0创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算。1.2 功能要求集合输入的形式为一个以"回车符"为结束标志的字符串，元素中字符顺序为先整数后字母，否则程序提示重新输入,若出现重复元素或非法字符，不符合集合的定义,程序提示重新输入。本段程序旨在对输入的元素进行并集,交集,差集和布尔和运算。 2 概要设计2.1链表表的抽象数据类型定义1为实现上述程序功能，并要求以有序链表表示集合。所以，抽象数据类型就是单链表ADT OrderedLinkList数据对象：D=( ai, bi)|aiÎInteger，biÎCharSet, i=1,2,.,n, n³ 0数据关系：Rl=<( ai-1, bi-1), ( ai, bi)>| ( ai-1, bi-1), ( ai, bi)ÎD, ( ai-1, bi-1)< ( ai, bi),i=2,.,n基本操作：createLinkList(&L, n)操作结果：构造一个带表头的单链表，其中除表头外有n个结点。unionset(&A, &B, &C)初始条件：单链表A，B已经存在。操作结果：将单链表A和B的数据以结点为单位不重复地存入单链表C中。interset(&A, &B, &D)初始条件：单链表A，B已经存在。操作结果：以结点为单位，把同时存在于两个表中的数据存入单链表D中。diffence(&A, &B, &E)初始条件：单链表A，B已经存在。操作结果：以结点为单位将存在于链表A中而不存在于B的数据存入单链表E。insertsort(L)初始条件：有序表 L 已存在。操作结果：以结点数据从表头到表尾用直接插入法按从小到大排序。selectsort(L)初始条件：有序表L已存在。操作结果：以结点数据从表头到表尾用直接选择法按从小到大排序。bubblesort(L)初始条件：有序表L已存在。操作结果：以结点数据从表头到表尾用冒泡排序法按从小到大排序。shellsort(L)初始条件：有序表L已存在。操作结果：以结点数据从表头到表尾用冒泡排序法按从小到大排序。ADT OrderedLinkList3 详细设计3.1元素类型、结点类型和指针类型1宏定义：typedef int Status;用来作为函数的返回值类型。根据课题要求，每个结点必须含有两个类型的数据，即整数域和小写字母域，另外必须有一个指向下一个结点的结构类型的指针，故结构体有三个成员如下：typedef struct LNode/定义结构体，数据域两种类型int inte;char c;struct LNode *next;LNode,*LinkList;/结点类型，结构体指针3.2节点中元素大小的比较函数由于节点的数据域中有两个类型的数据，在后面的检查新输入的元素是否和已经输入的有重复，以及在排序过程中不便于结点元素的大小的比较，所以先写出这个功能的函数。其比较原则是先将结点数据的的整数成员比较，整数大的元素大，整数相等的情况下则进行小写字母域的比较，其大小按字符大小直接比较，参数为结点，用1、0、-1作为返回值，分别表明前一个结点数据大于、等于、小于后一个节点数据。然后在后面的过程中只需要调用即可。该功能函数如下：Status datacompare(LNode node1,LNode node2)/元素大小的比较：结点作参数，先比整数域，再比字母域/用点运算取结构体的成员变量if(node1.inte>node2.inte)return 1;elseif(node1.inte<node2.inte)return -1;elseif(node1.c>node2.c)return 1;elseif(node1.c<node2.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<=122 && 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;3.5创建链表，用来存储元素，以表示集合。先创建一个带表头结点的空链表，依次在第5点所述函数返回1，并且和以前输入的元素没有重复的情况下，用尾插法插入元素结点，每插入一个结点后将指针p指向表尾元素，并且p->nex=NULL。如用重复，则需要重新输入。直到元素的个数等于用户第一步输入的元素个数时函数调用结束。函数如下：Status createLinkList(LinkList &L,int n)cout<<"输入集合元素时，整数与字母之间没有任何符号，"<<endl<<"并且多余的字符将被程序处理掉，元素之间用回车键"<<endl;int x;LinkList p,s;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;for(int i=0;i<n;i+)printf("请输入第%d个元素：",i+1);s=(LinkList)malloc(sizeof(LNode);p=L;if(input(s)=1)/调用输入函数while(p->next)&& datacompare(*p->next,*s)!=0)/调用元素大小比较函数p=p->next;if(p->next)/检查到重复元素cout<<"元素有重复"<<endl;i-;x=-1;else/尾插法插入结点p->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 7 附录 源程序#include<iostream.h>#include<stdlib.h>#include<stdio.h>#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(node1.inte>node2.inte)return 1;elseif(node1.inte<node2.inte)return -1;elseif(node1.c>node2.c)return 1;elseif(node1.c<node2.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<=122 && 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<<"并且多余的字符将被程序处理掉，元素之间用回车键"<<endl;int x;LinkList p,s;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;for(int i=0;i<n;i+)printf("请输入第%d个元素：",i+1);s=(LinkList)malloc(sizeof(LNode);p=L;if(input(s)=1)/调用输入函数while(p->next)&& datacompare(*p->next,*s)!=0)p=p->next;if(p->next)cout<<"元素有重复"<<endl;i-;x=-1;elsep->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(p)/计算链表结点个数count+;p=p->next;for(d=count/2;d>0;d=d/2)r=s=L;for(i=0;i<d-1;i+)s=s->next;for(i=0;i<d;i+)r=r->next;while(r)p=L;flag=0;while(flag=0)if(datacompare(*(p->next),*r)>0)s->next=r->next;r->next=p->next;p->next=r;r=s->next;break;for(i=0;i<d;i+)p=p->next;if(p=r)|(p=NULL)flag=1;/标记扫描结束break;/防止指针越界if(flag=1)&&(r!=NULL)r=r->next;s=s->next;return OK;/输出链表Status dislinklist(LinkList &L)LinkList p;p=L;while(p->next)cout<<p->next->inte<<p->next->c<<" "p=p->next;cout<<endl;return OK;/销毁链表Status destroyLinkList(LinkList &L)LinkList p,q;p=L;while(p->next)/非表头结点的销毁q=p->next;p->next=p->next->next;free(q);if(p->next=NULL)/判定到表头结点时，也将其销毁free(L) ;return OK;Status main()