数据结构/集合

数据结构
介绍 - 渐进符号 - 数组 - 列表结构 & 迭代器
栈 & 队列 - 树 - 最小堆 & 最大堆 - 图
哈希表 - 集合 - 权衡

集合在软件应用程序中是一个有用的工具，就像在数学中一样，类似的抽象对象被聚合到集合中。一个数学集合有一个相当简单的接口，可以用许多不同的方式实现。

Set<item-type> ADT

contains(test-item:item-type):Boolean

如果 test-item 包含在集合中，则返回 True。

insert(new-item:item-type)

将 new-item 添加到集合中。

remove(item:item-type)

从集合中删除 item。如果 item 不在集合中，则此方法不做任何操作。

remove(item-iter:List Iterator<item-type>)

从集合中删除 item-iter 所指向的项目。

get-begin():List Iterator<item-type>

允许迭代集合中的元素。

get-end():List Iterator<item-type>

也允许迭代集合中的元素。

union(other:Set<item-type>):Set<item-type>

返回一个包含此集合或 other 集合中所有元素的集合。具有默认实现。

intersect(other:Set<item-type>):Set<item-type>

返回一个包含此集合和 other 集合中所有元素的集合。具有默认实现。

subtract(other:Set<item-type>):Set<item-type>

返回一个包含此集合中所有元素但 other 集合中没有的元素的集合。具有默认实现。

is-empty():Boolean

如果不再有项目可以弹出，并且没有顶端项目，则返回 True。

get-size():Integer

返回集合中的元素数量。

所有操作都可以在 $O(N)$ 时间内完成。

列表实现

实现集合的方法有很多。最简单但通常效率最低的方法是创建一个线性列表（数组、链表或类似结构），其中包含集合中的每个元素。对于最基本的操作，测试成员资格，可能的实现可能如下所示

function contains(List<T> list, T member)
    for item in list
        if item == member
            return True
    return False

要向此集合添加新成员，只需将元素添加到列表的开头或结尾。（如果进行检查以确保没有重复元素，则某些其他操作可能更简单。）其他操作也可以类似地根据简单的列表操作来实现。不幸的是，成员资格测试的 worst-case 运行时间为 $O(n)$，如果该项目不在列表中，甚至平均情况下也需要相同的时间，假设该项目在列表中的任何位置的可能性都相同。如果集合很小，或者如果频繁访问的项目可以放置在列表的前端，这可能是一个有效的解决方案，但其他选项可能具有更快的运行时间。

假设元素可以排序，并且插入和删除很少，则保证按排序顺序且没有重复元素的列表可以更高效。使用排序列表，成员资格测试的效率可以达到 $O(logn)$ 的级别。此外，并集、交集和差集可以在线性时间内实现，而对于无序列表，则需要二次时间。

位数组实现

对于某些数据，维护一个描述集合内容的位数组可能更实用。在此表示中，每个问题域元素都对应一个 1 或 0，指定该对象是否为集合的元素。对于一个简单的案例，假设只有从 0 到 n 的整数可以是集合的成员，其中 n 预先已知。这可以用长度为 n+1 的位数组来表示。contains 操作很简单

function contains(BitArray array, Int member)
    if member >= length(array)
       return False
    else if array[member] == 1
       return True
    else
       return False

要向这种类型的集合中添加或删除元素，只需修改位数组以反映该索引应该是 1 还是 0。成员资格在正好 $O(1)$（常数）时间内运行，但它的域受到严重限制。可以移动域，从 m 到 n 步长为 k，而不是如上所述从 0 到 n 步长为 1，但这里没有太多灵活性。然而，对于正确的域，这通常是最有效的解决方案。

位数组是存储布尔变量集合的有效结构。一个例子是启用应用程序各种运行时行为的命令行选项集。C 和类似语言提供位运算符，允许程序员在单个机器指令中访问位字段，而数组访问通常需要两个或三个指令，包括内存读取操作。一个功能齐全的位集实现包括用于计算集合并集、集合交集、集合差集和元素值的运算符。

关联数组实现

关联数组——即哈希表和二叉搜索树，代表了一种重量级但通用的集合表示。二叉树通常具有 $O(logn)$ 时间实现，用于查找和修改特定键，哈希表具有 $O(1)$ 实现（尽管有一个更高的常数因子）。此外，它们能够存储几乎任何类型的键。成员资格测试很简单：只需测试潜在的集合成员是否作为关联数组中的键存在。要添加元素，只需将集合成员作为关联数组中的键添加，并使用一个虚拟值。在优化的实现中，可以使用专门的哈希表或二叉树，而不是重用现有的关联数组实现，这些哈希表或二叉树不存储与键相对应的值。在这里，值没有意义，它们占用了一部分额外的内存空间。

数据结构
介绍 - 渐进符号 - 数组 - 列表结构 & 迭代器
栈 & 队列 - 树 - 最小堆 & 最大堆 - 图
哈希表 - 集合 - 权衡