C - 如何实现Set数据结构？ [英] C - How to implement Set data structure?

问题描述

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

如我所知，对于整数，可以真正快速完成不用使用值索引数组。但我想要一个非常通用的Set数据类型。如果一个集合可以包含自己，那将是很好的。

解决方案

有很多实施方式设置（和映射）功能，例如：

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


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

由于您提到了值索引数组，我们来试试基于哈希的方法，自然地建立在值索引数组技术之上。

谨防基于哈希的和基于树的方法的优缺点

您可以设计一个哈希集（特殊情况哈希 哈希表）rel =noref errer> POD ，链接，内部表示为固定的，

• 所有哈希设备具有相同的哈希值


• 一个存储桶可以实现为动态数组或链接的哈希值列表


• a 哈希值的哈希值用于索引


• 哈希集中包含的一个或多个哈希设备的数组可能是（a指针）另一个哈希集，甚至哈希集本身（即自我包容是可能的）

拥有大量内存，您可以调整数组大小并且结合一个好的哈希方法，大大降低了碰撞的可能性，实现几乎不变的时间表现。

你必须实现：

• 等式函数的哈希函数对于用于测试两个哈希值是否相等的类型


• 哈希集包含 / 插入 / 删除功能。

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

Is there any tricky way to implement a set data structure (a collection of unique values) in C? All elements in a set will be of the same type and there is a huge RAM memory.

As I know, for integers it can be done really fast'N'easy using value-indexed arrays. But I'd like to have a very general Set data type. And it would be nice if a set could include itself.

解决方案

There are multiple ways of implementing set (and map) functionality, for example:

• tree-based approach (ordered traversal)
• hash-based approach (unordered traversal)

Since you mentioned value-indexed arrays, let's try the hash-based approach which builds naturally on top of the value-indexed array technique.

Beware of the advantages and disadvantages of hash-based vs. tree-based approaches.

You can design a hash-set (a special case of hash-tables) of pointers to hashable PODs, with chaining, internally represented as a fixed-size array of buckets of hashables, where:

• all hashables in a bucket have the same hash value
• a bucket can be implemented as a dynamic array or linked list of hashables
• a hashable's hash value is used to index into the array of buckets (hash-value-indexed array)
• one or more of the hashables contained in the hash-set could be (a pointer to) another hash-set, or even to the hash-set itself (i.e. self-inclusion is possible)

With large amounts of memory at your disposal, you can size your array of buckets generously and, in combination with a good hash method, drastically reduce the probability of collision, achieving virtually constant-time performance.

You would have to implement:

• the hash function for the type being hashed
• an equality function for the type being used to test whether two hashables are equal or not
• the hash-set contains/insert/remove functionality.

You can also use open addressing as an alternative to maintaining and managing buckets.

这篇关于C - 如何实现Set数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！