From Unsplash

什么是数据结构决定了数据的顺序和位置关系

数据存储于计算机的内存中。内存如右图所示，形似排成 1 列的箱子，1 个箱子里存储 1 个数据。

数据存储于内存时，决定了数据顺序和位置关系的便是“数据结构”。

电话簿的数据结构

▶ 例①：从上往下顺序添加

举个简单的例子。假设我们有 1 个电话簿——虽说现在很多人都把电话号码存在手机里，但是这里我们考虑使用纸质电话簿的情况——每当我们得到了新的电话号码，就按从上往下的顺序把它们记在电话簿上。

假设此时我们想给“张伟”打电话，但是因为数据都是按获取顺序排列的，所以我们并不知道张伟的号码具体在哪里，只能从头一个个往下找（虽说也可以“从后往前找”或者“随机查找”，但是效率并不会比“从上往下找”高）。如果电话簿上号码不多的话很快就能找到，但如果存了 500 个号码，找起来就不那么容易了。

▶ 例②：按姓名的拼音顺序排列

接下来，试试以联系人姓名的拼音顺序排列吧。因为数据都是以字典顺序排列的，所以它们是有“结构”的。

使用这种方式给联系人排序的话，想要找到目标人物就轻松多了。通过姓名的拼音首字母就能推测出该数据的大致位置。

那么，如何往这个按拼音顺序排列的电话簿里添加数据呢？假设我们认识了新朋友“柯津博”并拿到了他的电话号码，打算把号码记到电话簿中。由于数据按姓名的拼音顺序排列，所以柯津博必须写在韩宏宇和李希之间，但是上面的这张表里已经没有空位可供填写，所以需要把李希及其以下的数据往下移 1 行。

此时我们需要从下往上执行“将本行的内容写进下一行，然后清除本行内容”的操作。如果一共有 500 个数据，一次操作需要 10 秒，那么 1 个小时也完成不了这项工作。

▶ 两种方法的优缺点

总的来说，数据按获取顺序排列的话，虽然添加数据非常简单，只需要把数据加在最后就可以了，但是在查询时较为麻烦；以拼音顺序来排列的话，虽然在查询上较为简单，但是添加数据时又会比较麻烦。

虽说这两种方法各有各的优缺点，但具体选择哪种还是要取决于这个电话簿的用法。如果电话簿做好之后就不再添加新号码，那么选择后者更为合适；如果需要经常添加新号码，但不怎么需要再查询，就应该选择前者。

▶ 将获取顺序与拼音顺序结合起来怎么样

我们还可以考虑一种新的排列方法，将二者的优点结合起来。那就是分别使用不同的表存储不同的拼音首字母，比如表 L、表 M、表 N 等，然后将同一张表中的数据按获取顺序进行排列。

这样一来，在添加新数据时，直接将数据加入到相应表中的末尾就可以了，而查询数据时，也只需要到其对应的表中去查找即可。

因为各个表中存储的数据依旧是没有规律的，所以查询时仍需从表头开始找起，但比查询整个电话簿来说还是要轻松多了。

选择合适的数据结构以提高内存的利用率

数据结构方面的思路也和制作电话簿时的一样。将数据存储于内存时，根据使用目的选择合适的数据结构，可以提高内存的利用率。

本文将会讲解 7 种数据结构。如开头所述，数据在内存中是呈线性排列的，但是我们也可以使用指针等道具，构造出类似“树形”的复杂结构。

1.链表

链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。

这就是链表的概念图。Blue、Yellow、Red 这 3 个字符串作为数据被存储于链表中。每个数据都有 1 个“指针”，它指向下一个数据的内存地址。

在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内。

因为数据都是分散存储的，所以如果想要访问数据，只能从第 1 个数据开始，顺着指针的指向一一往下访问（这便是顺序访问）。比如，想要找到 Red 这一数据，就得从 Blue 开始访问。

这之后，还要经过 Yellow，我们才能找到 Red。

