前面讲了 '' 谈谈数据结构之集合的顺序存储 '', 今天接着讲集合的链式存储,链式存储不像顺序存储要求存储的地址空间是连续的,链式存储的地址空间是任意的.但是所有任意的地址空间必须可以串联起来,不能中断,只要某一个地址没有被串联,那么,它后面的数据也就丢失了.链式存储的示意图如下:
链式存储结构图
其中每个节点的地址是任意的,每个节点包含两部分:数据部分和指向下一节点地址的指针.
相比于顺序存储,它需要更多的空间, 因为每个节点除了保存数据外,还需要保存一个代表元素之间关系的下一节点地址的指针.
它的优点是,插入和删除元素不需要移动元素,只需改变指针的指向关系就可以了,比如删除上图中的 a2 节点,则只需把 a1 的指针指向 a3 即可.所以时间复杂度是 O(1),而顺序存储由于要移动元素,时间复杂度是 O(n).
它的缺点是,访问元素必须重头开始遍历,比顺序存储慢.比如要访问 a7, 则必须从 a1 遍历到 a7 才行.所以时间复制度是 O(n),而顺序存储只需要通过下标即可访问,所以时间复杂度是 O(1).
集合的抽象数据类型之前讲了,'' 谈谈数据结构之集合的顺序存储 ''
如下:
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) // 求两个集合的交集
同样的,我用 Java 把集合的链式存和操作进行了实现,比之前的顺序存储实现,稍微难度难了那么一点点,但是总体来说还是比较简单的.
先看链表的节点类型, 上面讲了它包含两部分,数据和指向下一节点的指针
节点类型代码
接着看看链表的非操作部分, 一个是代表集合长度的 len,和链表的头指针,以及集合的初始化, 集合链表实现了上篇文章讲的 Set 接口, Set 接口包含了集合的所有操作.
链表的初始化
下面是具体的操作部分:
新增操作
首先进行集合中是否包含新增元素的校验, 因为集合不能出现重复元素, 时间复杂度为 O(n).不包含则新增. 集合长度加一,所以新增的时间复杂度为 O(n).
新增操作代码
删除操作
首先要找到删除节点的位置, 要从头结点开始遍历,所以时间复制度为 O(n),没找到则返回 false.如果找到删除位置后,则用删除节点的下一节点的指针替换删除节点的指针,集合长度减一.所以整体时间复杂度 O(n)
删除操作代码
查找操作
直接从头结点开始遍历,找到则返回该节点的值,否则返回 null,时间复杂度 O(n)
查找操作代码
获取第 i 个元素操作
i 从 0 开始,也需要从头结点遍历, 找到第 i 个元素后,获取该节点的值.时间复杂度为 O(n)
获取第 i 个元素代码
判断元素是否存在于集合操作
首先也得从头结点开始遍历,判断是否等于每个节点的值,如果相等,则存在
判断元素是否存在于集合代码
清空集合操作
直接把集合长度设置为 0,然后头指针指向 null,所以时间复杂度为 O(1)
清空集合代码
集合判空操作
直接判断 len 是否等于 0 来实现, 时间复杂度 O(1)
集合判空代码
集合输出操作
直接从头开始遍历输出,时间复杂度 O(n)
集合输出代码
获取集合长度操作
直接返回 len 的值即可,时间复杂度 O(1)
获取集合长度
求两个集合的并集操作
求并集, 即求两个集合的非共同元素, 即求只包含于 A 集合, 但不包含于 B 集合或者只包含于 B 集合, 但不包含与 A 集合的元素.
首先值循环遍历本集合 A 的每个元素赋值给目标集合并集 des(时间复杂度 O(n)),然后遍历 B 集合 set1 得到每个元素 (遍历 m 次, 时间复杂度 O(m)), 如果不包含与 A 集合,则添加该元素到并集中 (contains 需要遍历 A, 时间复杂度 O(n)).所以整的时间复杂度为 O(m*n),m,n 分别为两个集合的长度
求两个集合并集代码
求两个集合交集操作
求交集, 即求两个集合的共有元素, 即既存在于 A 集合,,也存在于 B 集合的元素.
首先循环遍历一个集合 (循环 n 次, n 为 A 集合的长度), 判断是否存在于另外一个集合(contains 时间复杂度为 o(m),m 为 B 集合的长度), 如果存在则添加到交集中, 整体时间复杂度为 O(m*n).
求两个集合交集代码
好了,到现在,对集合的说明以及它的顺序存储实现和链式存储实现都讲完了,整的花了大概四五个小时的时间写代码和调试,三四个小时在简书写博文,但是乐在其中,后面接着聊另外一种比较重要和常见的数据结构线性表.欢迎大家关注吐槽,谢谢.
下面附上所有的代码和调试代码
链式集合完整代码
测试代码
来源: http://www.jianshu.com/p/5a6e4640b3a5