文档介绍：数据结构课程设计系别电子信息系专业计算机科学与技术班级学号 4090104 姓名植昊指导教师党群成绩 2011 年 7月 14日一、需求分析 1 .本演示程序中,集合的元素限定为小写字母字符[‘a’..’z’] ,集合的大小 n<27 。集合输入的形式为一个以“回车符”为结束标志的字符串, 串中字符顺序不限, 且允许出现重复字符或非法字符,程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。 2 .演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后, 由用户在键盘上输入演示程序中规定的运算命令;相应的输入数据(滤去输入中非法字符) 和运算结果显示在其后。 3 .程序执行的命令包括: 1 )构造集合 1;2 )构造集合 2;3 )求并集; 4 )求交集; 5 )求差集; 6 )结束。“构造集合 1”和“构造集合 2”时,需以字符串的形式键入集合元素。 4 .测试数据(1) Set1= ” magazine ”, Set2= ” paper ”, Set1? Set2= ” aegimnprz ”, Set1? Set2= ” ae”, Set1-Set2= ” gimnz ”; (2) Set1= ” 012oper4a6tion89 ”, Set2= ” error data ”, Set1? Set2= ” adeinoprt ”, Set1? Set2= ” aeort ”, Set1-Set2= ” inp ”。二、概要设计为实现上述程序功能, 应以有序链表表示集合。为此, 需要两个抽象数据类型: 有序表和集合。 1 .有序表的抽象数据类型定义为: ADT OrderedList{ 数据对象: D= { | , 1, 2, , , 0 i i a a CharSet i n n ? ???} 数据关系: R1 ={ 1 1 1 , | , , , 1, 2, , i i i i i i a a a a D a a i n ? ? ?? ?????} 基本操作: InitList(&L) 操作结果:构造一个空的有序表 L。 DestroyList(&L) 初始条件:有序表 L 已存在。操作结果:销毁有序表 L。 ListLength(L) 初始条件:有序表 L 已存在。操作结果:返回有序表 L 的长度。 ListEmpty(L) 初始条件:有序表 L 已存在。操作结果:若有序表 L 为空表,则返回 True ,否则返回 False 。 GetElem(L , pos) 初始条件:有序表 L 已存在。操作结果:若 1 ( ) pos Length L ? ?,则返回表中第 pos 个数据元素。 LocateElem(L ,e, &q) 初始条件:有序表 L 已存在。操作结果: 若有序表 L 中存在元素 e,则q 指示 L 中第一个值为 e 的元素的位置,并返回函数值 True ;否则 q 指示第一个大于 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{ 数据对象: D= {ia |ia 为小写英文字母且互不相同, 1, 2, , i n ??, 0 26 n ? ?} 数据关系: 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