数据结构集合运算

数据结构实验报告

姓 名 主讲教师 课程名称 吴科敏 周锦程 学 号 指导教师 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='error data'， Set1∪Set2＝'adelnoprt'，Set1∩Set＝'aeort'，Setl－Set2＝'Inp'； 三、概要设计 内容： 二、概要设计 为实现上述程序功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。 （1）有序表的抽象数据类型定义为： ADT OrderedList｛ 数据对象；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已存在。

1

操作结果：返回有序表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（）。 ｝ADT OrderedList （2）集合的抽象数据类型定义为： ADT Set｛ 数据对象：①=（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的全部元素。 ｝ADT Set （3）本程序包含4个模块：

2

1）主程序模块： void main(){ 初始化； do{ 接受命令； 处理命令； }while(“命令”=“退出”)； } 2）集合单元模块——实现集合的抽象数据类型； 3）有序表单元模块——实现有序表的抽象数据类型； 4）结点结构单元模块——定义有序表的结点结构.各模块之间的调用关系如下： 四、详细设计： 程序实现（源程序，注意添加适当的注释） #include #include #include using namespace std; #define ElemType char typedef struct ElemNode { ElemType elem; struct ElemNode *next; }ElemNode, *Set; int LengthOf(Set src);//返回一个集合的长度 void CreateSet(Set dest);//创建一个新的字母集合，限定a-z void EmptySet(Set dest);//清空一个集合，保留头结点 void DestroySet(Set dest);//销毁集合 void SortSet(Set dest);//对一个集合进行从小到大的排序 void DisplaySet(Set src);//打印集合的所有元素 int ExistElem(Set dest, ElemType e);//判断元素是否存在于集合中

3

void DelElem(Set dest, ElemType e);//删除集合中的一个元素一次 void AddElem(Set dest, ElemType e);//在链表尾部追加一个元素 void ContactSet(Set dest, Set src);//连接一个集合到另一个集合 void AddSet(Set dest, Set src1, Set src2);//集合并运算 void MulSet(Set dest, Set src1, Set src2);//集合交运算 void SubSet(Set dest, Set src1, Set src2);//集合差运算 int main() { Set dest=(Set)malloc(sizeof(ElemNode)); Set src1=(Set)malloc(sizeof(ElemNode)); Set src2=(Set)malloc(sizeof(ElemNode)); dest->next=NULL; cout<<\输入两个集合，按回车键结束，第一个集合大于等于第二个集合：\ cout<<\请输入第一个集合，按回车键结束：\ CreateSet(src1); cout<<\请输入第二个集合，按回车键结束：\ CreateSet(src2); cout<错误！重输\ \进入下一步演示\ while(cin>>item) { if(item) switch(item) { case 1: cout<<\集合并运算：Set1∪Set2 = \ AddSet(dest, src1, src2); DisplaySet(dest); EmptySet(dest); cout<

4

} else {cout<<\进入下一步演示...\ } getchar(); cout<<\输入一个集合：\ CreateSet(dest); cout<<\原集合为：\ DisplaySet(dest); cout<>ch; AddElem(dest, ch); DisplaySet(dest); cout<>ch; DelElem(dest, ch); DisplaySet(dest);cout<next=NULL; DisplaySet(p); cout<next!=NULL) { i++;

5

src=src->next; } return i; }//LengthOf void CreateSet(Set dest) { //创建一个新的字母集合，限定a-z ElemType ch; Set p=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 void EmptySet(Set dest) { //清空一个集合，保留头结点 Set p,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 void DestroySet(Set dest) { //销毁集合 EmptySet(dest); free(dest); }//DestroySet void SortSet(Set dest)

6

{ //对一个字母集合进行从小到大的排序 int i,j,l,flag; Set p,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;jelem>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 void DisplaySet(Set src) { //打印集合的所有元素 Set p; if(src->next==NULL) { printf(\φ\ return ; } p=src; do { p=p->next; putchar(p->elem); } while(p->next!=NULL); }//DisplaySet

7

int ExistElem(Set dest, ElemType e) { //判断元素是否存在于集合中 Set p=dest; if(LengthOf(p)==0) return 0; else{ p=p->next; while(p->elem!=e) { if(p->next==NULL) return 0; p=p->next; } return 1; } }//ExistElem void DelElem(Set dest, ElemType e) { //删除集合中的一个元素一次 Set p=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 void AddElem(Set dest, ElemType e) { //在链表尾部追加一个元素 Set p=dest, n;

8

while(p->next!=NULL) p=p->next; n=(Set)malloc(sizeof(ElemNode)); p->next=n; n->elem=e; n->next=NULL; }//AddElem void ContactSet(Set dest, Set src) { //连接一个集合到另一个集合 Set p=dest; while(p->next!=NULL) p=p->next; p->next=src->next; }//ContactSet void AddSet(Set dest, Set src1, Set src2) { //集合并运算 SortSet(src1);SortSet(src2); int i=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2); src1=src1->next;src2=src2->next; while(ielem<=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 {

9

src2=src2->next; } } } while(ielem)) { AddElem(dest, src1->elem); src1=src1->next; } } while(jelem)) { AddElem(dest, src2->elem); src2=src2->next; } } }//AddSet void MulSet(Set dest, Set src1, Set src2) { //集合交运算 SortSet(src1);SortSet(src2); int i=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2); src1=src1->next;src2=src2->next; while(ielemelem) {i++;src1=src1->next;} else if(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 void SubSet(Set dest, Set src1, Set src2)

10

{ //集合差运算 SortSet(src1);SortSet(src2); int i=0,len=LengthOf(src1); src1=src1->next; while(ielem)) { if(!ExistElem(dest, src1->elem)) { AddElem(dest, src1->elem); src1=src1->next; } } else { src1=src1->next; } } } 测试数据：

11

五、教师评语（或成绩）： 教师签字 ：周锦程

2011年 月 日

12

本文来源：https://www.bwwdw.com/article/iek3.html