相关文章：计算机科学速成课 17
i.e. Data Structures
上集讲了一些经典算法，比如给数组排序，找图的最短路径，而上集没讲的是 算法处理的数据 存在内存里的格式是什么。
你肯定不想数据像 John Green 的大学宿舍一样乱 ，到处都是食物，衣服和纸，我们希望数据是结构化的，方便读取，因此计算机科学家发明了 “数据结构”！
上集已经介绍了一种基本数据结构：数组（Array），也叫列表（list）或向量（Vector）（在其它编程语言里）。数组的值一个个连续存在内存里，所以不像之前，一个变量里只存一个值（比如 j = 5），我们可以把多个值存在数组变量里。为了拿出数组中某个值，我们要指定一个下标（index），大多数编程语言里，数组下标都从 0 开始，用方括号 [ ] 代表访问数组。如果想相加数组 J 的第一个和第三个元素，把结果存在变量 a，可以写上图这样一行代码。
数组存在内存里的方式十分易懂。
为了简单，假设编译器从内存地址 1000 开始存数组，数组有 7 个数字，像上图一样按顺序存。写 j[0]，会去内存地址 1000 加 0 个偏移，得到地址 1000，拿值：5 ，如果写 j[5]，会去内存地址 1000 加 5 个偏移，得到地址 1005，拿值： 4 。很容易混淆 “数组中第 5 个数” 和 “数组下标为 5 的数”，它们不是一回事，记住，下标 5 其实是数组中第 6 个数，因为下标是从 0 开始算的。
数组的用途广泛。所以几乎所有编程语言都自带了很多函数来处理数组，举例，数组排序函数很常见，只需要传入数组，就会返回排序后的数组，不需要写排序算法。
数组的亲戚是 字符串 (string)，其实就是字母，数字，标点符号等 组成的数组。第 4 集讨论过计算机怎么存储字符，写代码时 用引号括起来就行了 j = "STAN ROCKS" 。虽然长的不像数组，但的确是数组，幕后看起来像这样。
注意，字符串在内存里以 0 结尾。不是"字符 0"，是"二进制值 0"，这叫字符"null"，表示字符串结尾。这个字符非常重要，如果调用 print 函数，print 在屏幕上输出字符串，会从开始位置，逐个显示到屏幕，但得知道什么时候停下来！否则会把内存里所有东西 都显示出来，0 告诉函数何时停下。
因为计算机经常处理字符串，所以有很多函数专门处理字符串，比如连接字符串的 strcat，strcat 接收两个字符串，把第二个放到第一个结尾。
我们可以用数组做一维列表（one dimensional lists），但有时想操作二维数据，比如电子表格，或屏幕上的像素，那么需要 矩阵（Matrix）- 可以把矩阵看成 数组的数组！
一个 3x3 矩阵就是一个长度为 3 的数组 ，数组里每个元素都是一个长度为 3 的数组。可以这样初始化，内存里是这样排列的。为了拿一个值，需要两个下标，比如 j[2][1] ，告诉计算机在找数组 2 里，位置是 1 的元素，得到数字 12 。
矩阵酷的地方是，不止能做 3x3 的矩阵，任何维度都行，可以做一个 5 维矩阵，然后这样访问 a = j[2][0][18][18][3] 。现在你知道了，怎么读一个 5 维矩阵，快去告诉你的朋友！
目前我们只存过单个数字/字符，存进数组或矩阵，但有时，把几个有关系的变量存在一起，会很有用。比如银行账户号和余额，多个变量打包在一起叫 结构体 (Struct)。现在多个不同类型数据，可以放在一起，甚至可以做一个数组，里面放很多结构体，这些数据在内存里会自动打包在一起。如果写 j[0]，能拿到 j[0] 里的结构体，然后拿银行账户和余额。存结构体的数组，和其它数组一样，创建时就有固定大小，不能动态增加大小，还有，数组在内存中 按顺序存储，在中间插入一个值很困难。
结构体可以创造更复杂的数据结构，消除这些限制，我们来看一个结构体，叫 节点 (node)，它存一个变量 - 一个指针（pointer）。“指针” 是一种特殊变量，指向一个内存地址，因此得名。用 节点 可以做 链表（linked list），链表是一种灵活数据结构，能存很多个 节点 (node)，灵活性是通过每个节点 指向 下一个节点实现的。
假设有三个节点，在内存地址 1000，1002, 1008，隔开的原因 可能是创建时间不同，它们之间有其他数据。可以看到第一个节点，值是 7，指向地址 1008，代表下一个节点，位于内存地址 1008，现在来到下一个节点，值是 112，指向地址 1002，如果跟着它，会看到一个值为 14 的节点，这个节点 指回地址 1000，也就是第一个节点，这叫 循环链表 。
但链表也可以是非循环的，最后一个指针是 0 - “null”，代表链表尽头。当程序员用链表时，很少看指针具体指向哪里，而是用链表的抽象模型，就像上图，更容易看懂。
数组大小需要预先定好，链表大小可以动态增减。可以创建一个新节点，通过改变指针值，把新节点插入链表；链表也很容易重新排序，两端缩减，分割，倒序等。超方便！
链表也适合上集的排序算法，因为灵活，很多复杂数据结构 都用链表，最出名的是 队列（queue）和 栈。“队列” 就像邮局排队，谁先来就排前面，虽然你可能只想买邮票，而前面的人要寄 23 个包裹，这叫 先进先出（FIFO）。我指队列，不是指那 23 个包裹。想象有个指针叫"邮局队列"，指向链表第一个节点。第一个节点是 Hank，服务完 Hank 之后 读取 Hank 的指针，把"邮局队列"指向下一个人，这样就把 Hank “出队”（dequeue）了。如果我们想把某人"入队"（enqueue） - 意思是加到队列里，要遍历整个链表到结尾，然后把结尾的指针，指向新人（Nick）。
只要稍作修改，就能用链表做 栈，栈是后进先出 (LIFO)。可以把"栈"想成一堆松饼。做好一个新松饼，就堆在之前上面，吃的时候，是从最上面开始。美味！栈就不叫"入队"“出队"了，叫"入栈”（push） “出栈”（pop）。对，这些是正确术语！
如果节点改一下，改成 2 个指针，就能做 树（tree）。很多算法用了 “树” 这种数据结构。同样，程序员很少看指针的具体值，而是把"树"抽象成这样：最高的节点叫"根节点"（root），“根节点"下的所有节点都叫"子节点”（children）。任何子节点的直属上层节点，叫"母节点"（parent node）。没有任何"子节点"的节点，也就是"树"结束的地方，叫"叶节点"（leaf）
在这里的例子中，节点最多只可以有 2 个子节点，因此叫 二叉树（binary tree）。但你可以随便改，弄成 3 个，4 个，或更多，甚至节点 可以用链表存所有子节点。“树"的一个重要性质是（不管现实中还是数据结构中），“根"到"叶"是 单向 的。如果根连到叶，叶连到根，就很奇怪。
如果数据随意连接，包括循环，可以用"图"表示，还记得上集用路连接城市的"图"吗？这种结构可以用有多个指针的节点表示，因此没有 根、叶、子节点、父节点这些概念，可以随意指向！
以上概述了计算机科学中，最主要的一些数据结构，这些基本结构之上，程序员做了各种新变体，有不同性质。比如"红黑树"和"堆”，我们没时间讲。
不同数据结构适用于不同场景，选择正确数据结构会让工作更简单，所以花时间考虑用什么数据结构是值得的。幸运的是，大多数编程语言自带了预先做好的数据结构。比如，C++有"标准模板库”，Java 有"Java 类库"，程序员不用浪费时间从零写，时间可以花在更有趣的事情。
又提升了一层抽象！
下周见！
