数据结构 集合运算
- 格式：docx
- 大小：210.63 KB
- 文档页数：16
数据结构课程设计报告
设计题目：集合运算
学生姓名：
专业：软件工程
班级：
学号：
指导老师：
完成日期：
合肥工业大学软件学院 数据结构与算法课程设计
一、 需求和规格说明
问题描述：
设有两个用单链表表示的集合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个。
二、设计
1. 存储结构
链表
2. 操作函数
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 );检测是否在集合中，并返回值
二、 用户手册
1. 首先先建立两个做实验的集合A和B
2. 自动显示你所建的集合
3. 进入选择界面，选择你想要用的功能（数字表示）
4. 执行功能，输出结果
5. 自动退出程序
四、 调试与测试
分别展示六个功能
1.
2.
3.
4.
5.
6.
五、 复杂度分析 做的时候没有考虑复杂度问题，主要就是求交集的时候先排序再求交还是先求交集在排序的问题，如果代码是顺序的，可以让求交集这个操作复杂度变成了o(m + n);比先求交在排序复杂度低很多。而且做课题时并没有把复杂度加入代码的考虑之中
六、 附录
主要为三个文件，目录是控制台（汗。。。。。用switch-case做的）
1. 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;
};
2. list.cpp
#include"list.h"
#include
using namespace std;
list::list ()
{
head = new node;
head -> next = NULL;
count = 0;
head -> data = 0;
}
int list::length ()const
{
return count;
}
int list::get_element(const int i)const
{
node *p;
p = head -> next;
int j=1;
while ( p != NULL && j != i )
{
p = p -> next;
j ++;
}
if ( p == NULL )
return -1;
else
return p -> data;
}
void list::insert(const int i,const int x)
{
node *p;
p = head -> next;
int j = 0;
while ( p != NULL && j != i - 1)
{
p = p -> next;
j ++;
}
if ( i < 1 || i > count + 1 )
return; else
{
node *s = new node;
s -> data = x;
s -> next = p -> next;
p -> next = s;
count ++;
}
}
void list::delete_element(const int i)
{
node *p = head;
int j = 0;
while ( j != i -1 && p != NULL)
{
p = p -> next;
j ++;
}
if ( i < 1 || i > count )
return;
else
{
node *u = p -> next;
p -> next = u -> next;
delete u;
count --;
}
}
void list::creatlist ()
{
int x;
cout <<" 输º?入¨?数ºy据Y：êo"<< endl;
cin >> x;
node *rear = head;
while ( x != -1)
{
count ++;
node *s = new node;
s -> data = x;
rear -> next = s;
rear = s;
rear -> next = NULL;
cout <<" 输º?入¨?数ºy据Y：êo"<< endl;
cin >> x; }
}
void list::increaseArray ()
{
for ( int i = 1 ; i <= count ;i ++ )
{
node *p = head -> next;
while ( p -> next != NULL)
{
if ( p -> data >= ( p -> next ) -> data)
{
int i = p -> data;
p -> data = ( p -> next ) -> data;
( p -> next ) -> data = i;
}
p = p -> next;
}
}
}
void list::showArray()
{
node *p = head -> next;
while( p != NULL )
{
cout << p -> data <<" ";
p = p -> next;
}
}
list::~list ()
{}
void list::decreaseArray()
{
for ( int i = 1 ; i <= count ;i ++ )
{
node *p = head -> next;
while ( p -> next != NULL)
{
if ( p -> data <= ( p -> next ) -> data)
{
int i = p -> data;
p -> data = ( p -> next ) -> data;
( p -> next ) -> data = i;
}
