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

《数据结构课程设计-集合运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集合的运算1需求分析1.1设计任务集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符[‘a’......‘z’]；演示程序以用户和计算机的对话方式执行；其中运用了编程软件MicrosoftVisualC++6.0创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算。1.2功能要求集合输入的形式为一个以"回车符"为结束标志的字符串，元素中字符顺序为先整数后字母，否则程序提示重新输入,若出现重复元素或非法字符，不符合集合的定义,程序提示重新输入。本段程序旨在对输入的元素进行并集,交集,差集和布尔和运算。2概要设计2.1

2、链表表的抽象数据类型定义[1]为实现上述程序功能，并要求以有序链表表示集合。所以，抽象数据类型就是单链表ADTOrderedLinkList{数据对象：D={(ai,bi)

3、aiÎInteger，biÎCharSet,i=1,2,...,n,n³0}数据关系：Rl={<(ai-1,bi-1),(ai,bi)>

4、(ai-1,bi-1),(ai,bi)ÎD,(ai-1,bi-1)<(ai,bi),i=2,...,n}基本操作：createLinkList(&L,n)操作结果：构造一个带表头的单链表，其中除表头外有n个结点。30集合的运算unionset(&A,&B,&C)初始条件：单链表

5、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已存在。操作结果：以结点数据从表头到表尾用直接选择法按从小到大排序。bubble

6、sort(L)初始条件：有序表L已存在。操作结果：以结点数据从表头到表尾用冒泡排序法按从小到大排序。shellsort(L)初始条件：有序表L已存在。操作结果：以结点数据从表头到表尾用冒泡排序法按从小到大排序。}ADTOrderedLinkList1详细设计3.1元素类型、结点类型和指针类型[1]30集合的运算宏定义：typedefintStatus;用来作为函数的返回值类型。根据课题要求，每个结点必须含有两个类型的数据，即整数域和小写字母域，另外必须有一个指向下一个结点的结构类型的指针，故结构体有三个成员如下：typedefstructLNode{//定义结构体，数据域两种类型in

7、tinte;charc;structLNode*next;}LNode,*LinkList;//结点类型，结构体指针3.2节点中元素大小的比较函数由于节点的数据域中有两个类型的数据，在后面的检查新输入的元素是否和已经输入的有重复，以及在排序过程中不便于结点元素的大小的比较，所以先写出这个功能的函数。其比较原则是先将结点数据的的整数成员比较，整数大的元素大，整数相等的情况下则进行小写字母域的比较，其大小按字符大小直接比较，参数为结点，用1、0、-1作为返回值，分别表明前一个结点数据大于、等于、小于后一个节点数据。然后在后面的过程中只需要调用即可。该功能函数如下：Statusdataco

8、mpare(LNodenode1,LNodenode2){//元素大小的比较：结点作参数，先比整数域，再比字母域//用点运算取结构体的成员变量if(node1.inte>node2.inte)return1;elseif(node1.intenode2.c)return1;30集合的运算elseif(node1.c

9、行下一步操作。如果用户输入的有多余的字符，存在输入输入缓冲却，将会被函数中调用的fflush(stdin)[6]函数处理掉，消除了缓冲区残留信息对下一步操作的影响。函数如下：Statusinput1(intn){while(1){if(scanf("%d",&n)==1){fflush(stdin);//清除输入缓冲区break;}else{cout<<"请正确输入整数："<