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

Question

在C中实现set数据结构(一组唯一值)是否有任何棘手的方法？集合中的所有元素都是相同的类型,并且存在巨大的RAM内存.

据我所知,对于整数,使用值索引数组可以非常快速地完成它.但我想要一个非常通用的Set数据类型.如果一个集合可以包含它本身就会很好.

Answer 1

有多种方法可以实现 set(和map)功能,例如:

• 基于树的方法(有序遍历)
• 基于散列的方法(无序遍历)

既然你提到了值索引数组,那么让我们尝试基于散列的方法,该方法自然地构建在值索引数组技术之上.

注意基于散列与基于树的方法的优缺点.

可以设计出散列的组(的特例哈希表的指针),以可哈希 POD S,与链接,内部表示为的铲斗的固定大小的数组hashables,其中:

• 所有hashables水桶具有相同的哈希值
• 存储桶可以实现为动态数组或连接的链表
• 一个可哈希的哈希值用于索引到桶的阵列(散列值索引的阵列)
• 散列集中包含的一个或多个hashables可以是(指向)另一个散列集,或者甚至是散列集本身(即可以包含自包含)

有了大量内存供您使用,您可以大量调整存储桶数量,并结合良好的散列方法,大幅降低碰撞概率,实现几乎恒定的时间性能.

你必须实现:

• 哈希类型的哈希函数
• 用于测试两个hashables是否相等的类型的相等函数
• 哈希集contains/ insert/ remove功能.

您还可以使用开放式寻址作为维护和管理存储桶的替代方法.

Answer 2

集合通常实现为某种二叉树. 红黑树具有良好的最坏情况表现.

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

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

如果您将集合成员资格限制为C中明确定义的类型,我不确定如何管理可能使用二叉树包含自身的集合...这些构造之间的比较可能会有问题.但是,您可以在C++中轻松完成.

Answer 3

在 C 中获得通用性的方法是 by void *，所以无论如何你都会使用指针，并且指向不同对象的指针是唯一的。这意味着您需要一个包含指针的哈希图或二叉树，这适用于所有数据对象。

这样做的缺点是您无法独立输入右值。你不能有一个包含值 5 的集合；你必须将 5 分配给一个变量，这意味着它不会匹配随机的 5。你可以将其输入为(void *) 5，出于实际目的，这可能适用于小整数，但如果你的整数可以达到足够大的大小与指针竞争，失败的可能性很小。

这也不适用于字符串值。给定char a[] = "Hello, World!"; char b[] = "Hello, World!";，一组指针将发现a和b是不同的。您可能想要对值进行哈希处理，但如果您担心哈希冲突，则应该将字符串保存在集合中，并将strncmp()存储的字符串与探测字符串进行比较。

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

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