数据结构试验报告-集合的交并差.docx

文档介绍：实验报告: 集合的交并差运算题目:编写一个演示集合的交并差运算的计算机程序一、需求分析 1. 本次实验中要求输入的集合的元素类型为小写字母 a到z, 集合输入结束的标志是一“回车符”为标志的, 集合的输入不限字符输入的顺序且允许重复输入和输入非法字符; 2. 本次实验中输出的集合中不包含重复的元素, 集合中的元素按 ASCII 从小到大排列输出且将自动过滤输入的非法字符; 3. 本次实验的程序可以计算用户输入的两个集合的交集、并集和补集; 4. 本次实验的测试数据有: 输入的集合为 Set1= ” magazine ”, Set2= ” paper ”, 输出的集合为 Set1= ” aegimnz ”, Set2= ” aepr ”, 并集为” aegimnprz ”, 交集为” ae”, 差集为” gimnz ”; 输入的集合为 Set1= ” WE056gyh ”, Set2= ” asyE ”, 输出的集合为 Set1= ” ghy ”, Set2= ” asy ”,并集为” aghsy ”,并集为”y”, 差集为” aghs ”。二、概要分析为实现上述程序的功能,用有序链表表示集合。因此,需要有两个抽象数据类型:有序表和集合。 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=2...n} 基本操作: InitList(&L) 操作结果;构造一个空的有序表 L。 DestroyList(&L) 初始条件:有序表 L 已存在。操作结果:销毁有序表 L。 ListLength(L) 初始条件:有序表 L 已存在。操作结果:返回有序表 L 的长度。 ListEmpty(L) 初始条件:有序表 L 已存在。操作结果:若有序表 L 为空表,返回 True ,否则返回 False 。 GetElem(L,i,&e) 初始条件:有序表 L 已存在,若 1<=i<=Length(L) 。操作结果:用 e 返回 L 中第 i 个元素的值。 LocateElem(L,pare()) 初始条件:有序表 L 已存在, compare() 是数据元素判定函数操作结果:返回 L 中第一个与 e pare() 的数据元素的位序。若这样的元素不存在,则返回值为 0。 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 OderedList 2. 集合的抽象数据类型定义: ADT Set{ 数据对象: D={ai|ai 为小写英文字母且互不相同, i=1,2,....,n,0<=n<=26} 数据关系: R1={} 基本操作: CreateSet(&T,Str) 初始条件: Str 为字符串。操作结果:生成一个由 Str 中小写字母构成的集合 T。 DestroySet(&T) 初始条件:集合 T 已存在。操作结果:销毁集合 T 的结构。 Union(&T,S1,S2) 初始条件:集合 S1和 S2 存在。操作结果:生成一个由 S1和 S2 的并集构成的集合 T。 Intersection(&T,S1,S2) 初始条件:集合 S1和 S2 存在。操作结果:生成一个由 S1和 S2 的并集构成的集合 T。 Difference(&T,S1,S2) 初始条件:集合 S1和 S2 存在。操作结果:生成一个由 S1和 S2 的差集构成的集合 T。 PrintSet(T) 初始条件:集合 T 已存在。操作结果:按字母次序顺序显示集合 T 的全部元素。}ADT Set 3. 本程序包含四个模块(1 )主程序模块: void main(){ 初始化; do{ 接受命令; 处理命令; }while( “命令”=“退出”); }(2 )集合单元模块—实现集合的抽象数据类型; (3 )有序表单元模块—实现有序表的抽象数据类型; (4 )结点结构单元模块—定义有序表的结点结构。各模块调用关系: 主程序模块→集合单元模块→有序表单元模块→结点结构单元模块三、详细设计 a) 函数的调用关系图为: b) 具体函数代码为: #define TRUE 1 #define FALSE 0 #define