本书涵盖了“数据结构”的主要内容，具体介绍了线性表、栈和队列、串、数组和广义表、递归、树、图等常用数据结构及递归思想，讨论了常用的排序和查找两种基本操作，重点介绍了不同数据结构在不同存储结构下基本运算的算法实现，并给出了经典应用实例。
本书遵循“理论够用”的原则，重实践，重实用；每章开始列出内容的重点和难点，每章末有知识巩固和实训演练，其中实训演练给出了验证性实验、设计性实验和综合性实验3种不同类型的实验，供学生进行实践；除第1章外，每章介绍完基本内容后，都通过一些经典应用实例帮助学生巩固已学知识。
本书适合作为高等学校计算机专业及相关专业的教材，也可作为编程爱好者的自学参考用书。

数据结构”是计算机学科各个专业的一门专业基础课程，旨在培养学生在软件设计领域的科学思维方式，以及程序设计能力与程序调试能力。同时，它也是软件设计师认证和计算机专业研究生入学考试的首选课程。该课程的重点是数据的逻辑结构、物理结构及其各种操作的算法实现和应用。但是，由于这门课程自身的特点，学生普遍反映理论难懂，实践复杂。针对这种情况，编者编写了本书，希望能将理论和实践有机结合，帮助学生轻松地掌握数据结构中的主要内容。本书对读者的技术背景要求比较低，比较容易上手，只要学过一门高级编程语言，例如C、C++、Java、C#等，就可以开始学习本书的内容。
本书的主要特色如下：
1．重实践、重实用
重实践，描述算法时用已经学过的C/C++语言函数，学生只做简单转换，就能上机调试，验证算法的正确性，并分析算法；重实用，尽可能介绍算法在日常生活中的用途，让学生觉得算法有用，从而提高学习兴趣。
2．经典应用实例
除第1章外，每章基本内容介绍完成后，都安排了一节专门介绍经典应用实例。在这一节中，主要安排一些日常生活方面的实例，实例中用到了这一章介绍的数据结构，并详细介绍如何用数据结构的思维解决问题，采取“问题描述—数据结构分析—实体模拟—算法实现”的思路。
3．知识巩固和实训演练
每章结束后，根据所讲内容，设置了知识巩固和实训演练。知识巩固有加强理解概念的填空题、选择题，还有帮助理解算法思想的简答题和算法应用题。实训演练为培养算法设计能力的验证性实验、设计性实验和综合性实验，学生按照层级要求针对性完成。
4．重点和难点
每章详细介绍内容之前，列出了本章的重点和难点，为学生学习知识提供了方向性参考。
5．微课视频
每章节针对容易出错和较难问题提供了微课视频，供学生课前预习和课后复习，可反复回看。
6．计算思维
通过本课程的学习，学生掌握数据结构相关的基础知识和基本技能，了解这些知识与技能在实践中的应用，使学生学会如何把现实世界的问题转化为计算机表示和处理，学会组织数据，选择合适的存储结构，培养较强的计算思维能力。
本书由多年从事数据结构教学的教师编写，是他们集体智慧和经验的结晶。本书由徐新爱、万里勇任主编，刘日华、胡佳、卢昕、朱莹婷任副主编。其中：万里勇、刘日华和胡佳、卢昕负责编写第3、5、10章，朱莹婷负责编写第6章，其他章节由徐新爱负责编写，全书由徐新爱统一组稿和改稿。书中所有算法都在VC++6.0环境下调试通过。
本书在编写与出版过程中，得到中国铁道出版社有限公司的领导和编辑的指导和帮助，在此表示衷心的感谢！同时，对教材中引用和参考的文献资料的作者一并致谢。
本书建议授课64课时，理论课和实践课各32课时。
在本书编写和实践过程中，编者做了大量的努力，但由于时间紧迫，编者水平有限，书中难免存在疏漏和不足之处，真诚地欢迎各位专家和广大读者提出宝贵的意见和建议。

