数据结构集合运算.docxVIP

合肥工业大学软件学院设计题目：集合运算 合肥工业大学软件学院 设计题目：集合运算 学生姓名： 专业：软件工程 班级： 学号： 指导老师： 完成日期： 数据结构课程设计报告 数据结构与算法课程设计 需求和规格说明 问题描述： 设有两个用单链表表示的集合A、B，其元素类型是int且以非递减方式存储，其头结点分别为a、b。要求下面各问题中的结果集合同样以非递减方式存储，结果集合不影响原集合。 实现要求： ⑴ 编写集合元素测试函数IN_SET，如果元素已经在集合中返回0，否则返回1； ⑵ 编写集合元素输入并插入到单链表中的函数INSERT_SET，保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中； ⑶ 编写集合元素输出函数，对建立的集合链表按非递增方式输出； ⑷ 编写求集合A、B的交C=A∩B的函数，并输出集合C的元素； ⑸ 编写求集合A、B的并D=A∪B的函数，并输出集合D的元素； ⑹ 求集合A与B的对称差E=(A-B)∪(B-A) 的函数，并输出集合D的元素； ⑺ 设计一个菜单，具有输入集合元素、求集合A、B的交C、求集合A、B的并D、求集合A与B的对称差E、退出等基本的功能。 测试数据：由读者自定，但集合A、B的元素个数不得少于16个。 二、设计 存储结构 链表 操作函数 void creatlist ();创建集合 void increaseArray ();递增排序 void decreaseArray ();递减排序 void showArray ();输出集合 void AandB ( list a , list b);交运算 void AorB ( list a , list b );并运算 void AaddB ( list a , list b);和运算 void AsubtractB( list a , list b );集合减运算 void symmetricDifference ( list a , list b );对称差运算 void AequalB ( list a );复制 void INSERT_SET ( );递增储存 void DECREASESHOW( );递减输出 int IN_SET ( int i );检测是否在集合中，并返回值 用户手册 首先先建立两个做实验的集合A和B 自动显示你所建的集合 进入选择界面，选择你想要用的功能（数字表示） 执行功能，输出结果 自动退出程序 调试与测试 分别展示六个功能 1. 2. 3. 4. 5. 6. 复杂度分析 做的时候没有考虑复杂度问题，主要就是求交集的时候先排序再求交还是先求交集在排序的问题，如果代码是顺序的，可以让求交集这个操作复杂度变成了o(m + n);比先求交在排序复杂度低很多。而且做课题时并没有把复杂度加入代码的考虑之中 附录 主要为三个文件，目录是控制台（汗。。。。。用switch-case做的） list.h struct node { node *next; int data; }; class list { public: list (); int length () const; ~list (); int get_element (const int i) const; void insert (const int i,const int x); void delete_element (const int i); void creatlist (); void increaseArray (); void decreaseArray (); void showArray (); node *gethead () { return head; } void AandB ( list a , list b); void AorB ( list a , list b ); void AaddB ( list a , list b); void AsubtractB( list a , list b ); void symmetricDifference ( list a , list b ); void AequalB ( list a ); void INSERT_SET ( ); void DECREASESHOW( ); int IN_SET ( int i ); private: int count; node *head; }; list.cpp #includelis