数据结构集合运算.docx
《数据结构集合运算.docx》由会员分享,可在线阅读,更多相关《数据结构集合运算.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构集合运算
数据结构实验报告
姓名
吴科敏
学号
2009051531
系别
数学系
班级
09信息与计算科学
主讲教师
周锦程
指导教师
周锦程
实验日期
2011、11、5
专业
信息与计算科学
(2)
课程名称
数据结构
同组实验者
一、实验名称
实验一、集合的并、交和差运算
二、需求分析
(1)本演示程序中,集合的元素限定为小写字母字符['a'..'z'],集合的大小n<27。
集合输入的形式为一个以“回车符”为结束标志的字符串,串中的字符顺序不限,且允许出现重复字符或非法字符,程序应能自动滤去。
输出的运算结果字符串中将不含重复字符或非法字符。
(2)演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令;相应的输人数据(滤去输入中的非法字符)和运算结果显示在其后。
(3)程序执行的命令包括:
1)构造集合1;
2)构造集合2;
3)求并集;
4)求交集;
5)求差集;
6)结束。
“构造集合1”和“构造集合2”时,需以字符串的形式键入集合元素。
(4)测试数据
1)Setl='magazine',Set2='paper',
Set1∪Set2='aeglmnprz',Setl∩Set2='ae',Setl-Set2='glmnz‘;
2)Set='012oper4a6hon89',Set2='errordata',
Set1∪Set2='adelnoprt',Set1∩Set='aeort',Setl-Set2='Inp';
三、概要设计
内容:
二、概要设计
为实现上述程序功能,应以有序链表表示集合。
为此,需要两个抽象数据类型:
有序表和集合。
(1)有序表的抽象数据类型定义为:
ADTOrderedList{
数据对象;D={ai|ai∈CharSet,i=1,2,…,n,n≥0}
数据关系:
R1={<ai-1,ai>|ai-1,ai∈D,ai-1<ai,i=1,2,…,n,}
基本操作:
InitList(&i)
操作结果;构造=个空的有序表L。
DestroyList(&L)
初始条件:
有序表L已存在。
操作结果:
销毁有序表L。
ListLength(L)
初始条件:
有序表L已存在。
操作结果:
返回有序表L的长度。
ListEmpty(L)
初始条件:
有序表L已存在。
操作结果:
若有序表L为空表,则返回True,否则返回False。
GetElem(L,pos)
初始条件:
有序表L已存在。
操作结果:
若l≤pos≤Length(),则返回表中第pos个数据元素。
LocateElem(L,e,&q)
初始条件:
有序表L已存在。
操作结果:
若有序表L中存在元素e,则q指示L中第一个值为e的元素的位置,并返回函数值TRUE;否则e指示第一个大于e的元素的前驱的位置,并返回函数值FALSE。
APPend(&L,e)
初始条件:
有序表L已存在。
操作结果:
在有序表L的末尾插入元素e。
InsertAfter(&L,q,e)
初始条件:
有序表L已存在,q指示L中一个元素。
操作结果:
在有序表L中q指示的元素之后插入元素e。
ListTraverse(q,visit())
初始条件:
有序表L已存在,q指示L中一个元素。
操作结果:
依次对L中q指示的元素开始的每个元素调用过程visit()。
}ADTOrderedList
(2)集合的抽象数据类型定义为:
ADTSet{
数据对象:
①=(ai|ai为小写英文字母且互不相同,i=1,2,…,n,0≤n≤26)
数据关系:
R1={}
基本操作:
Createset(&T,Str)
初始条件:
Str为字符串。
操作结果:
生成一个由*中小写字母构成的集合T。
Destroyset(&T)
初始条件:
集合T已存在。
操作结果:
销毁集合T的结构。
Union(t,S1,S2)
初始条件:
集合S1和S2存在。
操作结果:
生成一个由S1和S2的并集构成的集合T。
Intersection(&T,S1,S2)
初始条件:
集合S1和S2存在。
操作结果:
生成一个由a和S2的交集构成的集合T。
Difference(&T,S1,S2)
初始条件:
集合S1和S2存在。
操作结果:
生成一个由S1和S2的差集构成的集合T。
Printset(T)
初始条件:
集合T已存在。
操作结果:
按字母次序顺序显示集合T的全部元素。
}ADTSet
(3)本程序包含4个模块:
1)主程序模块:
voidmain(){
初始化;
do{
接受命令;
处理命令;
}while(“命令”=“退出”);
}
2)集合单元模块——实现集合的抽象数据类型;
3)有序表单元模块——实现有序表的抽象数据类型;
4)结点结构单元模块——定义有序表的结点结构.各模块之间的调用关系如下:
四、详细设计:
程序实现(源程序,注意添加适当的注释)
#include
#include
#include
usingnamespacestd;
#defineElemTypechar
typedefstructElemNode
{
ElemTypeelem;
structElemNode*next;
}ElemNode,*Set;
intLengthOf(Setsrc);//返回一个集合的长度
voidCreateSet(Setdest);//创建一个新的字母集合,限定a-z
voidEmptySet(Setdest);//清空一个集合,保留头结点
voidDestroySet(Setdest);//销毁集合
voidSortSet(Setdest);//对一个集合进行从小到大的排序
voidDisplaySet(Setsrc);//打印集合的所有元素
intExistElem(Setdest,ElemTypee);//判断元素是否存在于集合中
voidDelElem(Setdest,ElemTypee);//删除集合中的一个元素一次
voidAddElem(Setdest,ElemTypee);//在链表尾部追加一个元素
voidContactSet(Setdest,Setsrc);//连接一个集合到另一个集合
voidAddSet(Setdest,Setsrc1,Setsrc2);//集合并运算
voidMulSet(Setdest,Setsrc1,Setsrc2);//集合交运算
voidSubSet(Setdest,Setsrc1,Setsrc2);//集合差运算
intmain()
{
Setdest=(Set)malloc(sizeof(ElemNode));
Setsrc1=(Set)malloc(sizeof(ElemNode));
Setsrc2=(Set)malloc(sizeof(ElemNode));
dest->next=NULL;
cout<<"输入两个集合,按回车键结束,第一个集合大于等于第二个集合:
"<cout<<"请输入第一个集合,按回车键结束:
"<CreateSet(src1);
cout<<"请输入第二个集合,按回车键结束:
"<CreateSet(src2);
cout<cout<<"Set1=";DisplaySet(src1);
cout<<"\t";
cout<<"Set2=";DisplaySet(src2);
cout<intitem;
cout<<"1->集合并"<<""<<"2->集合交"<<""<<"3->集合差"<<""<<"非零整数->错误!
重输"<<""<<"0->进入下一步演示"<while(cin>>item)
{
if(item)
switch(item)
{
case1:
cout<<"集合并运算:
Set1∪Set2=";
AddSet(dest,src1,src2);
DisplaySet(dest);
EmptySet(dest);
cout<case2:
cout<<"集合交运算:
Set1∩Set2=";
MulSet(dest,src1,src2);
DisplaySet(dest);
EmptySet(dest);
cout<case3:
cout<<"集合差运算:
Set1-Set2=";
SubSet(dest,src1,src2);
DisplaySet(dest);
EmptySet(dest);
cout<default:
cout<<"输入错误!
重输!
!
!
"<}
else{cout<<"进入下一步演示..."<}
getchar();
cout<<"输入一个集合:
"<CreateSet(dest);
cout<<"原集合为:
";
DisplaySet(dest);
cout<charch;
cout<<"在链表尾部添加一个元素ch=";
cin>>ch;
AddElem(dest,ch);
DisplaySet(dest);
cout<cout<<"删除集合中的存在的某个元素ch=";cin>>ch;
DelElem(dest,ch);
DisplaySet(dest);cout<cout<<"再创建一个集合src=";
Setsrc=(Set)malloc(sizeof(ElemNode));
getchar();
CreateSet(src);
cout<<"将src集合链接到集合dest中..."<ContactSet(dest,src);
cout<<"此时dest为:
";
DisplaySet(dest);
cout<cout<DisplaySet(dest);
cout<cout<<"dest的补集是:
";
Setp=(Set)malloc(sizeof(ElemNode));
p->next=NULL;
DisplaySet(p);
cout<!
!
"<DestroySet(dest);
return0;
}
intLengthOf(Setsrc)
{
//返回一个集合的长度
inti=0;
while(src->next!
=NULL)
{
i++;
src=src->next;
}
returni;
}//LengthOf
voidCreateSet(Setdest)
{
//创建一个新的字母集合,限定a-z
ElemTypech;
Setp=dest,n;
for(;;)
{
ch=getchar();
if(ch=='\n')break;
if(ch<97||ch>122)continue;
n=(Set)malloc(sizeof(ElemNode));
p->next=n;
n->elem=ch;
n->next=NULL;
p=n;
}
return;
}//CreateSet
voidEmptySet(Setdest)
{
//清空一个集合,保留头结点
Setp,n;
while(dest->next!
=NULL)
{
p=dest;
n=p->next;
for(;n->next!
=NULL;)
{
p=n;
n=n->next;
}
free(n);
p->next=NULL;
}
}//EmptySet
voidDestroySet(Setdest)
{
//销毁集合
EmptySet(dest);
free(dest);
}//DestroySet
voidSortSet(Setdest)
{
//对一个字母集合进行从小到大的排序
inti,j,l,flag;
Setp,q,n;
l=LengthOf(dest);
if(l<2)return;
flag=1;
for(i=l-1;i>0&&flag==1;i--)
{
flag=0;
p=dest;
q=p->next;
n=q->next;
for(j=0;j
{
if(q->elem>n->elem)
{
flag=1;
p->next=n;
q->next=n->next;
n->next=q;
q=p->next;
n=q->next;
}
p=q;
q=n;
n=n->next;
}
}
}//SortSet
voidDisplaySet(Setsrc)
{
//打印集合的所有元素
Setp;
if(src->next==NULL)
{
printf("φ");
return;
}
p=src;
do
{
p=p->next;
putchar(p->elem);
}while(p->next!
=NULL);
}//DisplaySet
intExistElem(Setdest,ElemTypee)
{
//判断元素是否存在于集合中
Setp=dest;
if(LengthOf(p)==0)
return0;
else{
p=p->next;
while(p->elem!
=e)
{
if(p->next==NULL)
return0;
p=p->next;
}
return1;
}
}//ExistElem
voidDelElem(Setdest,ElemTypee)
{
//删除集合中的一个元素一次
Setp=dest,q;
if(LengthOf(p)==0)
return;
q=p->next;
if(LengthOf(p)==1)
{
p->next=NULL;
free(q);
}
while(q->elem!
=e)
{
p=p->next;
q=q->next;
}
if(q->next==NULL)
{
p->next=NULL;
free(q);
}
else
p->next=q->next;
}//DelElem
voidAddElem(Setdest,ElemTypee)
{
//在链表尾部追加一个元素
Setp=dest,n;
while(p->next!
=NULL)
p=p->next;
n=(Set)malloc(sizeof(ElemNode));
p->next=n;
n->elem=e;
n->next=NULL;
}//AddElem
voidContactSet(Setdest,Setsrc)
{
//连接一个集合到另一个集合
Setp=dest;
while(p->next!
=NULL)
p=p->next;
p->next=src->next;
}//ContactSet
voidAddSet(Setdest,Setsrc1,Setsrc2)
{
//集合并运算
SortSet(src1);SortSet(src2);
inti=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2);
src1=src1->next;src2=src2->next;
while(i{
if(src1->elem<=src2->elem)
{
i++;
if(!
ExistElem(dest,src1->elem))
{
AddElem(dest,src1->elem);
src1=src1->next;
}
else
{
src1=src1->next;
}
}
else
{
j++;
if(!
ExistElem(dest,src2->elem))
{
AddElem(dest,src2->elem);
src2=src2->next;
}
else
{
src2=src2->next;
}
}
}
while(i{
i++;
if(!
ExistElem(dest,src1->elem))
{
AddElem(dest,src1->elem);
src1=src1->next;
}
}
while(j{
j++;
if(!
ExistElem(dest,src2->elem))
{
AddElem(dest,src2->elem);
src2=src2->next;
}
}
}//AddSet
voidMulSet(Setdest,Setsrc1,Setsrc2)
{
//集合交运算
SortSet(src1);SortSet(src2);
inti=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2);
src1=src1->next;src2=src2->next;
while(i{
if(src1->elemelem){i++;src1=src1->next;}
elseif(src1->elem>src2->elem){j++;src2=src2->next;}
else
{
i++;j++;
if(!
ExistElem(dest,src1->elem))
{
AddElem(dest,src1->elem);
src1=src1->next;
src2=src2->next;
}
}
}
}//MulSet
voidSubSet(Setdest,Setsrc1,Setsrc2)
{
//集合差运算
SortSet(src1);SortSet(src2);
inti=0,len=LengthOf(src1);
src1=src1->next;
while(i{
i++;
if(!
ExistElem(src2,src1->elem))
{
if(!
ExistElem(dest,src1->elem))
{
AddElem(dest,src1->elem);
src1=src1->next;
}
}
else
{
src1=src1->next;
}
}
}
测试数据:
五、教师评语(或成绩):
教师签字:
周锦程 2011年月日