编  者
2020年5月

第1章  绪论 1
1.1  数据结构概述 1
1.1.1  基本概念 1
1.1.2  数据结构的定义 2
1.2  算法及其描述 8
1.2.1  算法的概念 8
1.2.2  算法描述 9
1.3  算法分析 11
1.3.1  时间复杂度 12
1.3.2  空间复杂度 14
小结 14
知识巩固 14
实训演练 15
第2章  线性表 16
2.1  线性表的定义及基本运算 16
2.1.1  线性表的定义 16
2.1.2  线性表的基本运算 17
2.2  线性表的顺序存储结构及其基本运算的实现 18
2.2.1  线性表的顺序存储结构 18
2.2.2  顺序表基本运算的实现 19
2.3  线性表的链式存储结构及其基本运算的实现 23
2.3.1  单链表 24
2.3.2  双向链表 29
2.3.3  循环单链表 32
2.3.4  循环双向链表 33
2.3.5  顺序表与链表的比较 35
2.4  经典应用实例 36
2.4.1  约瑟夫问题 36
2.4.2  多项式求和 41
小结 46
知识巩固 46
实训演练 48
第3章  栈和队列 50
3.1  栈的定义及基本运算 50
3.1.1  栈的定义 50
3.1.2  栈的基本运算 51
3.2  栈的顺序存储结构及其基本运算的实现 51
3.2.1  栈的顺序存储结构 52
3.2.2  栈的基本运算在顺序栈上的实现 52
3.2.3  栈在递归中的应用 54
3.3  栈的链式存储结构及其基本运算的实现 56
3.3.1  栈的链式存储结构 56
3.3.2  栈的基本运算在链栈上的实现 56
3.4  栈的经典应用实例 57
3.4.1  数制转换 57
3.4.2  表达式求值 59
3.5  队列的定义及基本运算 66
3.5.1  队列的定义 66
3.5.2  队列的基本运算 67
3.6  队列的顺序存储结构及其基本运算的实现 67
3.6.1  队列的顺序存储结构 67
3.6.2  顺序队列基本运算的实现 68
3.6.3  循环队列 69
3.7  队列的链式存储结构及其基本运算的实现 71
3.7.1  队列的链式存储结构 71
3.7.2  链式队列基本运算的实现 71
3.8  队列的经典应用实例 73
3.8.1  迷宫问题 73
3.8.2  模拟就诊过程 78
小结 81
知识巩固 81
实训演练 84
第4章  串 86
4.1  串的概念与操作 86
4.1.1  串的概念 86
4.1.2  串的操作 87
4.2  串的顺序存储结构及其基本运算的实现 88
4.2.1  串的顺序存储结构 88
4.2.2  顺序串基本运算的实现 88
4.2.3  常用的字符串处理函数 90
4.3  串的链式存储结构及其基本运算的实现 92
4.3.1  串的链式存储结构 92
4.3.2  链串基本运算的实现 93
4.4  经典应用实例 96
4.4.1  测试串的基本操作 96
4.4.2  模式匹配 102
小结 105
知识巩固 105
实训演练 107
第5章  数组和广义表 109
5.1  数组 109
5.1.1  数组的基本概念 109
5.1.2  数组的存储结构 110
5.2  特殊矩阵的压缩存储 112
5.2.1  三角矩阵 112
5.2.2  对称矩阵 113
5.2.3  带状矩阵 114
5.2.4  稀疏矩阵 114
5.3  广义表 117
5.3.1  广义表的概念 117
5.3.2  广义表的存储结构 118
5.3.3  广义表的运算 119
5.4  经典应用实例 119
5.4.1  矩阵鞍点 120
5.4.2  稀疏矩阵相加 122
小结 126
知识巩固 126
实训演练 127
第6章  递归 128
6.1  递归 128
6.1.1  递归的定义 128
6.1.2  递归的使用 129
6.2  递归算法的设计 130
6.2.1  递归模型的建立 130
6.2.2  递归算法的设计 131
6.2.3  递归算法的性能分析 132
6.3  递归和栈 132
6.3.1  递归调用与栈 132
6.3.2  递归到非递归的转换 133
6.4  经典应用实例 134
小结 136
知识巩固 136
实训演练 137
第7章  树 138
7.1  树的定义及基本概念 138
7.1.1  树的定义 138
7.1.2  树的逻辑表示 139
7.1.3  树的基本概念 140
7.1.4  树的基本性质 141
7.1.5  树的基本运算 141
7.1.6  树的存储结构 142
7.2  二叉树的定义及基本性质 143
7.2.1  二叉树的定义 143
7.2.2  二叉树的性质 143
7.2.3  树、森林与二叉树的转换 145
7.3  二叉树的存储结构 148
7.3.1  二叉树的顺序存储结构 148
7.3.2  二叉树的链式存储结构 150
7.4  二叉树的基本运算及其实现 150
7.4.1  二叉树的基本运算概述 150
7.4.2  二叉树的基本运算实现 151
7.5  二叉树的遍历 152
7.5.1  二叉树遍历的概念 153
7.5.2  二叉树遍历算法 154
7.5.3  二叉树遍历算法的应用 155
7.6  二叉树的构造 156
7.7  哈夫曼树 160
7.7.1  哈夫曼树及其构造 160
7.7.2  哈夫曼树的应用 163
7.8  经典应用实例 165
7.8.1  二叉树的操作 165
7.8.2  信息编码 168
小结 174
知识巩固 174
实训演练 177

