C语言 - 如何实现Set数据结构？

Question

有没有什么巧妙的方法在C语言中实现一个集合数据结构（一个唯一值的集合）？集合中的所有元素将是相同类型，并且有巨大的内存。

据我所知，对于整数，可以使用值索引数组来快速轻松地完成此操作。但我想要一个非常通用的Set数据类型。如果一个集合可以包括自己，那就太好了。

- psihodelia

---

我在这里有同样的问题：https://dev59.com/Z0zSa4cB1Zd3GeqPqNyK。也许它会有所帮助！ - Andrei Ciobanu

不要介意我自夸一下：我用 C 语言写了一个内存中 B 树库：http://ccan.ozlabs.org/info/btree.html。B 树在集合方面基本上扮演着二叉树的同等角色。 - Joey Adams

当然，实现包含它们自己的集合只会带来麻烦。 - High Performance Mark

Answer 1

有多种实现集合（和映射）功能的方法，例如：

• 基于树的方法（有序遍历）
• 基于哈希的方法（无序遍历）

既然您提到了值索引数组，让我们尝试基于哈希的方法，它可以自然地建立在值索引数组技术之上。

请注意哈希和树的方法的优缺点。

您可以设计一个哈希集（哈希表的一种特殊情况），其中包含指向可哈希POD的指针，并使用链式法在内部表示为固定大小的哈希桶数组，其中：

• 同一个桶中的所有可哈希对象具有相同的哈希值
• 一个桶可以实现为动态数组或者可哈希对象的链表
• 可哈希对象的哈希值用于索引到桶的数组（哈希值索引数组）
• 哈希集合中包含的一个或多个可哈希对象可能是（指向）另一个哈希集合，甚至是哈希集合本身（即自我包含是可能的）

如果您拥有大量的内存，可以慷慨地调整桶的大小，并与良好的哈希方法结合使用，大大减少冲突的概率，从而实现几乎恒定的性能。

您需要实现：

• 被哈希类型的哈希函数
• 用于测试两个可哈希对象是否相等的类型的等式函数
• 哈希集合的contains/insert/remove功能。

您还可以使用开放地址法作为维护和管理桶的替代方案。

- vladr

Answer 2

集合通常实现为二叉树的某种变体。红黑树具有良好的最坏情况性能。

这些也可以用于构建映射以允许键/值查找。

这种方法需要对集合中的元素和映射中的键值进行某种排序。

如果您将C中的集合成员限制为定义明确的类型，则不确定如何使用二叉树管理可能包含自身的集合...这种结构之间的比较可能会出现问题。但在C++中可以很容易地完成。

- andand

Answer 3

在C语言中实现泛型的方式是使用void *，因此您仍然需要使用指针，不同对象的指针是唯一的。这意味着您需要一个包含指针的哈希映射或二叉树，这将适用于所有数据对象。

缺点是您无法独立地输入rvalue。您不能拥有一个包含值5的集合；您必须将5赋值给变量，这意味着它不会匹配随机的5。您可以将其输入为(void *) 5，在实际情况下，这很可能适用于小整数，但是如果您的整数足够大以与指针竞争，则失败的概率非常小。

字符串值也无法按此方式处理。给定char a [] ="Hello，World！"; char b [] ="Hello，World！";，指针集将找到a和b是不同的。您可能希望对值进行哈希，但是如果您担心哈希冲突，应将字符串保存在集合中，并使用strncmp()将存储的字符串与探测字符串进行比较。

（浮点数也存在类似的问题，但是尝试在集合中表示浮点数本身就是一个坏主意。）

因此，您可能需要一个标记值，一个用于任何类型的对象，一个用于整数值，一个用于字符串值，以及可能用于不同类型值的其他标记。这很复杂，但是可行。

- David Thornley

Answer 4

如果集合中的元素数量（基础数据类型的基数）足够小，您可能希望考虑使用普通的位数组（或者在您喜欢的语言中称为什么）。然后您可以进行简单的成员资格检查：如果元素n在集合中，则位n为1。您甚至可以从1开始计算“普通”成员，并且只有当集合包含自身时，才使位0等于1。这种方法可能需要某种其他数据结构（或函数）来将成员数据类型转换为位数组中的位置（和返回），但它使基本的集合操作（并集、交集、成员资格测试、差异、插入、删除、补集）非常容易。它仅适用于相对较小的集合，我不认为您会想要将其用于32位整数集。

- High Performance Mark