一些鲜为人知却非常实用的数据结构

偏执的太偏执、 2022-10-03 00:51 150阅读 0赞

原文: [http://www.cnblogs.com/haippy/archive/2013/05/27/3101697.html][http_www.cnblogs.com_haippy_archive_2013_05_27_3101697.html]

作者: 傅海平

================================================================================================================================

作为程序猿（媛），你必须熟知一些常见的数据结构，比如栈、队列、字符串、链表、二叉树、哈希，但是除了这些常见的数据结构以外，还有没有其他不是很有名，但却非常实用的数据结构呢，有人在 [stackoverflow][] 上问了这样一个问题，得到了很多热心观众的回答，我们今天就来看看那些鲜为人知却非常实用的数据结构吧。

首先，维基百科上的一个页面列举了[常见的数据结构][Link 1]，你可以先去那个页面看看。下面我们就来看看一些不是很常见的数据结构吧：

*  [Tries][](前缀树)
 *  [Bloom filter][](布隆过滤器)
 *  [Rope][]: 主要用于某些文本编辑器中，可用于字符串高效地插入、删除、追加等操作。SGI 的 STL 中实现了 Rope(http://www.sgi.com/tech/stl/Rope.html)
 *  [Skiplist][](跳表)
 *  [Spatial Indices][](空间索引)，如[R-trees][] 和 [KD-trees][]
 *  [Splay trees][](伸展树)
 *  [Disjoint Set][](并查集)
 *  [Fibonacci heaps][](斐波那切堆)
 *  [Huffman trees][](哈夫曼树)
 *  [ring buffer][](又名circular buffer)
 *  [Merkle trees][](哈希树)
 *  [min-max heap][]
 *  [bitset][](又称bit array, 位数组)
 *  [Xor linked list][]
 *  [AA tree][]
 *  [Log-structured merge-tree][]
 *  [Radix tree][]
 *  [Judy array][]

[http_www.cnblogs.com_haippy_archive_2013_05_27_3101697.html]: http://www.cnblogs.com/haippy/archive/2013/05/27/3101697.html
[stackoverflow]: http://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-useful-data-structures?page=1&tab=votes#tab-top
[Link 1]: http://en.wikipedia.org/wiki/List_of_data_structures
[Tries]: http://en.wikipedia.org/wiki/Trie
[Bloom filter]: http://en.wikipedia.org/wiki/Bloom_filter
[Rope]: http://en.wikipedia.org/wiki/Rope_%28data_structure%29
[Skiplist]: http://en.wikipedia.org/wiki/Skip_list
[Spatial Indices]: http://en.wikipedia.org/wiki/Spatial_index
[R-trees]: http://en.wikipedia.org/wiki/R-tree
[KD-trees]: http://en.wikipedia.org/wiki/Kd-tree
[Splay trees]: http://en.wikipedia.org/wiki/Splay_tree
[Disjoint Set]: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
[Fibonacci heaps]: http://en.wikipedia.org/wiki/Fibonacci_heap
[Huffman trees]: http://en.wikipedia.org/wiki/Huffman_coding
[ring buffer]: http://en.wikipedia.org/wiki/Circular_buffer
[Merkle trees]: http://en.wikipedia.org/wiki/Merkle_tree
[min-max heap]: http://cg.scs.carleton.ca/~morin/teaching/5408/refs/minmax.pdf
[bitset]: http://en.wikipedia.org/wiki/Bit_array
[Xor linked list]: http://en.wikipedia.org/wiki/Xor_linked_list
[AA tree]: http://en.wikipedia.org/wiki/AA_tree
[Log-structured merge-tree]: http://en.wikipedia.org/wiki/Log-structured_merge-tree
[Radix tree]: http://en.wikipedia.org/wiki/Radix_tree
[Judy array]: http://en.wikipedia.org/wiki/Judy_array