我想用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)；
- 集合相等：O(n*m)；
O(n*m) 似乎可能有点大，特别是对于大量数据......有没有办法更有效地实现我的 Set ？
集合通常实现为红黑树（这要求元素具有总顺序），或实现为自动调整大小的哈希表（这需要哈希函数）。
后者通常是通过将哈希表大小加倍并在超过某个容量阈值（75% 效果很好）时重新插入所有元素来实现的。这意味着单个插入操作的复杂度可能是 O(n)，但是当分摊到许多操作时，它实际上是 O(1)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
