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 类库",程序员不用浪费时间从零写,时间可以花在更有趣的事情。
又提升了一层抽象!
下周见!