logo标签列表

有哪些不太为人知但很有用的数据结构？

language-agnosticdata-structurescomputer-science
793

有一些数据结构对于大多数程序员来说很有用，但是却不为人所知。它们都是哪些呢？

每个人都知道链表、二叉树和哈希表，但是例如跳表和布隆过滤器呢？我想了解更多不太常见但值得知道的数据结构，因为它们依赖于巨大的思想，并且丰富了程序员的工具箱。

PS：我还对像舞蹈链这样聪明地利用常见数据结构属性的技术感兴趣。

编辑: 请尝试在描述数据结构的页面中包含链接。此外，请尽量添加一些关于为什么某个数据结构很酷的词语（正如Jonas Kölker 已经指出的）。此外，请每次只提供一个数据结构的答案。这将使更好的数据结构根据它们的投票结果浮现在最上面。

16
http://zh.wikipedia.org/wiki/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%88%97%E8%A1%A8 + http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%86%B3%E5%AE%9A%E5%9B%BE - Fanatic23
83个回答
5
5
4

你可以使用一个小根堆在常数时间内找到最小元素，或者使用大根堆找到最大元素。但如果想要同时执行这两个操作怎么办？你可以使用 Min-Max 来在常数时间内执行这两个操作。它通过使用 min max 排序来工作：在相邻的树层之间交替使用小根堆和大根堆比较。

1
这是我最喜欢的数据结构之一。甚至有一种变体叫做min-max-median堆，它允许O(1)检索其中的任何一个。 - Martin
4
伸展树很酷。它们以一种方式重新排序，将最常查询的元素移动到更靠近根部的位置。
这是一个重复的答案。也许你想要为之前的回答添加一些补充元素？ - Francois G
4
根据布隆过滤器的提及，可删除布隆过滤器（DlBF）在某些方面比基本计数变体更好。请参见http://arxiv.org/abs/1005.0352。
4

远离所有这些图形结构，我特别喜欢简单的环形缓冲区(Ring-Buffer)。

当正确实现时，您可以严重减少内存占用，同时保持性能，有时甚至会提高性能。

4

B*树

B*树是一种B树的变体，更适合于搜索，但插入操作花费更高。

3
我认为Paolo Ferragina和Giovanni Manzini的FM-index非常酷，特别是在生物信息学中。 它实质上是一个压缩的全文索引，利用后缀数组和参考文本的Burrows-Wheeler变换的组合。 可以在不解压整个索引的情况下搜索索引。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接