数据结构集合运算.docx

数据结构集合运算.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年月日