c - 如何实现一套？

Question

我想用 C 实现一个 Set。在创建 SET 时使用链表是否可以，还是我应该使用其他方法？

您通常如何实现自己的集合(如果需要)。

注意:如果我使用链表方法，我的 Set 操作可能会有以下复杂性:

• 初始化:O(1)；
• 销毁:O(n)；
• 插入:O(n);
• 删除:O(n)；
• 并集:O(n*m);
• 交点:O(n*m);
• 差异:O(n*m)；
• 成员:O(n);
• 是子集:O(n*m);
• setisequal: O(n*m);

O(n*m) 似乎有点大，尤其是对于海量数据...有没有办法更有效地实现我的 Set ？

Answer 1

集合通常实现为红黑树(要求元素具有总顺序)或自动调整大小的哈希表(需要哈希函数)。

后者通常是通过将哈希表的大小加倍并在超过特定容量阈值(75% 很好)时重新插入所有元素来实现的。这意味着单个插入操作可以是 O(n)，但当分摊到许多操作时，它实际上是 O(1)。