周围有一些数据结构非常有用,但大多数程序员都不知道。他们是哪一个?

每个人都知道链表、二叉树和散列,但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构,因为它们依赖于伟大的想法,丰富了程序员的工具箱。

PS:我还对舞蹈链接等技术感兴趣,这些技术巧妙地利用了通用数据结构的财产。

编辑:请尝试包含更详细描述数据结构的页面链接。此外,试着补充几句关于数据结构为什么很酷的话(正如乔纳斯·Kölker已经指出的那样)。此外,尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。


当前回答

区域四叉树

(引自维基百科)

区域四叉树通过将区域分解为四个相等的象限、子象限等来表示二维空间的分区,每个叶节点包含对应于特定子区域的数据。树中的每个节点要么正好有四个子节点,要么没有子节点(叶节点)。

像这样的四叉树很适合存储空间数据,例如纬度和经度或其他类型的坐标。

这是我在大学里最喜欢的数据结构。对这家伙进行编码并看到它的工作非常酷。如果你正在寻找一个需要思考并且有点偏离常规的项目,我强烈建议你这样做。无论如何,它比通常在数据结构类中分配的标准BST派生工具有趣得多!

事实上,作为奖励,我在这里找到了(弗吉尼亚理工大学的)课堂项目前的演讲笔记(pdf警告)。

其他回答

正确的字符串数据结构。几乎每个程序员都满足于一种语言对结构的任何原生支持,而这种支持通常是低效的(尤其是对于构建字符串,你需要一个单独的类或其他东西)。

最糟糕的是将字符串作为C中的字符数组,并依赖NULL字节来确保安全。

张开树怎么样?

此外,Chris Okasaki的纯功能数据结构也在脑海中浮现。

它非常特定于领域,但半边缘数据结构非常整洁。它提供了一种在多边形网格(面和边)上迭代的方法,这在计算机图形和计算几何中非常有用。

跳过列表实际上非常棒:http://en.wikipedia.org/wiki/Skip_list

任何有3D渲染经验的人都应该熟悉BSP树。通常,这是一种通过构造3D场景来进行渲染的方法,该方法可以在知道相机坐标和方位的情况下进行管理。

二进制空间分区(BSP)是一种递归细分a的方法通过超平面将空间划分为凸集。该细分产生通过方法表示场景树数据结构的BSP树。换句话说,这是一种方法形状复杂的破碎多边形转化为凸集,或更小多边形完全由非反射角(小于180°). 更一般的描述空间分区,请参见空间分区。最初,提出了这种方法在3D计算机图形方面渲染效率。其他一些应用程序包括执行具有形状的几何操作(构造实体几何),机器人和3D中的碰撞检测计算机游戏和其他计算机涉及处理的应用程序复杂的空间场景。