用链表实现集合交并补等运算(共11页).doc

一、 数据结构定义1. 抽象数据类型本设计中用到的数据结构ADT定义如下：ADT List{ 数据对象：D={} 数据关系：={} 基本操作：InitList(&L) 操作结果：构造一个空的线性表L； DestroyList(&L) 初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(&L) 初始条件：线性表L已存在 操作结果：将L重置为空表 ListEmpty(L) 初始条件：线性表L已存在 操作结果：若L为空表，则返回TRUE，否则返回FALSE ListLenght(L) 初始条件：线性表L已存在 操作结果：返回L中数据元素的个数2. 存储结构定义数据存储结构的C语言定义如下：typedef struct LNode//定义单链表结点类型 { ElemType data; struct LNode *next;}LinkList;3. 基本操作数据结构的基本操作实现如下：DispList(LinkList *L)：输出单链表LCreatListR(LinkList *&L,ElemType a[],int n)：运用尾插法建立单链表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语句进行运算的选择，使用相关函数对有序链表进行交并差的相关运算二、 解题过程1. 问题分解该问题主要应实现以下功能：1. 利用尾差法建立单链表2. 对于输入的链表进行有序排列3. 删除有序链表中不符合要求的元素4. 调用函数对单链表进行交，并，差运算，并输出2. 模块结构系统主要由8个模块组成，分别是：1. 单链表的建立2. 单链表的有序排列3. 删除单链表中不符合条件的元素4. 集合交集5. 集合并集6. 集合差集7. 单链表输出8. 主函数模块之间的结构如下：主函数单链表的建立及由于排列删除不符合条件的元素集合交集集合差集单链表输出集合并集3. 解题思路各模块的实现步骤为：1. 在尾差法建立单链表时，开始时指针指向头结点2. 建立有序列表是利用指针的移动来是后续的元素和第一次个元素进行比较，并使用while循环实现单链表的有序排列3. 判定有序单链表中的重复元素定义指针p，通过指针p访问链表中的元素并且通过if语句检测链表中的元素对于不属于小写字母的元素判定后进行删除操作4. 定义三个头结点pa，pb，pc，把ha的元素赋给hc，在使用指针移动与hb中的元素进行比较，不同的元素则插入到hc中，相同时指针移动到ha的下一个元素。

当ha为空，直接把hb赋给hc5. 同样定义了三个结点，不过hc是pa与pb不同的元素6. 差集是通过指针的移位把两个有序单链表中的元素进行比较，不同的话，则赋给hc7. 利用主函数把有序单链表，及三个函数输出链表进行输出8. 主函数通过一个switch语句，方便的对函数进行调用，从而进行集合的交，并，差运算三、 实现代码及注释:#include #include using namespace std;typedef char ElemType;typedef struct LNode//定义单链表结点类型 { ElemType data; struct LNode *next;}LinkList;void CreatListR(LinkList *&L,ElemType a[],int n) //运用尾插法建立单链表{ LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点，为头结点分配空间 L->next=NULL; r=L; //r先指向头结点后指向尾结点，开始时指针指向头结点 for(i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL;//尾结点指向空 } void Sort(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->datadata) q=q->next; p->next=q->next; q->next=p; p=r; } } }void shanchu(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); } else p=p->next; } if(r->next->data>'z'||r->next->data<'a') { f=r->next; r->next=f->next; free(f); } }void bing(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; }}void jiao(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->datadata) 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; }void cha(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->datadata) 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; }void DispList(LinkList *L)//输出单链表L { LinkList *p=L->next; while(p!=NULL) { cout<data; 。