《数据结构课程设计-集合运算》由会员分享，可在线阅读，更多相关《数据结构课程设计-集合运算（30页珍藏版）》请在金锄头文库上搜索。
1、 集合的运算11 需求分析1.1 设计任务集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符a .z；演示程序以用户和计算机的对话方式执行；其中运用了编程软件 Microsoft Visual C+ 6.0 创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算。1.2 功能要求集合输入的形式为一个以回车符为结束标志的字符串，元素中字符顺序为先整数后字母，否则程序提示重新输入,若出现重复元素或非法字符，不符合集合的定义,程序提示重新输入。本段程序旨在对输入的元素进行并集,交集,差集和布尔和运算。2 概要设计2.1 链表表的抽象
2、数据类型定义 1为实现上述程序功能，并要求以有序链表表示集合。所以，抽象数据类型就是单链表ADT OrderedLinkList数据对象：D=( ai, bi)|aiInteger，b iCharSet, i=1,2,.,n, n 0数据关系：Rl=| ( ai-1, bi-1), ( ai, bi)D, ( ai-1, bi-1)node2.inte)return 1;elseif(node1.intenode2.c) 集合的运算4return 1;elseif(node1.c=97)s-inte=a;s-c=c;fflush(stdin);/清除缓冲区的一个输入流x=1;elsecoutn
3、ex=NULL。如用重复，则需要重新输入。直到元素的个数等于用户第一步输入的元素个数时函数调用结束。函数如下：Status createLinkList(LinkList &L,int n)coutnext=NULL;for(int i=0;inext)& datacompare(*p-next,*s)!=0)/调用元素大小比较函数p=p-next;if(p-next)/检查到重复元素coutnext=s;p=p-next;p-next=NULL;x=OK;elsei-;/为下一次循环显示元素的 ID 号x=-1;return x;3.6 求集合的并集 2求集合的并集，根据课题要求，转化为合并
4、两个链表的的问题。先把链表 A 的元素拷贝到链表 C 中，然后对链表 B 从头开始检索，依次和链表 C 中的每一个元素进行比较，如果该元素不存在于链表 C 中，就将该元素用尾插法插入链表 C。直到链表 B 集合的运算8为空，就完成了两个集合的并集运算。函数如下：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!=NUL
5、L)/复制链表 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; 集合的
6、运算9pb=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 的第
7、一个结点，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; 集合的运算10r=s;pa=pa-next;r-next=NULL;return OK;3.8 求差集 2转化
8、为求两表中，存在于前一个表中而不存在于后一个表中的元素的组成，即为差集。具体思路是先创建空链表 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)m
9、alloc(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; 集合的运算11s-c=pa-c;r-next=s;r=s;pa=pa-next;/外层循环的指针后移r-next=NULL;return OK;3.9 求布尔和。依据数学上的定义，布尔和即为两集合
10、的对称差，其实质是（A-B ）U （B-A） ，再次转化为（AUB）-（A B ） 。所以只需要对并集和交集调用求差集函数即可。4 调试分析4.1 调试过程中遇到的问题死循环问题1. 在输入合法性检查中，输入整数时，如果不合法，带有其他字符，产生死循环。这种问题产生于循环体的条件是永真式，而循环体内没有用 break 语句或者其他跳出语句；2. 同样是在输入时造成的死循环，在 while(1)中，用了 break 语句，但是仍然出现的死循环。比如用 scanf(“%d”,n)=1 来判断是否输入一个整数时，在输入的不是合理整数的情况下，就死循环。其原因是输入的字符存为整数不成功，它将留在输入缓
11、冲区，进入下一次存储，也不成功，就形成死循环。查阅资料可以找到一个清除输入缓冲区的库函数 fflush(stdin)，这个函数很有效，在每次有可能在输入缓冲区残留信息的地方调用一次该函数就可以了（部分程序如下）：while(1) 集合的运算12if(scanf(%d,&n)=1)fflush(stdin);break;elsecout#include#include#define NULL 0 #define OK 1#define ERROR 0typedef int Status;typedef struct LNode /定义结构体，数据域两种类型int inte;char c;stru
12、ct LNode *next;LNode,*LinkList;/比较元素大小Status datacompare(LNode node1,LNode node2) /元素大小的比较：结点作参数，先比整数域，再比字母域/用点运算取结构体的成员变量if(node1.intenode2.inte)return 1;elseif(node1.intenode2.c)return 1;elseif(node1.c=97)s-inte=a;s-c=c;fflush(stdin);/清除缓冲区的一个输入流x=1;elsecoutnext=NULL;for(int i=0;inext)& datacompar
13、e(*p-next,*s)!=0)p=p-next;if(p-next)coutnext=s;p=p-next;p-next=NULL;x=OK;elsei-;x=-1;return x; 集合的运算24/求集合并集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(si
14、zeof(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!=NUL
