Google Reader

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

by Haippy

at 2013-05-27 16:46:00

original http://www.udpwork.com/item/9932.html

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

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

• 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

本文链接

        <div style="margin-top:8px;padding:6px 0;border-top:1px solid #3cf">
            <div style="text-align:center;margin:16px 0;padding:6px;border:0px dashed #999;font-family:arial;font-size:26px;font-weight:bold">
<a href="http://www.udpwork.com/item/9932.html#review_form" title="不喜欢" style="text-decoration:none">
    <img src="http://www.udpwork.com//images/thumb_down24.gif" alt="">
    <span style="color:#f33">0</span>
</a>
   
<a href="http://www.udpwork.com/item/9932.html#review_form" title="喜欢" style="text-decoration:none">
    <img src="http://www.udpwork.com//images/thumb_up24.gif" alt="">
    <span style="color:#3c3">0</span>
</a>