数据结构与算法入门

粥可以用碗装，也可以用袋子装；馒头可以用袋子装，也可以用盒子装。用碗装粥和用袋子装粥，在不同的使用场景下，有各自的优劣之处。我们也可以用纸包包子、包馒头，但是，用纸包粥，显然就是不适合的。

对于计算机中的数据，也是如此。对于不同的数据，我们需要考虑数据的大小、形式，以及其使用场景，来决定适合的存储方式。

数据结构是在计算机中存储、组织数据的方式。程序运行离不开数据结构，不同的数据结构又各有优劣，能够处理的问题各不相同，而根据具体问题选取合适的数据结构，可以大大提升程序的效率。所以，学习各种各样的数据结构是很有必要的。

存储一个变量

之前我们说到，计算机中存储的信息都是数字。那么要存储这些数字，就需要有相应的格式。比如有“16”“23”“185”三个数，它们写作二进制分别是“10000”“10111”“101111001”。如果我们分别存储这几个二进制数，那么分别用 2 个 5 位二进制数的空间和 1 个 8 位二进制数的空间即可。这样，我们需要分别记住，前两个数的长度是 5 位、后一个数的长度是 8 位，这样才能在需要时不多不少刚好得到我们存储的信息。

不过，这样子很显然不够方便，需要不少额外的信息来记录每一个变量的长度。所以我们统一用 8 位二进制数来存储这几个数。这样，就算我们把他们放在一起，也不用额外的信息就能清楚，这串数据里面，每 8 位即为一个数。实际上，一般计算机在存储和索引数据时，最小的单位即为 8 位，也就是一个字节（Byte）。

对齐存放虽然浪费了一些空间，但是对于存储、处理数据来说就方便多了。一般有几个常用的格式，其长度可能为 8 位、16 位、32 位、64 位等，我们需要根据实际的使用情况选择合适大小的容器。

在存储数据时，也有一定的规范。对于自然数来说，我们可以将其转换为二进制，直接就可以放进我们之前所谓的容器中。而对于负整数，事情就变得复杂一些了。我们可以选择用一个“符号位”来标记该数为负。但实际上，计算机中采用的是一种叫做“补码”的方式，这种方式在进行计算时更为高效，这里暂时不展开讨论。而对于小数，则更为复杂。任何人都可以想出一种方式来将小数以二进制方式存储。而为了方便交流，我们需要统一各数位所代表的含义，比如 IEEE 754 规范。

当数据超出了其格式所能容纳的范围，就是所谓的“溢出（overflow）”现象。举个例子，32 位二进制数所能表示的最大的自然数为 2 的 32 次幂（\(2^{32}\)）。而当我们对这个数进行“加 1”操作后，其第 1 至 32 位均变为了 0，而第 33 位变成了 1。但由于我们只有 32 位的空间，这次加法所产生的第 33 位的数据不能被存储，因此数据变成了 0。

顺序存储与链式存储

想象排成一排的若干房间，它们之间是相互毗邻的，123 号的下一个房间就是 124 号；每个房间的大小也是一致的，假如每个房间的宽度是 1 米、最开始处是 0 号房间，那么第 0 米处就是第 0 个房间，第 50 米处就应该是第 50 个房间。

这和计算机内存中数据的存储是很相像的。每一个内存单元都被编号，我们可以通过编号轻易的计算出地址，寻找到准确的位置。因此，顺序存储和数据实际的存储方式很是相仿。

顺序存储依赖元素在实际存储环境下的相对位置（或者说物理上的相对位置）以确定元素之间的先后关系。因此，我们能通过简单的计算，轻松寻找到第 n 个内容的所在位置。我们把这种访问方式称之为“随机访问”。但是，这就要求我们，存储的数据字段必须是相同的长度。而且当我们想要修改元素之间的先后关系时，就需要对涉及到的元素进行移动，以维持物理上的先后关系；比如交换两个元素的位置，就需要对两个位置进行擦写操作（甚至需要一个额外的位置来作为中转场地）。而当涉及到插入、删除时，情况就更严重了：假如要在 123 和 124 号之间插入一块内容，那么所有 123 号之后的内容都要向后移动；当内容数量庞大时，这项移动无疑是一项巨大的工程。当要删除一个内容时，也是同理，需要将大量的元素往前移动。

于是就有了链式存储。这种方式通过在数据段之外额外加上位置信息来记录元素之间的位置信息。比如，班级里的同学排成一串，其中“小刚”记得自己的前面是“小明”，“小明”记得自己的前面是“小王”……如此，每个同学都记得自己的前一位同学是谁。这样，我们只需要找到队伍的最后一名同学，就能还原整个队伍。

