下载掌阅APP，畅读海量书库
立即打开
本章主要内容
●为什么需要了解数据结构和算法
●算法和数据结构的区别
●对问题进行抽象
●从问题到解决方案
学习算法与数据结构是一个非常好的决定！
如果你还在犹豫不决，我们希望本章介绍的内容能打消你的疑虑并激发你对这个主题的兴趣。
为什么要学习数据结构和算法？简单来说，想要成为更优秀的软件开发人员，学习数据结构和算法能让我们事半功倍。
你有没有听说过“马斯洛的锤子”（又称为“工具规律”）？这是一个通过观察得到的假设，意味着只知道一种做事方式的人，想把这种方式运用到所有情况之下，而不关注情况的差异性。
如果只有锤子这一个工具，那么容易把所有东西当作钉子。类似地，如果只知道可以对列表进行排序，那么在向任务列表中添加新的任务或者选择下一个需要处理的任务时，通常就会尝试对任务列表进行排序，而不会根据上下文来获得更高效的解决方案。
本书旨在为你提供更多用于解决问题的“工具”。我们将以计算机科学专业基础课通常都会介绍的基本算法作为基础，向你介绍更高级的内容。
读完本书，你应该能够知道在什么情况下，可以使用特定的数据结构和（或）算法来提高代码的性能。
当然，我们并不期望你能把后面将要讨论的所有数据结构的每个细节都熟记于心，而更希望你能够了解如何推理问题，进而找到可以解决问题的相关算法。作为一本类似于菜谱的手册，本书会把各种问题归纳到常见的几个大类里，并给出可以解决这几大类问题的最佳数据结构。
需要注意的是，本书的某些主题较为超前。因此，在深入研究具体细节时，你可能需要反复阅读才能真正理解所有的内容。本书会给出多层次的深入分析，并将高级的部分放在各章的末尾。因此，如果只是想要了解这些主题，那么你可以忽略这些针对理论而进行的深入研究。
首先，我们需要使用一种统一的方式来描述并评估算法。
一种非常标准的描述方式如下：算法会根据所接收的输入以及所提供的输出进行描述。算法的具体细节可以用伪代码（忽略编程语言的实现细节）或者实际代码加以说明。
数据结构虽然与算法类似，但稍有不同，因为在其中还必须描述对数据结构所能执行的操作。通常来说，每个操作都会像算法那样，通过输入和输出进行描述。除此之外，对于数据结构来说，这些操作的 副作用 也需要描述，因为这些操作可能会对数据结构本身进行修改。
要彻底了解为什么会有副作用产生，你首先需要正确地对数据结构进行定义。
数据结构（data structure）是一种对数据进行组织的特定解决方案，不仅可以为元素提供存储空间，还提供了存放和获取这些元素的功能 [1] 。
[1] 具体来说，至少会有一个将新元素添加到数据结构的方法，以及另一个可以获取特定元素或者查询数据结构的方法。
最简单的数据结构就是数组。比如，字符数组可以为有限数量的字符提供存储空间，并且提供了根据位置来获取字符数组中各个字符的方法。图1.1展示了array = ['C', 'A', 'R']是如何存储的。对于存放了字符'C'、'A'和'R'的字符数组来说，array[1]对应的值就是'A'。
图1.1 数组的（简化的）内部表示。数组中的每个元素都对应着内存 [2] 中的一个字节。位于这些元素下方的是内存地址，位于其上方的则是对应的索引。数组是通过连续的内存块进行存储的，因此可以通过元素在数组里的索引并加上数组中第一个元素的偏移量来得到其地址。例如，数组中第4个字符（array[3]，图中为空）的地址就是0xFF00 + 3 = 0xFF03
[2] 在现代架构或编程语言中，数组元素可能会对应内存中的一个 字 （word）而不是一个字节（byte）。但是为了简便，这里假设字符数组被存放在一系列的字节中。
数据结构既可以是抽象的，也可以是具体的。
●抽象数据类型（Abstract Data Type，ADT）会指定对某些数据可以执行的操作以及这些操作的计算复杂度，但不会提供有关如何存储数据或者如何使用物理内存的详细信息。
●数据结构是基于抽象数据类型所提供的规范而得到的具体实现。
抽象数据类型可以理解为蓝图，而数据结构则会把其中的规范转换为真实代码。
抽象数据类型是从使用者的角度定义的，因此其行为会使用可能的值、可能的操作以及与这些操作对应的输出和副作用加以描述。
如果要更正式地来描述抽象数据类型，那么应该是“由一组类型、这组类型的指定类型、一组功能以及一组公理构成的合集”。
对于数据的具体表示——数据结构来说，数据结构则是从实现者而非使用者的角度描述的。
对于上面这个数组来说，一种可能的静态数组的抽象数据类型如下：“数组是一个可以存储固定数量元素的容器，其中的每个元素都有一个与之对应的索引（数组中元素的位置），可通过元素的位置来访问任何元素（随机访问）”。
要实现静态数组，还需要注意以下细节。
●数组的大小在数组创建之后是固定不变的，还是可以修改的？
●数组使用的内存是静态分配的，还是动态分配的？
●数组只能包含单一类型的元素，还是可以包含多种类型的元素？
●数组会实现为原始的内存块，还是实现为对象？如果实现为对象的话，数组会有哪些属性？
即使对于像数组这样的简单数据结构，不同的编程语言也会对上面的问题做出不同的选择。但是，所有的编程语言都会确保对数组的实现能够满足上面对数组的抽象数据类型所做的描述。
堆栈是另一个可以用来了解抽象数据类型和数据结构之间差异的好例子。我们将在附录C和附录D中对堆栈进行描述。当然，你应该听说过堆栈这种数据结构。
堆栈的抽象数据类型可以描述如下：“一个可以存储无限数量元素的容器，并且可以按照与插入顺序相反的顺序从最新的元素开始依次删除元素”。
进一步来讲，通过分解容器上可执行的操作可以得到堆栈的另一种描述：“堆栈是一个支持如下两种主要方法的容器”。
●插入元素。
●删除元素。如果堆栈不为空，那么最后插入的元素将从堆栈中被删除并返回。
尽管以上描述还是不那么通俗易懂，但是要比前一种描述更清晰，也更模块化。
这两种描述都足够抽象，也都具有一般性，足以让你在不同的编程语言、范式和系统 [3] 中实现堆栈。
[3] 原则上，系统并不是必须和计算机科学相关。例如，你可以把一堆需要检查的文件描述为系统。另外，洗一堆盘子这个经常在计算机科学课堂上见到的例子也可以视为一个系统。
不过在某些时候，我们还是得对数据结构进行具体的实现，这时就需要讨论下面这些细节了。
●元素用什么方式来存储？
❏ 数组？
❏ 链表？
❏ 磁盘上的B树？
●如何记录插入的顺序？（与上一个问题相关）
●堆栈的最大尺寸是已知并且保持不变的吗？
●堆栈是否可以包含多种类型的元素，还是所有元素都必须属于同一类型？
●如果想在空的堆栈上执行删除操作，应该怎么办？（例如，应该返回null还是抛出错误呢？）
诸如这样的问题数不胜数，这里列举的问题仅为让你有个大致的了解。
定义抽象数据类型的关键在于列出其允许的一系列操作。这就相当于定义了一套API [4] ，也可以说是与客户端的契约。
[4] 应用程序接口（Application Programming Interface）。
在需要对数据结构进行描述时，我们可以遵循一些简单的步骤，以确保提供的规范是全面且明确的。
●指定数据结构的API ，并且确定方法的输入与输出。
●描述数据结构的高阶行为。
●详细描述具体实现的行为。
●对数据结构的方法进行性能分析。
在本书中，我们都会先描述实际使用各种数据结构的具体情况，然后按照相同的流程来介绍它们。
在介绍第一种数据结构时（见第2章开头），我们还会对API描述的约定作进一步的详细解释。
算法和数据结构并不是同一件事。严格来说，它们并不是等效的。但是，我们通常在使用的时候会互换这两个术语。为了简便，后文我们会用 数据结构 这个术语来指代“数据结构及其所有相关的方法”。
有很多方法可以用来说明这两个术语之间的区别，但是笔者特别喜欢下面这个比喻：数据结构好比 名词 ，而算法好比 动词 。
笔者之所以喜欢这个比喻，是因为这个比喻不仅表明了它们的不同行为，还暗示了它们之间的依赖性。例如，要在英语中构建一个有意义的短语，就需要同时包含名词和动词，还需要给出主语（或宾语）以及将要执行（或承受）的动作。
数据结构和算法是相互联系的，就好比一张纸的正反两面。
●数据结构是基础，是一种通过组织内存区域来表示数据的方法。
●算法是过程，是用来对数据进行转换的一系列指令。
如果没有用来对数据进行转换的算法，数据结构就只是存放在内存芯片里的一堆二进制数；而如果没有可以操作的数据结构，则大多数算法甚至不会出现。
除此之外，每种数据结构还隐式地定义了其中可以执行的算法。例如，用来向数据结构中添加元素的方法以及从中获取或删除元素的方法。
实际上，一些数据结构的定义就是为了能让某些算法更高效地运行而出现的，例如哈希表以及按键进行搜索的算法 [5] 。
[5] 你可以在附录C里找到有关这个主题的更多信息。
因此，我们可以把算法和数据结构当作同义词来使用，毕竟在这个上下文中提到其中一个时总会暗示另一个。例如，在描述数据结构时，如果要让描述是有意义且准确的，就必须同时描述数据结构的方法（算法）。
读到这里，你可能想问：“我还需要自行编写数据结构吗？”
通常来说，你应该很少会遇到“只能从头开始编写一种新的数据结构”这种情况。如今，就大多数编程语言来说，找到一个包含常见数据结构实现的库还是很容易的。此外，这些库的编写者都是懂得如何对性能进行优化或是能解决安全问题的专家。
实际上，本书的主要目标是让你熟悉各种工具，并且通过训练让你能够识别出可以使用这些工具改进代码的机会。在较高层次上了解这些工具的内部工作方式是学习过程中的重要组成部分。但是，在某些特殊情况下，你还是会需要动手编写代码。例如，你使用了一种没有太多可用库的全新编程语言，或者你需要自定义一种数据结构来解决特殊问题，等等。
因此，是否要为数据结构编写你自己的实现取决于许多因素。其中一个因素就是，你需要的数据结构有多高级以及你使用的编程语言有多主流。
为了说明这一点，让我们以聚类为例。
如果你使用的是像Java或Python这样的主流语言，那么通常你能找到许多包含 k 均值算法且值得信赖的库。 k 均值算法是一种非常简单的聚类算法。
如果你使用的是像Nim或Rust这样的新兴语言，那么你可能很难找到一个由团队实现的、进行过全面测试的并且会不断得到维护的开源库。
另外，如果你需要的是像DeLiClu这样的高级聚类算法，那么即便使用的是Java或Python语言，也很难找到可以信任的且可以直接放在生产环境中运行的实现。
需要了解这些算法的内部工作方式的另一个因素是，你需要对某种算法进行自定义。这可能是因为你需要针对现实环境进行优化。例如，你需要一些特别的类似支持多线程运行且保证线程安全这样的属性，或者需要一种略有不同的行为。
也就是说，即使你只专注我们在前面所呈现的内容（只是了解应该什么时候以及如何使用这些数据结构），也足以让你的编码技能提升一个层次。下面让我们通过一个例子来说明算法在现实世界中的重要性，并介绍我们是如何对算法进行描述的。
恭喜，你被选中为火星定居点的首个居民！不过，火星上并没有商店，不能随便购物。鉴于这种情况，你只能自己种植农作物以获取食物。但是，在最初的几个月里，你可以依靠随身携带的食物来维持自己的生命。
不过，你能携带的食物有这样一个问题：货运箱的总重量不能超过1000kg，这是一个硬性限制。
更麻烦的是，你只能从下面这组已经打包在盒子里的食物中进行选择。
●土豆，800kg。
●大米，300kg。
●面粉，400kg。
●花生酱，20kg。
●番茄罐头，300kg。
●豆类，300kg。
●草莓酱，50kg。
水是不限量的，但是对于上面的每一种食物，你只能选择要不要带，而不能拆分并重新打包。显然，你不会只带土豆（就像《火星救援》里那样），而是会对要放进货运箱里的东西有所选择。
对于探险队来说，他们期望你在逗留期间能够保持良好的身体状态和充沛的精力。因此，要带什么食物的主要选择标准是食物的营养价值。如果用食物的总热量（总卡路里，1卡路里 = 4.19焦耳）来表示其营养价值，那么每一种可带食物的总卡路里如表1.1所示。
表1.1 每一种可带食物的重量及其总卡路里
[6]为便于计算，对于食物的总热量，本书保留了总卡路里（单位：卡，1卡 = 4.19焦耳）这一说法。——编辑注。
实际上，你的选择并不能改变实际可以携带的食物（尽管你的抗议可以理解，但任务控制部门在这一点上绝不会让步），真正重要的是每个盒子的重量及其所能提供的总卡路里。
我们的问题可以抽象为：“ 在不能对任何元素进行分割的情况下 ，从一个集合中选择任意数量的元素，使得它们的总重量不超过1 000kg并且提供的热量最高。”
问题已经明确了，接下来我们就可以开始寻找解决方案了。
装箱的一种方式是，优先选择内有总卡路里最高的食物的盒子，也就是重达800kg的一整盒土豆。
但是，这样做会导致大米和面粉无法被放进货运箱，而且它们两者的总卡路里远远超过你可以在剩余的200kg内放进的其他任何食物组合。按照这种策略，你可以获得的最高热量是1 749 400卡路里（选择土豆、草莓酱和花生酱）。
因此，看起来最自然的策略—— 贪心算法 （greedy algorithm） [7] ，会在每个步骤里选择目前最优的选项——并不能带来最好的结果。为了得到更好的答案，你需要再仔细考虑一下这个问题。
[7] 贪心算法是解决问题的一种策略，通过在每个步骤里做出局部最优选择来尝试找到最优解。贪心算法虽然只能针对一小类问题找到最佳解决方案，但是也可被用来作为获得近似（次优）解决方案的启发式算法。
是时候集思广益了。为此，你召集了整个物流团队一起寻找解决方案。
很快，有人建议应该查看每千克食物的平均卡路里而不是一整盒食物的总卡路里。于是，你为表1.1新添加了一列，并基于这一列中的值进行了相应的排序，如表1.2所示。
表1.2 将表1.1按照每千克食物的平均卡路里进行排序的结果
接下来，我们可以试着从上至下挑选单位重量卡路里最高的食物，最后得到包含花生酱、大米、面粉和草莓酱的组合——总共能提供2 813 800卡路里。
这比第一个结果要好很多。但是，稍加注意你就能发现，在选择花生酱之后，我们就不能再带上豆类了；而如果携带豆类的话，则还能进一步增加货运箱里食品的总热量。不过，至少你不用再被迫接受《火星救援》里的食物了，因为这次火星上没有土豆。
在进行若干小时的集思广益之后，你打算放弃寻找更好的解决方案了。你发现要解决这个问题，得到更优解决方案的唯一办法就是逐一检查每种食物以确定要不要携带。唯一能做到这一点的方法就是枚举出所有可能的解决方案，并剔除超出重量阈值的解决方案，然后从剩下的解决方案中挑选出最好的那个。这就是所谓的 暴力 （brute force）算法，是一种代价非常高昂的算法。
对于每种食物，你都可以选择是携带还是留下，因此可能的解决方案有2 7 = 128种。显然，你并不太愿意逐一尝试这100多种解决方案。几小时之后，你已经筋疲力尽，但也理解了为什么这种算法被称为暴力算法，并且至少解决了这个问题。
然后消息传开了。在收到一些未来定居者的投诉之后，任务控制部门打来了电话，告诉你清单里会额外增加25种新的食物，包括糖、橙子、大豆和马麦酱等。
看完你给出的计算组合，所有人都倍感沮丧，因为现在有大约40亿种不同的组合需要尝试。
显然，这时你需要一个计算机程序来帮助你实施计算，以得出最佳决策。
你会在接下来的几小时内编写相关的代码。但是，即使用上了计算机程序，你也需要花费很长的时间（若干小时）才能得到结果。紧接着，你发现自己的算法需要假设所有定居者的饮食习惯相同，但是实际上，其中的一部分人对某些食物过敏。比如，有25%的人不能吃麸质食物，还有更多的人声明他们对马麦酱过敏。因此，你必须根据不同人的过敏情况分别运行这个算法若干次。更糟的是，任务控制部门为了让有过敏反应的人也能吃得足够丰富，正在考虑为食品清单额外添加30种食物。如果真的决定了要这样做，那么我们最终会有62种食物可选，所编写的程序将不得不遍历超过数十亿种可能的组合。你尝试运行了一下这个程序，发现一天之后这个程序仍在运行，并且离得到结果还很远。
团队打算放弃找到最佳组合，回到吃土豆这个方案。这时，有人想起发射团队中某个人的桌子上有一本算法书。
你给发射团队打了电话，他们马上反馈这是一个0-1背包问题。坏消息是，0-1背包问题属于NP完全问题 [8] ，从而意味着这个问题很难解决，因为不会有“很快速的”（能在多项式时间内完成的）算法能计算出这个问题的最优解。
[8] NP完全（NP-complete）问题是这样一组问题，它们的任何解都可以被快速（在多项式时间内）验证，但尚不存在有效的方法能找到这个解。根据定义，NP完全问题无法在经典的确定型机器（例如我们将在第2章中定义的RAM模型）上，在多项式时间内得到答案。
不过好消息是，对于0-1背包问题，有一个伪多项式 [9] 解决方案。这是一种使用 动态编程 （dynamic programming）的解决方案 [10] ，所要花费的时间与背包的最大容量成正比。更好的办法是让货运箱的容量变得有限，于是这个解决方案需要执行的步骤数量就等于可能的填充容量乘以食物种类的数量。因此，假设最小单位是1kg，那么只需要执行1000 × 62步，就能得到答案了。这相比2 62 这个数要好太多了！在重写算法之后，新算法在几秒内就能找到最佳解决方案。
[9] 对于伪多项式算法，最坏情况下的运行时间（多项式时间）还取决于输入的 值 ，而不仅仅取决于输入的大小。例如，对于0-1背包问题，输入是 n 个元素（重量和值的组合），背包的容量为 C 。多项式算法的复杂度仅由元素的数量 n 决定，而伪多项式算法的复杂度还取决于（或者仅取决于） 背包的容量 C 。
[10] 动态编程是一种解决具有某种特征的复杂问题的策略。这种特性是指，要计算出最终解决方案，就需要对子问题进行多次递归调用。这种策略会通过把问题分解为更简单的子问题的集合来得到最终解决方案，并且这些子问题的解决方案会被保存起来，从而保证只被计算或解决一次。
于是，你可以把这个算法当作一个黑盒，直接把它插入程序中而不用再关心更多的细节。但是，这一决择与你的职业发展密切相关，因此你还是应该对这个算法的工作原理进行更深入的了解。
对于最初的例子来说，明显可以找到的最佳组合是大米、面粉和豆类，总计3 256 000卡路里。与第一次尝试相比，这已经是一个非常好的结果了！
最初的例子其实很简单（只有7种食物），因此你可能直接猜到了最佳组合。如果是这样的话，你可以试着计算在面对更接近实际情况的上百种不同的食物时，需要多少年才能手动找到最佳解决方案！
这个解决方案已经很不错了，因为在各种限制下，这已经是我们能够找到的最佳解决方案了。
但是，真正的算法专家会怎么做呢？假设在准备环节，恰好有一位专家在航天基地访问，并且受邀帮助我们计算节省燃料的最佳路线。午休时，有人非常自豪地告诉专家你们如何出色地解决了打包食物的问题。专家随后问道：“为什么不把盒子拆开呢？”
答案可能是“从来没有拆开过盒子”，或是“这些食物在供应商那里已经打包好了，重新打包需要花费更多的时间和金钱”。
接下来，这位专家就会解释道：“如果我们可以把包装盒拆开，那么0-1背包问题（属于NP完全问题）就会变成无限制背包问题。通常来说，无限制背包问题的线性时间 [11] 的贪婪解决方案，甚至都要比0-1背包问题的最佳解决方案更好一些。”
[11] 线性时间需要假设食物列表是有序的，否则就会产生线性对数时间的复杂度。
简单来说，我们可以把这个问题转换为其他更容易解决的问题，从而使得打包在货运箱里的食物能提供尽可能多的卡路里。于是，问题就变成了“在 可以 对元素进行分割的情况下，从一个集合中选择任意数量的元素，使得它们的总重量不超过1000千克并且提供的热量最高。”
再者说，即使需要更多的花销来重新打包所有食物也是值得的，因为这样做能得到更好的结果。
具体来说，如果可以选择打包各种食物的一部分，就可以简单地从卡路里含量最高的食物（在本例中为花生酱）开始打包。当发现不能把一个盒子里的所有食物都打包进去时，只需要打包其中一部分以填满整个货运箱就行了。因此，最终重新打包所有食物甚至都不是必需的，只需重新打包一种食物就行了。
于是，最佳解决方案是打包花生酱、大米、面粉、草莓酱和230kg的豆类，共计3 342 800卡路里。
未来的火星定居者能够维持生存的能力还是不错的，也不会因为只吃土豆、花生酱和草莓酱而沮丧了。
从计算的角度看，我们从不正确的算法（采用最高总数和最高比例的贪婪解决方案），过渡到了正确但不可行的算法（枚举出所有可能组合的暴力解决方案），最后得到了一种非常灵活且更高效的解决方案。
同样重要甚至更重要的是，我们打破了常规来思考这个问题。我们通过删除一些约束条件简化了问题，进而找到一种更简单的算法和更好的解决方案。这个过程实际上是一条黄金法则，即“持续彻底地研究需求，思考是否需要它们，并且在可能的情况下尝试删除它们。”这些可能的情况包括：删除这些需求能够带来价值至少相同的解决方案，或者可以用更低的成本实现价值稍低的解决方案。当然在这个过程中，也有一些必须考虑的其他方面的问题（例如各个层面的法律和安全性），因此某些约束条件是不能删除的。
如前所述，在描述算法的过程中，接下来要做的是详细描述这个解决方案并给出实现方法的指南。
这里我们省略了0-1背包问题的动态规划算法的具体步骤。原因是：首先，这是一种算法，而不是数据结构；其次，这种算法在大量文献里都有相应的描述；最后，我们在本章中提到它，只是为了说明避免选择使用错误的算法和数据结构是多么重要，以及概述在第2章中介绍问题及其解决方案时所要遵循的过程。
●算法应该基于输入和输出以及用来处理输入并产生预期输出的一系列指令来进行定义。
●数据结构是抽象数据类型的具体实现，由保存数据的结构和一组操作这些数据的算法组成。
●对问题进行抽象意味着创建清晰的问题陈述，然后讨论问题的解决方案。
●合理且高效地收拾行囊可能会很困难（尤其是如果打算去火星的话）。但是，只要有算法和合适的数据结构，（几乎）没有什么是不可能的！