如果想要添加数据，只需要改变添加位置前后的指针指向就可以，非常简单。比如，在 Blue 和 Yellow 之间添加 Green。

将 Blue 的指针指向的位置变成 Green，然后再把 Green 的指针指向 Yellow，数据的添加就大功告成了。

数据的删除也一样，只要改变指针的指向就可以，比如删除 Yellow。

这时，只需要把 Green 指针指向的位置从 Yellow 变成 Red，删除就完成了。虽然 Yellow 本身还存储在内存中，但是不管从哪里都无法访问这个数据，所以也就没有特意去删除它的必要了。今后需要用到 Yellow 所在的存储空间时，只要用新数据覆盖掉就可以了。

解说

对链表的操作所需的运行时间到底是多少呢？在这里，我们把链表中的数据量记成n。访问数据时，我们需要从链表头部开始查找（线性查找），如果目标数据在链表最后的话，需要的时间就是O(n)。

另外，添加数据只需要更改两个指针的指向，所以耗费的时间与n 无关。如果已经到达了添加数据的位置，那么添加操作只需花费O(1) 的时间。删除数据同样也只需O(1) 的时间。

参考：3-1 线性查找

补充说明

上文中讲述的链表是最基本的一种链表。除此之外，还存在几种扩展方便的链表。

虽然上文中提到的链表在尾部没有指针，但我们也可以在链表尾部使用指针，并且让它指向链表头部的数据，将链表变成环形。这便是“循环链表”，也叫“环形链表”。循环链表没有头和尾的概念。想要保存数量固定的最新数据时通常会使用这种链表。

另外，上文链表里的每个数据都只有一个指针，但我们可以把指针设定为两个，并且让它们分别指向前后数据，这就是“双向链表”。使用这种链表，不仅可以从前往后，还可以从后往前遍历数据，十分方便。

但是，双向链表存在两个缺点：一是指针数的增加会导致存储空间需求增加；二是添加和删除数据时需要改变更多指针的指向。

2. 数组

数组也是数据呈线性排列的一种数据结构。与前一节中的链表不同，在数组中，访问数据十分简单，而添加和删除数据比较耗工夫。这和刚开始讲到的姓名按拼音顺序排列的电话簿类似。

这就是数组的概念图。Blue、Yellow、Red 作为数据存储在数组中。

数据按顺序存储在内存的连续空间内。

由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫作“随机访问”）。

比如现在我们想要访问Red。如果使用指针就只能从头开始查找，但在数组中，只需要指定a[2]，便能直接访问Red。

但是，如果想在任意位置上添加或者删除数据，数组的操作就要比链表复杂多了。这里我们尝试将Green 添加到第2 个位置上。

首先，在数组的末尾确保需要增加的存储空间。

为了给新数据腾出位置，要把已有数据一个个移开。首先把Red 往后移。

然后把Yellow 往后移。

最后在空出来的位置上写入Green。

添加数据的操作就完成了。

反过来，如果想要删除Green……

首先，删掉目标数据（在这里指Green）。

然后把后面的数据一个个往空位移。先把Yellow 往前移。

接下来移动Red。

最后再删掉多余的空间。这样一来Green 便被删掉了。

解说

这里讲解一下对数组操作所花费的运行时间。假设数组中有n 个数据，由于访问数据时使用的是随机访问（通过下标可计算出内存地址），所以需要的运行时间仅为恒定的O(1)。

但另一方面，想要向数组中添加新数据时，必须把目标位置后面的数据一个个移开。所以，如果在数组头部添加数据，就需要O(n) 的时间。删除操作同理。

补充说明

在链表和数组中，数据都是线性地排成一列。在链表中访问数据较为复杂，添加和删除数据较为简单；而在数组中访问数据比较简单，添加和删除数据却比较复杂。

我们可以根据哪种操作较为频繁来决定使用哪种数据结构。

3.栈

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。

这就是栈的概念图。现在存储在栈中的只有数据Blue。

然后，栈中添加了数据Green。

接下来，数据Red 入栈。

从栈中取出数据时，是从最上面，也就是最新的数据开始取出的。这里取出的是Red。