这个例子建立在我们能够通过名字直接找到对应的同学的基础上。在计算机的内存中，我们只能通过地址直接找到对应的信息，否则需要逐个比对，才能确认某个位置的信息是我们需要寻找的。

这个场景放在计算机里，就是每个元素除了记录本身的数据外，还要记录与其相邻下一个元素在内存中的位置（在内存中的地址）。这种存储方式依赖地址关系，将元素链接成串，故称为链式存储。

链式存储在元素的插入和删除方面有着优势。比如，我们想在“小明”和“小王”之间插入“小张”，那么“小明”只需要将自己记忆中前面的同学改为“小张”，再令“小张”记忆自己前面的同学是“小王”即可。即，我们只需要更改元素记录的位置信息，即可修改元素之间的相对位置关系。

而链式存储的不足在于，假如我们想知道“小明”在队伍中的第几个，并不能直接通过其实际位置得到这个问题的结果，而必须从最后的同学开始逐个访问，直到访问到“小明”为止。

并且，我们上述提到的，只是记录了每个元素前者的位置，这种结构一般称之为“单链”。这样的话，当我们已知某个位置是“小明”后，只能得知其下一位同学的所在，并不能直接得知其之前为哪位同学。为了解决这个问题，我们可以增加一个字段，以便同时记录某一元素“前后”两者的位置，这样的结构称之为“双链”。

顺序表与链表

在计算机中，我们会把连续的数据称作“表”。当我们实际用顺序存储与链式存储两种思想分别存储数据时，所得的即为“顺序表”和“链表”。由于这些数据只在一个方向上有联系，所以我们也合称两者为“线性表”。

之所以采用“思想”来形容两种方式，是因为链表也可以通过顺序存储的方式来实现，这种链表通常称之为“静态链表”。与之相对的“动态链表”往往需要根据使用情况进行“动态内存分配”来获得新的空间或者释放不再需要的空间。而“静态链表”使用的是预先分配好的固定大小的一块空间，可以视作一个简化版的计算机内存，在这种情况下，内存的获取与归还则需要通过编程者的操作来实现，而不是操作系统的“动态内存分配”。一般来说，“静态”意味着使用的是事先分配好的空间，因此可能更容易发生越界的情况。

数据结构与容器

在基础的数据存储上，人们设计出了多种多样的数据结构，这些数据结构通常是规定了一些添加与删除的限制，以满足实际使用中的各种需求。

在编程中，我们将能够存放数据、并且提供好操作接口的类型称作“容器（Container）”。其中，有“顺序容器（Sequential Container）”和“关联容器（associative container）”。

顺序容器

在顺序容器中，元素之间的顺序是必要的。或者说，当我们对数据的顺序有要求时，则需要采用顺序方式存储。比如，一场赛跑中依次到达终点线的选手，或者某一年中从 3 月到 8 月的月均温度。

栈

栈（Stack），其修改遵循“后进先出”的原则，因此又称 LIFO 表，即“last in first out”的缩写。

如何理解这句话呢？专业一点的话说，就是我们只能在“栈顶”进行“压入（push）”和“弹出（pop）”操作。用具体的例子来理解就是，比如有若干有编号的饼干和一个杯口刚好能放进饼干的圆柱形杯子，这样，我们只能从杯口放入或取出饼干，每次放入的饼干只能在杯底或者已有饼干的最上方，而只能取出最上端的饼干。比如我们依次放入编号“23”“8”“15”的饼干，再依次取出，则取出饼干的编号的顺序为“15”“8”“23”。

当我们讨论“后进先出”“先进先出”的时候，针对的是容器内的当前状态。比如，向一个栈中压入“5”，紧接着再弹出，得到“5”；然后压入“3”，紧接着再弹出，得到“3”。从整体上看，“5”是最先弹出的，而“3”是最后进入的，显然，这样理解是错误的。

关于具体的栈的实现，我们可以使用顺序存储结构，也可以使用链式存储结构。同前文的静态链表，顺序存储结构往往意味着相对更加有限的空间，需要注意处理越界的情况。

队列

队列（queue），其修改遵循“先进先出”的原则，也称 FIFO 表，即“first in first out”的缩写。

关于队列，我们可以考虑现实生活中排队的场景。假设没有人插队。那么先来排队的人，一定先完成任务并出队。用专业一点的语言来归纳，即队列只能在队尾添加/压入元素，在队首删除/弹出元素。顾名思义，队列这种结构通常用来存储待处理的一些数据或任务。

也有一些特殊的队列。比如双端队列（double-ended queue），该种队列允许分别在队首和队尾进行添加和删除操作。再比如优先队列，这种队列的出队、入队操作和元素的优先级有关。

