数据结构课程设计集合运算.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的数据存入单链表Einsertsort(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; else if(node1.intenode2.c) return 1; else if(node1.c

如果用户输入的有多余的字符，存在输入输入缓冲却，将会被函数中调用的fflush(stdin) [6]函数处理掉，消除了缓冲区残留信息对下一步操作的影响函数如下：Status input1(int n){ while(1) { if(scanf("%d",&n)==1) { fflush(stdin);//清除输入缓冲区 break; } else { cout<<"请正确输入整数："<=97) { s->inte=a; s->c=c; fflush(stdin); //清除缓冲区的一个输入流 x=1; } else { cout<<"输入失败,第二部分是小写字母"<

先创建一个带表头结点的空链表，依次在第5点所述函数返回1，并且和以前输入的元素没有重复的情况下，用尾插法插入元素结点，每插入一个结点后将指针p指向表尾元素，并且p->nex=NULL如用重复，则需要重新输入直到元素的个数等于用户第一步输入的元素个数时函数调用结束函数如下：Status createLinkList(LinkList &L,int n){ cout<<"输入集合元素时，整数与字母之间没有任何符号，"<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; } } else { i--;//为下一次循环显示元素的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)//依次检索链表B { pa=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))内层循环，找相等元素 。