数据结构集合运算.docx
- 文档编号:16882485
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:18
- 大小:39.84KB
数据结构集合运算.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->elem 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年月日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 集合 运算