用链表实现集合交并补等运算

1一、数据结构定义1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADTList{数据对象：D={|,1,2,,,0iiaaElemSetinn}数据关系：1R={11,|,,1,2,,iiiiaaaaDin}基本操作：InitList(&L)操作结果：构造一个空的线性表L；DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表LClearList(&L)初始条件：线性表L已存在操作结果：将L重置为空表ListEmpty(L)初始条件：线性表L已存在操作结果：若L为空表，则返回TRUE，否则返回FALSEListLenght(L)初始条件：线性表L已存在操作结果：返回L中数据元素的个数22.存储结构定义数据存储结构的C语言定义如下：typedefstructLNode//定义单链表结点类型{ElemTypedata;structLNode*next;}LinkList;3.基本操作数据结构的基本操作实现如下：DispList(LinkList*L)：输出单链表LCreatListR(LinkList*&L,ElemTypea[],intn)：运用尾插法建立单链表Sort(LinkList*&head)：单链表元素排序shanchu(LinkList*&head)：在进行过Sort排序之后，删除单链表里相同的元素bing(LinkList*&ha,LinkList*&hb,LinkList*&hc)：求两个有序集合的并jiao(LinkList*ha,LinkList*hb,LinkList*&hc)：求两个有序集合的交cha(LinkList*ha,LinkList*hb,LinkList*&hc)：求两个有序集合的差、main()：采用尾差法建立单链表，使用Sort进行单链表排序构成有序链表，在使用shanchu函数删除相同元素和非小写字母。利用一个switch语句进行运算的选择，使用相关函数对有序链表进行交并差的相关运算3二、解题过程1.问题分解该问题主要应实现以下功能：1.利用尾差法建立单链表2.对于输入的链表进行有序排列3.删除有序链表中不符合要求的元素4.调用函数对单链表进行交，并，差运算，并输出2.模块结构系统主要由8个模块组成，分别是：1.单链表的建立2.单链表的有序排列3.删除单链表中不符合条件的元素4.集合交集5.集合并集6.集合差集7.单链表输出8.主函数4模块之间的结构如下：3.解题思路各模块的实现步骤为：主函数单链表的建立及由于排列删除不符合条件的元素单链表输出集合交集集合并集集合差集51.在尾差法建立单链表时，开始时指针指向头结点。2.建立有序列表是利用指针的移动来是后续的元素和第一次个元素进行比较，并使用while循环实现单链表的有序排列。3.判定有序单链表中的重复元素定义指针p，通过指针p访问链表中的元素并且通过if语句检测链表中的元素。对于不属于小写字母的元素判定后进行删除操作。4.定义三个头结点pa，pb，pc，把ha的元素赋给hc，在使用指针移动与hb中的元素进行比较，不同的元素则插入到hc中，相同时指针移动到ha的下一个元素。当ha为空，直接把hb赋给hc。5.同样定义了三个结点，不过hc是pa与pb不同的元素。6.差集是通过指针的移位把两个有序单链表中的元素进行比较，不同的话，则赋给hc。7.利用主函数把有序单链表，及三个函数输出链表进行输出8.主函数通过一个switch语句，方便的对函数进行调用，从而进行集合的交，并，差运算。三、实现代码及注释:#includeiostream#includemalloc.husingnamespacestd;typedefcharElemType;typedefstructLNode//定义单链表结点类型{ElemTypedata;structLNode*next;}LinkList;voidCreatListR(LinkList*&L,ElemTypea[],intn)//运用尾插法建立单链表{LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList));//创建头结点，为头结点分配空间6L-next=NULL;r=L;//r先指向头结点后指向尾结点，开始时指针指向头结点for(i=0;in;i++){s=(LinkList*)malloc(sizeof(LinkList));//创建新结点s-data=a[i];r-next=s;r=s;}r-next=NULL;//尾结点指向空}voidSort(LinkList*&head)//建立有序链表{LinkList*p=head-next,*q,*r;if(p!=NULL){r=p-next;p-next=NULL;p=r;while(p!=NULL)//后续元素与第一个元素进行比较{r=p-next;q=head;while(q-next!=NULL&&q-next-datap-data)q=q-next;p-next=q-next;q-next=p;p=r;}}}voidshanchu(LinkList*&head)//删除有序链表中重复的元素及非小写字母的元素{LinkList*p=head-next,*r=head,*q,*f;while(p-next){if(p-data==p-next-data||((p-next-data'z')||(p-next-data'a'))){q=p-next;p-next=q-next;free(q);}elsep=p-next;7}if(r-next-data'z'||r-next-data'a'){f=r-next;r-next=f-next;free(f);}}voidbing(LinkList*ha,LinkList*hb,LinkList*hc)//求并集hc{LinkList*pa,*pb,*pc;pa=ha-next;while(pa!=NULL){pc=(LinkList*)malloc(sizeof(LinkList));pc-data=pa-data;pc-next=hc-next;hc-next=pc;pa=pa-next;}pb=hb-next;while(pb!=NULL){pa=ha-next;while((pa!=NULL)&&(pa-data!=pb-data))pa=pa-next;if(pa==NULL){pc=(LinkList*)malloc(sizeof(LinkList));pc-data=pb-data;pc-next=hc-next;hc-next=pc;}pb=pb-next;}8}voidjiao(LinkList*ha,LinkList*hb,LinkList*&hc)//求交集hc{LinkList*pa=ha-next,*pb,*s,*tc;hc=(LinkList*)malloc(sizeof(LinkList));//定义hc的头结点tc=hc;while(pa){pb=hb-next;while(pb&&pb-datapa-data)pb=pb-next;if(pb&&pb-data==pa-data){s=(LinkList*)malloc(sizeof(LinkList));s-data=pa-data;tc-next=s;tc=s;}pa=pa-next;}tc-next=NULL;}voidcha(LinkList*ha,LinkList*hb,LinkList*&hc)//求差集hc{LinkList*pa=ha-next,*pb,*s,*tc;hc=(LinkList*)malloc(sizeof(LinkList));//定义hc的头结点tc=hc;while(pa){pb=hb-next;while(pb&&pb-datapa-data)pb=pb-next;if(!(pb&&pb-data==pa-data)){s=(LinkList*)malloc(sizeof(LinkList));s-data=pa-data;tc-next=s;tc=s;}pa=pa-next;}tc-next=NULL;}9voidDispList(LinkList*L)//输出单链表L{LinkList*p=L-next;while(p!=NULL){coutp-data;p=p-next;}coutendl;}intmain(){LinkList*ha,*hb,*hc;ElemTypea[100],b[100];//建立两个数组存储集合intla,lb,x;cout请输入集合1：;cin.getline(a,100);cout请输入集合2：;cin.getline(b,100);la=strlen(a);lb=strlen(b);CreatListR(ha,a,la);CreatListR(hb,b,lb);Sort(ha);Sort(hb);shanchu(ha);shanchu(hb);cout1.输出有序集合2.求集合交集3.求集合并集4.求集合并集endl;while(x!=0){//循环对运算的选择cout请选择运算：（选0退出）;cinx;switch(x){case1:cout有序1集合:;DispList(ha);cout有序2集合:;DispList(hb);//输出有序集合break;case2:jiao(ha,hb,hc);10cout交集合:;DispList(hc);//调用求交集函数break;case3:bing(ha,hb,hc);cout并集合:;DispList(hc);//调求用并集函数break;case4:cha(ha,hb,hc);cout差集合:;DispList(hc);//调用求差集函数break;}}return0;}四、实验结果1.实验数据集合1：xiaosihehe集合2：wuhaha112.实验结果