集合 ADT

1. 集合的定义

和数学上的集合类似，集合是一种由不重复元素组成的全体。

同样地，集合也具有以下特性：

确定性：给定一个集合，集合中的元素是确定的。即一个元素，或者属于该集合，或者不属于该集合。
无序性：在一个集合中，不考虑元素之间的顺序，只要元素完全相同，就认为是同一个集合。
互异性：集合中任意两个元素都是不同的。

而且，由于计算机的有限性，一般意义的集合中元素的数量也是有限的。本文不会讨论基于符号的集合表示，你可以参考 SymPy 的 Set 细节在新窗口打开来研究符号意义的集合表示。

数据结构上的集合存在一些变体，这些变体将在下面进行讲解。

多集（multiset）：允许重复元素的集合，也称为包（bag）。
有序集（ordered set）：元素有序的集合。注意这和数学上的 偏序集（poset）不是一种概念。^[1]
位集（bitset）：以紧凑形式存储位集合。

2. 集合 ADT

我们先讨论最基本的集合，它是使用哈希表实现的，因此它的元素是无序的。

我们期望的集合 ADT 应该具有以下方法或属性：

操作	描述	运行时间
`add(e)`	向集合添加一个新元素 `e`	$\mathcal{O}(1)$
`remove(e)`	从集合中移除元素 `e`	$\mathcal{O}(1)$
`contains(e)`	判断集合中是否包含元素 `e`	$\mathcal{O}(1)$
`size()`	返回集合的大小	$\mathcal{O}(1)$

还有一些可选的操作：

操作	描述	运行时间
`discard(e)`	从集合中移除元素 `e`，如果不存在则不做任何操作	$\mathcal{O}(1)$
`clear()`	清空集合
`pop()`	随机移除并返回一个元素	$\mathcal{O}(1)$
`is_empty()`	判断集合是否为空	$\mathcal{O}(1)$
`iter()`	返回集合的迭代器	$\mathcal{O}(1)$
`equal(s)`	判断集合是否与集合 `s` 相等
`union(s)`	返回集合与集合 `s` 的并集
`intersect(s)`	返回集合与集合 `s` 的交集
`difference(s)`	返回集合与集合 `s` 的差集
`issubset(s)`	判断集合是否是集合 `s` 的子集
`issuperset(s)`	判断集合是否是集合 `s` 的超集

偏序关系，维基百科，https://zh.wikipedia.org/wiki/偏序关系在新窗口打开 ↩︎