集合的定义
昨天我们聊了 数据结构的由来与分类 ，根据数据之间关系的不同，我们把数据结构分为了四类逻辑结构，其中第一类就是集合结构。今天我们就来详细的讲一下集合结构。
集合是数据逻辑结构中的一种，它是由一个或者多个没有任何关系的数据元素聚集而成，集合中各个数据元素之间不存在任何逻辑依赖关系。跟数学中的集合一样，集合中不会有相同的数据元素。
下图可是个集合示意图(各个美女都处在同一个篮子里，但是他们之间没有任何关系哦)，你get到了吗？
集合的抽象数据类型
要想从与语言无关的层次描述集合，那就是抽象数据类型，抽象数据类型包括数据和操作两部分，数据部分为集合，可以用任何一种存储方式存储，比如昨天讲的顺序存储结构和链式存储结构，这两种存储结构我们都会讲到。操作部分是对集合的各种运算，包括插入元素、删除元素、查找元素等等。
集合的抽象数据类型定义如下：
ADT Set is
Data:
采用任何一种存储方法存储的一个集合
Operation:
initSet() //初始化集合
add(obj)//添加元素
remove(obj)//删除元素
find(obj)//查找元素并返回
value(i)//返回集合中第i个元素的值
contains(obj)//集合中是否包含某个元素
size()//获取集合的长度
isEmpty//判断集合是否为空
clear()//清空集合
output()//输出集合中的所有值
union(set)//求两个集合的并集
intersection(set) //求两个集合的交集
集合的顺序存储结构和操作实现
集合的顺序存储要求地址空间是连续的，地址必须一个接一个，不能中断。如下图为顺序存储结构：
顺序存储结构
顺序存储的每个节点只包含数据部分，不需要额外包含数据之间的关系，因为数据之间的关系通过地址连续来体现，所以非常省空间(这点好处对于集合来说无所谓，因为集合元素之间没有关系，所以集合之间的元素可以随便放入顺序存储结构中。但是对于有序的线性结构来说就有好处了，线性表后面说。)
它的优点访问非常快速，因为地址是连续的，只要知道首地址，任意一个元素的地址都可以算出来。假设每个地址占c个空间,则第i个地址为(i-1)*c。
它的缺点是在插入和删除数据时，可能要移动许多数据,比如一个10000个元素的有序数据，如果我删除了第二个元素，为了继续保持地址连续，所以要把后面9999个元素都向前移动。
但是对于集合来说，插入和删除不需要移动很多元素，只要移动一个元素就行了，因为集合本就是无序的，假入我删除了10000个元素的第二个元素，为了保持地址连续，我只要把最后一个元素移动到已删除的第二个元素的位置上就行了。
我用Java实现集合的顺序存储结构，根据上面的抽象数据类型的操作，首先定义一个接口Set,包含集合的各种操作，然后让子类实现该接口，覆写各种操作方法，并且子类用数组来存储数据部分
Set接口
集合的顺序存储结和构操作实现如下图代码,详细说明都在注释里面
SequenceSet类
其中对于插入、删除、查找元素、contains、输出集合的每个元素等操作都是O(n)的时间复杂度,
对于获取第i个元素、初始化集合、获取集合长度、集合判空、清空集合的时间复杂度都是O(1)的。
对于求并集和交集的时间复杂度都是O(m*n)，m、n分别代表两个集合的长度。
测试类：
马上就要凌晨一点半了！！！明天还要上班！一不小心就写了两三个小时了，别看内容不多，代码可都是一个个码的，码完经过测试才敢发出来，今晚就聊到这里了，集合的顺序存储结构比较简单，明天接着聊集合的链式存储结构，欢迎大家吐槽关注，谢谢
网友评论