数据结构试验报告：集合的交叉并

1、数据结构实验报告题目：集合的并、交、差专业：信息管理与信息系统班级：17信管3组别：一组长：胡源完成日期：2018年10月23日评分依据及结果态度（A-D）规范性（A-D）完成度（A-D）总评（A-D）评语代码分工情况姓名胡源肖晓红景新月关延宇杜彪工作内容改进代码编写原始代码调试代码处理bug运行代码实验报告分工情况姓名胡源肖晓红景新月关延宇杜彪工作内容报告初稿报告规范化处理报告细节处理实验调试和截图报告整合一、需求分析1. .本演示程序中，集合的元素限定为小写字母和数字，集合的大小小于MAXSIZE=100T以通过宏定义来动态改变大小）。集合的输入形式为以一个“回车符”为结束标志的字符串，串

2、中字符顺序不限。程序能自动过滤出现的重复字符和非法字符，且经过过滤的集合中，数字始终在字母前面。输出运算结果字符中不含重复字符或非法字符。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（除去非法字符）和运算结果显不在其后。3. 程序的执行命令包括：1）构造集合1;2）构造集合2;3）求并集；4）求交集；5）求差集；6）程序结束。“构造集合1”和“构造集合2”时，需要以字符串的形式链入集合元素。4. 测试数据（1） Set1="abcdefg"，Set1="123456”（

3、未赋值时的原始集合）Set2nSet2="123456abcdefg"，Set2nSet2="，Set2-Set2='abcdefg”（2） Set1="1314524huyuan"，Set1="748fuck”Set2nSet2="12345678acfhknuy”,Set2nSet2=4u”，Set2-Set2=?1235ahny"（3） Set1="1314524huyuan数据结构"Set1="958abcd考研”Set2nSet2="1234589abcdh

4、nuy；Set2nSet2=5a”，Set2-Set2=1234hnuy”二、概要设计用有序链表表示集合来使程序达到预期功能。因此，需要一个抽象数据类型：有序集合。1 .有序集合的抽象数据类型定义为：ADTOrderedList数据对象：D=a|a为数字(1-9)或字母(a-z)数据关系：R=<ai-1,ai>|ai-1,ai6D,ai-1<ai,i为自然数基本操作：InitList(&L)操作结果：构造空的有序链集合LocateElem(L,e,&p)初始条件：L为存在的有序表，e为一个字符操作结果：如果能找到元素，p带回e元素的下标，结果为true。若找不

5、到元素，用p带回比与元素e最近的一个元素的位置。如果e元素比所有元素都要小，返回指向头结点的指针，结果为false。InsertAfter(&L,q,s)初始条件：L为存在的有序表，q是指向L中一个结点的指针操作结果：让s结点插在q结点后面一个位置。Append(&L,s)初始条件：L为有序表，s为一个结点的指针操作结果：把s指向的结点插在L的最后面。CreateSet(&L,*s)初始条件：L为存在的顺序集和，s指向一个串操作结果：生成一个由s串组成的顺序集合ListTraverse(p)初始条件：p为一个集合的头结点指针操作结果：打印出这个集合Append(&

6、;L,s)初始条件：L为顺序表，s为一个结点的指针操作结果：把s指向的结点插在L的最后面。Union(&L,S1,S2)初始条件：S1,S2为有序集合操作结果：L=S1US2Intersection(&T,S1,S2)初始条件：S1,S2为有序集合操作结果：L=S1AS2Difference(&T,S1,S2)初始条件：S1,S2为有序集合操作结果：L=S1S2)2 .本程序包括3个模块：(1)主程序模块：voidmain初始化；do接受命令；处理命令；while(“命令”=“退出”)(2)有序集合单元模块一一实现有序集合的抽象数据类型(3)结点结构模块一一定义有序表的

