基于单链表实现集合的并交差运算实验报告.docx
《基于单链表实现集合的并交差运算实验报告.docx》由会员分享,可在线阅读,更多相关《基于单链表实现集合的并交差运算实验报告.docx(27页珍藏版)》请在冰点文库上搜索。
基于单链表实现集合的并交差运算实验报告
基于单链表实现集合的并交差运算实验报告
一实验题目:
基于单链表实现集合的并交差运算
二实验要求:
2.2:
编写一个程序,实现顺序表的各种基本运算
(1)初始化单链表h;
(2)依次采用尾插法插入a,b,c,d,e元素;
(3)输出单链表h
(4)输出单链表h的长度
(5)判断单链表h是否为空
(6)输出单链表h的第三个元素
(7)输出元素在a的位置
(8)在第4个元素位置上插入f元素
(9)输出单链表h
(10)删除L的第3个元素
(11)输出单链表
(12)释放单链表
2.2:
编写一个程序,采用单链表表示集合(集合中不存在重复的元素),并将其按照递增的方式排序,构成有序单链表,并求这样的两个集合的并,交和差。
三实验内容:
3.1线性表的抽象数据类型:
ADTList{
数据对象;D=
数据关系:
R1=
基本操作:
InitList(&L)
操作结果;构造一个空的线性表L
DestroyList(&L)
初始条件:
线性表L已存在
操作结果:
销毁线性表L
ClearList(&L)
初始条件:
线性表L已存在
操作结果:
将L置为空表
ListEmpty(L)
初始条件:
线性表已存在
操作结果:
若L为空表,则返回TRUE,否则返回FALSE
ListLength(L)
初始条件:
线性表已存在
操作结果:
返回L中数据元素的个数
GetElem(L,i)
初始条件:
线性表已存在,1<=i<=ListLength(L)
操作结果:
用e返回L中第i个数据元素的值
LocateElem(L,i,e)
初始条件:
线性表已存在,用循环遍历整个线性表,如果e与线性表中的元素相同;
操作结果:
用此时的i+1返回该元素在线性表的位序
ListInsert(&L,i,e)
初始条件:
线性表存在,1<=i<=ListLength(L)+1;
操作结果:
在L中第i个位置之前插入新的数据元素,e,L的长度加1。
ListDelete(&L,i,&e)
初始条件:
线性表L已存在且非空,1<=i<=ListLength(L);
操作结果:
删除L的第i个数据元素,并用e返回其值,L的长度减1
}ADTList
3.2存储结构的定义;
typedefcharElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LinkList;
3.3基本操作实现:
/*单链表的初始化*/
voidInitList(LinkList*&L)
{
L=(LinkList*)malloc(sizeof(LinkList));
L->next=NULL;
}
/*向单链表中插入数据元素*/
boolListInsert(LinkList*&L,intx,chare)
{
intj=0;
LinkList*p=L,*s;
while(p!
=NULL&&j{
p=p->next;
j++;
}
if(p==NULL)
{
returnfalse;
}
else
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
returntrue;
}
}
/*输出单链表*/
voidDispList(LinkList*L)
{
LinkList*p=L->next;
while(p!
=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
/*求单链表的长度*/
intListLength(LinkList*L)
{
LinkList*p=L->next;
inti=0;
while(p!
=NULL)
{
i++;
p=p->next;
}
returni;
}
/*查看单链表是否为空*/
boolListEmpty(LinkList*L)
{
returnL->next==NULL;
}
/*求单链表中某个数据元素值*/
boolGetElem(LinkList*L,inti,ElemType&e)
{
LinkList*p=L;
intj=0;
while(p!
=NULL&&j
{
p=p->next;
j++;
}
if(p==NULL)
{
returnfalse;
}
else
{
e=p->data;
returntrue;
}
}
/*在单链表中查找元素*/
intLocateElem(LinkList*L,ElemTypee)
{
LinkList*p=L;
inti=0;
while(p!
=NULL&&p->data!
=e)
{
p=p->next;
i++;
}
if(p==NULL)
{
return0;
}
else
{
returni;
}
}
/*删除单链表中第i个元素*/
boolListDelete(LinkList*&L,inti,ElemType&e)
{
intj=0;
LinkList*p=L,*q;
while(p!
=NULL&&j{
p=p->next;
j++;
}
if(p==NULL)
returnfalse;
else
{
q=p->next;
if(q==NULL)
returnfalse;
e=q->data;
p->next=q->next;
free(q);
returntrue;
}
}
/*删除单链表*/
voidDestroyList(LinkList*&L)
{
LinkList*p=L;
LinkList*q=p->next;
while(q!
=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
3.4解题思路:
1.先通过CreateListR函数将集合a和b中的元素添加到顺序表ha和hb中,添加过程使用的是顺序表原有的Initlist函数(初始化表)和ListInsert函数(向表中插入元素)。
2.因为原集合是无序的,所以我通过sort函数(选择排序),使得集合变得有序。
3.得到有序集合ha和hb后,便可以使用Union函数(类似归并的思想写出来的求并集的函数),求出ha和hb的并集。
4.而求交集的方法则是,通过将集合a中的元素一个一个取出,并通过函数LocateElem,查看集合hb中是否存在该元素,如果存在则将元素放入hc,如果不存在,则舍去。
以此求得两集合的交集。
5.求两集合的差则可以反过来,同样通过将集合a中的元素一个一个取出,并通过函数LocateElem,查看集合hb中是否存在该元素,如果不存在则将元素放入hc,如果存在,则舍去。
以此求得两集合的差集。
(单链表求交并差集合的思想和顺序表求交并差集合的思想基本相同)
3.5解题过程:
实验源代码如下:
3.5.1单链表的各种运算
#include
#include
#include
usingnamespacestd;
/*定义单链表数据*/
typedefcharElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LinkList;
/*单链表的初始化*/
voidInitList(LinkList*&L)
{
L=(LinkList*)malloc(sizeof(LinkList));
L->next=NULL;
}
/*向单链表中插入数据元素*/
boolListInsert(LinkList*&L,intx,chare)
{
intj=0;
LinkList*p=L,*s;
while(p!
=NULL&&j{
p=p->next;
j++;
}
if(p==NULL)
{
returnfalse;
}
else
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
returntrue;
}
}
/*输出单链表*/
voidDispList(LinkList*L)
{
LinkList*p=L->next;
while(p!
=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
/*求单链表的长度*/
intListLength(LinkList*L)
{
LinkList*p=L->next;
inti=0;
while(p!
=NULL)
{
i++;
p=p->next;
}
returni;
}
/*查看单链表是否为空*/
boolListEmpty(LinkList*L)
{
returnL->next==NULL;
}
/*求单链表中某个数据元素值*/
boolGetElem(LinkList*L,inti,ElemType&e)
{
LinkList*p=L;
intj=0;
while(p!
=NULL&&j
{
p=p->next;
j++;
}
if(p==NULL)
{
returnfalse;
}
else
{
e=p->data;
returntrue;
}
}
/*在单链表中查找元素*/
intLocateElem(LinkList*L,ElemTypee)
{
LinkList*p=L;
inti=0;
while(p!
=NULL&&p->data!
=e)
{
p=p->next;
i++;
}
if(p==NULL)
{
return0;
}
else
{
returni;
}
}
/*删除单链表中第i个元素*/
boolListDelete(LinkList*&L,inti,ElemType&e)
{
intj=0;
LinkList*p=L,*q;
while(p!
=NULL&&j{
p=p->next;
j++;
}
if(p==NULL)
returnfalse;
else
{
q=p->next;
if(q==NULL)
returnfalse;
e=q->data;
p->next=q->next;
free(q);
returntrue;
}
}
/*删除单链表*/
voidDestroyList(LinkList*&L)
{
LinkList*p=L;
LinkList*q=p->next;
while(q!
=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
intmain()
{
LinkList*h;
ElemTypee;
printf("单链表的基本运算如下:
\n");
printf("
(1)初始化单链表\n");
InitList(h);
printf("
(2)依次采用尾插法插入a,b,c,d,e元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf("(3)输出单链表:
");
DispList(h);
printf("(4)单链表h的长度=%d\n",ListLength(h));
printf("(5)单链表h为%s\n",(ListEmpty(h)?
"空":
"非空"));
GetElem(h,3,e);
printf("(6)单链表h的第3个元素=%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));
printf("(8)在第4个元素位置上插入f元素\n");
ListInsert(h,4,'f');
printf("(9)输出单链表h:
");
DispList(h);
printf("(10)删除h的第3个元素\n");
ListDelete(h,3,e);
printf("(11)输出单链表h:
");
DispList(h);
printf("(12)释放单链表h\n");
DestroyList(h);
return0;
}
3.5.2求集合的并交差
#include
#include
#include
usingnamespacestd;
/*定义单链表数据*/
typedefcharElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LinkList;
/*单链表的初始化*/
voidInitList(LinkList*&L)
{
L=(LinkList*)malloc(sizeof(LinkList));
L->next=NULL;
}
/*向单链表中插入数据元素*/
boolListInsert(LinkList*&L,intx,chare)
{
intj=0;
LinkList*p=L,*s;
while(p!
=NULL&&j{
p=p->next;
j++;
}
if(p==NULL)
{
returnfalse;
}
else
{
s=(LinkList*)malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
returntrue;
}
}
/*输出单链表*/
voidDispList(LinkList*L)
{
LinkList*p=L->next;
while(p!
=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
/*求单链表的长度*/
intListLength(LinkList*L)
{
LinkList*p=L->next;
inti=0;
while(p!
=NULL)
{
i++;
p=p->next;
}
returni;
}
/*查看单链表是否为空*/
boolListEmpty(LinkList*L)
{
returnL->next==NULL;
}
/*求单链表中某个数据元素值*/
boolGetElem(LinkList*L,inti,ElemType&e)
{
LinkList*p=L;
intj=0;
while(p!
=NULL&&j
{
p=p->next;
j++;
}
if(p==NULL)
{
returnfalse;
}
else
{
e=p->data;
returntrue;
}
}
/*在单链表中查找元素*/
intLocateElem(LinkList*L,ElemTypee)
{
LinkList*p=L;
inti=0;
while(p!
=NULL&&p->data!
=e)
{
p=p->next;
i++;
}
if(p==NULL)
{
return0;
}
else
{
returni;
}
}
/*删除单链表中第i个元素*/
boolListDelete(LinkList*&L,inti,ElemType&e)
{
intj=0;
LinkList*p=L,*q;
while(p!
=NULL&&j{
p=p->next;
j++;
}
if(p==NULL)
returnfalse;
else
{
q=p->next;
if(q==NULL)
returnfalse;
e=q->data;
p->next=q->next;
free(q);
returntrue;
}
}
/*删除单链表*/
voidDestroyList(LinkList*&L)
{
LinkList*p=L;
LinkList*q=p->next;
while(q!
=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
voidCreateListR(LinkList*&L,ElemTypee[],intn)
{
InitList(L);
inti;
for(i=0;i{
if(!
LocateElem(L,e[i]))
ListInsert(L,i+1,e[i]);
}
}
voidInsterSect(LinkList*a,LinkList*b,LinkList*&c)
{
DestroyList(c);
InitList(c);
LinkList*p=a->next;
inti=0;
while(p!
=NULL)
{
if(LocateElem(b,p->data))
ListInsert(c,++i,p->data);
p=p->next;
}
}
voidSubs(LinkList*a,LinkList*b,LinkList*&c)
{
DestroyList(c);
InitList(c);
LinkList*p=a->next;
inti=0;
while(p!
=NULL)
{
if(!
LocateElem(b,p->data))
ListInsert(c,++i,p->data);
p=p->next;
}
}
voidUnion(LinkList*a,LinkList*b,LinkList*&c)
{
InitList(c);
LinkList*p=a->next;
LinkList*q=b->next;
intk=0;
while(p!
=NULL&&q!
=NULL)
{
if(p->datadata)
{
ListInsert(c,k+1,p->data);
p=p->next;
k++;
}
elseif(p->data==q->data)
{
ListInsert(c,k+1,p->data);
p=p->next;
q=q->next;
k++;
}
else
{
ListInsert(c,k+1,q->data);
q=q->next;
k++;
}
}
while(p!
=NULL)
{
ListInsert(c,k+1,p->data);
p=p->next;
k++;
}
while(q!
=NULL)
{
ListInsert(c,k+1,q->data);
q=q->next;
k++;
}
///cout<<"hehe"<}
voidsort(LinkList*&L)
{
LinkList*p,*pre,*q,*k;
InitList(p);
inti=0;
charc;
while(!
ListEmpty(L))
{
pre=L->next;
c=pre->data;
while(pre!
=NULL)
{
if(c>=pre->data)
c=pre->data;
pre=pre->next;
}
ListInsert(p,++i,c);
inttag=LocateElem(L,c);
ListDelete(L,tag,c);
}
L=p;
}
intmain()
{
LinkList*ha,*hb,*hc;
ElemTypea[]={'c','a','e','h'};
ElemTypeb[]={'f','h','b','g','d','a'};
printf("集合的运算如下\n");
CreateListR(ha,a,4);
CreateListR(hb,b,6);
printf("原集合A:
");DispList(ha);
printf("原集合B:
");DispList(hb);
sort(ha);
sort(hb);
printf("有序集合A:
");DispList(ha);
printf("有序集合B:
");DispList(hb);
Union(ha,hb,hc);
printf("集合的并