2022年2022年集合的交并差运算 .pdf

《2022年2022年集合的交并差运算 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年集合的交并差运算 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计一、实验内容 1.本演示程序中，集合的元素限定为小写字符a,z，集合的大小n=0 数据关系：R1=|ai-1,aiD,ai-1=a&edata=e;p-next=NULL;return OK;/MakeNode 2根据有序表的基本操作的特点，有序表采用有序链表实现。链表设头指针和表长数据域，并附设头结点，头结点的数据域没有实在意义。typedefstruct LinkType head;/指向线性链表的头结点int size;/指向线性链表当前的长度 OrderedList；/有序链表类型有序表的基本操作的伪代码设置如下：Status InitList(OrderedList&

2、L)/创建有序链表 MakeNode(p,);/申请新结点 L.head=p;L.size=0;return OK;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -/InitList Status DestoryList(OrderedList L)/销毁有序链表 L if(L.head)p=L.head-next;while(p)L.head-next=p-next;free(p);p=p-next;free(L.head);/DestoryList Status LocateElem(OrderedList L,LinkType&q,ElemType e)/如果有

3、序表 L 中存在元素 e，则 q 指示 L 中值为 e 的元素的前驱的位置,/并返回 OK;否则,q指示第一个大于 e的元素的前驱的位置，并返回 ERROR if(L.head)p=L.head;q=L.head-next;if(q)while(q)if(q-data next;else break;/while if(q&q-data=e)q=p;return OK;else q=p;return ERROR;else q=L.head;return ERROR;else return ERROR;/LocateElem void InsertList(OrderedList&L,ElemT

4、ype e)/若 L 中不存在和 e相同的元素，则在L 中插入一个元素为e的新结点名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 17 页 -if(!LocateElem(L,p,e)MakeNode(t,e);if(p-next)t-next=p-next;p-next=t;L.size+;/InsertList void DeleteList(OrderedList&L,ElemType e)/若 L 中存在和 e相同的结点元素，则删除L 中结点元素为 e的结点if(LocateElem(L,p,e)q=p-next;p-next=q-next;free(q);L.size-

5、;/DeleteList 3.集合 Set利用有序链表类型OrderedList 来实现，定义为有序集OrderSet；typedefOrderedList OrderedSet；集合类型的基本操作的伪代码描述如下：void CreateSet(OrderedSet&T,char s)/生成有串 s中小写字母构成的集合T InitList(T)；for(i=0;aaa(si)=OK;i+)if(Changeelem(si)=OK)InsertList(T,si)/CreateSet void DestorySet(OrderedSet T)/销毁集合 T DestoryList(T);/Des

6、torySet 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 17 页 -void PrintSet(OrderedSet T)/输出集合 T 中全部元素p=T.head;if(!T.head|!p-next)printf(NULL);/如果头结点为空，或者只有头结点，则返回NULL else q=p-next;while(q)printf(q-data);q=q-next;/PrintSet void CompleteSet(OrderedSet&E)/构造全集 for(i=0;inext;/p指向 S1 的第一个元素q=S2.head-next;/q指向 S2 的第一个元素

7、while(q)e=q-data;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 17 页 -if(JudgeSet(S1,e)InsertList(T,e);/如果元素 e 属于集合 S1，插入 T 中q=q-next;/InsertSet Status CopySet(OrderedSet&T,OrderedSet S)/把集合 S 中元素插入到集合T 中,若成功，则返回 OK；否则，返回 ERROR if(S.head)p=S.head-next;while(p)InsertList(T,p-data);p=p-next;return OK;elsereturn ERROR

8、;/CopySet void DeleteSet(OrderedSet&T,OrderedSet S)/删除集合 T 中与集合 S 中元素重复的元素q=S.head-next;while(q)e=q-data;if(JudgeSet(T,e)=OK)DeleteList(T,e);/如果元素 e 属于集合 T，则删除 T 中和 e相同的元素q=q-next;/DeleteSet void Union(OrderedSet&T,OrderedSet S1,OrderedSet S2)/求已建成的集合 S1和 S2的并集InitList(T);CopySet(T,S1);/把集合 S1 中元素复制

9、到集合T 中CopySet(T,S2);/把集合 S2 中元素复制到集合T 中 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 17 页 -void Intersection(OrderedSet&T,OrderedSet S1,OrderedSet S2)/求已建成的集合 S1和 S2的交集InitList(T);if(!S1.head|!S2.head|!S1.head-next|!S2.head-next)T.head=NULL;/如果 S1或 S2中有一个为空，则集合T 为空elseInsertSet(T,S1,S2);/把 S1与 S2中共有的元素插入集合T 中/In

10、tersection void Difference(OrderedSet&T,OrderedSet S1,OrderedSet S2)/求已建成的集合 S1和 S2的差集InitList(T);CopySet(T,S1);/把集合 S1 中元素复制到 T 中if(S2.head|S2.head-next)DeleteSet(T,S2);/删除集合 T 中与集合 S2中元素重复的元素/Difference Status JudgeElem(OrderedSet S,ElemType e)/判定元素 e是否属于集合 S if(JudgeSet(S,e)=OK)return OK;else ret

11、urn ERROR;/JudgeElemvoid Status Judge(OrderedSet S1,OrderedSet S2)/判定集合 S2是否为集合 S1的子集if(!S2.head-next)return OK;else p=S2.head-next;while(p)e=p-data;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 17 页 -if(JudgeSet(S1,e)=OK)p=p-next;else return ERROR;break;if(!p)return OK;else return ERROR;/Judge void Complement(Or

12、deredSet&T,OrderedSet E,OrderedSet S2)/求已建成的集合 S2的补集 T CopySet(T,E);/把集合 S1中元素复制到 T 中if(S2.head|S2.head-next)DeleteSet(T,S2);/删除集合 T 中与集合 S2中元素重复的元素/Complement 4.主函数和其他函数的伪码算法：void main()Initialization();/初始化do Interpret(cmd);/解释执行操作命令符ReadCommand(cmd);/读入一个操作命令符while(cmd!=q)销毁集合 E,Set1,Set2；void In

13、itialization()/系统初始化printf(*n);printf(*MakeSet1-1 MakeSet2-2 CompleteSet-3 Union-u*n);printf(*Intersection-i Difference-d JudgeElem-e Judge-j*);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 17 页 -printf(*Complement-c Quit-q*n);printf(*n);/Initialization voidReadCommand(char&cmd)/读入操作命令符 do cmd=getchar();while(cmd

14、 不属于 1 ,2 ,3 ,u ,i ,d ,e ,j ,c ,q)/ReadCommand voidInterpret(char cmd)/解释执行操作命令 switch(cmd)case1:Gets(str);/读入集合元素到串变量str CreateSet(Set1,str);PrintSet(Set1);break;/构造并显示有序集Set1 case2:Gets(str);/读入集合元素到串变量str CreateSet(Set2,str);PrintSet(Set2);break;/构造并显示有序集Set2 case3:CompleteSet(E);/构造全集 E PrintSet

15、(E);break;/构造并显示全集E caseu:Union(Set3,Set1,Set2);PrintSet(Set3);DestorySet(Set3);break;casei:Intersection(Set3,Set1,Set2);PrintSet(Set3);DestorySet(Set3);名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -break;cased:Difference(Set3,Set1,Set2);PrintSet(Set3);DestorySet(Set3);break;casee:Getchar(e);/判定元素if(JudgeEl

16、em(Set1,e)=OK)printf(属于n);else printf(不属于 n);break;casej:if(Judge(Set1,Set2)=OK)printf(是n);/判定子集else printf(不是n);break;casec:Complement(Set3,E,Set1);/求 Set1的补集PrintSet(Set3);DestorySet(Set3);/switch/Interpret 四、测试数据及程序运行情况测试数据:(1)Set1=magazine,Set2=paper,运行结果：*MakeSet1-1 MakeSet2-2 CompleteSet-3 Uni

17、on-u Intersection-i*Difference-d JudgeElem-e Judge-j Complement-c Quit-q *-Enter a operation code:1 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 17 页 -执行命令 1:m a g a z i n e#键入 m,a,g,a,z,i,n,e,后，构造集合 Set1:a,e,g,i,m,n,z,-Enter a operation code:2 执行命令 2:p a p e r#键入 p,a,p,e,r,后，构造集合 Set2:a,e,p,r,-Enter a operation

18、 code:3 执行命令 3:构造全集E:a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,-Enter a operation code:u 执行命令 u:构造集合 Set1 和 Set2 的并集:a,e,g,i,m,n,p,r,z,-Enter a operation code:i 执行命令 u:构造集合 Set1 和 Set2 的交集:a,e,-Enter a operation code:d 执行命令 u:构造集合 Set1 和 Set2 的差集:g,i,m,n,z,-Enter a operation code:e 执行命令 e:

19、输入元素：j 判定元素 e 是否属于集合 Set1:不属于 -Enter a operation code:c 执行命令 c:集合 Set1 的补集是:b,c,d,f,h,j,k,l,o,p,q,r,s,t,u,v,w,x,y,名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 17 页 -Enter a operation code:q Press any key to continue (2)Set1=012oper4a6tion89,Set2=error date,运行结果：*MakeSet1-1 MakeSet2-2 CompleteSet-3 Union-u Inters

20、ection-i*Difference-d JudgeElem-e Judge-j Complement-c Quit-q *-Enter a operation code:1 执行命令 1:m a g a z i n e#键入 m,a,g,a,z,i,n,e,后，构造集合 Set1:a,e,g,i,m,n,z,-Enter a operation code:2 执行命令 2:p a p e r#键入 p,a,p,e,r,后，构造集合 Set2:a,e,p,r,-Enter a operation code:3 执行命令 3:构造全集E:a,b,c,d,e,f,g,h,i,j,k,l,m,n,

21、o,p,q,r,s,t,u,v,w,x,y,z,-Enter a operation code:u 执行命令 u:构造集合 Set1 和 Set2 的并集:a,e,g,i,m,n,p,r,z,-名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -Enter a operation code:i 执行命令 u:构造集合 Set1 和 Set2 的交集:a,e,-Enter a operation code:d 执行命令 u:构造集合 Set1 和 Set2 的差集:g,i,m,n,z,-Enter a operation code:e 执行命令 e:输入元素：j 判定元素 e 是否属于集合 Set1:不属于 -Enter a operation code:c 执行命令 c:集合 Set1 的补集是:b,c,d,f,h,j,k,l,o,p,q,r,s,t,u,v,w,x,y,-Enter a operation code:q Press any key to continue 名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 17 页 -