这是一个创建于 1682 天前的主题，其中的信息可能已经有所发展或是发生改变。
计算机的数据结构这个东西，看起来东西不多，但是里面有一些很突兀的存在。绝大部分书也好，教程也好，介绍数据结构的时候，套路都是 数组 链表 Map(table) ，队列，栈。然后就会出现两个画风（难度）和之前的东西截然不同的存在——树和图。
我搞这行的时间也不算短了，也接触了不少人，发现 树和图 对于大部分人来说都是难以理解的存在，包括我自己也是。不是说他们的表现形式难以理解，而是指附加其上的计算行为，很复杂，有多重变种。和在他们之前的那些数据结构比起来，感觉他们的复杂度猛然抬了个台阶起来。非常的显眼而且突兀。
我注意到这点越久，就越怀疑这两个东西存在的“合理性”，他们就像塞进耗子窝里的大象那么显眼。这中间是不是缺少了什么，我们知道计算机的一切往上追溯都来自于数学，数学能解释这两个东西如此突兀的现象吗，还是说历史埋葬了一些东西，在 树和图 之前其实存在某些“前置科技”，只是因为种种原因，“前置科技”的功能被后来者覆盖了，就消失在历史长河里了
我搞这行的时间也不算短了，也接触了不少人，发现 树和图 对于大部分人来说都是难以理解的存在，包括我自己也是。不是说他们的表现形式难以理解，而是指附加其上的计算行为，很复杂，有多重变种。和在他们之前的那些数据结构比起来，感觉他们的复杂度猛然抬了个台阶起来。非常的显眼而且突兀。
我注意到这点越久，就越怀疑这两个东西存在的“合理性”，他们就像塞进耗子窝里的大象那么显眼。这中间是不是缺少了什么，我们知道计算机的一切往上追溯都来自于数学，数学能解释这两个东西如此突兀的现象吗，还是说历史埋葬了一些东西，在 树和图 之前其实存在某些“前置科技”，只是因为种种原因，“前置科技”的功能被后来者覆盖了，就消失在历史长河里了
 |
101
XenoAmess 2020-04-15 15:18:39 +08:00
你把链，做成多子节点 不就成了树？
这是个非常自然的过程啊。 归根结底还是你归纳总结能力不足。 |
 |
102
janxin 2020-04-15 15:27:12 +08:00
没有吧，其实是一种扩展关系
|
 |
103
oshio 2020-04-15 16:00:45 +08:00  2
@ipwx 没错，教材不可能包括这些内容，但相关的资料应该还是有的。直接读论文对我来说有点太难了，对我来说科普读物就能解决大部分疑惑，比如微积分就有《微积分的历程》，就是不知道有没有类似的算法的历程这样的资料，当故事读读也挺好的。
对一个智力正常的人来说，一个东西难以理解可能是真的很难，比如说量子力学；也可能是步子迈的太大，缺乏必要的基础，比如说小学没学完就学微积分。我们教科书上的算法，基本上应该是第二类，觉得难以理解不是因为它已经达到人类智力的极限（毕竟绝大多数都是几百年前数学家研究透了的东西里面最简单的部分了），而是我们缺了一些中间过程，补上这些就能更好的理解了。 |
 |
104
calpes 2020-04-15 16:09:43 +08:00
缺乏现实中理解指数型问题的经验。
|
 |
105
IGJacklove 2020-04-15 16:14:10 +08:00
这两个确实一般程序员都接触不到，尤其是图，大部分程序员基本都接触不到
|
 |
106
otakustay 2020-04-15 16:19:40 +08:00
我觉得大的断层是堆和图
然后树内部也有断层，普通树和平衡树 |
 |
107
GrayXu 2020-04-15 16:20:25 +08:00
请问链表难道不是一种特殊的树形式？
别啥前置科技了，整的跟民科似的 |
|
108
GrayXu 2020-04-15 16:23:50 +08:00
翻了一遍评论，认为真的有这种断层的朋友们，你们是怎么去理解更复杂的算法和数据结构的（字典树、线段树）。。
还是多多读书和论文吧，感觉这个问题还是学的少导致的… |
 |
109
zzhzero 2020-04-15 16:28:56 +08:00
无外乎是顺序储存和链式储存的不同应用而已 有这种疑惑是好事 去书里面找答案吧
|
 |