如果再进行一次出栈操作，取出的就是Green了。

解说

像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为Last InFirst Out，简称LIFO。

与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才行。

应用示例

栈只能在一端操作这一点看起来似乎十分不便，但在只需要访问最新数据时，使用它就比较方便了。

比如，规定（AB（C（DE）F）（G（（H）I J）K））这一串字符中括号的处理方式如下：首先从左边开始读取字符，读到左括号就将其入栈，读到右括号就将栈顶的左括号出栈。此时，出栈的左括号便与当前读取的右括号相匹配。通过这种处理方式，我们就能得知配对括号的具体位置。

另外，深度优先搜索算法，通常会选择最新的数据作为候补顶点。在候补顶点的管理上就可以使用栈。

4.队列

与前面提到的数据结构相同，队列中的数据也呈线性排列。虽然与栈有些相似，但队列中添加和删除数据的操作分别是在两端进行的。就和“队列”这个名字一样，把它想象成排成一队的人更容易理解。在队列中，处理总是从第一名开始往后进行，而新来的人只能排在队尾。

这就是队列的概念图。现在队列中只有数据Blue。

然后，队列中添加了数据Green。

紧接着，数据Red 也入队了。

从队列中取出（删除）数据时，是从最下面，也就是最早入队的数据开始的。这里取出的是Blue。

如果再进行一次出队操作，取出的就是Green了。

解说

像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为First InFirst Out，简称FIFO。

与栈类似，队列中可以操作数据的位置也有一定的限制。在栈中，数据的添加和删除都在同一端进行，而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。

应用示例

“先来的数据先处理”是一种很常见的思路，所以队列的应用范围非常广泛。比如广度优先搜索算法，通常就会从搜索候补中选择最早的数据作为下一个顶点。此时，在候补顶点的管理上就可以使用队列。

5.哈希表

在哈希表这种数据结构中，使用“哈希函数”，可以使数据的查询效率得到显著提升。

哈希表存储的是由键（key）和值（value）组成的数据。例如，我们将每个人的性别作为数据进行存储，键为人名，值为对应的性别。

为了和哈希表进行对比，我们先将这些数据存储在数组中。

此处准备了6 个箱子（即长度为6 的数组）来存储数据。假设我们需要查询Ally 的性别，由于不知道Ally 的数据存储在哪个箱子里，所以只能从头开始查询。这个操作便叫作“线性查找”。

提示：一般来说，我们可以把键当成数据的标识符，把值当成数据的内容。

0 号箱子中存储的键是Joe 而不是Ally。

1 号箱子中的也不是Ally。

同样，2 号、3 号箱子中的也都不是Ally。

查找到4 号箱子的时候，发现其中数据的键为Ally。把键对应的值取出，我们就知道Ally 的性别为女（F）了。

数据量越多，线性查找耗费的时间就越长。由此可知：由于数据的查询较为耗时，所以此处并不适合使用数组来存储数据。

使用哈希表便可以解决这个问题。首先准备好数组，这次我们用5 个箱子的数组来存储数据。

尝试把Joe 存进去。

使用哈希函数（Hash）计算Joe 的键，也就是字符串“Joe”的哈希值。得到的结果为4928（哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景）。

将得到的哈希值除以数组的长度5，求得其余数。这样的求余运算叫作“mod 运算”。此处mod 运算的结果为3。

因此，我们将Joe 的数据存进数组的3 号箱子中。重复前面的操作，将其他数据也存进数组中。

Sue 键的哈希值为7291，mod 5 的结果为1，将Sue 的数据存进1 号箱中。

Dan 键的哈希值为1539，mod 5 的结果为4，将Dan 的数据存进4 号箱中。

Nell 键的哈希值为6276，mod 5 的结果为1。本应将其存进数组的1 号箱中，但此时1 号箱中已经存储了Sue 的数据。这种存储位置重复了的情况便叫作“冲突”。

遇到这种情况，可使用链表在已有数据的后面继续存储新的数据。

