《数据结构》书评与 MOOC 推荐
tison
兴趣使然的小工程师
14 人赞同了该文章
Algorithms + Data Structures = Programs 是 Pascal 的作者 Niklaus Wirth 提出的著名观点。讲解算法与数据结构的书籍有很多，包括经典的《算法导论》、《算法（第四版）》、《算法设计》和《数据结构与算法分析（C 语言描述）》等等。今天要介绍的是这林林总总的书籍当中本土出版的，清华大学邓俊辉教授的《数据结构（C++ 语言版）》以及学堂在线配套上线的 MOOC 系列。
相比于英文教材原版对本土学生有语言障碍，翻译版本难免词不达意，这本《数据结构》从邓老师几十年来的教学经验出发，以中文原版的讲述方式介绍了计算机科学中重要的知识点[数据结构与算法]。虽然书名是数据结构，但是数据结构某种程度上也是服务于算法的；或者换个角度说，为了实现某种特定的算法，设计出了与其相匹配的数据结构。无论如何，数据结构和算法是分不开的。
本书从算法的一般性讨论出发，回顾了计算机抽象问题的方法以及归纳算法的一般过程，提出了好的算法的评判标准。随后，将常见的数据结构拆分为向量、列表、栈与队列、二叉树、图、搜索树、词典、优先级队列和字符串一一讲解，最后一章针对排序额外讨论了一些经典算法。全书各章节以问题引入开篇，在逐步介绍问题背景和提出具体问题的过程中，给出数据结构的 ADT 定义，穿插着各种算法的讲解和分析。本书的一大特点是讲解非常的流畅，仿佛邓俊辉教授面对面地讲授他多年以来在数据结构与算法这个领域的思考。另外，在清华美院的同学的帮助下，全书排版非常美观，演示数据结构与算法的图片赏心悦目，一看就懂。本书精巧的编排和严谨但不失流畅的用词，以及时不时碰撞出的思维火花，真的是给计算机科学的学生在接触数据结构与算法的时候感受到其中的乐趣的契机。通过这本书及其配套资料的学习，我相信你能够感受到邓俊辉教授对数据结构与算法的热爱与倾注的心血。
我有幸在《数据结构》MOOC 上线学堂在线初期就加入到线上学习当中，当时还在上大一或者大二。那个学期邓老师只开了公选课，面对清华全校同学教授，我在线下溜过去参与过其中一节，还记得讲到了最大栈和排序算法下界的问题。时至今日，很多复杂算法或者严谨证明和计算的内容已经记不清楚了，但是邓老师的人格魅力以及讲授课程的时候给人愉快而享受其中的感觉仍然难以忘怀。最近整理书籍的时候又看到了这本《数据结构》，回想起在大学期间学习数据结构与算法，以及后来面试的时候依靠它应对技术面试的过往，仍然能记起当时的快乐和印象深刻的案例。
本文下面将首先列出《数据结构》一书的豆瓣链接以及课程网站地址，可以从课程网站上获取全套讲义以及 MOOC 链接等等公开材料。随后，列举自己当时学习过程中印象深刻的算法，以期达到帮助管中窥豹的效果，同时也是对自己记忆的一次整理。
数据结构 (豆瓣)
book.douban.com数据结构习题解析（第3版） (豆瓣)
book.douban.comDSACPP 课程网站
dsa.cs.tsinghua.edu.cn
众数指的是在任一无需向量 A 中，若有一半以上元素的数值同为 m，则 m 就是 A 的众数。例如，向量 { 5, 3, 9, 3, 3, 2, 3, 3 } 的众数为 3；而虽然 3 在向量 { 5, 3, 9, 3, 1, 2, 3, 3 } 中最多，由于我们要求数量严格为一半以上，它就不是众数。众数问题要解决的就是给定一个向量，找到向量中的众数或者返回不存在。
这个问题的解法是我第一次对一个问题的解法印象如此深刻，以至于我从当时一直记到了现在。其他一些有趣算法的解我中间还曾经忘过，这个却从来没有忘过。在校招面试字节跳动的时候，提问了一个这个问题的变种，因为对这个问题印象太深，我很顺利的给出题目的解法。
我们注意到众数要求的是严格数量超过一半以上，这里我们跳过思考过程直接给解法，由于众数在向量中出现的次数必定超过一半，因此将众数与任何同样数量的其他数字一同从向量中移除，在剩下的向量中众数仍然是众数。口水话说，众数人多，就算跟你极限一换一，最后至少还是比你多一个。严格证明这里略去。
在有这样的前提之后，我们从向量的一端逐个遍历，最初的时候将最初的元素作为众数候补并在遍历过程中计数，一旦发现众数候补的数量不超过向量遍历前缀的一半，则把整个前缀一起丢掉，重复刚才的过程。最后，我们或者找到一个众数候补，或者找不到。后者我们显然有不存在众数，而前者我们再对整个向量做一次 O(n) 的检查，看看众数候补是否是真的众数即可，可以对上面两个例子做验证。
这个算法有趣的点在于它第一次让我知道在改变观察视角之后对数据的处理可以多么大胆。朴素的众数解法是对向量的所有数据计数然后逐个判断是否过半，或者先排序在计数然后每次比较相邻两个元素的计数，最后看计数最多的那个是否过半。但是我们转换角度看问题，众数拥有如此强的性质，完全可以用一种极端的同归于尽的方式来选择候补，从而找到一个时间 O(n)，空间 O(1) 的神奇算法。
在前面提到的面试过程中，我们要找的是出现次数超过 1/k 的元素。众数可以看做是 k = 2 的特例。对于这个扩展情形，我们可以维护一个容量为 k – 1 的候补集并初始化候补，当[其他]元素出现时，对候补集集体减一，一旦候补集有空缺，新的元素将加入成为替补。其实还是类似于同归于尽的方案。最后对候补进行验证即可。
就地循环位移
这个问题将数据按照一定的步长循环位移。例如，数组 { 1, 2, 3, 4, 5, 6 } 整体左移 2 位的结果是 { 3, 4, 5, 6, 1, 2 }。这里并不要求数组有序，但是与元素无关，我们不妨将内容用其位置表示。
问题的解法有两种，一种是利用同余将需要移位的元素类似于海豚跳跃那样移动，即按照同余关系分组之后在分组内移动 1 位；另一种更有意思的是以移动步长的位置的元素为分界，左右两端分别 reverse，然后整个数组再 reverse，经过证明可以得到这样的解法也能够达到循环位移的效果。具体的证明和说理这里不展开，两者的主要差距是后者在每次翻转中更利用了数组元素在实际存储的连续性，从而能够激活缓存获得更好的实际效果。这一点在排序算法中也极为重要，典型的如堆排序，虽然拥有 O(nlogn) 的理论最佳复杂度，但是堆的调整确是一个可能横跨多个缓存行的操作，实际效果经常不仅比归并排序差，甚至在某些场景下由于缓存未命中的原因比插入排序还差。这个问题我依稀记得当时还有更复杂的衍生问题，也是基于数据分段 reverse 的，但是记不清了。这个问题在 MOOC 中有非常可爱的图像演示，非常生动。
Floyd 建堆
相当有趣的算法。这个算法其实不复杂，建堆的时候采用下滤代替上滤，就能将算法复杂度由 O(nlogn) 的量级改良到 O(n) 的量级。思考更好方案的动因是堆并不需要完全排序，所以很可能有比排序下界更好的算法；而寻找算法的过程，即将茂盛叶子的上滤改变角度变为稀疏根部的下滤，也是非常有启发性的。
当你看到这样一个朴素算法 O(nlogn) 而且怎么看怎么顺眼的时候，突然冒出来一个 O(n) 的算法，提醒了我们探索极致的效率，发掘隐藏的约束，是永远的追求。
Kruskal 算法与并查集
我从来都没搞懂 Prim 算法是怎么工作的，Kruskal 算法是我一眼就看得懂的算法。其实《数据结构》这本书我记得只讲了 Prim 算法，Kruskal 算法和并查集应该是在刘汝佳的《算法竞赛入门经典（第 2 版）》里看到的。那本也是一本神奇的书，下次有空讲。
我就是感觉列举心中有趣的算法的话，并查集实在是太爱了，Kruskal 算法实在是太好懂了。说起来塞奇威克老爷的《算法》也喜欢开篇讲一长串的并查集，不过那个好复杂，搞不懂。
编辑于 2020-04-07
数据结构
