实验报告:集合的交并差运算
题目：编写一个演示集合的交并差运算的计算机程序
一、需求分析
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|ai∈CharSet,i=1,2...,n,n>=0}
数据关系：R1={ 初始条件：有序表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 OderedList 2.集合的抽象数据类型定义： 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 ElemType a[100]=\"magazine\"; ElemType b[100]=\"paper\"; OrderedList L1,L2,L3; //定义三个线性链表// //定义全局变量// void main() { char cmd; do { ReadCommand(cmd); //读出命令// Interpret(cmd); //执行命令// }while(cmd!='q'); //当输入的命令为”q”时，退出程序// } //该实验函数的主函数// void ReadCommand(char &cmd) { printf(\"\\n****************************************************************************\\n\"); printf(\"MakeSet1-1\MakeSet2-2\Union-u\\\nIntersection-i\Difference-d\Quit-q\\Display-y\"); printf(\"\\n****************************************************************************\\n\"); printf(\"\\n\\n请选择操作：\"); 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(\"\\n\请输入字符串：\"); gets(a); printf(\"\原始字符串:\"); printf(\"\%s\\n\CreateSet(L1, a); printf(\"\构建的集合S1为:\"); ListTraverse(L1.head->next,Print); break; //当输入的指令为”1”时，利用输入的元素建立集合S1// case '2': printf(\"\\n\请输入字符串：\"); gets(b); printf(\"\原始字符串:\"); printf(\"\%s\\n\CreateSet(L2, b); printf(\"\构建的集合S2:\"); ListTraverse(L2.head->next,Print); break; //当输入的指令为”2”时，利用输入的元素建立集合S2// case 'u': CreateSet(L1, a); CreateSet(L2, b); Union(L3,L1,L2); printf(\"\\n\集合1:\"); ListTraverse(L1.head->next,Print); printf(\"\集合2:\"); ListTraverse(L2.head->next,Print); printf(\"\并集:\"); ListTraverse(L3.head->next,Print); break; //当输入的指令为”u”时，执行集合的并集运算并输出// case 'i': CreateSet(L1, a); CreateSet(L2, b); Intersection(L3,L1,L2); printf(\"\\n\集合1:\"); ListTraverse(L1.head->next,Print); printf(\"\集合2:\"); ListTraverse(L2.head->next,Print); printf(\"\交集:\"); ListTraverse(L3.head->next,Print); break; //当输入的指令为”i”时，执行集合的交集运算并输出// case 'd': CreateSet(L1, a); CreateSet(L2, b); Difference(L3,L1,L2); . printf(\"\\n\集合1:\"); ListTraverse(L1.head->next,Print); printf(\"\集合2:\"); ListTraverse(L2.head->next,Print); printf(\"\差集:\"); ListTraverse(L3.head->next,Print); break; //当输入的指令为”d”时，执行集合的差集运算并输出// case 'y': printf(\"\\n\原始字符串:\\n\"); printf(\"\\%s\\n\\%s\\n\CreateSet(L1, a); CreateSet(L2, b); printf(\"\由字符串构建的集合:\\n\"); printf(\"\\"); ListTraverse(L1.head->next,Print); printf(\"\\"); ListTraverse(L2.head->next,Print); Union(L3,L1,L2); printf(\"\并集:\"); ListTraverse(L3.head->next,Print); Intersection(L3,L1,L2); printf(\"\交集:\"); ListTraverse(L3.head->next,Print); Difference(L3,L1,L2); printf(\"\差集:\"); 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<=strlen(s);i++) { if(s[i]>='a' &&s[i]<='z' && !LocateElem(T,s[i],p)) { if(MakeNode(q,s[i])) .. . { InsertAfter(T,p,q); //当输入的是合法字符时，创建包含该元素的结点 } } } } } //创建一个能存储有用户输入的元素的线性链表// void InsertAfter(OrderedList L, LinkType q, LinkType s) { if(L.head && q && s) { s->next=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->data .. . else return FALSE; } //建立一个元素从小到大排列的链表并返回TRUE,否则返回FALSE// Status InitList(OrderedList &L) { if(MakeNode(L.head,' ')) { L.tail=L.head; L.size=0; return TRUE; } else { L.head=NULL; return FALSE; } } //创建一个有头结点的线性链表并返回TRUE,否则返回FALSE// void ListTraverse(LinkType p, Status (*visit)( LinkType )) { printf(\"%c\ while(p) { visit(p); p=p->next; } printf(\"%c\ } //将用户输入的元素转化为集合并输出// 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 NodeType { ElemType data; struct NodeType *next; } NodeType,*LinkType; //定义一个线性链表的指针结构类型// typedef struct { LinkType 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->data<=p2->data) { 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; } else { p=(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) else L.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; else { p1=S1.head->next; p2=S2.head->next; while( p1 && p2) { if(p1->data .. . } p1=p1->next; else if(p1->data>p2->data) p2=p2->next; else { p=(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; else { p1=S1.head->next; p2=S2.head->next; while( p1 && p2) { if(p1->data .. . 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(n^2)。 求并集算法Union利用集合的有序性将两个集合的m+n个元素不重复地依次利用Append插入到当前并集的末尾，所以时间复杂度为O(m+n) 对于求交集Intersection和求差集Difference作类似分析，它们的时间复杂度也是O(m+n) 销毁集合算法DestroySet和显示集合算法PrintSet的时间复杂度是O(n) 5. 本次实验作业先编写主函数，然后依次完善其他各函数，设计思路清晰，条理清楚。、 五、 用户手册 1. 本程序的运行环境为DOS操作系统，执行文件为：jihe.exe 2. 进入演示程序后即显示文本方式的用户界面： .. . 3. 进入“构造集合1（MakeSet1-1）”和“构造集合2(MakeSet2-2)”的命令后，即 提示输入集合字符串，结束命令为回车符。 4. 键入相关菜单操作，程序执行相关代码并输出相关结果。 六、 测试结果 1. 2. 3. 4. 5. 6. 7. 执行命令”1”：输入excise后，构造的集合Set1为：[c,e,i,s,x]; 执行命令”2”：输入instruction后，构造的集合Set1为：[c,i,n,o,r,s,t,u]; 执行命令”u”：构造集合Set1和Set2的并集为：[c,e,i,n,o,r,s,t,u,x]; 执行命令”i”：构造集合Set1和Set2的交集为：[c,i,s]; 执行命令”d”：构造集合Set1和Set2的差集为：[n,o,r,t,u]; 执行命令”q”：直接退出； 执行命令”y”：构造集合Set1和Set2的并集为：[c,e,i,n,o,r,s,t,u,x];构造集合Set1和Set2的交集为：[c,i,s]；构造集合Set1和Set2的差集为：[n,o,r,t,u]; 源程序文件名清单： Node.H //元素结点实现单元 OrdList.H //有序链表实现单元 OrderSet.H //有序集实现单元 SetOperation.C //主程序 七、 附录 .. 因篇幅问题不能全部显示，请点此查看更多更全内容