作者：汪建
出版社：人民邮电出版社有限公司
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
图解数据结构与算法试读：
前言
Linux内核之父林纳斯·托瓦兹（ Linus Torvalds）曾说过：“我认为一个优秀的程序员和一个不合格的程序员之间的区别在于，他是否将数据结构看得比代码更重要。不合格的程序员总是在关注代码，而优秀的程序员则会更看重数据结构。”Pascal之父及图灵奖获得者尼古拉斯·沃斯（Niklaus Wirth）也曾提出了一个著名的公式：算法+数据结构=程序。
由此可见，数据结构和算法才是程序的核心。对于程序而言，数据结构和算法都是缺一不可的，一个具有合适数据结构和优异算法的程序就像是一个艺术品。虽然数据结构和算法都无比重要，但现实情况却是很多工作了三五年的程序员并不重视数据结构和算法，他们所实现的程序往往运行效率低且难以维护。
随着面向对象思想的兴起，面向对象的编程语言将众多常用的数据结构和算法封装成了各种对象，比如不同种类的列表、集合、队列、树等。那么它们到底是如何实现的呢？实现的原理是什么？可能多数程序员都会回答：“不知道，反正编程语言已经提供了相关类，直接使用就行了。”对于编程语言，封装常用的数据结构和算法固然有很多好处，比如降低了使用成本，也大大降低了编码出错的概率。但封装同样会导致黑盒现象的产生，造成很多人在并不知道所用对象的具体实现原理的情况下，胡乱使用。
那么，数据结构是什么？算法又是什么？根据维基百科的定义，数据结构是一种数据组织、管理和存储的格式，它能提供有效的数据访问和修改操作。更准确地说，数据结构就是数据的集合，描述了各数据之间的关系，并提供了对这些数据的各种操作。而算法是一组定义清晰的指令集合，用于解决某类问题或执行某种运算任务。算法应该在有限的空间和时间内进行表达，其运行从初始状态和初始输入开始，经过一系列有限而定义清晰的指令操作后，最终产生输出并终止于某个状态。
尽管目前已经存在几本经典的算法书籍，但这几本书籍都很厚，而且内容和要点相当多。对于不是专门写算法的程序员来说，他们更需要通过一种形象且更加容易理解的方式来学习数据结构和算法。对于常见的数据结构和算法的核心思想，程序员更应该从感性的角度来理解把握，从而能够在不同的场景中知道要使用怎样的数据结构和算法。作者希望不管是刚入行的程序员还是经验丰富的工程师，都能轻松领悟常见的数据结构和算法的精髓及思想。这也是本书的写作意图。
本书具备如下特点。● 本书不与任何具体的编程语言绑定，而是注重用图解的方式
来描述数据结构和算法的思想。所以不管是前端程序员还是后端
程序员，不管使用的编程语言是JavaScript、Java、C++还是
Python，都能够轻松阅读本书。● 本书以读者能够轻松地从感性的角度来理解并掌握常用的数
据结构和算法为目标，摒弃繁杂的学术式陈述，以通俗易懂的方
式进行讲解，跟着执行示意图便能理解核心思想。● 本书采用大量图解，对讲解的每个数据结构和算法的执行过
程都给出了详细的步骤图，使读者能轻松理解各类数据结构和算
法的思想。● 本书所讲解的都是常见的数据结构和算法，能够帮助读者在
实际项目开发中理解相关的实现原理。● 本书脉络结构比较清晰，由简单到复杂，循序渐进。各知识
点的连贯性比较强，对于基础知识也有补充说明，便于读者阅读。组织结构
本书通篇紧扣“少字多图”的写作方针，以图来描述与数据结构和算法相关的机制原理，目的是让读者能够轻松地从感性的角度来理解并掌握常用的数据结构和算法。全书共分为7章，具体介绍如下。● 第1章 基础数据结构，介绍了一些基础的数据结构，包括
数组、链表、栈和队列等，其中数组包括一维数组、二维数组、
三维及更高维数组，链表包括单向链表和双向链表，栈包括基于
数组的栈和基于链表的栈，队列包括基于数组的队列和基于链表
的队列。● 第2章 递归与动态规划，介绍了递归和动态规划的算法思
想。递归思想主要以阶乘和斐波那契数列为例进行讲解，动态规
划思想则主要以斐波那契数列和最长公共子序列为例进行讲解。● 第3章 树，介绍了树这种常见的数据结构。根据不同的用
途，树衍生出了多种不同的结构，包括二叉树、二叉搜索树、
AVL树、红黑树、2-3树、B树以及Trie树等，其中分别介绍了这
些树的结构、性质及与其相关的主要操作。● 第4章 堆，介绍了堆数据结构，主要包括二叉堆、二项堆
和斐波那契堆等。除了介绍各种堆的结构和性质外，还介绍了堆
的相关操作。● 第5章 图，介绍了图数据结构，主要包括图的表示方式、
图的遍历、图的最短路径以及最小生成树。在图的表示方式中，
主要介绍了邻接表和邻接矩阵两种方式；在图的遍历中，主要介
绍了广度优先搜索和深度优先搜索；在图的最短路径中，主要介
绍了Dijkstra和Floyd两种算法；在最小生成树中，主要介绍了
Prim和Kruskal两种算法。● 第6章 比较排序，介绍了多种常见的基于比较的排序算法，
包括选择排序、冒泡排序、插入排序、快速排序、希尔排序、合
并排序和堆排序等，其中分别介绍了它们的排序要点、排序性能、
排序过程。● 第7章 非比较排序，介绍了三种常见的非比较排序算法，
包括计数排序、基数排序和桶排序，分别介绍了它们的排序要点、
排序性能以及排序过程。其中，计数排序主要介绍了考虑稳定性
的情况和不考虑稳定性的情况，基数排序主要介绍了基于计数排
序的实现、基于桶排序的实现和MSD排序方式等。读者对象● 假如你对数据结构和算法感兴趣，那么这本书适合你。● 假如你已经从事编程工作好几年，却没有熟练掌握常见的数
据结构和算法，那么这本书适合你。● 假如你想轻松学习并理解数据结构和算法，那么这本书适合
你。● 假如你想顺利解答面试中常见的算法题，那么这本书适合
你。● 本书侧重于用图讲解数据结构和算法的核心思想，并未与具
体的某种编程语言绑定在一起，因此没有编程基础或者只会某一
门编程语言的读者也可以顺利地阅读本书。● 对数据结构和算法已经很熟悉了还有必要看吗？有必要。本
书附带了常见的数据结构和算法的要点，同时通过图片形象地描
述了它们的执行过程，能使读者快速抓住要点，可作为常用数据
结构和算法的查阅手册。反馈
在本书交稿时，我仍在担心是否遗漏了某些知识点，本书的内容是否详细完整，是否能让读者有所收获，是否会因为自己理解的偏差而误导读者。受写作水平和写作时间所限，本书中难免存在谬误，恳请读者批评指正。
读者可将任何意见及建议发送到邮箱wyzz8888@foxmail.com，本书相关的勘误也会发布到我的博客上，欢迎读者通过邮件或博客与我交流。资源与支持
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。提交勘误
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。与我们联系
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。关于异步社区和异步图书“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。异步社区微信服务号第1章 基础数据结构1.1 数组
在计算机科学中，数组是我们最熟悉也是最基础的一种数据结构。通常地，数组由有限个相同数据类型的元素按顺序排列组合而成。数组的数据是连续的，并且会设定上界和下界，其中的每个元素都有属于它们自己的索引值（也称下标），通过这些下标就能定位到元素。对于绝大多数编程语言来说，数组的索引都是从0开始，但不排除有的编程语言从1开始。
几乎所有程序都会使用数组结构，而且很多其他的数据结构也可以由数组来实现，比如栈、队列、列表等。
根据维度的不同，数组可以分为一维数组、二维数组、三维数组等，以此类推。1.1.1 一维数组
在各种维度的数组中，一维数组是最简单的数组结构，通常它也被称为线性数组。
① 创建一个长度为10的数组。
② 将11、22、33、44四个数字放到数组中。
③ 再将“the”“monster”“is”“coming”四个字符串放到数组中，覆盖原来的前四个元素。
④ 获取数组下标为0和3所对应元素的字符串。
⑤ 数组大小为10，则下标范围为0～9，如果超出范围即越界，将会导致错误。1.1.2 二维数组
由于数学领域中的矩阵可以通过二维数组来表示，因此二维数组也被称为矩阵。此外，因为它是二维的结构，所以需要两个下标才能确定一个元素，即行下标和列下标。
① 创建一个3行10列的二维数组（矩阵），它一共可存放30个元素。
② 将“the”“monster”“is”“coming”四个字符串分别放到数组的(0,1)、(2,2)、(2,6)、(1,4)四个坐标上。
③ 获取二维数组(2,6)、(1,4)坐标中所保存的字符串。1.1.3 三维及更高维数组
数组的维度数可以看成是获取一个元素所需的索引数，比如一维数组需要一个索引，二维数组则需要两个索引。三维数组即由三个维度组成的数组，它是最常见的多维数组，由三个下标去描述数组中的元素，也就是说获取数组中的一个元素需要三个索引。
按照正常思维，我们常常会用现实世界中的三维空间来对应三维数组以进行理解，比如一维数组对应列表，二维数组对应方形表格，而三维数组对应的是立体空间表格。对于三维及三维以下的数组，这样理解没什么问题，但对于更高维度的数组，我们就很难用现实世界中相关的概念来对应四维、五维或更高维数组，所以这样的思维方式不利于我们理解更高维度的数组。
通常地，我们可以以索引的形式来理解数组，每个维度都可以看成是一层索引，三维的情况则可以看成如下的形式。
如果将“the”放到(0,1,2)坐标中，则如下图所示。
更高维度的数组则可以继续往上抽取一维，形成一种类似于树的结构。1.2 链表
链表是一种线性的数据集合。在链表中，每个节点都指向后继或前驱节点，也就是说每个节点都会包含数据和指针。链表中的节点在逻辑上是相连的，但在物理内存中却是不相连的，这种特性让链表拥有了高效的插入和删除操作。
总的来说，虽然链表实现的存储结构与传统数组的结构类似，但它也有一定的优势。其优势主要体现在两方面：其一，链表能够实现更高效的插入和删除操作；其二，较于数组，它能避免重新分配内存的情况，因为数组是有固定大小的，当数组内存不够使用时，则需要重新分配更大的内存。以上优势得益于链表的存储可以是非连续的内存空间，这样就允许在链表的任意位置进行插入和删除操作，并且能在常数的时间复杂度内完成。
当然，链表也有自己的缺点，具体如下。● 比起数组，链表会占用更多内存空间，因为链表需要保存额外的
指针。● 链表不支持随机访问，只能按顺序从头开始查找，访问时间是线
性的，而数组则可以实现随机访问。● 链表存储的内存是非连续的，在计算机中，这种情况有可能导致
访问的效率降低，因为CPU存在缓存机制，而CPU缓存一般是将
整块连续内存缓存起来，链表的非连续内存形式会降低CPU缓存
的命中率。● 链表实现逆向遍历比较困难，因为单向链表只有一个方向的指
针，而双向链表虽然多了一个方向的指针，但它会耗费更多的内
存。
比较常见的两类链表为单向链表和双向链表。1.2.1 单向链表
单向链表属于链表的一种，也叫单链表。单向是说它的链接方向是单向的，它由若干个节点组成，每个节点都包含了数据和后继节点指针next。单向链表主要的操作包括插入、删除和遍历。需要注意的是，头部节点head不保存任何数据（也可保存数据，但为了减少一些判断，这里不保存数据），只用于指向单向链表的第一个节点，并且整个链表的指针都指向一个方向。❖ 单向链表的特点● 创建单向链表时无须指定链表的长度，这比起数组更加有优势，
而数组纵使定义成动态数组也是需要指定一个更大的数组长度，
并且要把原来的数组元素都复制到新数组中。● 单向链表中的节点删除操作很方便，它可以直接通过改变指针指
向来实现删除操作，而某些场景下数组的删除操作需要移动剩下
的元素。● 单向链表中的节点需要通过顺序访问，即通过遍历的方式来访问
节点，而数组则可以实现随机访问。❖ 单向链表的创建
单向链表的创建操作很简单，只需创建头部节点head即可。❖ 插入节点至链尾
现准备将“nobody”“grows”“old”“merely”“by”“a”“number”“of”“years”等字符串按顺序分别插入链尾。下面我们看看执行过程。
① 创建“nobody”节点。
② 将头部节点的next指针指向“nobody”节点，同时维护链表长度，此时为1。
③ 继续创建“grows”节点。
④ 将“nobody”节点的next指针指向“grows”节点，此时链表长度为2。
⑤ 创建“old”节点，并将“grows”节点的next指针指向“old”节点，此时链表长度为3。
⑥ 以此类推，将剩下的字符串分别创建节点并通过next指针连接起来，最终链表长度为9。❖ 创建迭代器
迭代器（iterator）也称为游标（cursor），属于一种设计模式。迭代器可以提供链表上的访问接口，进而遍历链表上的全部元素。下面我们看看迭代器的使用。
① 迭代器的当前位置指针current初始时指向头部节点head。
② 执行两次next操作后，current指针指向索引为2的节点。
③ 此时的节点值为“grows”。
④ 也可以直接设置current指针指向索引为4的节点，此时的节点值为“merely”。❖ 指定位置插入节点
单向链表的插入操作默认是在链尾插入节点，但如果使用了迭代器则可以指定插入的位置。下面准备在链表索引为1的位置后面插入“but”和“someone”两个节点，过程如下。
① 先将current指针指向索引为1的节点，然后创建一个新节点“but”。
② 接着根据current指针指向的位置将“but”节点插入到链表中，同时将“nobody”节点的next指针指向“but”节点，并将“but”节点的next指针指向“grows”节点。并且维护链表长度，此时为10。
③ 执行next操作，将current指针后移一个位置。
④ 创建一个新节点“someone”。
⑤ 根据current指针指向的位置将“someone”节点插入到链表中，同时将“but”节点的next指针指向“someone”节点，并将“someone”节点的next指针指向“grows”节点。此时链表长度为11。❖ 删除指定节点
删除操作的核心是将原本指向待删除节点的next指针改成指向待删除节点的next指针所指向的节点，然后废弃被删除的节点。另外，在删除之前需要先通过遍历找到待删除的节点。下面来删除“but”和“someone”两个节点，我们看看删除的过程。
① 首先找到“but”节点，从头部节点head开始遍历查找“but”节点，找到该节点后进行删除操作，这时只要将“nobody”节点的next指针指向“someone”节点即可。
② 然后将“but”节点废弃，同时维护链表的长度，此时为10。
试读结束[说明：试读内容隐藏了图片]