# 集合运算
## 课程设计说明书
### 一 需求分析
对于集合交、并、差等运算的实现比较简单。
为了实现不同类型数据的集合运算,需要使用 string类型,string类是STL中封装好的类。在自定义了单链表结构的基础上,使用string而不是自定义字符串结构可以有效避免数据结构的复杂性。但需要对STL中容器操作的使用和原理较为熟悉,才能定义高效实用且符合要求的数据结构。
要求用到数据结构课上学到的线性表的知识,所以就要充分而清晰的理解关于线性表的知识。
要求实现的基本功能有集合的交、并、补、差运算,如果基于链表实现,需要对链表的元素插入、元素删除、链表合并等操作很熟练。而且在此基础上,为了完整实现各功能,还需要熟练掌握链表的其他操作。
这个课题的核心实现集中在对链表的操作上,但除此之外还要设计完好的用户交互界面,这需要熟练掌握语言方面的格式化输入输出。
综上,做这个课题,要具备的知识就是线性表的基本算法,链表的基本操作,必要的C或者C++知识(由于该题的数据结构并不复杂,且核心便是链表,因此我基本采用c语言来实现),以及丰富的程序调适经验。
### 二 概要设计
我将数据结构的定义以及相关算法函数的声明放在头文件set.h中,并将函数的定义以及算法的实现放在cpp文件set.cpp中,而将主函数以及用户交互界面相关控制函数放在main.cpp中。
考虑到该课题的核心便在于链表的各种操作运算,且总体上并不复杂,我基本采用c语言来实现了集合数据结构的构建,为了方便,只适当地使用了部分c++ 特有的特性,因此为cpp文件。
对于集合实现,我使用单链表。对于每一个节点,由data数据域及next指针域组成。为了实现不同类型元素的集合运算,我使用string类型作为数据域的类型,即集合元素的类型。除了将每一个元素和其后继元素的指针封装为一个元素结点 struct 外,我还将链表的头节点、尾节点、链表长度封装为一个集合 struct。从而方便对链表操作。
集合的数据结构定义如下:
```c++
typedef string ElemType;
typedef struct Node {
ElemType data;//数据元素
struct Node* next;//下一个节点的地址
} Node, * PNode; //单个节点的结构体
typedef struct List {
PNode head;//集合的头节点
PNode tail;//集合中的最后一个元素所在节点 int length;//集合中元素的个数
} List, * PList;
```
对于集合各项运算,我基于单链表实现。对于单链表的各运算算法,除了基本的操作外,为了方便后续集合算法的实现,我新增了如链表排序等函数。
各函数原型及其功能、使用说明如下:
```c++
/* 创建集合 */
bool CreateSet(List& L);
/* 创建集合_重载 */
bool CreateSet(List& L, ElemType* s, int length);
/* 销毁集合 */
bool DestroySet(List& L);
/* 并集 */
bool Union(List L1, List L2, List& L3);
/* 交集 */
bool Intersection(List L1, List L2, List& L3);
/* 补集 */
bool Complement(List L1, List L2, List& L3);
/* 差集 */
bool Difference(List L1, List L2, List& L3);
/* 拷贝线性表 */
bool Copy(List L1, List& L2);
/* 求线性表长度 */
bool ListLength(List L, int& index);
/* 初始化线性表 */
bool InitList(List& L);//初始化线性表
/* 销毁线性表 */
bool DestroyList(List& L);//销毁线性表
/* 清空线性表 */
bool ClearList(List& L);//清空线性表
/* 操作: 获取线性表index位置的元素 */ /* L 指向一个已初始化的链表 */
/* index 为查找位置 */
/* e 返回第i个位置元素的值 */
/* 后置条件: 查找成功返回true,查找失败返回false*/
bool GetElem(List L, int index, ElemType& e);//获取线性表index位置的元素
/* 操作: 查找线性表中值为e的元素 */ /* L 指向一个已初始化的链表 */ /* e 为要查找的值 */
/* 后置条件: 查找成功返回元素位置,查找失败返回 0 */
bool LocateElem(List L, ElemType e);//判断e是否在L中, 不在返回false
/* 操作: 添加e到线性表末尾 */
/* L 指向一个已初始化的链表 */ /* e 为要查找的值 */
/* 后置条件: 查找成功返回元素位置,查找失败返回 0 */
bool Append(List& L, ElemType e);//添加e到线性表末尾
/* 操作: 在线性表第i个位置插入元素 */ /* L 指向一个已初始化的链表 */
/* index 为要插入的位置 */
/* e 为要插入的值 */
/* 后置条件: 插入成功返回true,插入失败返回false*/
bool InsertElem(List& L, int index, ElemType e);//插入e到index位置
/* 操作: 删除线性表中值为e的元素 */ /* L 指向一个已初始化的链表 */
/* e 为要删除的元素值 */
/* 后置条件: 删除成功返回true,删除失败返回false*/
bool removeElem(List& L, ElemType e);//删除线性表中e元素
/* 操作: 删除线性表中第i个元素 */
/* L 指向一个已初始化的链表 */
/* index 为要删除的位置 */
/* 后置条件: 删除成功返回true,删除失败返回false */
bool removeIndex(List& L, int index);//删除线性表中index号元素
/* 操作: 将集合元素排序 */ /* L 指向一个已初始化的集合 */ /* 后置条件: 集合元素递增排列 */ bool sort(List& L);//给线性表排序,默认升序
/* 输出链表 */
bool printList(List L);
/* 操作: 判断集合中元素是否是数字 */ /* L 为需要判断的集合 */
/* 后置条件: 是数字,返回true;否则返回false */
bool isNum(string str);
```
### 详细设计
1)宏定义,定义全局变量、结构体
```
/* 特定程序的声明 */
# define ERROR false
# define OK true
# define TRUE true
# define FALSE false
/* 一般类型定义 */
typedef string ElemType;
typedef struct Node {
ElemType data;//数据元素 struct Node* next;//下一个节点的地址
} Node, * PNode; //单个节点的结构体
typedef struct List {
PNode head;//集合的头节点
PNode tail;//集合中的最后一个元素所在节点 int length;//集合中元素的个数
} List, * PList;
```
2)主函数处理输入的算法如下:
```c++
while (true) {
cout << "\n请选择操作:";
int ch;
cin >> ch;
switch (ch) {
case 1:
Intersection(set1, set2, set3);
cout << set3;
ClearList(set3);
break;//交集 case 2:
Union(set1, set2, set3);
cout << set3;
ClearList(set3);
break;//并集 case 3:
Complement(set1, set2, set3);
cout << set3;
ClearList(set3);
break;//!A(AUB为全集) case 4:
Complement(set2, set1, set3);
cout << set3;
ClearList(set3);
break;//!B(AUB为全集)
case 5:
Difference(set1, set2, set3);
cout << set3;
ClearList(set3);
break;//A-B case 6:
Difference(set2, set1, set3);
cout << set3;
ClearList(set3);
break;//B-A case 7:
DestroySet(set1);
DestroySet(set2);
DestroySet(set3);
cout << endl;
goto Lab;//重新输入集合 case 8:
DestroySet(set1);
DestroySet(set2);
DestroySet(set3);
return 0;//退出 default: cout << "操作有误!"; break;
}
}
```
创建集合的算法如下:
```c++
void inputSet(List& set) {
ElemType* deal;
int length;
while (true) {
string str;
cin >> str;
if (str.length() == 2) {
deal = new string[0];
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
对于集合交、并、差等运算的实现比较简单。 为了实现不同类型数据的集合运算,需要使用 string类型,string类是STL中封装好的类。在自定义了单链表结构的基础上,使用string而不是自定义字符串结构可以有效避免数据结构的复杂性。但需要对STL中容器操作的使用和原理较为熟悉,才能定义高效实用且符合要求的数据结构。
资源推荐
资源详情
资源评论
收起资源包目录
100011964-基于C语言实现集合运算.zip (14个子文件)
data-structure
line editor
editor.cpp 6KB
editor.h 2KB
writeme.txt 579B
main.cpp 7KB
readme.txt 2KB
LICENSE 1KB
report
数据结构课设报告_简单行编辑器.pdf 2.66MB
数据结构课设报告_集合运算.pdf 870KB
img.doc-md
1-44dca650d9f696a4dd6e0fdb13d6aeb8.png 81KB
2-6842f43d62f2c542b8f4c10552772245.png 178KB
README.md 12KB
set operation
set.h 3KB
main.cpp 3KB
set.cpp 6KB
共 14 条
- 1
资源评论
神仙别闹
- 粉丝: 2673
- 资源: 7640
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功