7、结点结构各个模块之间的调用如下：结点结构单元三、详细设计1 .用字符串a,字符串b表示原始输入的字符串。2 .两个集合的并运算：把字符串a中各个元素过滤后放在有序集合L1中。将数组b中的元素过滤后放在有序集合L2中。将L1中的元素和L2中的元素进行比较，会出现三种情况:当L1中的元素比L2中的元素小的时候，把L1中的当前元素放在L3中，L1指向下一个元素；当L1中的元素与L2中的元素相等的时候，把L1中的当前元素放在L3中，L1和L2指向下一个元素；当L1中的元素比L2中的元素大的时候，把L2中的当前元素放在L3中，L2指向下一个元素。这样比较，直到L1或L2为空。最后，把L1或L2中的剩余元

8、素，放在L3表的后面。3 .两个集合的交运算：把字符串a中各个元素过滤后放在有序集合L1中，将数组b中的元素过滤后放在有序集合L2中。L1中的元素和L2中的元素进行比较，会出现三种情况：如果L1中的元素大于L2中的元素，L2指向下一个位置；如果L1中的元素小于L2中的元素，L1指向下一个位置；如果L1中的元素与L2中的元素相等，把这个元素放在L3中，L1和L2都指向下一个位置，直到其中L1或L2为空。4 .两个集合的差运算：把字符串a中各个元素过滤后放在有序集合L1中，将数组b中的元素过滤后的放在有序集合L2中。会出现三种情况：如果L1中的元素小于L2中的元素，把L1中的元素放入L3中；如果L

9、1中的元素等于L2中的元素，则L1和L2分别指向下一个元素；如果L1中的元素大于L2中的元素，则把L1中的元素指向下一位置，直到L1或L2中的元素为空。如果L1中有剩余元素，则把L1中的剩余元素全部给L35 .函数之间的调用关系如下图：mainIIREadCommandInterpretI1IfIIDifferencEIntersedioiiUnionUsff哪R怖CreateSet1-iiinAppendtnhLstInitlist赫岫怖四、调试分析1 .问题分析及解决：(1)没有设置尾指针和长度，算法的效率低下。添加尾指针和长度，对于一些函数不再需要从头结点出发寻找元素，提高了算法的执行效

10、率。(2)忽略"&'：在传递参数的时候，表示符"&”不可缺少。通过参数传递可以改变参数的值有两种情况引用和指针。但此算法更多的是用引用指针来传递参数，改变指针的走向。2 .时间复杂度分析：(1)假设L1串有m个字符，L2串有n个字符，对于Union和Insersection以及Difference这三个函数，都需要对两个集合中的元素不重复的进行检查，并插入L3中，所以时间复杂度是O(m+n)。(2) ListTraverse函数是打印这个集合中的元素，若集合有n个元素，则时间复杂度是O(n)。(3) CreateSet函数是把不重复的字符串中的元素依

11、次赋给有序表。若有n个不重复的元素，则时间复杂度为O(n)。(4) 进方案：(1)拓展集合元素的多样性。通过改变CreateSet函数的条件，使集合的元素扩展到数字，甚至是英文大写字母。(2)采用#defineMAXSIZE100;来动态调整最大限度，以此来解决初始集合没有约定固定的最大限度问题。(3)添加delete或free释放内存空间，防止内存泄漏。五、用户手则(1)本程序的运行环境为DOS操作系统，执行文件为：SET.exe(2)进入演示程序后显示文本的用户界面；进入“创建集合1”和“创建集合2”的命令后，即提示键入集合元素串，结束符命令为“回车符”接受其他命令后即执行相应运算和显示相

12、应结果六、测试结果(及截图)(1)Set1="abcdefg"，Set1="123456”(未赋值时的原始集合)Set2nSet2="123456abcdefg”,Set2nSet2=",Set2-Set2=abcdefg"如图：(2)Set1="1314524huyuan"，Set1='748fuck”Set2-Set2=M235ahny”Set2nSet2=M2345678acfhknuy”,Set2nSet2=4u”,如图:(3)Set1="1314524huyuan数据结构”，Set1=&

