数据结构试验报告-集合的交并差.doc

。实验报告:集合的交并差运算题目：编写一个演示集合的交并差运算的计算机程序一、需求分析1. 本次实验中要求输入的集合的元素类型为小写字母a到z，集合输入结束的标志是一“回车符”为标志的，集合的输入不限字符输入的顺序且允许重复输入和输入非法字符；2. 本次实验中输出的集合中不包含重复的元素,集合中的元素按ASCII从小到大排列输出且将自动过滤输入的非法字符；3. 本次实验的程序可以计算用户输入的两个集合的交集、并集和补集；4. 本次实验的测试数据有：输入的集合为Set1=”magazine”，Set2=”paper”,输出的集合为Set1=”aegimnz”，Set2=”aepr”, 并集为”aegimnprz”, 交集为”ae”, 差集为”gimnz”；输入的集合为 Set1=”WE056gyh”，Set2=”asyE”，输出的集合为 Set1=”ghy”，Set2=”asy”，并集为”aghsy”，并集为”y”,差集为”aghs”。二、概要分析 为实现上述程序的功能，用有序链表表示集合。因此，需要有两个抽象数据类型：有序表和集合。1. 有序表的抽象数据类型定义：ADT OrderedList 数据对象：D=ai|aiCharSet,i=1,2.,n,n=0 数据关系：R1=|ai-1,aiD,ai-1ai,i=2.n 基本操作： InitList(&L) 操作结果；构造一个空的有序表L。 DestroyList(&L) 初始条件：有序表L已存在。 操作结果：销毁有序表L。 ListLength(L) 初始条件：有序表L已存在。 操作结果：返回有序表L的长度。 ListEmpty(L) 初始条件：有序表L已存在。 操作结果：若有序表L为空表，返回True，否则返回False。 GetElem(L,i,&e) 初始条件：有序表L已存在,若1=i=Length(L)。 操作结果：用e返回L中第i个元素的值。 LocateElem(L,e,compare() 初始条件：有序表L已存在，compare()是数据元素判定函数 操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。 若这样的元素不存在，则返回值为0。 Append(&L,e) 初始条件：有序表L已存在。 操作结果：在有序表L的末尾插入元素e。 InsertAfter(&L,q,e) 初始条件：有序表L已存在，q指示L中的一个元素。 操作结果：在有序表L中q指示的元素之后插入元素e。 ListTraverse(q,visit() 初始条件：有序表L已存在，q指示L中的一个元素。 操作结果：依次对L中q指示的元素开始的每个元素调用函数visit()。ADT OderedList2.集合的抽象数据类型定义：ADT Set 数据对象：D=ai|ai为小写英文字母且互不相同，i=1,2,.,n,0=n=26 数据关系：R1= 基本操作： CreateSet(&T,Str) 初始条件：Str为字符串。 操作结果：生成一个由Str中小写字母构成的集合T。 DestroySet(&T) 初始条件：集合T已存在。 操作结果：销毁集合T的结构。 Union(&T,S1,S2) 初始条件：集合S1和S2存在。 操作结果：生成一个由S1和S2的并集构成的集合T。 Intersection(&T,S1,S2) 初始条件：集合S1和S2存在。 操作结果：生成一个由S1和S2的并集构成的集合T。 Difference(&T,S1,S2) 初始条件：集合S1和S2存在。 操作结果：生成一个由S1和S2的差集构成的集合T。 PrintSet(T) 初始条件：集合T已存在。 操作结果：按字母次序顺序显示集合T的全部元素。 ADT Set 3.本程序包含四个模块 （1）主程序模块： void main() 初始化；do 接受命令； 处理命令；while(“命令”=“退出”); （2）集合单元模块实现集合的抽象数据类型； （3）有序表单元模块实现有序表的抽象数据类型； （4）结点结构单元模块定义有序表的结点结构。 各模块调用关系： 主程序模块集合单元模块有序表单元模块结点结构单元模块三、详细设计a) 函数的调用关系图为： b) 具体函数代码为：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/函数常量的声明/typedef int Status;typedef char ElemType;/元素类型的定义/#include #include #include #include /函数的头文件/ElemType a100=magazine;ElemType b100=paper;OrderedList L1,L2,L3; /定义三个线性链表/定义全局变量/ void main()char cmd;doReadCommand(cmd); /读出命令/Interpret(cmd); /执行命令/while(cmd!=q); /当输入的命令为”q”时，退出程序/该实验函数的主函数/void ReadCommand(char &cmd)printf(n*n);printf(MakeSet1-1tMakeSet2-2tUnion-utnIntersection-itDifference-dtQuit-qttDisplay-y);printf(n*n);printf(nn请选择操作：);cmd=getch();if(cmd!=1 & cmd!=2 & cmd!=u & cmd!=i & cmd!=d & cmd!=q & cmd!=y)printf(n你输入的是非法指令，请重新输入！n); ReadCommand(cmd);/编写一个用户使用手册并输入命令/void Interpret(char &cmd)system(cls); /清屏/switch(cmd)case 1:printf(nt请输入字符串：);gets(a);printf(t原始字符串:);printf(t%sn,a);CreateSet(L1, a);printf(t构建的集合S1为:);ListTraverse(L1.head-next,Print);break; /当输入的指令为”1”时，利用输入的元素建立集合S1/case 2:printf(nt请输入字符串：);gets(b);printf(t原始字符串:);printf(t%sn,b);CreateSet(L2, b);printf(t构建的集合S2:);ListTraverse(L2.head-next,Print);break; /当输入的指令为”2”时，利用输入的元素建立集合S2/case u:CreateSet(L1, a);CreateSet(L2, b);Union(L3,L1,L2);printf(nt集合1:);ListTraverse(L1.head-next,Print);printf(t集合2:);ListTraverse(L2.head-next,Print);printf(t并集:);ListTraverse(L3.head-next,Print);break; /当输入的指令为”u”时，执行集合的并集运算并输出/case i:CreateSet(L1, a);CreateSet(L2, b);Intersection(L3,L1,L2);printf(nt集合1:);ListTraverse(L1.head-next,Print);printf(t集合2:);ListTraverse(L2.head-next,Print);printf(t交集:);ListTraverse(L3.head-next,Print);break; /当输入的指令为”i”时，执行集合的交集运算并输出/case d:CreateSet(L1, a);CreateSet(L2, b);Difference(L3,L1,L2);printf(nt集合1:);ListTraverse(L1.head-next,Print);printf(t集合2:);ListTraverse(L2.head-next,Print);printf(t差集:);ListTraverse(L3.head-next,Print);break; /当输入的指令为”d”时，执行集合的差集运算并输出/case y:printf(nt原始字符串:n);printf(tt%sntt%sn,a,b);CreateSet(L1, a);CreateSet(L2, b);printf(t由字符串构建的集合:n);printf(t);ListTraverse(L1.head-next,Print);printf(t);ListTraverse(L2.head-next,Print);Union(L3,L1,L2);printf(t并集:);ListTraverse(L3.head-next,Print);Intersection(L3,L1,L2);printf(t交集:);ListTraverse(L3.head-next,Print);Difference(L3,L1,L2);printf(t差集:);ListTraverse(L3.head-next,Print);break; /当输入的指令为”2”时，同时进行集合的交并差集运算并输出/读取相关指令进行运算并输出结果/void CreateSet(OrderedList &T, char *s)unsigned i;LinkType p ,q;if(InitList(T)for(i=0;i=a &sinext=q-next;q-next=s;if(L.tail=q)L.tail=s;L.size+;/在链表的指定中插入一个结点/Status LocateElem(OrderedList L, ElemType e, LinkType &p)NodeType *pre;if(L.head)pre=L.head;p=pre-next;while(p & p-datanext;if(p & p-data=e)return TRUE;elsep=pre;return FALSE;elsereturn FALSE;/建立一个元素从小到大排列的链表并返回TRUE,否则返回FALSE/Status InitList(OrderedList &L)if(MakeNode(L.head, )L.tail=L.head;L.size=0;return TRUE;elseL.head=NULL;return FALSE;/创建一个有头结点的线性链表并返回TRUE,否则返回FALSE/void ListTraverse(LinkType p, Status (*visit)( LinkType )printf(%c,t);while(p)visit(p);p=p-next;printf(%c,n);/将用户输入的元素转化为集合并输出/Status MakeNode(LinkType &p,ElemType e)p=(LinkType)malloc(sizeof(NodeType);/为建立的结点创建一个内存空间/if(!p)return FALSE;p-data=e;p-next=NULL;return TRUE;/创建一个结点并返回TRUE,否则返回FALSE/typedef struct NodeTypeElemType data;struct NodeType *next; NodeType,*LinkType;/定义一个线性链表的指针结构类型/typedef structLinkType head,tail; /定义线性表的头指针和尾指针/int size; /表示该链表的长度/OrderedList;void Union(OrderedList &T,OrderedList S1,OrderedList S2)LinkType p1,p2,p;if(InitList(T)p1=S1.head-next;p2=S2.head-next;while( p1 & p2)if(p1-datadata) p=(LinkType)malloc(sizeof(NodeType);p-data=p1-data;p-next=NULL;Append(T,p);if(p1-data=p2-data)p2=p2-next;p1=p1-next;elsep=(LinkType)malloc(sizeof(NodeType);p-data=p2-data;p-next=NULL;Append(T,p);p2=p2-next; /将两个集合的元素比较按照从小到大的顺序输入到新的集合中/while(p1)p=(LinkType)malloc(sizeof(NodeType);p-data=p1-data;p-next=NULL;Append(T,p);p1=p1-next;while(p2)p=(LinkType)malloc(sizeof(NodeType);p-data=p2-data;p-next=NULL;Append(T,p);p2=p2-next;/比较完后将两个集合中元素较多的那个集合中剩余的元素全部插入到新建的集合中/求集合S1和集合S2中元素的并集/void Append(OrderedList &L,LinkType s)if(L.head & s)if(L.tail!=L.head)elseL.tail-next=s;L.head-next=s;L.tail=s;L.size+;/插入一个结点到链表中/void Intersection(OrderedList &T,OrderedList S1,OrderedList S2)LinkType p1,p2,p;if(!InitList(T)T.head=NULL;elsep1=S1.head-next;p2=S2.head-next;while( p1 & p2)if(p1-datadata)p1=p1-next;else if(p1-datap2-data)p2=p2-next;elsep=(LinkType)malloc(sizeof(NodeType);p-data=p1-data;p-next=NULL;Append(T,p);p2=p2-next;p1=p1-next;/顺次寻找两个集合中相同的元素并输入到新的集合中输出/求集合S1和集合S2中元素的交集/void Difference(OrderedList &T,OrderedList S1,OrderedList S2)LinkType p1,p2,p;if(!InitList(T)T.head=NULL;elsep1=S1.head-next;p2=S2.head-next;while( p1 & p2)if(p1-datadata)p=(LinkType)malloc(sizeof(NodeType);p-data=p1-data;p-next=NULL;Append(T,p);p1=p1-next;else if(p1-datap2-data)p2=p2-next;elsep1=p1-next;p2=p2-next;while(p1)p=(LinkType)malloc(sizeof(NodeType);p-data=p1-data;p-next=NULL;Append(T,p);p1=p1-next;/求集合S1和集合S2中元素的补集/四、调试分析1. 在本次实验中编写将数组中的元素插入到新的链表和将新的结点插入到已知链表中两个插入函数时没注意到两个插入方法的不同导致算法出现问题；2. 在编写函数时有时没有区分大小写导致函数无法调用；3. 2.算法的时空分析：4. （1）有序表采用的是有序单链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理。 InitList,ListEmpty,ListLength,Append和InsertAfter时间复杂度都是O(1),DestroyList,LocateElem和TraverseList及确定链表中间结点的时间复杂度为O(n),n为链表长度。（2）基于有序链表实现的有序集的各种运算和操作的时间复杂度分析： 构造有序集算法CreateSet读入n个元素，逐个用LocateElem判定不在当前集合中及确定插入位置之后，才用InsertAfter插入到有序集中，所以时间复杂度是O(n2)。 求并集算法Union利用集合的有序性将两个集合的m+n个元素不重复地依次利用Append插入到当前并集的末尾，所以时间复杂度为O(m+n) 对于