如何实现集合?[英] 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