13、quot;958abcd考研”Set2nSet2=1234589abcdhnuy,Set2nSet2="5a：Set2-Set2=1234hnuy”如图：七、附录（源代码）头文件SET.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/#defineOVERFLOW-2typedefintStatus;typedefcharElemType;typedefstructNodeTypeElemTypedata;structNodeType*next;NodeType,*LinkType;/链表typ

14、edefstructLinkTypehead;LinkTypetail;intsize;OrderedList;/头尾指针和长度源文件SET.cpp#include"SET.h"ElemTypeaMAXSIZE="abcdefg"ElemTypebMAXSIZE="123456”;OrderedListL1,L2,L3;/StatusMakeNode(LinkType&p,ElemTypee)p=newNodeType;if(!p)returnFALSE;/分配不成功p->data=e;p->next=NULL;return

15、TRUE"/新建一个结点，并用e对其赋值，即p指向一个数据域为e,指针域为null的新结点。/StatusInitList(OrderedList&L)if(MakeNode(L.head,'')/L.head指向头节点L.tail=L.head;L.size=0;returnTRUE)else(returnFALSE;)/初始化，如果成功初始化，L.head指向头结点，头节点的数据域为空格，L.tail也指向头节点，长度为0,返回true。/初始化不成功，返回false此时头结点指向null/StatusclearList(OrderedList&L