Ally 键的哈希值为9143，mod 5 的结果为3。本应将其存储在数组的3 号箱中，但3 号箱中已经有了Joe 的数据，所以使用链表，在其后面存储Ally 的数据。

Bob 键的哈希值为5278，mod 5 的结果为3。本应将其存储在数组的3 号箱中，但3 号箱中已经有了Joe 和Ally 的数据，所以使用链表，在Ally 的后面继续存储Bob 的数据。

像这样存储完所有数据，哈希表也就制作完成了。

接下来讲解数据的查询方法。假设我们要查询Dan 的性别。

为了知道Dan存储在哪个箱子里，首先需要算出Dan键的哈希值，然后对其进行mod运算。最后得到的结果为4，于是我们知道了它存储在4号箱中。

查看4 号箱可知，其中的数据的键与Dan 一致，于是取出对应的值。由此我们便知道了Dan 的性别为男（M）。

那么，想要查询Ally 的性别时该怎么做呢？为了找到它的存储位置，先要算出Ally键的哈希值，再对其进行mod运算。最终得到的结果为3。

然而3 号箱中数据的键是Joe 而不是Ally。此时便需要对Joe 所在的链表进行线性查找。

于是我们找到了键为Ally 的数据。取出其对应的值，便知道了Ally 的性别为女（F）。

解说

在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。

如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间非常重要。

补充说明

在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。

除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是“开放地址法”。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通过多次使用哈希函数或“线性探测法”等方法计算候补地址。

另外，哈希函数中“无法根据哈希值推算出原值”。不过，这只是在把哈希表应用于密码等安全方面时需要留意的条件，并不是使用哈希表时必须要遵守的规则。

因为哈希表在数据存储上的灵活性和数据查询上的高效性，编程语言的关联数组等也常常会使用它。

6.堆

堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。

这就是堆的示例。结点内的数字就是存储的数据。堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。

在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。

我们试试往堆里添加数字5。

首先按照02的说明寻找新数据的位置。该图中最下面一排空着一个位置，所以将数据加在此处。

如果父结点大于子结点，则不符合上文提到的规则，因此需要交换父子结点的位置。

这里由于父结点的6 大于子结点的5，所以交换了这两个数字。重复这样的操作直到数据都符合规则，不再需要交换为止。

现在，父结点的1 小于子结点的5，父结点的数字更小，所以不再交换。

这样，往堆中添加数据的操作就完成了。

从堆中取出数据时，取出的是最上面的数据。这样，堆中就能始终保持最上面的数据最小。

由于最上面的数据被取出，因此堆的结构也需要重新调整。

按照01 中说明的排列顺序，将最后的数据（此处为6）移动到最顶端。

如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换。

这里由于父结点的6大于子结点（右）的5大于子结点（左）的3，所以将左边的子结点与父结点进行交换。重复这个操作直到数据都符合规则，不再需要交换为止。

现在，子结点（右）的8 大于父结点的6 大于子结点（左）的4，需要将左边的子结点与父结点进行交换。

这样，从堆中取出数据的操作便完成了。

解说

堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O(1)。

另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log₂n ，那么重构树的时间复杂度便为O(logn)。

添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是O(logn)。

应用示例

如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。比如狄克斯特拉算法，每一步都需要从候补顶点中选择距离起点最近的那个顶点。此时，在顶点的选择上就可以用到堆。

7.二叉查找树

二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构。数据存储于二叉查找树的各个结点中。

这就是二叉查找树的示例。结点中的数字便是存储的数据。此处以不存在相同数字为前提进行说明。

二叉查找树有两个性质。第一个是每个结点的值均大于其左子树上任意一个结点的值。比如结点9 大于其左子树上的3 和8。

同样，结点15 也大于其左子树上任意一个结点的值。

第二个是每个结点的值均小于其右子树上任意一个结点的值。比如结点15 小于其右子树上的23、17 和28。

根据这两个性质可以得到以下结论。首先，二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。此处最小值为3。

反过来，二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。此处最大值为28。

