如何实现集合?[英] How to implement a set?

问题描述

我想在C中实现集合. 可以在创建集合时使用链接列表，还是可以使用另一种方法?

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

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

• init:o(1);
• 销毁:o(n);
• 插入:o(n);
• 删除:o(n);
• 联合:o(n*m);
• 交叉点:o(n*m);
• 差异:o(n*m);
• ismember:o(n);
• issubset:o(n*m);
• senisisequal:o(n*m);

o(n*m)似乎可能有点大，特别是对于庞大的数据而言……有没有办法实施我的集合效率更高?

推荐答案

我过去曾经使用过红黑树来构建集合.

这是Wikipedia文章的时间复杂性.

空间o(n)
搜索o(log n)
插入o(log n)
删除o(log n)

其他推荐答案

集合通常被用作红色树木(需要元素具有总顺序)，或者作为自动衡量的Hashtable(需要哈希函数).

通常，当超过一定的容量阈值(75％的效果很好)时，将后者的大小具有尺寸的双重尺寸和重新插入所有元素来实现.这意味着不重要的插入操作可以是o(n)，但是当在许多操作上摊销时，实际上是o(1).

其他推荐答案

std::set通常以红色黑树的形式实现: .wikipedia.org/wiki/red-black_tree

这种方法将使您在所有列出的操作中都更好地复杂性.

本文地址：https://www.itbaoku.cn/post/359367.html