编制一个演示集合的并、交和差运算的程序实习报告
编制一个演示集合的并、交和差运算的程编制一个演示集合的并、交和差运算的程 序实习报告序实习报告题目：编制一个演示集合的并、交和差运算的程序一、 需求分析1. 本演示程序中，集合的元素限度为小写字母字符【a.z 】,集合的大小 n=0数据关系：R1=基本操作：InitList(p->next=NULL; return TRUE;void FreeNode(LinkType if(!s)return NULL;s->data=p->data; s->next=NULL;return s;ElemType Elem(LinkType p)LinkType SuccNode(LinkType p)typedef struct LinkType head,tail;int size;OrderedLise;有序链表的基本操作设置如下:bool InitList(OrderedLise void DestroyList(OrderedLise bool ListEmpty(OrderedLise L);int ListLength(OrderedLise L);LinkType GetElemPos(OrderedLise L,int pos);bool LocateElem(OrderedLise L, ElemType e,LinkType void Append(OrderedLise void InsertAfter(OrderedLise void ListTraverse(LinkType p,status(*visit)(LinkType q);BOOL InitList(OrderedLise L.size=0;return TRUE;else L.head=NULL;return FALSE;/InitListvoid DestroyList(OrderedLise while(p)q=p;p=SuccNode(p);FreeNode(q);L.head=L.tail=NULL;/DestroyListLinkType GetElemPos(OrderedList L, int pos )if (! L.head / posL.size ) return NULL;else if( pos = L.size ) return L.tail;else p=L.head->next; k=1;while(p/pre 指向*p 的前驱,p 指向第一个元素结点while (pelsep=pre; return FALSE;else return FALSE; /LocateElemvoid Append( OrderedLisrelse L.head->next=s;L.tail=s; L.size+;/Appendvoid InsertAfter(Orderlist q->next=s;if(L.tail=q)L.tail=s;L.size+; /InserAftervoid ListTraverse(LinkType p, status(*visit)(LinkType)while(p)viset(p); p=SuccNode(p);/ListTraverse3.集合typedef OrderedList OrderedSet;集合类型的基本操作的类 C 伪码描述如下：void CreateSet(OrderedSer ic2)p2=SuccNode(p2);else Append(T,Copy(p1);p1=SuccNode(p1);p2=SuccNode(p2);void Difference(OrderedSet else p1=GetElemPos(S1,1); p2=GetElemPos(S2,1);while(p1 c2=Elem(p2);if(c1c2) p2=SuccNode(p2);else p1=SuccNode(p1); p2=SuccNode(p2);while(p1)Append(T,Copy(p1); p1=SuccNode(p1);void WriteSetElem(linkTypep)printf(','); WriteElem(Elem(p);void printSet(OrderedSet T)p=GetElempos(t,1);printf('');if(p) WriteElem(Elem(p);p=SuccNode(p);ListTraverse(p,WriteSetElem);printf('');4.主函数和其他函数的伪码算法void main()Initilization();do ReadCommand(cmd);Interpret(cmd);while(cmd!='q'void Initialization()clrser();在屏幕上方显示操作命令清单:MakeSet1-1 MakeSet2-2 Union-u Intersaction-i Difference-d Quit-q;在屏幕下方显示操作命令提示框；CreateSet(Set1,“); PrintSet(Set1);CreateSet(Set2,“); PrintSet(Set1);void ReadCommand(char cmd)显示键入操作命令符的提示信息;do cmd=getche();while(cmd '1','2','U','i','I','d','D','q','Q');void Interpret(char cmd)switch(cmd)case'1':显示以串的形式键入集合元素的提示信息;scanf(v);CreatSet(Set1,v); PrintSet(set1);break;case'2':显示以串的形式键入集合元素的提示信息;scanf(v);CreatSet(Set2,v); PrintSet(set2);break;case'u','U':Union(Set3,Set1,Set2);printSet(Set3);DestroyList(Set3);break;case'i','I':Intersaction(Set3,Set1,Set2);Set3printSet(Set3);DestroyList(Set3);break;case'd','D':Difference(Set3,Set1,Set2);Set3printSet(Set3);DestroyList(Set3);/Interpret四、调试分析1.由于对集合的三种运算推敲不足，在有序链表类型的早期版本未设置尾指针和 Append 操作，导致算法低效。2.刚开始是曾忽略了一些变量参数的标识“&” ，是调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区别和标识。3.本程序的模板划分比较合理，且尽可能将指针的操作装在结点和链表的两个模块中，致使集合模块的调试比较顺利。反之，如此划分的模块并非完全集合，因为在实现集合操作的编码中仍然需要判别指针是否为空。按理，两个链表的并、交和差的操作也应封装在链表的模块中，而在集合的模块中，只要进行相应的应用即可。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）时间完成。可对求交集算法 Intersection 和求差集算法 Difference 作类似地分析，它们也是 O（m+n） 。销毁集合算法 DestorySet 和显示集合算法 PruntSet 都是对每个元素调用一个 O(1)的函数，因此都是 O(n)的。除了构造有序集算法 CreateSet 用一个串变量读入 个元素，需要 O(n) 的辅助空间外，其余算法使用的辅助空间与元素个数无关，即是 O(1) 的。5.本实习作业采用数据抽象的程序设计方法，将程序划分为四个层次结果：元素结点，有序链表、有序集和主控模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。六、测试结果执行命令1：键入 magazine 后,构造集合Set1:a,e,g,I,m,n,z执行命令2：键入 paper 后,构造集合 Set2:a,p,e,r执行命令u：构建集合 Set1 和 Set2 的并集：a,e,g,i,m,n,p,r,z执行命令i：构建集合 Set1 和 Set2 的交集：a,e执行命令d：构建集合 Set1 和 Set2 的差集：g,I,m,n,z执行命令1：键入 012oper4a6tion89 后,构造集合Set1:a,e,I,n,o,p,r,t执行命令2：键入 errordata 后,构造集合 Set2:a,d,e,o,r,t执行命令u：构建集合 Set1 和 Set2 的并集：a,d,e,i,n,o,p,r,t执行命令i：构建集合 Set1 和 Set2 的交集：a,e,o,r,t执行命令d：构建集合 Set1 和 Set2 的差集：i,n,p
