第 1 章 数据结构

第 1 章 数据结构

No. 1-1 什么是数据结构

决定了数据的顺序和位置关系

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

{%}

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

电话簿的数据结构

▶ 例①从上往下顺序添加

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

姓名

电话号码

武小小

010-uuuu-uuuu

田美丽

010-xxxx-xxxx

王野

010-yyyy-yyyy

小季酒店

021-zzzz-zzzz

……

……

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

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

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

姓名

电话号码

董大海

010-aaaa-aaaa

方帅

010-bbbb-bbbb

韩宏宇

020-zzzz-zzzz

李希

010-cccc-cccc

……

……

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

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

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

▶ 两种方法的优缺点

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

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

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

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

表 L

姓名

电话号码

李博

010-aaaa-aaaa

林广川

010-bbbb-bbbb

陆顺平

021-zzzz-zzzz

刘彻

010-ccc-cccc

……

……

表 M

姓名

电话号码

马岩

010-aaaa-aaaa

孟田

021-zzzz-zzzz

明小慧

010-zzzz-zzzz

孟舒怡

010-aaaa-aaaa

……

……

表 N

姓名

电话号码

宁川

021-aaaa-aaaa

……

……

……

……

……

……

……

……

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

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

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

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

本章将会讲解 7 种数据结构。如本节开头所述,数据在内存中是呈线性排列的,但是我们也可以使用指针等道具,构造出类似“树形”的复杂结构(树形结构将在 4-2 节详细说明)。

参考:4-2 广度优先搜索

No. 1-2 链表

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

这就是链表的概念图。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 线性查找

 

补充说明

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

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

另外,上文链表里的每个数据都只有一个指针,但我们可以把指针设定为两个,并

且让它们分别指向前后数据,这就是“双向链表”。使用这种链表,不仅可以从前往后,还可以从后往前遍历数据,十分方便。

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

No. 1-3 数组

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

参考:1-1 什么是数据结构

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

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

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

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

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

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

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

然后把 Yellow 往后移。

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

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

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

首先,删掉目标数据(在这里指 Green)。

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

接下来移动 Red。

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

解说

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

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

 

补充说明

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

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

 

访问

添加

删除

链表

数组

No. 1-4 栈

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

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

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

接下来,数据 Red 入栈。

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

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

解说

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

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

 

应用示例

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

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

另外,我们将要在 4-3 节中学习的深度优先搜索算法,通常会选择最新的数据作为候补顶点。在候补顶点的管理上就可以使用栈。

参考:4-3 深度优先搜索

No. 1-5 队列

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

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

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

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

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

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

解说

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

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

 

应用示例

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

参考:4-2 广度优先搜索

No. 1-6 哈希表

在哈希表这种数据结构中,使用将在 5-3 节讲解的“哈希函数”,可以使数据的查询效率得到显著提升。

参考:5-3 哈希函数

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

{%}

为了和哈希表进行对比,我们先将这些数据存储在数组中(数组的详细讲解在 1-3 节)。

参考:1 - 3 数组

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

参考:3 - 1 线性查找

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

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

1 号箱子中的也不是 Ally。

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

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

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

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

尝试把 Joe 存进去。

使用哈希函数(Hash)计算 Joe 的键,也就是字符串“Joe”的哈希值。得到的结果为 4928(哈希函数的详细说明在 5-3 节)。

参考:5 - 3 哈希函数

将得到的哈希值除以数组的长度 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 的数据。这种存储位置重复了的情况便叫作“冲突”。

遇到这种情况,可使用链表在已有数据的后面继续存储新的数据。关于链表的详细说明请见 1-2 节。

参考:1 - 2 链表

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)。

解说

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

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

 

补充说明

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

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

另外,本书在 5-3 节关于哈希函数的说明中将会提到“无法根据哈希值推算出原值”这个条件。不过,这只是在把哈希表应用于密码等安全方面时需要留意的条件,并不是使用哈希表时必须要遵守的规则。

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

No. 1-7 堆

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

参考:4-1 什么是图

参考:4-2 广度优先搜索

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

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

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

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

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

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

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

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

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

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

按照 中说明的排列顺序,将最后的数据(此处为 6)移动到最顶端。

{%}

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

{%}

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

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

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

解说

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

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

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

 

应用示例

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

参考:4-5 狄克斯特拉算法

No. 1-8 二叉查找树

二叉查找树(又叫作二叉搜索树或二叉排序树)是一种数据结构,采用了图的树形结构(关于树形结构的详细说明请参考 4-2 节)。数据存储于二叉查找树的各个结点中。

参考:4-1 什么是图

参考:4-2 广度优先搜索

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

二叉查找树有两个性质。第一个是每个结点的值均大于其左子树上任意一个结点的值。比如结点 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)还有子结点,就递归执行前面的操作(关于递归,请参照 7-4 节的内容)。

参考:7 - 4 汉诺塔

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

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

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

由于 12 > 4,所以往右移。

找到结点 12 了。

解说

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

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

 

补充说明

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

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

目录