本书第三版及其配套的学习指导教材为普通高等教育“十一五”国家级规划教材。本次修订除保留前三版中的经典数据结构知识外，还增加了红黑树等新内容。本书结构严谨，内容深入浅出，反映了抽象、封装和信息隐蔽等现代软件设计理念，重视算法的时间和空间分析，包括搜索和排序时间的下界分析。本书使用C语言描述。
本书重视实践性和程序设计。书中算法都有完整的C程序，程序代码构思精巧、结构清晰、注释详细，所有程序都已在TC 2.01下编译通过并能正确运行。这些程序既是学习数据结构和算法的很好示例，也是很好的C程序设计示例。本书最后一章是实习指导和实习题，指导学生按软件工程学的方法设计算法、编写程序和书写文档。本书配有大量的实例和图示，并有丰富的习题，易教易学。本书涵盖计算机学科专业考研大纲数据结构部分的考查内容。
本书可作为计算机类、电子信息类、电气类、自动化类、电子商务、信息管理与信息系统等相关专业数据结构课程的教材和考研参考书，也可供从事计算机软件和应用工作的工程技术人员参考。
全书条理清晰，内容详实，深入浅出；配有大量的实例和图示，有利于读者理解算法的实质和编程思想。
作者在南京邮电大学的从教生涯中，编写出版了多本教材，其中《数据结构—使用C++语言描述》《数据结构—C语言描述》《〈数据结构—C语言描述〉学习指导和习题解析》以及《算法设计与分析》均为普通高等教育“十一五”国家级规划教材。本书初次出版是在2003年，此次第四版依据ACM/IEEE的《计算机科学课程体系规范2013》，对教材内容作了更新和增添。
“数据结构”作为计算机学科的一门基础课，不仅讲授经典数据结构和算法，而且强调在现代编程环境中实现这些算法，此外，还应让学生学习和理解问题分解、抽象、封装和信息隐蔽、规范与实现分离、递归和算法效率等概念和方法，为学生进一步学习计算机科学技术打下良好的基础。
本次再版秉承作者以往的做法，采用抽象数据类型讨论数据结构，并直接采用C程序设计语言描述数据结构和算法。书中算法有完整的C程序，程序结构清晰，构思精巧。所有C程序都在Dev-C++环境下编译通过并能正确运行。它们既是学习数据结构和算法的很好示例，也是很好的C程序设计示例。同时，本书强化了算法分析，书中多数算法作了时空效率分析，对超出本书范围的也不加证明地给出了结论，还引入了更多实用的高级数据结构。
本书条理清晰，内容翔实，深入浅出，书中对算法作了较详细的解释，尽可能做到可读易懂，并配有大量的实例和图示，有利于读者理解算法的实质和编程思想。每章引言和结尾处的小结可帮助读者了解本章的要点，每章后还配有丰富的习题，有助于读者对重点知识及时复习巩固。
本书满足高等院校计算机科学与技术专业和其他相关专业“数据结构”课程84学时的教学安排。对于学时数少于84学时的授课计划，可根据实际学时对书中内容加以取舍。作者已在目录中对难度较大或非基本的章节标注*号，供读者选取时参考。除标*号部分外的基本内容适合48～56学时授课计划。
书中若有不当之处，敬请读者批评指正。
编 者
2021年7月于上海
第1章 概论 1
1.1 问题求解方法 1
1.1.1 问题和问题求解 1
1.1.2 问题求解过程 2
1.1.3 计算机求解问题的过程 2
1.1.4 算法与数据结构 2
1.2 什么是数据结构 3
1.2.1 基本概念 3
1.2.2 数据的逻辑结构 4
1.2.3 数据的存储结构 5
1.2.4 数据结构的运算 6
1.3 数据抽象和抽象数据类型 7
1.3.1 抽象、数据抽象和过程抽象 7
1.3.2 封装和信息隐蔽 7
1.3.3 数据类型和抽象数据类型 7
1.3.4 数据结构与抽象数据类型 8
1.4 描述数据结构 9
1.4.1 数据结构的规范 9
1.4.2 实现数据结构 9
1.5 算法和算法分析 11
1.5.1 算法及其性能标准 11
1.5.2 算法的时间复杂度 12
1.5.3 渐近时间复杂度 14
1.5.4 最坏、最好和平均情况时间
复杂度 15
1.5.5 算法的空间复杂度 15
小结 15
习题1 16
第2章 数组和链表 18
2.1 结构与联合 18
2.1.1 结构 18
2.1.2 联合 19
2.2 数组 20
2.2.1 一维数组 20
2.2.2 二维数组 20
2.2.3 多维数组 22
2.3 链表 22
2.3.1 指针 22
2.3.2 单链表 26
2.3.3 带表头结点的单链表 32
2.3.4 循环链表 32
2.3.5 双向链表 33
2.4 采用模拟指针的链表 35
2.4.1 结点结构 35
2.4.2 可用空间表 35
小结 37
习题2 37
第3章 堆栈和队列 39
3.1 堆栈 39
3.1.1 堆栈ADT 39
3.1.2 堆栈的顺序表示 40
3.1.3 堆栈的链接表示 42
3.2 队列 43
3.2.1 队列ADT 43
3.2.2 队列的顺序表示 44
3.2.3 队列的链接表示 47
*3.3 表达式的计算 47
3.3.1 表达式 47
3.3.2 中缀表达式转换为后缀表达式 48
3.3.3 计算后缀表达式的值 52
*3.4 递归和递归过程 54
3.4.1 递归的概念 54
3.4.2 递归的实现 55
*3.5 演示和测试 57
小结 59
习题3 59
第4章 线性表和数组ADT 61
4.1 线性表 61
4.1.1 线性表ADT 61
4.1.2 线性表的顺序表示 62
4.1.3 线性表的链接表示 65
4.1.4 两种存储表示的比较 69
*4.2 多项式的算术运算 69
4.2.1 多项式ADT 69
4.2.2 多项式的链接表示 70
4.2.3 多项式的输入和输出 71
4.2.4 多项式相加 73
4.3 数组作为抽象数据类型 74
4.4 特殊矩阵 75
4.4.1 对称矩阵 75
*4.4.2 带状矩阵 76
4.5 稀疏矩阵 77
4.5.1 稀疏矩阵ADT 77
4.5.2 稀疏矩阵的顺序表示 78
4.5.3 稀疏矩阵转置 79
4.5.4 稀疏矩阵的正交链表表示 82
小结 84
习题4 84
第5章 字符串和广义表 86
5.1 字符串 86
5.1.1 字符串ADT 86
5.1.2 字符串的存储表示 87
5.1.3 简单模式匹配算法 88
*5.1.4 模式匹配的KMP算法 91
*5.2 广义表 95
5.2.1 广义表的概念 95
5.2.2 广义表ADT 96
5.2.3 广义表的存储表示 97
5.2.4 广义表的算法 98
小结 99
习题5 99
第6章 树 100
6.1 树的基本概念 100
6.1.1 树的定义 100
6.1.2 基本术语 101
6.2 二叉树 102
6.2.1 二叉树的定义和性质 102
6.2.2 二叉树ADT 104
6.2.3 二叉树的存储表示 105
6.2.4 二叉树的遍历 108
*6.2.5 二叉树遍历的非递归算法 112
*6.2.6 二叉树遍历的应用实例 114
*6.2.7 线索二叉树 116
6.3 树和森林 120
6.3.1 森林与二叉树的转换 120
6.3.2 树和森林的存储表示 121
6.3.3 树和森林的遍历 123
*6.4 堆和优先权队列 124
6.4.1 堆 124
6.4.2 优先权队列 127
6.5 哈夫曼树和哈夫曼编码 130
6.5.1 树的路径长度 130
6.5.2 哈夫曼树和哈夫曼算法 131
6.5.3 哈夫曼编码 133
*6.6 并查集和等价关系 135
6.6.1 并查集 135
6.6.2 并查集的实现 135
6.6.3 集合按等价关系分组 138
小结 139
习题6 139
第7章 集合和搜索 141
7.1 集合及其表示 141
7.1.1 集合和搜索 141
7.1.2 集合ADT 142
7.1.3 集合的表示 143
7.2 顺序搜索 143
7.3 二分搜索 145
7.3.1 对半搜索 146
7.3.2 二叉判定树 147
*7.3.3 斐波那契搜索 149
7.3.4 插值搜索 150
7.4 分块搜索 151
*7.5 搜索算法的时间下界 152
小结 153
习题7 153
第8章 搜索树 154
8.1 二叉搜索树 154
8.1.1 二叉搜索树的定义 154
8.1.2 二叉搜索树的搜索 154
8.1.3 二叉搜索树的插入 155
8.1.4 二叉搜索树的删除 157
*8.1.5 二叉搜索树的高度 159
8.2 二叉平衡树 160
8.2.1 二叉平衡树的定义 160
8.2.2 二叉平衡树的平衡旋转 161
8.2.3 二叉平衡树的插入 167
8.2.4 二叉平衡树的删除 170
8.2.5 二叉平衡树的高度 173
8.3 B-树 173
8.3.1 m叉搜索树 173
8.3.2 B-树的定义 175
8.3.3 B-树的高度 175
8.3.4 B-树的搜索 176
8.3.5 B-树的插入 176
8.3.6 B-树的删除 179
*8.4 键树 181
8.4.1 键树的定义 181
8.4.2 双链树 182
8.4.3 Trie树 183
8.5 伸展树 184
8.5.1 自调节树和伸展树 184
8.5.2 伸展树的伸展操作 184
8.5.3 分摊时间分析 187
8.6 红黑树 187
8.6.1 红黑树的定义 188
8.6.2 红黑树的搜索 188
8.6.3 红黑树的插入 188
8.6.4 红黑树的删除 192
8.6.5 红黑树的高度 192
小结 192
习题8 193
第9章 跳表和散列表 195
9.1 字典 195
*9.2 跳表 195
9.2.1 什么是跳表 196
9.2.2 跳表的搜索 199
9.2.3 跳表的插入 200
9.2.4 跳表的删除 201
9.3 散列表 202
9.3.1 散列技术 202
9.3.2 散列函数 203
9.3.3 解决冲突的拉链法 204
9.3.4 解决冲突的线性探查法 205
9.3.5 解决冲突的其他开地址法 209
9.3.6 性能分析 211
小结 212
习题9 212
第10章 图 213
10.1 图的基本概念 213
10.1.1 图的定义与术语 213
10.1.2 图ADT 215
10.2 图的存储结构 216
10.2.1 矩阵表示法 216
10.2.2 邻接表表示法 220
*10.2.3 正交链表和多重表表示法 223
10.3 图的遍历 225
10.3.1 深度优先遍历 225
10.3.2 宽度优先遍历 227
10.4 拓扑排序和关键路径 229
10.4.1 拓扑排序 229
*10.4.2 关键路径 233
10.5 最小代价生成树 236
10.5.1 普里姆算法 237
*10.5.2 克鲁斯卡尔算法 238
*10.6 最短路径 240
10.6.1 单源最短路径 241
10.6.2 所有顶点之间的最短路径 244
小结 246
习题10 247
第11章 内排序 249
11.1 排序的基本概念 249
11.2 插入排序 250
11.2.1 直接插入排序 250
*11.2.2 希尔排序 254
11.2.3 对半插入排序 255
11.3 交换排序 255
11.3.1 冒泡排序 256
11.3.2 快速排序 257
11.4 合并排序 262
11.4.1 两路合并排序 262
11.4.2 合并排序的迭代算法 262
*11.4.3 链表上的合并排序 264
11.5 选择排序 267
11.5.1 简单选择排序 268
*11.5.2 堆排序 269
*11.6 排序算法的时间下界 270
*11.7 基数排序 271
小结 275
习题11 275
第12章 文件和外排序 277
*12.1 辅助存储器简介 277
12.1.1 主存储器和辅助存储器 277
12.1.2 磁盘存储器 277
12.2 文件 279
12.2.1 文件的基本概念 279
12.2.2 文件的组织方式 279
12.2.3 C语言文件 283
12.3 文件的索引结构 284
12.3.1 静态索引结构 284
12.3.2 动态索引结构 285
*12.4 外排序 286
12.4.1 外排序的基本过程 286
12.4.2 初始游程的生成 286
12.4.3 多路合并 288
12.4.4 最佳合并树 290
小结 291
习题12 292
第13章 实习指导和实习题 293
13.1 实习目的和要求 293
13.1.1 实习目的 293
13.1.2 实习要求 293
13.2 实习步骤 294
13.3 实习报告 294
13.4 实习题 295
13.5 实习报告范例 303
13.5.1 实习题：表达式计算 303
13.5.2 实习报告 303
13.6 上机考核 309
附录A 软件工程概述 311
附录B 考研大纲和教材内容 318
参考文献 322
书单推荐
