C-如何实现集合数据结构?

有 多种实施方式 设置(和映射)功能,例如:

• 基于树的方法(有序遍历)
• 基于哈希的方法(无序遍历)

自从 您提到了值索引数组 ,让我们尝试基于哈希的方法, 自然地建立在值索引数组技术之上 .

当心 advantages and disadvantages 基于哈希和基于树的方法。

你可以设计一个 哈希集 (特殊情况 hash-tables )指向的指针 可哈希 POD S,带 chaining ,内部表示为固定大小的存储桶数组 哈希表 ,其中:

• 全部的 哈希表 在桶中具有相同的哈希值
• 一个bucket可以实现为 dynamic array or linked list of hashables
• 一 可哈希 的 哈希值用于索引到存储桶数组中 (哈希值索引数组)
• 一个或多个 哈希表 包含在哈希集中的可能是(指向)另一个哈希集的指针,甚至是哈希集本身(即 自我包容是可能的 )

有了大量的内存,您可以大幅度地调整存储桶数组的大小,并结合一个好的哈希方法,大大降低了 collision 实现了几乎恒定的时间性能。

您必须实现:

• 这个 hash function 对于要散列的类型
• 用于测试两个哈希表是否相等的类型的相等函数
• 哈希集 contains / insert / remove 功能。

您也可以使用 open addressing 作为维护和管理桶的替代方案。

集合通常实现为 binary tree . Red black trees 具有良好的最坏情况性能。

这些还可用于构建 map 允许键/值查找。

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

如果将集合成员资格限制为C中定义良好的类型,我不确定如何使用二进制树管理可能包含自身的集合…这种结构之间的比较可能有问题。不过,在C++中,你可以很容易地完成它。

如果集合中元素的最大数目(基础数据类型的基数)足够小,您可能需要考虑使用一个普通的旧位数组(或用您最喜欢的语言调用它们的任何类型)。

然后有一个简单的集合成员资格检查:如果元素n在集合中,则位n为1。您甚至可以从1中计算“普通”成员,并且如果集合包含自身,则仅使位0等于1。

这种方法可能需要某种其他数据结构(或函数)来将成员数据类型转换为位数组(和位数组)中的位置,但它使基本的集合操作(联合、交集、成员测试、差异、插入、删除、强制)非常容易。它只适用于相对较小的集合,我想你不会想把它用于32位整数的集合。

在C语言中获得遗传性的方法是 void * ,所以您无论如何都要使用指针,指向不同对象的指针是唯一的。这意味着您需要一个包含指针的哈希映射或二叉树,这对所有数据对象都有效。

这样做的缺点是您不能独立输入rvalues。不能有一个包含值5的集合;必须将5赋给一个变量,这意味着它与随机5不匹配。您可以输入为 (void *) 5 对于实际用途,这可能适用于小整数,但如果您的整数可以变得足够大以与指针竞争,则失败的概率非常小。

这也不适用于字符串值。鉴于 char a[] = "Hello, World!"; char b[] = "Hello, World!"; ,一组指针将找到 a 和 b 与众不同。您可能希望散列这些值,但是如果您关心散列冲突,那么应该将字符串保存在集合中并执行 strncmp() 将存储的字符串与探测字符串进行比较。

(浮点数也有类似的问题,但首先尝试在集合中表示浮点数是个坏主意。)

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