似乎计算机数据结构中存在一个明显的“技术断层”？

[abcbuzhiming]

计算机的数据结构这个东西，看起来东西不多，但是里面有一些很突兀的存在。绝大部分书也好，教程也好，介绍数据结构的时候，套路都是 数组 链表 Map(table) ，队列，栈。然后就会出现两个画风（难度）和之前的东西截然不同的存在——树和图。
我搞这行的时间也不算短了，也接触了不少人，发现 树和图 对于大部分人来说都是难以理解的存在，包括我自己也是。不是说他们的表现形式难以理解，而是指附加其上的计算行为，很复杂，有多重变种。和在他们之前的那些数据结构比起来，感觉他们的复杂度猛然抬了个台阶起来。非常的显眼而且突兀。
我注意到这点越久，就越怀疑这两个东西存在的“合理性”，他们就像塞进耗子窝里的大象那么显眼。这中间是不是缺少了什么，我们知道计算机的一切往上追溯都来自于数学，数学能解释这两个东西如此突兀的现象吗，还是说历史埋葬了一些东西，在 树和图 之前其实存在某些“前置科技”，只是因为种种原因，“前置科技”的功能被后来者覆盖了，就消失在历史长河里了

[oshio]

我咋觉得很多人理解错了，楼主不是觉得树和图难以理解（这些本来就是日常生活中和常见的东西），而是觉得“其上的计算行为”（算法）难以理解。我觉得这很正常啊，有些本来就不是很直观，否则凭啥最先写出来人还能把名字加到前面。在写出来这些最终的算法前，是不是还有一些更直观但是更低效的算法，又是如何一步一步发展到现在的，我想这才是楼主想知道的，我觉得这个问题挺有趣，有没有资料是讲这个内容的？

举个例子，比如微积分，我们现在学到的都是有严格定义的，也是极其抽象也难以理解。但并非一开始就是这样，牛顿搞微积分的时候是相对直观但不严谨的，他处理无穷大无穷小的时候都是极其简单粗暴的，发展到现在这样是无数天才的数学家不断改进的结果。一来就是ε～δ这套东西，就能马上理解不感到困惑才是少数吧。现在很多算法就相当于直接就是ε～δ，难以理解也是正常的。

[BlackBerry999]

79 和 81 楼 才是理解楼主问题的回答，其他的答主都没有理解楼主要问的。

[logic2chen]

@oshio +1

[makefei]

很棒的问题，归因到最后或许是人脑在宇宙中的局限性。

[ipwx]

@oshio
@BlackBerry999 看我的回帖啊。图论的第一篇论文是欧拉 18 世纪发表的，早在计算机出现前就出现“图”和“树”了。计算机时代只不过是把人家的方法变成了程序而已。“算法”是不过是计算机中的应用数学。

如果你要看怎么一步步推出来的，去追溯以前的论文呀？从图论一直到拓扑，够你体会揣摩前人怎么一步步完善“图”的概念的 www

[ipwx]

当然我没有看过图论的一系列论文，计算机算法经典教材上的内容够我用了。我也不觉得有啥需要追本溯源的，算法已经是非常贴近直观的东西了，没有追本溯源的必要。

说到拓扑，我倒是一直很想学，但是一直没有充分的时间去做这件事情……

[wangyzj]

我觉得这个东西要从物理上对状态只能二进制保存和处理来解释
除非有一种别的物质可以物理的存储更多的状态且能控制一定的成本
而一切数学和数据结构的行程的确也是为这种物理结构服务的
这一些都要从存储物理结构的 01 状态和 cpu 物理结构的 01 处理方式
所有数据结构都是从 01 上抽象出来的
也就是说包括数和图都是从简单数据结构抽象，简单的从物理 01 来

我是这么理解的

[rtp]

没感觉是断层的，可能理解角度不同，个人理解最基本的存储结构就是连续的和不连续的，一个对应数组，另一个对应链表，然后剩下的所有的数据结构都是基于二者之上的，例如使用数组表达的队列和使用链表表达的队列，使用数组表达的树状结构和使用链表表达的树状结构…… 难于理解是肯定的，因为不直观啊……

[ipwx]

