用链表实现集合交并补等运算.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)：输出单链表L
CreatListR(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赋给hc。
5. 同样定义了三个结点，不过hc是pa与pb不同的元素。
6. 差集是通过指针的移位把两个有序单链表中的元素进行比较，不同的话，则赋给hc。
7. 利用主函数把有序单链表，及三个函数输出链表进行输出
8. 主函数通过一个switch语句，方便的对函数进行调用，从而进行集合的交，并，差运算。

三、 实现
代码及注释:
#include <iostream>
#include <malloc.h>
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;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList));//创建新结点
s->data=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->data<p->data)
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->data<pa->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;
}
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->data<pa->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;
}
void DispList(LinkList *L)//输出单链表L
{ LinkList *p=L->next;
while(p!=NULL)
{
cout<<p->data;
p=p->next;

}
cout<<endl;
}
int main()
{ LinkList *ha,*hb,*hc;
ElemType a[100],b[100];//建立两个数组存储集合
int la,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);
cout<<"1.输出有序集合 2.求集合交集 3.求集合并集 4.求集合并集"<<endl;
while(x!=0){ //循环对运算的选择
cout<<"请选择运算：（选0退出）";
cin>>x;
switch(x)
{
case 1:
cout<<"有序1集合:";DispList(ha);
cout<<"有序2集合:";DispList(hb);//输出有序集合
break;
case 2:
jiao(ha,hb,hc);
cout<<"交集合:";DispList(hc);//调用求交集函数
break;
case 3:
bing(ha,hb,hc);
cout<<"并集合:";DispList(hc);//调求用并集函数
break;
case 4:
cha(ha,hb,hc);
cout<<"差集合:";DispList(hc);//调用求差集函数
break;
}
}

return 0;

}
四、 实验结果
1. 实验数据
集合1：xiaosihehe
集合2：wuhaha
2. 实验结果

11