代码之家  ›  专栏  ›  技术社区  ›  Shamik

我们应该知道哪些不太知名的数据结构和算法?

  •  6
  • Shamik  · 技术社区  · 15 年前

    最近我遇到了skiplist数据结构。它真的帮助我解决了一个原本难以解决的问题。我一直在努力用平衡二叉树来解决它,但是它变得非常复杂,因为这棵树需要始终保持平衡,我想知道一个特定值的存在,而且在一定范围内的值。斯基普里斯特帮助我有效地解决了那个问题。

    我想知道我还需要了解哪些其他数据结构?我知道-数组、列表、堆栈、队列、链接列表、哈希表、树及其不同的形式,如B树、trie等。 想知道您是否发现一些其他的数据结构/概念在常规的开发周期中很有趣,也很有用。

    2 回复  |  直到 11 年前
        1
  •  3
  •   Niki Yoshiuchi    15 年前

    你没有提到那些非常强大的图表,如果你不知道它们,你应该仔细阅读。查找dijkstra算法和a*搜索算法,以及一般的深度优先搜索和宽度优先搜索。

    您还省略了堆,这些堆通常用作优先级队列的基础结构。二进制堆是最简单的,但您也可以查看最小-最大中值堆、二项式堆(快速合并)和斐波那契堆(快速减少键-对某些图形算法有用)。

    其他有趣的数据结构包括Patricia尝试,这是空间效率的尝试(键控子串而不是字符),伸展树,这是平衡的,可以编程为持久的。另外,检查bloom过滤器,这是一种概率数据结构,允许您确定元素是否是集合的成员。它可以有假阳性,但不能有假阴性,而且空间/时间效率很高。

    最后,您可以使用函数路由,研究不可变和持久的数据结构。其中许多只是您已经知道的数据结构的功能版本。如果你对此感兴趣,我建议你去冈崎看看 纯功能数据结构 .

        2
  •  1
  •   Jerry Coffin    15 年前

    你有“列表”和“链接列表”,而且你根本不清楚这两者之间有什么区别(如果有的话)。不管怎样,您跳过的一个明显的结构是堆(您可能将其归类为树的类型,但这充其量是不确定的)。最后,树是图的一个子集,所以如果您没有研究图(一般来说),这可能是一个需要探索的领域。

    我会注意到,这些都不是特别“最近”的——它们几十年来都是众所周知的。这些真正的一般结构中的大多数已经被知道了很长一段时间。最近发现的一个更倾向于与更具体的主题领域相关。