再多说一句，教材是很难把“怎么一步步推出来这东西”给你呈现出来的。别的不说，几百年的智慧积累，期间主流思考方法不知道换了多少茬。数学理论也是个不断修正的过程，比如三次数学危机以及后续改变：

1 、第一次为了解决等腰直角三角形斜边长的问题，诞生了无理数；
2 、第二次为了解决微积分中“无穷小量”定义不清晰的问题，诞生了实分析（也就楼上提到的 ε～δ 语言）。
3 、第三次为了解决罗素悖论（理发师悖论：理发师只为小镇上不给自己理发的人理发，请问理发师是不是应该给自己理发？），从朴素集合论发展出了现代集合论。

楼上提过一上来就说 ε～δ 语言让人无法理解，没错这很正确，我刚学微积分也为之愤慨。但是啊，你一个学期的内容，教材不可能从 18 世纪牛顿的微积分开始讲，然后告诉你这个时代的微积分有什么问题，后续遇到了什么问题，以及实分析的发展过程，最后是测度论的完善。近一点来说，一百多年前康托尔提出实数不可数的时候，同时代的数学家都在嘲笑他呢。

工科学个皮毛，懂点前几百年数学家总结出来的最精炼的内容（ε～δ 语言），省点功夫去学怎么写代码，岂不美哉？如果对于糊里糊涂感到不满、感到困惑，抽出业余时间自己学习一个呗。学的多了，自然理解这个中来龙去脉了。我也是在不断学习，试图懂得更多，满足自己的求知欲罢了。

[ahaxzh]

我觉得哈数组、链表、队、栈都算是一维数据结构。
树、图都属于二维数据结构，只是说树是图的一种。
所有的一维数据结构都是二维数据结构的一种特例。
所有的一维数据结构也都能用二维数据结构所表示。
所以哪有什么断层啊。只是多维数据结构变化复杂。


以上，纯粹只是个人的观点。

[ahaxzh]

至于前面有大佬说 树是二维，图是三维，不敢苟同。

[ipwx]

@ahaxzh 其实我觉得你用一维二维来分类，我也不敢苟同。。。

[besto]

话说没有树和图的章节，来个 KMP 算法，你就觉得简单了？？？

[ipwx]

@besto KMP 算法和 BM 算法，hhh 。图算法至少是直观的，这俩字符串比较算法，OMG 就是个极限优化版自动机，从来都记不住，临时查资料也要看半天的那种。

[jiangzhuo]

书里和教程里的确可能没写，但是上课的时候老师肯定教了吧。至少我们老师开始教树的时候先拿了个二维链表出来，然后竖了起来。

[BiteTheDust]

KMP 也可以认为是一种自动机 所以到头来还是一种图

[wozhizui]

@gggxxxx 不同意

[BiteTheDust]

另外有人提到用维度来类比树 /图。
可能是因为虽然说树是一种特殊的图，但是树的性质实在是很特殊。
很多一维数据结构问题迁移到树上 往往不需要增加复杂度或者只需要增加一个 log 的复杂度(树链剖分 /欧拉序之类的算法)。

但是我觉得吧，这个观点是搞反了，以下谈谈我的观点。
图是一种应用广泛的模型，几乎所有问题都可以用图来建模。
树是一种特殊的图(无环)。
序列(也就是数组)可以理解为一种特殊的树(单链)。

[phoolean]

我明白你的意思，这个问题是计算机模型造成的。
内存是图灵机纸带的具体实现，它本质上是一维的数据存储器。对计算机的操作可以抽象成对纸带的读写，也就是一维的操作，越接近底层的语言越是如此。
你觉得数组、链表、队列和栈比较简单，是因为你把它们理解成一维结构，这种结构和纸带是简单对应的。
而树和图，为了方便学习，人需要把它们理解成二维结构。你在纸上画出树和图很容易，但计算机看不懂二维的画。所以你说的附加其上的复杂的计算行为，是二维结构向纸带降维投影的过程。树和图实现起来复杂度上了个台阶，是因为要在一维空间保留二维结构的全部信息；显得突兀是因为它们比计算机模型高一个维度，确实是塞进耗子窝里的大象。

[phoolean]

还有很重要的一点，编程实现时，不像画在纸上的那种点线连接，没有直观结构了