集合的并交差运算

1《数据结构》课程设计说明书题目集合的并交差运算学号姓名指导教师康懿日期2015年7月2日2内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目集合的并交差运算指导教师康懿时间2013年秋学期第15周至第19周一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。集合的并交差运算以链表存储集合，在此基础上完成对集合的操作。要求设计类（或类模板）来描述集合，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：输入、输出集合查询集合中的元素在集合中进行插入、删除元素实现集合的并、交、差运算并设计主函数测试该类。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社20073目录目录............................................................................................................................................................................3第1章需求分析......................................................................................................................................................4第2章总体设计......................................................................................................................................................4第3章抽象数据类型定义......................................................................................................................................53.1LinkList抽象数据类型的设计....................................................................................................................53.2集合抽象数据类型的设计.........................................................................................................................5第4章详细设计......................................................................................................................................................54.1工程视图.....................................................................................................................................................54.2类图视图.....................................................................................................................................................64.3主要算法的详细设计.................................................................................................................................64.3.1插入算法的详细设计......................................................................................................................74.3.2清除算法的详细设计......................................................................................................................74.3.3求交集算法的详细设计..................................................................................................................74.3.4求并集算法的详细设计..................................................................................................................84.3.5求差集算法的详细设计..................................................................................................................9第5章测试..............................................................................................................................................................9第6章总结............................................................................................................................................................11附录：程序代码......................................................................................................................................................114第1章需求分析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章总体设计总体设计框架图，如图2.1所示：图2.1总体设计框架开始输入A集合输入B集合删除添加添加删除A∩BA∪BA-BB-A5第3章抽象数据类型定义定义格式如下：3.1LinkList抽象数据类型的设计ADTLinkList基本操作：InitList(LinkList*L)构造一个空的线性表LDestroyList(LinkList*L)初始条件：线性表L已存在ListEmpty(LinkListL)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSEStatusListInsert(LinkListL,inti,ElemTypee）在带头结点的单链线性表L中第i个位置之前插入元素eListPrint(LinkListL)依次输出链表中的元素3.2集合抽象数据类型的设计typedefstructLNode{chardata;structLNode*next;}LNode,*LinkList;第4章详细设计4.1工程视图6图4.1工程视图4.2类图视图图4.2类图视图4.3主要算法的详细设计74.3.1插入算法的详细设计voidListSort(LinkListL){LinkListfirst;/*为原链表剩下用于直接插入排序的节点头指针*/LinkListt;/*临时指针变量：插入节点*/LinkListp;/*临时指针变量*/LinkListq;/*临时指针变量*/first=L-next;/*原链表剩下用于直接插入排序的节点链表*/L-next=NULL;/*只含有一个节点的链表的有序链表。*/while(first!=NULL)/*遍历剩下无序的链表*/{/*插入排序*/for(t=first,q=L;((q!=NULL)&&(q-datat-data));p=q,q=q-next);/*无序节点在有序链表中找插入的位置*//*退出for循环，就是找到了插入的位置*/first=first-next;/*无序链表中的节点离开，以便它插入到有序链表中。*/if(q==L)L=t;/*插在第一个节点之前*/elsep-next=t;/*p是q的前驱*/t-next=q;/*完成插入动作*/}4.3.2清除算法的详细设计voidqingchu(LinkListLa)/*清除链表中相同的元素*/{chari,j;LinkListp,q;La-next;p=La;q=p-next;while(q){i=p-data;j=q-data;if(i==j){q=p-next;/*删除并释放结点*/p-next=q-next;free(q);}p=p-next;q=p-next;}}4.3.3求交集算法的详细设计voidJiaoji(LinkListLa,LinkListLb,LinkListLc){/*求两集合的交集，将结果存入另