110
lidlesseye11 2020-04-15 16:52:42 +08:00
我觉得楼主所谓的断层不是数据结构，而是应用于其之上的算法
楼上那么多说“树就是进化后的链表”的，serious ？(可能 V 站真的就是大佬多吧┑(￣Д ￣)┍ 树的结构，即使不是学计算机的，也都有“朴素”的理解。 但是一说到比如红黑树的实现，说实话我到现在也是懵逼的。。。 只是对照着定义撸出来就很麻烦了，更不要说自己证明或者“推导”出来了（此处求问大佬们有没有好的教材。。 |
 |
111
ipwx 2020-04-15 16:59:42 +08:00
红黑树、KMP 、BM，堪称入门级数据结构和算法教材最难学会的东西。不是因为概念太难，而是因为优化到极致，所以琐碎的东西太多了。。。
概念上不就是平衡树和自动机么。。。 |
 |
112
tairan2006 2020-04-15 19:18:41 +08:00
树退化一下就是链表啊，你这数学学的半桶水的别自己瞎想了…
|
 |
113
levelworm 2020-04-15 20:40:06 +08:00 via Android
@ipwx 作为一个非科班也不准备靠这个吃饭纯粹自学着玩的人来说，自平衡树我觉得是一道坎，之前的都很轻松，之后的困难一些。我因为没啥需求，到现在也没学超过自平衡树。。。
我觉得这道坎可能在于智商不足。之前的结构都能理解，但是自平衡树的那些旋转，没法直观的理解，又没能力从数学上证明，所以就弃疗了。 不过好在似乎想写的东西基本上不需要什么复杂的结构和算法，都是玩具反正。 |
 |
114
akira 2020-04-15 21:20:05 +08:00
一根树枝长了个分叉就不认识了啊。。
|
 |
115
CoderGeek 2020-04-15 21:21:50 +08:00
说实话 我之前准备考研 树还好 图那块有点突兀 不过专心还好
|
 |
116
msaionyc 2020-04-15 21:29:05 +08:00 via Android
多学习吧
|
 |
117
brickxu 2020-04-15 21:32:59 +08:00 2
建议去离散数学中寻找你所谓的“断层”的答案。
BTW，“我搞这行的时间也不算短了”，你这句话等于把自己底裤都漏出来了。 |
 |
118
bspp 2020-04-15 23:04:14 +08:00
@lidlesseye11 去网易云公开课搜平衡搜索树 非常好的讲解
|
 |
119
abcbuzhiming OP 1
@brickxu 我没觉得露底裤有啥不行的，每个人都有自己的极限，藏着掖着反而不利于自己进步，你看我主动暴露自己的弱点不就引来了一大堆牛人吗。至少我今天真的知道了一个方向：也许离散数学里有答案
|
 |
120
greenlake 2020-04-15 23:46:49 +08:00
我觉得计算机科学的基础研究没什么大变化，几十年前的数据结构大概就是这样了，但是应用层面大量的变化改变了我们的生活。就像基础物理一样，多少年没什么大变化，人类 60 年代还去过月球，现在呢？
|
 |
121
rus4db 2020-04-16 00:41:11 +08:00
图论的确是很奇妙的领域，近年来无论是深度神经网络、图神经网络，还是网络科学、复杂系统科学、知识图谱，背后都或多或少有图论的影子。
感觉计算复杂度理论（递归论）和图论之间存在微妙的联系。讲不清楚，这或许就是你说的“断层”吧。 |
 |
122
Chase2E 2020-04-16 02:05:43 +08:00 2
数组通过保持插入排出顺序成了 Stack 和 Queue，通过维持大小层级关系成了堆，
一条直线是链表，链表每个节点带 Hash 成了 Key_Value_Map, 链表分叉成了树，左右子树保持平衡是 23 树（红黑），树的节点换成 Character/String 成了 Trie， 链表分叉还连在一块儿了是图，一堆图分类了是 UnionFind 。 这不是很自然... 应用上也是很衔接啊，图用的不多只能是说对应的领域用不到太多图的知识 or 你不能判断一个数据结构 /算法实质上是图上的算法。 |
 |
123
nvkou 2020-04-16 02:29:28 +08:00 via Android
图论 是数学领域的
|
 |
124
wc951 2020-04-16 06:49:19 +08:00 via Android
大学 cs 专业有一门必修课叫集合与图论
|
 |
125
Perry 2020-04-16 08:05:23 +08:00
学 Combinatorial optimization 的时候那酸爽，确实会觉得复杂度很大。
|
 |
126
Greendays 2020-04-16 08:34:58 +08:00
难点不外乎“增删改查”，其实我当年刚接触这些东西的时候，数组，链表，栈的增删改查也令我很迷惑，不觉得这些东西特别简单。
然后到了树和图这块，难度显然是指数上升，因为数据不再是线性排布的了，“增删改查”的维度增加了。你说的“前置科技”大概是不存在的，你的这种感觉，我感觉有点像刚学完 2 元函数，然后去接触 3 元函数时的感觉，脑子里原先有用的“图像”好像都失效了，再接下来的 4 元函数就已经不能想象了，研究起来阻力很大，只能套公式，类似于计算机开发中的“只能调接口”的状态。 |
 |
127
ooozx 2020-04-16 08:51:49 +08:00
哈哈哈，看到大家都在批。图确实接触的比较少，最近在解决寻路算法、排程算法的时候经常用到。但树确实能经常接触，毕竟大学的时候大家都得学（半路出家的自动忽略，别杠）。
|
 |
128
exploreXin 2020-04-16 09:20:13 +08:00
人脑是组织是细胞神经结构，计算机的组织是电子电路结构，这个最底部的差异注定人脑与计算机的通信过程，需要经过多个层次的降维与升维，才能填平这个鸿沟。数据结构是高层抽象，高层的意思就是离人脑近，符合人脑的思考习惯，而离计算机电路远，不是底层电路通断的方式，但实际人脑神经与电子电路是分属高层抽象两旁的同一概念的实现，就像硬币的两面，逻辑上是一个东西，只是实现不同，之所以要分出两个部分，就是人脑善于决策与艺术性设计，但计算速度慢，而计算机的计算速度快，但是不善于创造性的行为，说白了计算机是辅助人脑的外设，相当于外脑，现阶段的计算机只能是人脑的附属物，无论计算速度与容量如何巨大，附属物的定位是改变不了的，除非强人工智能到来，否则不会改变，但强人工智能什么时候来临，能否来临，都是未知数。
说回楼主的疑问，从上面的角度去看楼主所说的鸿沟，就容易理解了，高层抽象是符合人脑习惯的理解方式，树和图更接近人脑的理解力，而链表，堆栈等等，这些相对容易理解，只是因为它更贴近计算机的一面，这时候想一下树和图从人脑角度理解，像什么？不就是脑神经的链接方式吗，局部脑神经连接方式是树结构，而大范围的脑连接结构就是图了，有环回结构。这时可以得出解决楼主疑问的方法了，楼主想搞清楚鸿沟的产生与原因，需要看一些生物学，尤其是神经科学方面的书籍与资料，然后再加深一下计算机硬件的了解，最后回到软件开发的范畴，就能看明白其实根本没有真正的软件，软件只是电路与人脑的粘合剂，直觉上来说的话，软件的存在是一个似乎很虚的东西，它只是为了拟合两个不同层次的计算体才产生的事物，这时候再看一下鸿沟，是不是问题就感觉很清楚了呢。 软件开发其实只是信息技术的一小部分，想要达到融会贯通的地步，还是需要多涉猎一些自己领域之外的东西，所谓跳出软件学软件，之后再回到软件，到了那时，没有神之力量，也可以获得近神之力了。 |
 |
129
kuangwinnie 2020-04-16 09:39:29 +08:00
题做少了
你做多了就知道这是很自然的 __树__ 是有向无环__图__ 链表也是一种特殊的树。。。 |
 |
130
augustheart 2020-04-16 09:39:35 +08:00
这只是思维方式没转变造成的。中学物理课能完全用日常经验理解，到大学的物理就是完全存在于数学公式里面，按中学的方法就无法理解了，继续强行理解的后果就是各种民科了……
|
 |
131
lenjeans 2020-04-16 15:02:43 +08:00
我记得我们那时候老师是用的教室外面的树举例的
反正教大学生应付考试足够用了。 |
 |
132
kcer 2020-04-16 16:42:37 +08:00
数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树~~~一个一个看~都是有关联的~
|
 |
133
CasualYours 2020-04-16 17:38:55 +08:00
因为计算机的内存地址是一维模型，而数组，链表，队列，栈数据结构也是一维的，对于这些数据结构的操作也是符合直觉的；通常我们在学习这一部分时，大部分人不用借助纸笔，都能想的明白。
但是像树这种结构，为了计算机能够表示，我们实现的时候，通常是将这种二维结构压扁成一维结构（使用数组）。这就导致像父节点和子节点这种在树里是连接的，而在数组实现时常常会出现隔断和跳跃。所以我们在学习过程中，往往会借助纸笔，借助手绘的更具象的模型去理解树的操作（上浮，下沉等）。 |
 |
134
winglight2016 2020-04-16 19:44:55 +08:00
如果 lz 表达的是难度忽然提升，这样说没什么问题，毕竟难者不会，会者不难。但是，从难度的跨越推理出“断层”，这就很没道理了，你不能期望世界上万事万物的变化都是平滑曲线拟合吧？归根结底，数学功底不扎实会导致抽象能力较弱，对于复杂对象理解起来会困难一些，但是树和图本身并不是很难，难点在于很多变体和应用场景的对应，没有实际例子来推导一遍，对于学习者来说算法就会变成天书一般莫名其妙。
|
 |
135
Cu635 2020-08-06 15:46:01 +08:00
@dreamapple
数据结构和算法导论是哪个出版社谁编写的？哪个版本？ |
Select Language