数据结构集合运算

数据结构实验报告

姓 名 主讲教师 课程名称 吴科敏 周锦程 学 号 指导教师 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