本书涵盖了“数据结构”的主要内容，具体介绍了线性表、栈和队列、串、数组和广义表、递归、树、图等常用数据结构及递归思想，讨论了常用的排序和查找两种基本操作，重点介绍了不同数据结构在不同存储结构下基本运算的算法实现，并给出了经典应用实例。
本书遵循“理论够用”的原则，重实践，重实用；每章开始列出内容的重点和难点，每章末有知识巩固和实训演练，其中实训演练给出了验证性实验、设计性实验和综合性实验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
​

徐新爱，1973年10月生，女，教授，江西省中青年骨干教师，南昌师范学院数学与计算机科学系副主任。从事“数据挖掘”“大数据分析”研究、高校教龄21年。省级精品课程负责人，校级数据挖掘团队负责人，校级首届“青蓝名师”认定对象。兼任江西省计算机学会理事，全国高师数学教育研究会小教培养工作委员会工委委员。近年来，主持并参与完成省教育规划重点课题等科研课题30余项，教育部产学合作协同育人项目2项，教育部大学生创新创业训练项目1项；主编并参与编写教材10余部；发表论文30余篇；获江西省高校优秀教材二等奖1项，江西省优秀教学成果一等奖1项，省级多媒体课件评比三等奖1项等；校级多媒体课件评比1等奖，教学成果二等奖1项，优秀教材一等奖1项，二等奖1项；指导学生参加“蓝桥杯”、“大数据技能”、“软件设计”、“师范生技能”赛获一等奖20多项；软件著作权3项。获学校“优秀共产党员”、“优秀教师”、“科研先进个人”、“师德先进个人”等荣誉称号。主讲课程包括有《C语言程序设计》、《编译原理》、《大数据可视化》和《数据结构》等。万里勇，男，汉族，中南大学计算机科学与技术专业硕士，江西师范大学管理科学与工程博士研究生（在读）、教育部高等学校青年骨干国内访问学者（浙江大学），副教授。数据库系统工程师、物联网系统认证讲师、深度学习开发与应用工程师，南昌工学院物联网工程专业负责人，中国计算机学会会员、国际电子电气工程师协会-计算机学会会员、江西省人工智能专业技术委员会委员、第九届高级数据挖掘与应用国际学术会议（ADMA 2013）大会出版主席、南昌市智能楼宇网络工程重点实验室成员，江西省智能楼宇网络重点实验室培育基地项目成员、2018年国家精品在线开放课程《电子线路仿真设计与实验实例》团队成员。 先后荣获省（部）级、校级优秀指导教师、优秀教师、优秀共产党员和科研先进个人等荣誉称号20余项；在《计算机工程》、《计算机系统应用》、《江西科学》期刊和国际三大检索会议发表论文40余篇，其中中文核心论文4篇，EI检索7篇，ISTP检索8篇；主编（参编）计算机类教材4部；参与国家级课题（国家科技支撑项目、国家自然基金项目等）3项、主持（参与）校级以上课题20余项，其中江西省教育厅科学研究技术项目2项、省高校教学课题6项、省高校党建研究课题1项、江西省教育科学“十三五”规划课题2项；获实用新型专利2项。​

本书配有丰富的微课资源，内容讲解生动有趣。​