本书以系统能力培养为宗旨，基于C语言，介绍了数据结构相关知识。本书各章均以实例引入，使学生理解不同数据结构应用于哪些场景。针对每种数据结构，均以理解和实现物理世界里各种联系在信息世界中的逻辑表示和在计算机中实现数据结构的存储和操作两条主线进行讲授。并配有大量的实践练习和教学资源，适合作为高校数据结构课程的教材。

“数据结构”是计算机类专业的基础课程，也是相关理工类专业的热门选修课程。本书是为该课程编写的教材，适合计算机类专业和相关理工类专业的本科生学习。 
本书主要介绍如何合理地组织数据、有效地存储和处理数据、正确地设计算法以及对算法的复杂度进行分析和评价。通过深入理解各种基本数据结构的逻辑关系、物理存储和基本操作，初步建立数据结构设计、实现和运用的概念。同时，结合各种典型案例，讨论不同数据结构的特点、适用范围以及基本算法复杂度的分析方法，为后续的专业课程学习提供必要的基础知识。 
本书的学习目标如下。 
目标1：掌握线性表、栈和队列、数组和广义表、树和二叉树、图等各种基本数据结构的逻辑表达、物理存储和基本操作；掌握查找、排序的经典算法。 
目标2：能够针对具体应用问题，根据问题的约束条件分析各种可选方案在数据存储、算法效率上的利弊，并选择恰当的数据结构、存储表示和与之对应的操作方法。 
目标3：能够结合具体应用案例，合理选择和改进经典的数据结构，使之针对具体应用能够有效地存储和处理数据，能够在此基础上正确地设计算法，并对算法进行有效的分析和评价。 
本书共分为8章。第1章主要介绍数据结构相关的概念及术语，以及算法的定义、特性和算法设计的目标。第2～4章主要讨论各种基本结构的抽象数据类型、顺序和链式表示与实现，以及相关的应用。第5章和第6章在讨论树和图的抽象数据类型、顺序和链式表示与实现的基础上，重点讨论树和图的遍历方法以及基于此的典型应用。第7章和第8章分别讨论查找和排序的经典算法与改进策略。 
对于广大读者来说，学习数据结构课程的关键是把握两条主线。 
一条主线是如何理解和实现物理世界中的各种联系在信息世界中的逻辑表示。物理世界中的万般联系都是形象而具体的，需要通过抽象建模抓住这些联系的本质，即线性、树形或者图状结构，从而将其转换为信息世界中的逻辑表示。例如：生活中的各种排队可以抽象成线性结构中的队列，家族谱可以映射为树形结构，专业课程的先修/后修关系可以构成有向的图结构。抽象建模与表示能力是工科类专业学生必须具备的基本能力。不论是不是计算机类专业的学生，在学习这门课程时，都必须牢牢把握这条主线。 
另一条主线是如何在计算机中实现数据结构的存储和操作。存储的方式主要分为顺序存储和链式存储两大类。基本操作一般包括初始化及销毁操作、访问型操作和加工型操作三大类。这三类操作在两种不同存储模式下的算法的效率是有差异的，需要进行比较分析，总结各自的优势和不足，从而针对具体的现实问题，选择恰当的存储方式来保证操作执行的效率。在比较分析基础上得到有效结论是这条主线中的能力训练要求。 
此外，算法设计与优化也是值得关注的问题，本书中的查找和排序部分将展示算法设计与优化的思路。例如，排序算法如何从时间复杂度O(n2)的经典算法开始，通过对恰当结构的引入将算法时间复杂度降到O(nlogn)；查找算法如何从时间复杂度O(n)的穷举算法开始，通过对数据的排序约束和树形结构的引入，将时间复杂度降到O(logn)，甚至在一些特殊规则的约束下能够接近O(1)。我们不仅要掌握经典算法本身，更要关注算法优化的策略和方向，以便在解决实际问题时能够设计出高效的算法。 
最后，从不同学习者的角度来讨论一下如何学习本门课程。 
对于计算机类专业的学生，本书所涉及的内容均需掌握。在此基础上，学生需要大量的训练，以具备抽象建模能力，能够就实际问题选择或设计恰当的数据结构。此外，在编程实现过程中，能够基于问题的约束，在比较、分析的基础上选择恰当的存储方式和算法的实现方式，能够对算法的时间和空间复杂度进行合理的分析，能够对算法的改进和优化有恰当的思路，从而为实际问题提供高效的解决方案。 
对于其他理工类专业的学生，希望通过本门课程的学习达成两点目标：一是具备抽象建模能力，能够对物理世界中的问题描述进行抽象建模，从而在信息世界里进行合理表达；二是具备算法选择能力，能够根据输入数据的表现形式、数据结构的存储方式和基于此的算法效率特征，选择相应的数据结构和算法来高效地解决实际问题。 
本书在构思和准备过程中参考了国内外相关的数据结构教材，特别是严蔚敏、殷人昆、陈越、邓俊辉等老师编写的教材，这些经典教材的内容、写法给了作者很多启发。在本书的编写过程中，南京航空航天大学的秦小麟老师给予了很多指导意见。在此一并向这些老师表示感谢。本书第1～3章由孙涵编写，第4章和第8章由高航老师编写，第5～7章由黄元元老师编写，全书由孙涵负责统稿和审定。 
尽管本书是作者多年教学经验的总结，但限于作者的学识，书中难免有疏漏与不足之处，敬请各位同行与读者批评指正，以利于我们不断提升教学水平、丰富课程内容。 


孙涵 
南京航空航天大学计算机科学与技术学院 
2019年12月

