作者：陈小玉
出版社：人民邮电出版社有限公司
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
趣学数据结构试读：
前言
2017年8月，本着让更多的人轻松学习算法的初心，我写作了第一本书《趣学算法》，该书在出版后受到广大读者一致好评，在一年内重印了10次，并输出了繁体版的版权。一位读者对我说，读这本书读到“停不下来”，我又何尝不是呢？写书写到“停不下来”，这是作者和读者的巨大共鸣！在交流学习算法的同时，越来越多的学生反映数据结构晦涩难懂，问我能不能写一本《趣学数据结构》。说实在的，写书是一项极其繁重的工作，每一句话，每一个图，都需要精心琢磨。正在我犹豫不决之际，一件事情坚定了我写作本书的信心。招聘趣事
如果你关注计算机专业招聘试题，会发现越是大型公司，问的问题越基础，有的甚至问你什么是栈和队列，反而一些小公司会关心你做过什么系统。从关注点的不同可以看出，大公司更注重基础扎实和发展潜力，而小公司希望你立刻能够为其干活。可以这样比喻：小公司喜欢细而长的竹子，大公司更喜欢碗口粗的竹笋。
我曾经推荐一个学生到某知名公司，没多久，学生向我说了应聘的事情：“我介绍我开发了企业管理系统、在线商城系统等，没想到他问我使用了什么数据结构和算法，我懂很多技术，那么多功能我都实现了，他不问，却问我使用了什么数据结构和算法，你说搞笑不？数据结构和算法我早就忘了，我会开发软件还不行吗？”人力资源总监也反馈过来意见：“很搞笑，这个学生做了不少系统，却说根本没用到数据结构和算法。”
既然双方都觉得这是一件搞笑的事情，那么我们就摊开来看，数据结构到底是什么。拨云见日，看清数据结构
当我们遇到一个实际问题时，首先需要解决两件事：（1）如何将数据存储在计算机中；（2）用什么方法和策略解决问题。
前者是数据结构，后者是算法。只有数据结构没有算法，相当于只把数据存储到计算机中，而没有有效的方法去处理，就像一幢只有框架的烂尾楼；若只有算法，没有数据结构，就像沙漠里的海市蜃楼，只不过是空中楼阁罢了。
数据是一切能输入计算机中的信息的总和，结构是指数据之间的关系。数据结构就是将数据及其之间的关系有效地存储在计算机中并进行基本操作。算法是对特定问题求解步骤的一种描述，通俗讲就是解决问题的方法和策略。
在遇到一个实际问题时，要充分利用自己所学的数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效地实现。这就是Niklaus Wirth教授所说的：“数据结构+算法＝程序”。为什么要学习数据结构
高校的计算机专业为本科生都开设了数据结构课程，它是计算机学科知识结构的核心和技术体系的基石，在研究生考试中也是必考科目。随着科学技术的飞速发展，数据结构的基础性地位不仅没有动摇，反而因近年来算法工程师的高薪形势，而得到了业内空前的重视。很多人认为基本的数据结构及操作已经在高级语言（如C++、Java语言）中封装，栈、队列、排序、优先队列等都可以直接调用库函数，学会怎么调用就好了，为什么要重复“造轮子”？那么到底有没有必要好好学习数据结构呢？
先看学习数据结构有什么用处。（1）学习有效存储数据的方法。很多学生在学习数据结构时，问我要不要把单链表插入、删除背下来？要不合上书就不会写了。我非常诧异，为什么要背？理工科技术知识很少需要记忆的，是用的，用的！学习知识不能只靠死记硬背，更重要的是学习处理问题的方法。如何有效地存储数据，不同的数据结构产生什么样的算法复杂性，有没有更好的存储方法提高算法的效率？（2）处理具有复杂关系的数据。现实中很多具有复杂关系的数据无法通过简单的库函数调用实现。如同现在很多芯片高度集成，完全不需要知道芯片内部如何，直接使用就行了。但是，如果在现实中遇到一个复杂问题，现有的芯片根本无法解决，或者一个芯片只能完成其中一个功能，而我们需要的是完成该复杂问题的一个集成芯片，这时就需要运用所学的数据结构知识来高效处理具有复杂关系的数据。（3）提高算法效率。很多问题的基础数据结构运行效率较低，需要借助高级数据结构或通过改进数据结构来提高算法效率。
通过学习数据结构，更加准确和深刻地理解不同数据结构之间的共性和联系，学会选择和改进数据结构，高效地设计并实现各种算法，这才是数据结构的精髓。数据结构为什么那么难
网络上太多的同学吐槽被“虐”，如“滔滔江水连绵不绝”，数据结构太难了！真的很难吗？其实数据结构只是讲了3部分内容：线性结构、树和图。到底难在哪里呢？我通过调查，了解到数据结构难学大概有以下4个原因。（1）无法接受它的描述方式。数据结构的描述大多是抽象的形式，我们习惯了使用自然语言表达，难以接受数据结构的抽象表达。不止一个学生问我，书上的“ElemType”到底是什么类型？运行时怎么经常提示错误。它的意思就是“元素类型”，只是这样来描述，你需要什么类型就写什么类型，例如int。这样的表达方式会让不少人感到崩溃。（2）不知道它有什么用处。尽管很多人学习数据结构，但目的各不相同。有的人是应付考试，有的人是参加算法竞赛需要，而很多人不太清楚学习数据结构有什么用处，迷迷糊糊看书、做题、考试。（3）体会不到其中的妙处。由于教材、教师等各种因素影响，很多学生没有体会到数据结构处理数据的妙处，经常为学不会而焦头烂额，学习重在体会其中的乐趣，有乐趣才有兴趣，兴趣是最好的驱动力。（4）语言基础不好。我一直强调先看图解，理清思路，再上机。可还是有很多同学已经理解了思路后，因为缺少main函数，输入/输出格式不对，缺少括号等各种语言问题卡壳，而这一切都被戴上了“数据结构太难了”的大帽子。数据结构学习秘籍
在讲学习秘籍之前，我们首先了解一下数据结构学习的3种境界。（1）会数据结构的基本操作。学会各种数据结构的基本操作，即取值、查找、插入、删除等，是最基础的要求。先看图解，理解各种数据结构的定义，操作方法，然后看代码，尝试自己动手上机运行，逐渐掌握基本操作。在初学时，要想理解数据结构，一定要学会画图。通过画图形象表达，能更好地体会其中的数据结构关系。因此，初学阶段学习利器是：画图、理解、画图。（2）会利用数据结构解决实际问题。在掌握了书中的基本操作之后，就可以尝试利用数据结构解决一些实际问题了。先学经典应用问题的解决方法，体会数据结构的使用方法，再做题，独立设计数据结构解决问题。要想熟练应用就必须做大量的题，在做题的过程中体会其中的方法。最好进行专项练习，比如线性表问题、二叉树问题、图问题。这一阶段的学习利器是：做题、反思、做题。（3）熟练使用和改进数据结构，优化算法。这是最高境界了，也是学习数据结构的精髓所在，单独学习数据结构是无法达到这种境界的。数据结构与算法相辅相成，需要在学习算法的过程中慢慢修炼。在学习算法的同时，逐步熟练应用、改进数据结构，慢慢体会不同数据结构和算法策略的算法复杂性，最终学会利用数据结构改进和优化算法。这一阶段已经在数据结构之上，可以通过在ACM测试系统上刷各种算法题，体会数据结构在算法设计中的应用。这一阶段的学习利器是：刷题、总结、刷题。本书特色
本书具有五大特色。（1）完美图解，通俗易懂。学习数据结构最好的办法就是画图、画图、画图。本书中的每一个基本操作和演示都有图解，有了图解，一切就都变得简单，迎刃而解。（2）实例丰富，简单有趣。本书结合大量实例，讲述如何利用数据结构解决实际问题，使复杂难懂的问题变得简单有趣，给读者带来巨大的阅读乐趣，使读者在阅读中不知不觉地学会数据结构知识，体会数据结构的妙处。（3）深入浅出，透析本质。本书采用简洁易懂的代码描述，抓住本质，通俗描述及注释使代码更加易懂。本书不仅对数据结构设计和操作描述全面细致，而且有复杂性分析过程。（4）实战演练，循序渐进。本书在每一个数据结构讲解清楚后，进行实战演练，使读者在实战中体会数据结构的设计和操作，增强自信，从而提高了读者独立思考、自己动手实践的能力。丰富的练习题和思考题及时检验对所学知识的掌握情况，为读者从小问题出发，逐步解决大型复杂性问题奠定基础。（5）网络资源，技术支持。本书为读者提供本书所有范例程序的源代码、练习题以及答案解析，这些源代码可以自由修改编译，以符合自己的需要。本书提供源代码执行、调试说明书，提供博客、QQ群技术支持，为读者答疑解惑。本书内容
本书包括10章。● 第1章是基础知识，介绍数据结构基础和算法复杂性的计算方法。● 第2～5章是线性结构，讲解线性表、栈和队列、字符串、数组
等的基本操作和应用。● 第6章是树形结构，讲解树、二叉树、线索二叉树、树和森林以
及树的经典应用。● 第7章是图形结构，讲解图的存储、遍历以及图的经典应用。● 第8～9章是数据结构的基本应用，讲解查找、排序的方法和算
法复杂性比较。● 第10章是高级数据结构及其应用，讲解优先队列、并查集、B-树、
B+树、红黑树等。
本书的每一章中都有大量图解，并给出数据结构的基本操作，最后结合实例帮助读者巩固相关知识点，力求学以致用、举一反三。建议和反馈
写一本书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书和网络支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，因为对本书的意见和建议有利于我们改进和提高，以帮助更多的读者。如果对本书有什么意见和建议，或者有问题需要帮助，可以加入QQ群887694770，也可以致信rainchxy@126.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、测试、前端、网络技术等。异步社区微信服务号Chapter 1 数据结构入门
1.1 数据结构基础知识
1.2 算法复杂度
1.3 一棋盘麦子
1.4 神奇魔鬼序列
1.5 本章要点
著名的瑞士科学家Niklaus Wirth教授提出：数据结构+算法＝程序。数据结构是程序的骨架，算法是程序的灵魂。1.1 数据结构基础知识
学习数据结构首先从认识以下几个概念开始。1．数据
数据是指所有能输入到计算机中的描述客观事物的符号，包括文本、声音、图像、符号等。我们经常使用的“扫一扫”的二维码，也是数据。2．数据元素
数据元素是数据的基本单位，也称节点或记录，如图1-1所示。图1-1 数据元素3．数据项
数据项表示有独立含义的数据最小单位，也称域。若干个数据项构成一个数据元素，数据项是不可分割的最小单位，如图1-1所示的“86”。4．数据对象
数据对象是指相同特性的数据元素的集合，是数据的一个子集。5．数据结构
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。数据结构研究的问题是将带有关系的数据存储在计算机中，并进行相关操作。数据结构包含逻辑结构、存储结构和运算三个要素。6．逻辑结构和存储结构
逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。例如，小明和小勇是表兄弟，这是他们之间的逻辑关系；他们在教室里面的位置是他们的存储结构。无论他们的座位怎样安排，是挨着坐，还是分开坐，都不影响他们的表兄弟关系。
逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题中抽象出来的数学模型。
数据结构的逻辑结构共有以下4种。（1）集合——数据元素间除“同属于一个集合”外，无其他关系。
集合中的元素是离散、无序的，就像鸡圈中的小鸡一样，可以随意走动，它们之间没有什么关系，唯一的亲密关系就是在同一个鸡圈里，如图1-2所示。数据结构重点研究的是数据之间的关系，而集合中的元素是离散的，没有什么关系。因此，集合虽然是一种数据结构，但在数据结构书中不讲，在离散数学的集合论部分有重点讲述。图1-2 集合（2）线性结构——一个对一个，如线性表、栈、队列、数组、广义表。
线性结构就像穿珠子，是一条线，不会分叉，如图1-3所示。有唯一的开始和唯一的结束，除了第一个元素外，每个元素都有唯一的直接前驱（前面那个）；除了最后一个元素外，每个元素都有唯一的直接后继（后面那个）。图1-3 线性结构（3）树形结构——一个对多个，如树。
树形结构就像一棵倒立的树，树根可以发出多个分支，每个每支也可以继续发出分支，树枝和树枝之间是不相交的，如图1-4所示。图1-4 树形结构（4）图形结构——多个对多个，如图、网。
图形结构就像我们经常见到的地图，任何一个节点都可能和其他节点有关系，就像一张错综复杂的网，如图1-5所示。图1-5 图形结构
存储结构：数据元素及其关系在计算机中的存储方式。
存储结构可以分为4种：顺序存储、链式存储、散列存储和索引存储。很多数据结构类书籍只介绍了前两种基本的存储结构，这里加上后两种，以便读者了解。（1）顺序存储
顺序存储是指逻辑上相邻的元素在计算机内的存储位置也是相邻的。例如，张小明是哥哥，张小波是弟弟，他们的逻辑关系是兄弟，如果他们住的房子是前后院，也是相邻的，就可以说他们是顺序存储，如图1-6所示。图1-6 兄弟两家前后相邻
顺序存储采用一段连续的存储空间，将逻辑上相邻的元素存储在连续的空间内，中间不允许有空。顺序存储可以快速定位第几个元素的地址，但是插入和删除时需要移动大量元素，如图1-7所示。图1-7 顺序存储（2）链式存储
链式存储是指逻辑上相邻的元素在计算机内的存储位置不一定是相邻的。例如，哥哥张小明因为工作调动去了北京，弟弟仍然在郑州，他们的位置是不相邻的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以说他们是链式存储，如图1-8所示。图1-8 哥哥有弟弟家地址
链式存储就像一个铁链子，一环扣一环才能连在一起。每个节点除了数据域，还有一个指针域，记录下一个元素的存储地址，如图1-9所示。图1-9 链式存储（3）散列存储
散列存储，又称哈希（Hash）存储，由节点的关键码值决定节点的存储地址。用散列函数确定数据元素的存储位置与关键码之间的对应关系，如图1-10所示。图1-10 散列存储
例如，假设散列表的地址范围为0～9，散列函数为H(key)=key%10。输入关键码序列：（24,10,32,17,41,15,49），构造散列表，如图1-11所示。
24%10=4：存储在下标为4的位置。
10%10=0：存储在下标为0的位置。
32%10=2：存储在下标为2的位置。
17%10=7：存储在下标为7的位置。
41%10=1：存储在下标为1的位置。
15%10=5：存储在下标为5的位置。
49%10=9：存储在下标为9的位置。图1-11 散列表
散列存储可以通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。如果有冲突，则有多种处理冲突的方法。（4）索引存储
索引存储是指除建立存储节点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。如果每个节点在索引表中都有一个索引项，则该索引表称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表称为稀疏索引。索引项的一般形式是关键字、地址，如图1-12所示。图1-12 索引存储
在搜索引擎中，需要按某些关键字的值来查找记录，为此可以按关键字建立索引，这种索引称为倒排索引。为什么称为倒排索引呢？因为正常情况下，都是由记录来确定属性值的，而这里是根据属性值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。带有倒排索引的文件称为倒排索引文件，又称为倒排文件。倒排文件可以实现快速检索，索引存储是目前搜索引擎最常用的存储方法，如图1-13所示。图1-13 倒排索引7．抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式，它和工程中的应用是一致的。在工程项目中，开始编程之前，首先列出程序需要完成的功能任务，先不用管具体怎么实现，实现细节在项目后期完成，一开始只是抽象出有哪些基本操作。把这些操作项封装为抽象数据类型，等待后面具体实现这些操作。而其他对象如果想调用这些操作，只需要按照规定好的参数接口调用，并不需要知道具体是怎么实现的，从而实现了数据封装和信息隐藏。在C++中可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型的具体操作。
抽象数据类型可以用以下的三元组来表示。
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT抽象数据类型名
例如，线性表的抽象数据类型的定义：
ADT List{
数据对象：D={a|a∈Elemset, i=1,2,…,n,n0}ii
数据关系：R={
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L
DestroyList(&L)
初始条件：线性表已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表已存在
操作结果：置线性表L为空表
ListEmpty(L)
初始条件：线性表已存在
操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE
ListLenght(L)
初始条件：线性表已存在
操作结果：返回线性表L数据元素个数
GetElem(L, i, &e)
初始条件：线性表已存在（1iListLenght(L)）
操作结果：用e返回线性表L中第i个数据元素的值
locatElem(L, e, comare())
初始条件：线性表已存在，comare()是数据元素判定函数
操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序
PriorElem(L, cur_e, &pre_e)
初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它
的前驱，否则操作失败，pre_e无定义
NextElem(L, cur_e, &next_e)
初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返
回它的后继，否则操作失败，next_e无定义
ListInsert(&L, i, e)
初始条件：线性表已存在（1iListLenght(L)+1）
操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1
ListDelete(&L, i, &e)
初始条件：线性表已存在（1iListLenght(L)）
操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1
ListTraverse(L, visit())
初始条件：线性表已存在
操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，
则操作失败
}ADT List（1）为什么要使用抽象数据类型？
抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。
试读结束[说明：试读内容隐藏了图片]