下面我们来试着往二叉查找树中添加数据。比如添加数字1。

首先，从二叉查找树的顶端结点开始寻找添加数字的位置。将想要添加的1与该结点中的值进行比较，小于它则往左移，大于它则往右移。

由于1 ＜ 9，所以将1 往左移。

由于1＜3，所以继续将1往左移，但前面已经没有结点了，所以把1 作为新结点添加到左下方。

这样，1 的添加操作便完成了。

接下来，我们再试试添加数字4。

和前面的步骤一样，首先从二叉查找树的顶端结点开始寻找添加数字的位置。

由于4 ＜ 9，所以将其往左移。

由于4 ＞ 3，所以将其往右移。

由于4＜8，所以需要将其往左移，但前面已经没有结点了，所以把4 作为新结点添加到左下方。

于是4 的添加操作也完成了。

接下来看看如何在二叉查找树中删除结点。比如我们来试试删除结点28。

如果需要删除的结点没有子结点，直接删掉该结点即可。

再试试删除结点8。

如果需要删除的结点只有一个子结点，那么先删掉目标结点……

然后把子结点移到被删除结点的位置上即可。

最后来试试删除结点9。

如果需要删除的结点有两个子结点，那么先删掉目标结点……

然后在被删除结点的左子树中寻找最大结点……

最后将最大结点移到被删除结点的位置上。这样一来，就能在满足二叉查找树性质的前提下删除结点了。如果需要移动的结点（此处为4）还有子结点，就递归执行前面的操作。

下面来看看如何在二叉查找树中查找结点。比如我们来试试查找12。

从二叉查找树的顶端结点开始往下查找。和添加数据时一样，把12 和结点中的值进行比较，小于该结点的值则往左移，大于则往右移。

提示：删除9 的时候，我们将“左子树中的最大结点”移动到了删除结点的位置上，但是根据二叉查找树的性质可知，移动“右子树中的最小结点”也没有问题。

由于12 ＞ 4，所以往右移。

找到结点12 了。

解说

我们可以把二叉查找树当作是二分查找算法思想的树形结构体现。因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移动了。

比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log₂n。因此，时间复杂度为O(logn)。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O(n)。

补充说明

有很多以二叉查找树为基础扩展的数据结构，比如“平衡二叉查找树”。这种数据结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率。

另外，虽然文中介绍的二叉查找树中一个结点最多有两个子结点，但我们可以把子结点数扩展为m（m 为预先设定好的常数）。像这种子结点数可以自由设定，并且形状均衡的树便是B 树。

——本文选自《我的第一本算法书》

书中用481张步骤图详解了26个算法和7个数据结构的基本原理，强烈推荐给想学算法的人。

目录

序章 算法的基本知识

0-1 什么是算法

0-2 运行时间的计算方法

第1章 数据结构

1-1 什么是数据结构

1-2 链表

1-3 数组

1-4 栈

1-5 队列

1-6 哈希表

1-7 堆

1-8 二叉查找树

第2章 排序

2-1 什么是排序

2-2 冒泡排序

2-3 选择排序

2-4 插入排序

2-5 堆排序

2-6 归并排序

2-7 快速排序

第3章 数组的查找

3-1 线性查找

3-2 二分查找

第4章 图的搜索

4-1 什么是图

4-2 广度优先搜索

4-3 深度优先搜索

4-4 贝尔曼- 福特算法

4-5 狄克斯特拉算法

4-6 A* 算法

第5章 安全算法

5-1 安全和算法

5-2 加密的基础知识

5-3 哈希函数

5-4 共享密钥加密

5-5 公开密钥加密

5-6 混合加密

5-7 迪菲- 赫尔曼密钥交换

5-8 消息认证码

5-9 数字签名

5-10 数字证书

第6章 聚类

6-1 什么是聚类

6-2 k-means 算法

第7章 其他算法

7-1 欧几里得算法

7-2 素性测试

7-3 网页排名

7-4 汉诺塔

点击【了解更多】到京东购买