前言 
第1章　概论 1 
1.1　引言 1 
1.2　数据结构相关概念及术语 1 
1.3　抽象数据类型的表示与实现 3 
1.4　算法与算法分析 6 
1.4.1　算法 6 
1.4.2　算法分析与度量 8 
1.5　小结 10 
1.6　练习 10 
第2章　线性表 11 
2.1　引言 11 
2.2　线性表的抽象数据类型 11 
2.3　线性表的顺序表示与实现 15 
2.3.1　顺序表的定义和特点 15 
2.3.2　顺序表的存储结构 15 
2.3.3　顺序表基本操作的实现与性能分析 16 
2.4　线性表的链式表示与实现 19 
2.4.1　单链表 20 
2.4.2　其他形式的链表 24 
2.5　线性表的应用举例 27 
2.6　小结 31 
2.7　练习 31 
第3章　栈和队列 32 
3.1　引言 32 
3.2　栈的抽象数据类型 32 
3.3　栈的顺序表示与实现 33 
3.4　栈的链式表示与实现 36 
3.5　栈的应用举例 37 
3.5.1　逆序输出问题 37 
3.5.2　最近匹配与比较问题 38 
3.5.3　递归与回溯问题 43 
3.6　队列的抽象数据类型 47 
3.7　队列的顺序表示与实现 48 
3.8　队列的链式表示与实现 50 
3.9　队列的应用举例 52 
3.10　小结 53 
3.11　练习 53 
第4章　数组、广义表和字符串 54 
4.1　引言 54 
4.2　数组 54 
4.2.1　一维数组 54 
4.2.2　二维数组 55 
4.3　特殊矩阵的压缩存储 56 
4.3.1　对称矩阵 56 
4.3.2　对角矩阵 57 
4.4　稀疏矩阵的压缩存储 57 
4.4.1　稀疏矩阵的三元组表示 57 
4.4.2　三元组的顺序表表示 58 
4.4.3　三元组的十字链表表示 61 
4.5　广义表 62 
4.5.1　广义表的概念 62 
4.5.2　广义表的抽象数据类型 63 
4.5.3　广义表的存储结构 64 
4.6　字符串 66 
4.6.1　字符串的抽象数据类型 66 
4.6.2　字符串的存储结构与子串定位 67 
4.7　小结 68 
4.8　练习 68 
第5章　树和二叉树 70 
5.1　引言 70 
5.2　树的定义和基本术语 70 
5.2.1　树的定义 70 
5.2.2　树的逻辑表示 71 
5.2.3　树的基本术语 72 
5.2.4　树的抽象数据类型 72 
5.3　二叉树 73 
5.3.1　二叉树的定义 73 
5.3.2　二叉树的抽象数据类型 74 
5.3.3　二叉树的性质 76 
5.3.4　二叉树的存储结构 77 
5.3.5　二叉树的遍历 79 
5.3.6　二叉树遍历算法的 
应用举例 81 
5.4　树和森林 85 
5.4.1　树与二叉树的转换 85 
5.4.2　森林与二叉树的转换 86 
5.4.3　树和森林的遍历 87 
5.5　霍夫曼树 88 
5.5.1　霍夫曼树的定义 88 
5.5.2　霍夫曼树的构造 90 
5.5.3　霍夫曼编码 90 
5.5.4　霍夫曼树和霍夫曼编码的算法实现 92 
5.6　小结 94 
5.7　练习 94 
第6章　图 95 
6.1　引言 95 
6.2　图的定义、基本术语和抽象数据类型 95 
6.3　图的存储方式 97 
6.3.1　邻接矩阵 97 
6.3.2　邻接表 99 
6.4　图的遍历 101 
6.4.1　深度优先遍历 101 
6.4.2　广度优先遍历 102 
6.4.3　图的遍历算法的应用举例 103 
6.5　最小生成树 107 
6.5.1　最小生成树的定义 107 
6.5.2　普里姆算法 108 
6.5.3　克鲁斯卡尔算法 111 
6.6　拓扑排序与关键路径 112 
6.6.1　拓扑排序 112 
6.6.2　AOE网与关键路径 113 
6.7　最短路径问题 116 
6.7.1　单源最短路径问题 116 
6.7.2　所有顶点对之间的最短路径 119 
6.8　小结 121 
6.9　练习 122 
第7章　查找 123 
7.1　引言 123 
7.2　查找表的定义与抽象数据类型 123 
7.3　顺序表的静态查找 124 
7.3.1　顺序查找 125 
7.3.2　折半查找 126 
7.3.3　索引查找 129 
7.4　树表的动态查找 130 
7.4.1　二叉排序树 130 
7.4.2　平衡二叉排序树 138 
7.4.3　B-树 141 
7.4.4　B+树 146 
7.5　哈希表的查找 147 
7.5.1　哈希表的定义 147 
7.5.2　哈希函数的构造方法 148 
7.5.3　处理冲突的方式 150 
7.5.4　哈希表的查找 152 
7.5.5　性能分析 153 
7.6　小结 155 
7.7　练习 156 
第8章　排序 157 
8.1　引言 157 
8.2　排序的定义与分类 157 
8.2.1　排序的定义 157 
8.2.2　排序的分类 157 
8.2.3　排序的数据类型 158 
8.3　插入排序 158 
8.3.1　直接插入排序 158 
8.3.2　希尔排序 160 
8.4　交换排序 162 
8.4.1　简单交换排序 162 
8.4.2　快速排序 164 
8.5　选择排序 166 
8.5.1　简单选择排序 167 
8.5.2　树形选择排序 168 
8.5.3　堆排序 169 
8.6　归并排序 173 
8.7　基数排序 175 
8.7.1　多关键字的排序 175 
8.7.2　基数排序的实现 176 
8.8　各种内部排序方法的比较 178 
8.9　小结 179 
8.10　练习 179