无序容器

当我们不关心数据的顺序时，则可以采取无序容器来存储。常见的场景即为“集合”——集合中的元素具有无序性。比如，某校 1 班中报名参加信息学竞赛的学生。

尽管数据是无序的，但是在计算机中，它们依旧会以某种特定的顺序来存储。

关联容器

对于顺序容器而言，其内部元素的存储是有一定顺序的。我们在使用时，关注的往往是元素的顺序，比如字符串（一连串字符），或者事物的排名。而有些时候，我们关注的是数据之间的对应关系，而不是它们的顺序。也就是说，我们需要根据具体的数据来存储和访问数据。满足这样需求的容器就叫做关联容器。

比如，我们想记录若干水果蔬菜的颜色——“苹果”是“红色”，“青菜”是“绿色”，“西兰花”是“绿色”，“梨”是“黄色”，“樱桃”是“红色”……也就是说，我们不再关注“红色”“绿色”等颜色的顺序，而是“苹果”“青菜”等的颜色。即，我们能够通过“苹果”这个“键（Key）”得到“红色”这个“值（Value）”。同时，我们也明白，“值”可以重复，但是“键”的值必须是唯一的。

哈希法

事实上，这些“键值对”在存储时，往往还是按照顺序存储的方式来存储。但为了效率，我们不希望通过逐个比较每个键值对的键，来得到我们想要的值。为此，我们通常使用一种特定的“哈希函数”，其值域往往是自然数集的一个子集。于是，我们可以将数据处理为一定区间内的一个数值，这个过程也叫做“哈希散列”。然后我们就可以把键所对应的值的内容存在相对应的位置上。为了不出现问题，我们需要保证相同的数据拥有一致的哈希值。

我们自然希望，哈希散列能帮助我们将若干键值对均匀的分布在一定的区间上。但事情往往没有这么简单。通常，若干不同的参数经过哈希函数可能会得到相同的值。这就导致了“哈希冲突”。事实上，哈希散列就好像将诸多数据粗略分成了若干堆，在用哈希函数处理键过后，我们只能找到匹配的若干键值对，而在这些键值里面，我们还需要再查找和待匹配数据相同的项。只不过，当数据量比较少，或者比较凑巧时，拥有相同哈希值的项只有 0 个和 1 个，看起来就是理想的“散列”情况。

我们要根据具体情况设计合适的哈希函数。哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。在现实生活中，“手机尾号”的例子就是一种哈希散列的应用。通常，我们会取手机号的末 4 位，因为手机号的末 4 位不算太长，容易计算而得（相对于取模而言），并且在一定范围的人群内不易重复，足以区分开不同用户。

二分法

为了键的减少比较次数，除了哈希散列，我们还可以采用其他方法。常用的有二分法。给定一个数，先和已有数值（按递增排序）位居中间的那一个比较：若等于，则直接命中；若大于，则说明待查找的值可能在右侧区间；若小于，则说明待查找的值可能在左侧区间。重复上述过程，直到查找到目标数据的位置，或者确定已有数值中不存在待查找的值。

描述数据的语言

编程语言中所操作的数据对象，往往可以通过由关联容器和顺序容器的组合表示出来。

比如，我们可以使用 JSON 来描述电话簿里面的若干联系人。其中，每个联系人除了姓名、称谓等属性外，可能有若干个联系方式。

在 JSON 中，我们用一个花括号 {} 内的键值对来描述一个对象的属性，使用方括号 [] 来表示一个列表，以包含若干有序的值或对象。键名为字符串，键值可以为值（数值或字符串）、列表或者另一个对象。

{
    "id": "My Contact Book",
    "items": [
        {
            "name": "Jane",
            "job": "teacher",
            "contacts": [
                {"Tel": "000-246813579"},
                {"IM": "12345abc"},
                {"Mobile": "135792468"}
            ]
        },
        {
            "name": "John",
            "job": "Worker",
            "contacts": [
                {"Mobile": "1234567"}
            ]
        }
    ]
}

由于应用程序的一些不同模块的不同运行配置通常为若干有层级、有组织的键值对，JSON 也常被用作应用程序配置文件的记录格式。

之前介绍到，可以使用命令行参数影响程序的运行。很多程序也会使用配置文件的方式来影响自身的运行，比如记录程序状态、记录用户相关个性化信息等。

除此之外，INI、TOML、YML 等也是常用的格式。

TOML 是“Tom's Obvious, Minimal Language”的首字母缩写，是一种与 JSON 相比较易于书写的配置文件格式。

参考资料

• 数据结构 - OI Wiki：https://oi-wiki.org/ds/