第8章  图 178
8.1  图的定义及基本概念 178
8.1.1  图的定义 178
8.1.2  图的基本概念 179
8.2  图的存储结构 181
8.2.1  图的顺序存储结构——邻接矩阵 182
8.2.2  图的链式存储结构——邻接表 183
8.2.3  图的基本运算 184
8.3  图的遍历 186
8.3.1  深度优先搜索遍历 186
8.3.2  广度优先搜索遍历 187
8.4  最小生成树 188
8.4.1  最小生成树的概念 189
8.4.2  最小生成树算法 192
8.5  最短路径 194
8.5.1  从一个顶点到其余各顶点的最短路径 194
8.5.2  每对顶点之间的最短路径 198
8.6  拓扑排序 201
8.6.1  拓扑排序的概念 201
8.6.2  拓扑序列 202
8.6.3  拓扑排序算法 202
8.7  经典应用实例 204
小结 207
知识巩固 207
实训演练 209
第9章  查找 210
9.1  查找的基本概念 210
9.2  线性表的查找 211
9.2.1  顺序查找 211
9.2.2  二分查找 212
9.2.3  分块查找 213
9.3  树的查找 214
9.3.1  二叉排序树查找 214
9.3.2  平衡二叉树查找 215
9.4  散列表的查找 217
9.4.1  散列表的概念 217
9.4.2  散列函数的构造 218
9.4.3  处理冲突的方法 219
9.4.4  散列表查找算法的性能分析 220
9.5  经典应用实例 221
9.5.1  模拟算法查找过程 221
9.5.2  电话号码查询 224
小结 229
知识巩固 230
实训演练 233
第10章  内部排序 234
10.1  内部排序的基本概念 234
10.2  插入排序 235
10.2.1  直接插入排序 235
10.2.2  折半插入排序 237
10.2.3  希尔排序 238
10.3  交换排序 239
10.3.1  冒泡排序 239
10.3.2  快速排序 241
10.4  选择排序 242
10.4.1  直接选择排序 242
10.4.2  堆排序 243
10.5  归并排序 246
10.6  基数排序 248
10.6.1  多关键字排序 248
10.6.2  链式基数排序 248
10.7  经典应用实例 251
10.7.1  考试成绩排序 251
10.7.2  拼色问题 253
小结 256
知识巩固 256
实训演练 258
参考文献 258

徐新爱 南昌师范大学教授

无