077 | 什么是计算机的数据结构

我们这周还会通过Google和高盛的面试题来介绍CS的原理及其思维方式，不过我们需要先接受CS的专业知识做铺垫。这周要用到的专业知识是计算机的数据结构，它对于专业的计算机人士来讲至关重要，数据结构没有学好，程序写得再快，也是业余水平。类似地做事方式可以推广到其他领域（那下面这些领域的数据结构是什么呢：创业、做产品/服务、一级/二级市场投资，财务、金融、供应链、英语、剑道、健身），掌握了它，就迈出了成为高级专业人士的第一步。

在介绍什么是数据结构之前，先讲两个绘画和摄影的例子。

我不知道你是否爱画画，或者曾经画过画，或者看过专业画家创作的过程。一般人画画通常就直接画了，比如要画水里的两条金鱼就直接从某一个部分开始，从外形画起来了。这种画法的经常结果是，画到后来比例不对，而且常常画得不像。专业画家不是这么画的，他们会把金鱼分解成几个简单的几何图形，比如头是一个大圆和两个小圆（即两个眼睛），身子是一个椭圆，鳍和尾巴是几个三角形。如果是几条金鱼，他会事先把位置安排好，为了画面美观，主要景物的布置可能要符合一些几何图形的形状，这一点我等会还会举例子。这些都用淡淡的铅笔或者淡墨勾好了，才把圆、椭圆和三角形经过平滑过渡，画成金鱼（在绘画里，思路像是，先把大概的框架搭建好）。不掌握这种绘画方法，永远走不进专业的大门。

在绘画和摄影当中，这些基本的几何图形使用的远比一般人想象的多得多，特别是在构图上，只不过当最终的作品完成时，你看不太出来最早的构图框架而已。在欣赏艺术品的时候，专业人士和一般人士也是有区别的。前者很快能看出作品构图的方法，各个部分之间的几何关系，他们在学习时会琢磨先前那些大师们匠心独运之处(“Ultimately, it all comes down to the taste, it all comes down to the taste.”)。而普通人看画则看不出来，也很少在意，他们会更关注一幅画画得像不像，颜色是否抢眼球。这也是很多人会觉得某幅画或者艺术作品创作得特别好，但说不出理由的原因。

举两个具体的例子。下面这张画是浪漫主义的开山鼻祖Gericault的《美杜莎之筏》(The Raft of the Medusa) 

关于这幅画为什么重要，这里由于篇幅的原因以后讲。但这次要向你介绍它的构图，它最高层的构图设计就是两个金字塔形状，下图就是靠着两个三角形的金字塔，画面保持了平衡。 

类似地，在米开朗基罗代表作《圣母怜子》中，他把圣母塑造成了悲天悯人的少女形象，但是为了体现神圣庄重，他也采用了金字塔造型。当然大艺术家采用各种基本几何结构构图未必需要打稿时画在图上，而是了然于胸。对于几何形状不太了解，不能从现实中的事物抽象出简单的几何形状（骨架）的人，完成了不少复杂的绘画，即使话简单的东西，也画不好。也就是说，不入门（噢噢噢，仔细拆解这句话“不能从现实的事物中抽象出简单的几何形状的人”，类似地思维方式也可以推广到其他领域啊）。 
​

对于CS来讲，写一个能够完成特定功能的程序，就相当于是作一幅画。因此，它也有两种方法，一种是直接就用一行行代码去实现功能，这是低水平的做法（哈哈哈，我能做到这一步就开心极了），有些时候看上去做得快，实际上漏洞百出（用专业术语讲就是Bug很多），回头需要修补。另一种就是理解需求之后，抽象出具体的基本几何形状这样的基础块（Hmmm，那module具体refer的是什么呢？），然后用算法将这些模块进行组合，写出符合需求的程序。

当然，这些基本模块也像绘画和雕塑中作为轮廓的几何图形一样，需要根据画面需求平滑过渡，而不是照搬照抄。这些程序中基本的几何图形，就是计算机的数据结构（卧槽，没想到）。如果说一幅画是点的有机组合，几何图形反应出点之间常用的具体关系，那么在CS中，数据就等同于点，数据结构就是数据中常用的具体关系。这样你就理解了什么是数据结构。世界著名的计算机科学家、因为发明帕斯卡程序语言（PASCAL）而获得图灵奖的N·沃斯（N Wirth）教授写过一本书，叫做《数据结构 + 算法 = 程序》，很好地讲清楚了这三者的关系

在这一周里，我们要介绍两种最常用的数据结构，这样大家会具体的感受。

第一种是数据的线性表。这相当于几何图形中的直线，它也是最基本的数据结构。线性表这种抽象的数据结构并非起源于科学计算本身，而是计算机早期的应用 —— 办公自动化。我们知道，虽然发明计算机的目的是为了科学计算，但是它最早期的商业应用则是在管理和商业方面（是啊，有道理，需求逼出的创新）。在商业上，报表是一种最常见的数据组织形式（噢噢噢，原来报表抽象来看就是数据组形式），在管理上，最多的见的则是人员或者物资的记录等等。它们都可以被抽象为线性的数据，然后按照1、2、3、4、5的顺序排列出来。