16、)(NodeType*p;NodeType*q;p=L.head->next;while(p)(q=p->next;deletep;p=q;L.head->next=NULL;returnTRUE/StatusLocateElem(OrderedListL,ElemTypee,LinkType&p)(NodeType*pre;if(L.head)/L表成功初始化并且未到表尾。(pre=L.head;p=pre->next;while(p&&p->data<e)/关系运算符“的优先级别大于逻辑运算符“&&(pre=p;p

17、=p->next;if(p&&p->data=e)关系运算符“=的优先级别大于逻辑运算符“&&(returnTRUEelsep=pre;returnFALSE;)elsereturnFALSE;/在顺序链表(从小到大)L中查找e元素。如果能找到，p带回e元素的下标。/如果找不到，用p带回比与元素e最近的一个元素的位置。如果e元素比所有元素都要小，返回的是指向头结点的指针。/voidInsertAfter(OrderedList&L,LinkTypeq,LinkTypes)(if(L.head&aqa&s)(s->next

18、=q->next;q->next=s;让s指向q指向的结点，然后q的下一个结点，就是s指向的节点。通俗的说，就是让s结点插在q节点后面。if(L.tail=q)L.tail=s;L.size+;/q是链表L中的一个结点，让s结点插在q结点后面一个位置。/voidCreateSet(OrderedList&T,char*s)(unsignedi;NodeType*p,*q;if(clearList(T)/T链表初始化成功的情况下，继续往后执行。(for(i=0;i<=strlen(s);i+)(if(si>='a'&&si<=

19、'z')|(si>='0'&&si<='9')&&!LocateElem(T,si,p)/s中的串的字符在a至Uz,并且不能重复。p指针此时指向的是一个与恰好数据域比s】的结点的指针。(if(MakeNode(q,si)/在成功创建一个q指向的以s】为数据域的结点以后，执行后面语句。(InsertAfter(T,p,q);/在p结点以后，插入q。/把s串中的所有字符分别赋给刚初始化过后的T链表。自动过滤重复的和非法字符。(有排序功能。)/voidListTraverse(LinkTypep)(while

20、(p)(cout<<p->data;p=p->next;cout<<endl;/若p为头结点，可以打印出串所有结点的数据域。/voidAppend(OrderedList&L,LinkTypes)(if(L.head&&s)(L.tail->next=s;L.tail=s;L.size+;/尾插法，在链表L中插入s指向的结点。/voidUnion(OrderedList&T,OrderedListS1,OrderedListS2)(LinkTypep1,p2,p;if(clearList(T)/初始化T成功的话。(p1=

21、S1.head->next;/p1指向S1的头结点p2=S2.head->next;/p2指向S2的头结点while(p1&&p2)(if(p1->data<=p2->data)(p=(LinkType)malloc(sizeof(NodeType);/为p创建空间。p->data=p1->data;p->next=NULL;Append(T,p);if(p1->data=p2->data)p2=p2->next;/避免重复出现相等的数。p1=p1->next;else(sizeof(NodeType);/

22、为p创建空间。(p=(LinkType)mallocp->data=p2->data;p->next=NULL;Append(T,p);p2=p2->next;while(p1)/S2的数据全部循环完毕，接下来把S1中的数全部放到T表的后面。(p=newNodeType;p->data=p1->data;p->next=NULL;Append(T,p);p1=p1->next;while(p2)/S1的数据全部循环完毕，接下来把S2中的数全部放到T表的后面。(p=newNodeType;p->data=p2->data;p->n

23、ext=NULL;Append(T,p);p2=p2->next;/初始化T,来带出来S1和S2的并集。即T=S1US2/voidIntersection(OrderedList&T,OrderedListS1,OrderedListS2)(LinkTypep1,p2,p;if(clearList(T)(p1=S1.head->next;p2=S2.head->next;while(p1&&p2)(if(p1->data<p2->data)p1=p1->next;elseif(p1->data>p2->data

24、)p2=p2->next;/谁的数据域的值更小，就往后移else/相等的话，执行次语句块。p=newNodeType;p->data=p1->data;p->next=NULL;Append(T,p);p2=p2->next;pl=p1->next;/相等的话，都要往后移。)/初始化T,来带出来S1和S2的交集。即T=S1S2/voidDifference(OrderedList&T,OrderedListS1,OrderedListS2)LinkTypep1,p2,p;if(clearList(T)p1=S1.head->next;p2=S2

25、.head->next;while(p1&&p2)if(p1->data<p2->data)p=newNodeType;p->data=p1->data;p->next=NULL;Append(T,p);p1=p1->next;若S1的数据域小于S2的数据域，则S2中不存在与此时S1中p1所指向的相等的值。elseif(p1->data>p2->data)p2=p2->next;若S1的数据域大于S2的数据域，则S2往后移动，寻找是否S2中存在与此时S1中p1所指向的相等的值。elsep1=p1->n

26、ext;p2=p2->next;/相等的话，都往后移。while(p1)p=newNodeType;p->data=p1->data;p->next=NULL;Append(T,p);p1=p1->next;/S2循环完毕，把S1中剩下的字符存入T./求S1和S2的差集，用T带出结果。即T=S1-S2./voidReadCommand(char&cmd)(CCII，/”*"cout<<"创建集合11"cout<<"创建集合22"cout<<"并集u"c

27、out<<"交集i"cout<<"差集d"cout<<"显示y"操作提示<<endl;<<endl;<<endl;<<endl;<<endl;<<endl;<<endl;<<endl;docout<<”*选择操作cout<<"退出q"<<endl;*”cin>>cmd;while(cmd!='1'&&cmd

28、!='2'&&cmd!='u'&&cmd!='i'&&cmd!='d'&&cmd!='q'&&cmd!='y');/voidInterpret(char&cmd)system("cls");/清屏(dos)switch(cmd)case'1':/创建集合cout<<"请输入字符串："cin>>a;cout<<"原

29、始字符串："；cout<<a<<endl;/输出没有处理过的字符。CreateSet(L1,a);初始化L1,把字符串a中的字符全部赋给L1。此过程把重复的，非法的过滤。cout<<"构建的集合："；ListTraverse(L1.head->next);/函数的名字体现函数的入口地址break;case'2':cout<<"请输入字符串："cin>>b;cout<<"原始字符串："；cout<<b<<end

30、l;CreateSet(L2,b);cout<<"构建的集合："；ListTraverse(L2.head->next);break;case'u':CreateSet(L1,a);CreateSet(L2,b);Union(L3,L1,L2);cout<<"集合1:"ListTraverse(L1.head->next);cout<<"集合2:"ListTraverse(L2.head->next);cout<<"并集:"ListTraverse(L3.head->next);break;case'i'CreateSet(L1,a);CreateSet(L2,b);Intersection(L3,L1,L2);cout<<"集合1:&quo