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

《用链表实现集合交并补等运.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、数据结构定义1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADTList{数据对象：D={}数据关系：={}基本操作：InitList(&L)操作结果：构造一个空的线性表L；DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表LClearList(&L)初始条件：线性表L已存在操作结果：将L重置为空表ListEmpty(L)初始条件：线性表L已存在操作结果：若L为空表，则返回TRUE，否则返回FALSEListLenght(L)初始条件：线性表L已存在操作结果：返回L中数据

2、元素的个数1.存储结构定义数据存储结构的C语言定义如下：typedefstructLNode//定义单链表结点类型{ElemTypedata;structLNode*next;}LinkList;2.基本操作数据结构的基本操作实现如下：DispList(LinkList*L)：输出单链表LCreatListR(LinkList*&L,ElemTypea[],intn)：运用尾插法建立单链表Sort(LinkList*&head)：单链表元素排序shanchu(LinkList*&head)：在进行过Sort

3、排序之后，删除单链表里相同的元素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语句进行运算的选择

4、，使用相关函数对有序链表进行交并差的相关运算一、解题过程1.问题分解该问题主要应实现以下功能：1.利用尾差法建立单链表2.对于输入的链表进行有序排列3.删除有序链表中不符合要求的元素4.调用函数对单链表进行交，并，差运算，并输出2.模块结构系统主要由8个模块组成，分别是：1.单链表的建立2.单链表的有序排列3.删除单链表中不符合条件的元素4.集合交集5.集合并集6.集合差集7.单链表输出8.主函数模块之间的结构如下：主函数单链表的建立及由于排列删除不符合条件的元素集合交集集合差集单链表输出集合并集1.解题思

5、路各模块的实现步骤为：1.在尾差法建立单链表时，开始时指针指向头结点。1.建立有序列表是利用指针的移动来是后续的元素和第一次个元素进行比较，并使用while循环实现单链表的有序排列。2.判定有序单链表中的重复元素定义指针p，通过指针p访问链表中的元素并且通过if语句检测链表中的元素。对于不属于小写字母的元素判定后进行删除操作。3.定义三个头结点pa，pb，pc，把ha的元素赋给hc，在使用指针移动与hb中的元素进行比较，不同的元素则插入到hc中，相同时指针移动到ha的下一个元素。当ha为空，直接把hb赋给h

6、c。4.同样定义了三个结点，不过hc是pa与pb不同的元素。5.差集是通过指针的移位把两个有序单链表中的元素进行比较，不同的话，则赋给hc。6.利用主函数把有序单链表，及三个函数输出链表进行输出7.主函数通过一个switch语句，方便的对函数进行调用，从而进行集合的交，并，差运算。一、实现代码及注释:#include #include usingnamespacestd; typedefcharElemType; typedefstructLNode//定义单链表结点

7、类型 {ElemTypedata; structLNode*next; }LinkList; voidCreatListR(LinkList*&L,ElemTypea[],intn)//运用尾插法建立单链表 {LinkList*s,*r;inti; L=(LinkList*)malloc(sizeof(LinkList));//创建头结点，为头结点分配空间 L->next=NULL; r=L;//r先指向头结点后指向尾结点，开始时指针指向头结点 for(i=0;i

8、)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!=NUL