比如一所大学所有学生的档案，就是这样一个个按照顺序排列的，而他们的编号就是学号。因此，很有必要设计一种抽象的数据结构概括所有这些顺序排列和储存的数据，它就是线性表。当然，随着计算机的数据规模的扩张，未必能给所有的数据都赋予一个编号顺序，结构化地存储，但是它们依然遵循一个顺序的特征。比如一个电商交易的日志记录，它是按照所发生的时间顺序，一条条线性地记录下来（linearly或non-linearly、线性或者非线性，每次听到这种词，都有一种很屌的感觉），因此，线性表的性质它们也有。

线性表本身是一个抽象的概念，在计算机中则是通过很多具体的方法实现的。最常见的一种实现方法就是所谓的数组(Array)，学习CS的人对此都非常数据。数组这个概念很简单，就是一组编了号的固定大小的单元。比如我们说一个具有1000个整数的数列，从a0，a1，a2 ，……，一直到a999。这就是Array（数组）。（感觉和金融很像诶，很多高大上的terms，其实都是对普罗大众嘴边日常生活tips的抽象总结，然后给你一种爆有逼格的感觉）。Array（数组）的好处是给定一个序号，可以直接找出里面的内容。比如，一个数组存着一个单位员工的信息，只要给出员工的工号，就能调出他的信息并且编辑修改。但是，数组这种数据结构有一个大的缺陷，就是在其中插入一个新的数据非常难。（用Excel呢？）比如客户经理常用一个Array来存放这周要去拜访的所有客户，如果他突然有一个未在计划中的客户必须要去拜访，如果他打算把这个客户插入到原来了的第五个客户和第六个客户之间。那么要在数组中塞进去这个新的客户其实并不容易，因为他需要把第六个客户从数组中的第六个位置挪到第七个，留出位置给这个新的客户。当然，也就需要把第七个挪到第八个的位置，第八个挪到第九个的位位置，以此类推。（对的，对的，这就是我当时学CS时特别强烈的感受，很多平时日常很简单的操作比如一些一句话就能让别人明白修改，完完全全没办法一句话让计算机明白，呵呵。）如果一个数组有上百万个记录，这么挪实在太浪费时间了。

为了弥补这个不足，科学家发明了一种被称为链表的线性数据结构。所谓链表，其实就如同我们买东西时排队一样，每个人只要记得前面或者后面的一个人是谁就可以了，彼此没有编号一说。比如要记录下这周造访的客户名单，王二之后是张三，张三之后是李四，李四之后是赵六…如果要把新加入的王五和安排在李四和赵六之间，很简单，只要修改一下这个链表，把李四后面的指针指向王五，把王五后面的指针指向赵六即可（要是有个gif版的图示就好了）。这样一来，插入一个新的数据就是一件很容易的事了。

但是，凡事有一利就有一弊，如果我们要找出列表中第五个造访的客户是谁，因为没有编号一说，因此必须要从头数一遍，一直数到第五个。如果一个列表有几百万个记录单元，数一遍可是很花时间的事情。那么对线性的数据，是否有更好一点，能够兼有前面的优点，而没有其缺点的数据结构呢？（这么好呀）到目前来讲还没有（可不是嘛，怎么能既让马儿跑又让马儿不吃草），而且估计以后也不会有，因为世界上凡事都不是十全十美的。对于这样简单的、有用但却不完美的数据结构，应该怎样弥补它的不足呢？这就是搞算法的人的工作了。（噢！原来这是边界线啊）

为了便于大家理解线性表，我再做一个类比：数据相当于盖房子，一块块整整齐齐地码着（stack!）。链表则相当于一个没有页号的活页夹笔记本，拿走一页纸，加入一页纸都很肉还有。它们都是搭建CS这个大厦的基本几何形状。

总结一下：

• 1. 专业人士和业余人士做东西的一个重要差别在于，前者掌握了如何使用基本图形，结构和组成部分来构建复杂设计和产品的方法，后者根据自己的脑子里的构思和直觉，直接构建最终的产品和设计。要想完成复杂的工作，必须掌握所谓科班出身人士掌握的工具和方法。(yes，不一定非要去从头读一遍科班，但要深入的理解和消化他们掌握的工具和方法，甚至是哲学）。另外，专业人士会把复杂的东西分解为简单的基本单元。
• 2. 在CS领域，数据结构则相当于设计中的基本几何图形，它们大多数是从具体的应用中抽象出来的，一个从业者水平的高下，首先在于领域使用这些数据结构的本领。
• 3. 凡事有一利就有一弊（every action has its equal opposite reaciton / Newtow’s third, Fa = - Fb, you got to leave something behind to get somewhere.），在计算机方面几乎任何设计都是如此，好的工程师并不是不切实际地追求没有弊病的设计，而是想其它办法补救相应的问题。

明天我会介绍计算机科学中另一个重要的数据结构 —— Binary Tree，有了这个概念，我们就可以讲几道面试题了。

Q（思考题）：从专业艺术家创作的方法出发，谈谈你所了解的专业人士在做事时和业余人士有什么不同？

• 1. Interview Question from Goldman Sachs： 有25名短跑选手比赛竞争金银铜牌，赛场上有5条赛道，因此一次可以有5个人同时比赛。比赛并不计时，只看相应的名次。假如选手的发挥是稳定的，也就是说如果John比张三跑得快，就那么John一定比Kelly跑得快。问题是，最少需要几组比赛才能决出前三名？
• 2. Interview Question from Google：如何设计一个地图的功能，找到离当前位置最近的5个加油站？（哇，这个feature好实用啊，我天天都在用哎！）

​