数据结构集合运算精选.doc

需求分析 1.1 设计任务 集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符[‘a’......‘z’]；演示程序以用户和计算机的对话方式执行；其中运用了编程软件Microsoft Visual C++ 6.0创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算。 1.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 OrderedLinkList 详细设计 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(ee) return 1; else if(ee) return -1; else { if(node1.cnode2.c) return 1; else if(node1.cnode2.c) return -1; else return 0; } } 3.3元素个数输入的合法性检查 这个函数完全是为了程序的健壮性准备的，当用户错误输入时，程序提示用户输入正确的整数，直到输入正确后才可以进行下一步操作。如果用户输入的有多余的字符，存在输入输入缓冲却，将会被函数中调用的fflush(stdin) [6]函数处理掉，消除了缓冲区残留信息对下一步操作的影响。函数如下： Status input1(int n) { while(1) { if(s