集合的并交差运算.doc

《数 据 结 构》 课程设计说明书 题 目 集合的并交差运算 姓 名 指导教师 康懿 日 期 2015年7月2日 内蒙古科技大学课程设计任务书 课程名称 数据结构课程设计 设计题目 集合的并交差运算1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。运算1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用. 设计完成后提交课程设计报告资料查阅与讨论1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。数据结构:用面向对象方法与C++语言描述?清华大学出版社 2007 目录 目录 3 第1章 需求分析 4 第2章 总体设计 4 第3章 抽象数据类型定义 5 3.1 LinkList抽象数据类型的设计 5 3.2 集合抽象数据类型的设计 5 第4章 详细设计 5 4.1 工程视图 5 4.2 类图视图 6 4.3 主要算法的详细设计 6 4.3.1 插入算法的详细设计 7 4.3.2 清除算法的详细设计 7 4.3.3 求交集算法的详细设计 7 4.3.4 求并集算法的详细设计 8 4.3.5 求差集算法的详细设计 9 第5章 测试 9 第6章 总结 11 附录：程序代码 11  需求分析 1、? 本演示程序中，集合的元素限定为小写字母字符[“a”…”z”]。集合输入的形式为一个以“0“为结束标志的字符串，串中字符顺序不限。 2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。 3、? 程序执行的命令包括： 1）?构造集合A；2）构造在集合B；3）删除集合A内的元素；4）删除集合B内的元素；5） 在集合A中插入元素；6）在集合B中插入元素；7）求AB集合的并集；8)求AB集合的交集；9）求AB及BA的差集 总体设计 总体设计框架图，如图2.1所示： 图2.1 总体设计框架  抽象数据类型定义 定义格式如下： LinkList抽象数据类型的设计 ADT LinkList 基本操作： InitList(LinkList *L) 构造一个空的线性表L DestroyList(LinkList *L) 初始条件：线性表L已存在 ListEmpty(LinkList L) 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE Status ListInsert(LinkList L,int i,ElemType e） 在带头结点的单链线性表L中第i个位置之前插入元素e ListPrint(LinkList L) 依次输出链表中的元素 集合抽象数据类型的设计 typedef struct LNode { char data; struct LNode *next; }LNode, *LinkList; 详细设计 工程视图 图4.1 工程视图 类图视图 图4.2 类图视图 主要算法的详细设计 插入算法的详细设计 void ListSort(LinkList L) { LinkList first; /*为原链表剩下用于直接插入排序的节点头指针*/ LinkList t; /*临时指针变量：插入节点*/ LinkList p; /*临时指针变量*/ LinkList q; /*临时指针变量*/ first = L-next; /*原链表剩下用于直接插入排序的节点链表*/ L-next = NULL; /*只含有一个节点的链表的有序链表。*/ while (first != NULL) /*遍历剩下无序的链表*/ { /*插入排序*/ for (t = first, q = L; ((q!=NULL) (q-data t-data)); p=