数据结构（C语言版）（第2版） / 清华大学计算机系列教材
￥49.50定价
作者： 殷人昆
出版时间：2017年4月
出版社：清华大学出版社
- 清华大学出版社
- 9787302459897
- 2-1
- 66339
- 16开
- 2017年4月
- 工学
- 软件工程
- TP311.12
- 计算机
- 本专科、高职高专
内容简介
本书是根据教育部《高等学校计算机科学与技术专业公共核心知识体系与课程》编写的数据结构主教材。全书共8章。第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。第2～8章分别介绍了线性表、栈和队列及其应用、多维数组、特殊矩阵、稀疏矩阵、字符串和广义表、树与二叉树、图、查找、排序，并做了适当延伸。作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排教材内容，力求透彻、全面，对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西都有适当的提示。 本书的编写得到清华大学2015年精品教材建设项目的资助。本书既可作为高等学校计算机科学与技术专业和软件工程专业本科生学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材，还可作为计算机或软件系统开发人员的参考资料。
目录
目录
第1章 绪论 1
1.1 数据结构的概念及分类 1
1.1.1
为什么要学习数据结构 1
1.1.2
与数据结构相关的基本术语 2
1.1.3
数据结构的分类 5
1.1.4
数据结构的存储结构 6
1.1.5
定义在数据结构上的操作 7
1.1.6 “好”数据结构 7
1.2 使用C语言描述数据结构 7
1.2.1
C语言的数据类型 8
1.2.2
算法的控制结构 9
1.2.3
算法的函数结构 10
1.2.4
动态存储分配 12
1.2.5
逻辑和关系运算的约定 12
1.2.6
输入与输出 13
1.3 算法和算法设计 13
1.3.1
算法的定义和特性 13
1.3.2
算法的设计步骤 14
1.3.3
算法设计的基本方法 15
1.4 算法分析与度量 18
1.4.1
算法的评价标准 18
1.4.2
算法的时间和空间复杂度度量 18
1.4.3
算法的渐近分析 21
小结 24
习题 24
第2章 线性表 27
2.1 线性表 27
2.1.1
线性表的定义和特点 27
2.1.2
线性表的主要操作 28
2.2 顺序表 29
2.2.1
顺序表的定义和特点 29
2.2.2
顺序表的结构定义 30
2.2.3
顺序表查找操作的实现 31
2.2.4
顺序表插入和删除操作的实现 32
2.2.5
顺序表的应用：集合运算 34
2.3 单链表 35
2.3.1
单链表的定义和特点 35
2.3.2
单链表的结构定义 36
2.3.3
单链表中的插入与删除 36
2.3.4
带头结点的单链表 40
2.3.5
单链表的遍历与创建 42
2.3.6
单链表的应用：集合运算 44
2.3.7
循环链表 46
2.3.8
双向链表 50
2.3.9
静态链表 53
2.4 顺序表与线性链表的比较 54
2.5 线性表的应用：一元多项式及其运算 56
2.5.1
一元多项式的表示 56
2.5.2
多项式的结构定义 57
2.5.3
多项式的加法 59
2.5.4
扩展阅读：多项式的乘法 60
小结 62
习题 63
第3章 栈和队列 66
3.1 栈 66
3.1.1
栈的概念 66
3.1.2
顺序栈 67
3.1.3
扩展阅读：多栈处理 70
3.1.4
链式栈 73
3.1.5
扩展阅读：栈的混洗 74
3.2 队列 76
3.2.1
队列的概念 76
3.2.2
循环队列 76
3.2.3
链式队列 80
3.3 栈的应用 82
3.3.1
数制转换 82
3.3.2
括号匹配 83
3.3.3
表达式的计算与优先级处理 84
3.3.4
栈与递归的实现 88
3.4 队列的应用 91
3.5 在算法设计中使用递归 92
3.5.1
汉诺塔问题与分治法 92
3.5.2
直接把递归过程改为非递归过程 94
3.5.3
扩展阅读：递归过程的非递归模拟算法 95
3.5.4
迷宫问题与回溯法 98
3.5.5
计算组合数与动态规划 101
3.6 扩展阅读：双端队列 102
3.6.1
双端队列的概念 102
3.6.2
输入受限的双端队列 103
3.6.3
输出受限的双端队列 104
3.6.4
双端队列的存储表示 104
3.7 扩展阅读：优先队列 106
3.7.1
优先队列的概念 106
3.7.2
优先队列的实现 107
小结 108
习题 108
第4章 数组、串和广义表 112
4.1 数组 112
4.1.1
一维数组 112
4.1.2
多维数组 114
4.2 特殊矩阵的压缩存储 116
4.2.1
对称矩阵的压缩存储 117
4.2.2
三对角矩阵的压缩存储 118
4.2.3
扩展阅读：w对角矩阵的压缩存储 119
4.3 稀疏矩阵 120
4.3.1
稀疏矩阵的概念 120
4.3.2
稀疏矩阵的顺序存储表示 121
4.3.3
稀疏矩阵的链表表示 124
4.4 字符串 125
4.4.1
字符串的概念 126
4.4.2
字符串的初始化和赋值 126
4.4.3
自定义字符串的存储表示 128
4.4.4
串的模式匹配 132
4.5 广义表 140
4.5.1
广义表的概念 140
4.5.2
广义表的性质 141
4.5.3
广义表的链接表示 141
4.5.4
扩展阅读：三元多项式的表示 147
小结 148
习题 149
第5章 树与二叉树 152
5.1 树的基本概念 152
5.1.1
树的定义和术语 152
5.1.2
树的基本操作 154
5.2 二叉树及其存储表示 155
5.2.1
二叉树的概念 155
5.2.2
二叉树的性质 156
5.2.3
二叉树的主要操作 158
5.2.4
二叉树的顺序存储表示 159
5.2.5
二叉树的链表存储表示 160
5.3 二叉树的遍历 161
5.3.1
二叉树遍历的递归算法 162
5.3.2
递归遍历算法的应用举例 163
5.3.3
二叉树遍历的非递归算法 166
5.3.4
利用队列实现二叉树的层次序遍历 169
5.3.5
非递归遍历算法的应用举例 170
5.3.6
二叉树的计数 171
5.4 线索二叉树 174
5.4.1
线索二叉树的概念 174
5.4.2
线索二叉树的种类 175
5.4.3
中序线索二叉树的建立和遍历 176
5.4.4
先序与后序线索二叉树 178
5.5 树与森林 180
5.5.1
树的存储表示 180
5.5.2
森林与二叉树的转换 184
5.5.3
树与森林的深度优先遍历 185
5.5.4
树与森林的广度优先遍历 187
5.5.5
树遍历算法的应用举例 188
5.6
Huffman树 190
5.6.1
带权路径长度的概念 190
5.6.2
Huffman树的概念 191
5.6.3
扩展阅读：最优判定树 194
5.6.4
Huffman编码 196
5.7 堆 198
5.7.1
小根堆和大根堆 198
5.7.2
堆的建立 199
5.7.3
堆的插入 201
5.7.4
堆的删除 202
5.8 等价类与并查集 202
5.8.1
等价关系与等价类 202
5.8.2
确定等价类的方法 203
5.8.3
并查集的定义及其实现 203
5.8.4
并查集操作的分析和改进 205
5.9 扩展阅读：八皇后问题与树的剪枝 207
5.9.1
八皇后问题的提出 207
5.9.2
八皇后问题的状态树 208
5.9.3
八皇后问题算法 210
小结 211
习题 212
第6章 图 216
6.1 图的基本概念 216
6.1.1
与图有关的若干概念 216
6.1.2
图的基本操作 219
6.2 图的存储结构 221
6.2.1
图的邻接矩阵表示 221
6.2.2
图的邻接表表示 225
6.2.3
邻接矩阵表示与邻接表表示的比较 229
6.2.4
图的邻接多重表和十字链表表示 230
6.3 图的遍历 231
6.3.1
深度优先搜索 232
6.3.2
广度优先搜索 234
6.3.3
连通分量 235
6.3.4
双连通图 237
6.3.5
有向图的强连通分量 238
6.4 最小生成树 240
6.4.1
最小生成树求解和贪心法 240
6.4.2
Kruskal算法 242
6.4.3
Prim算法 244
6.4.4
扩展阅读：其他建立最小生成树的方法 246
6.5 最短路径 248
6.5.1
非负权值的单源最短路径 248
6.5.2
扩展阅读：边上权值为任意值的单源最短路径问题 252
6.5.3
所有顶点之间的最短路径 254
6.5.4
无权值的最短路径 257
6.6 活动网络 259
6.6.1
AOV网络与拓扑排序 259
6.6.2
AOE网络与关键路径法 262
小结 267
习题 268
第7章 查找 273
7.1 查找的概念及简单查找方法 273
7.1.1
查找的基本概念 273
7.1.2
顺序查找法 274
7.1.3
折半查找法 276
7.1.4
扩展阅读：次优查找树 279
7.1.5
扩展阅读：斐波那契查找和插值查找 282
7.1.6
扩展阅读：跳表 283
7.2 二叉查找树 284
7.2.1
二叉查找树的概念 285
7.2.2
二叉查找树的查找 285
7.2.3
二叉查找树的插入 286
7.2.4
二叉查找树的删除 288
7.2.5
二叉查找树的性能分析 289
7.3
AVL树 292
7.3.1
AVL树的概念 292
7.3.2
平衡化旋转 293
7.3.3
AVL树的插入 295
7.3.4
AVL树的删除 296
7.3.5
AVL树的性能分析 299
7.4
B树 300
7.4.1
索引顺序表与分块查找 300
7.4.2
多级索引结构与m叉查找树 301
7.4.3
B树的概念 302
7.4.4
B树上的查找 304
7.4.5
B树上的插入 305
7.4.6
B树上的删除 306
7.4.7
B 树 308
7.5 扩展阅读：其他查找树 311
7.5.1
红黑树 311
7.5.2
伸展树 313
7.5.3
字典树 315
7.6 散列表及其查找 317
7.6.1
散列的概念 318
7.6.2
常见的散列函数 318
7.6.3
解决冲突的开地址法 321
7.6.4
解决冲突的链地址法 327
7.6.5
散列法分析 329
小结 330
习题 330
第8章 排序 335
8.1 排序的概念 335
8.1.1
排序的相关概念 335
8.1.2
排序算法的性能分析 336
8.1.3
数据表的结构定义 337
8.2 插入排序 338
8.2.1
直接插入排序 338
8.2.2
基于静态链表的直接插入排序 339
8.2.3
折半插入排序 341
8.2.4
希尔排序 342
8.3 交换排序 343
8.3.1
起泡排序 344
8.3.2
快速排序 345
8.3.3
快速排序的改进算法 348
8.4 选择排序 350
8.4.1
简单选择排序 350
8.4.2
锦标赛排序 351
8.4.3
堆排序 352
8.5 归并排序 356
8.5.1
二路归并排序的设计思路 356
8.5.2
二路归并排序的递归算法 356
8.5.3
扩展阅读：基于链表的归并排序算法 358
8.5.4
扩展阅读：迭代的归并排序算法 359
8.6 基数排序 361
8.6.1
基数排序 362
8.6.2
MSD基数排序 362
8.6.3
LSD基数排序 364
8.7 内排序算法的分析和比较 367
8.7.1
排序方法的下界 367
8.7.2
各种内排序方法的比较 368
8.8 外排序 371
8.8.1
常用的外存储器与缓冲区 371
8.8.2
基于磁盘的外排序过程 372
8.8.3
m路平衡归并的过程 374
8.8.4
初始归并段的生成 378
8.8.5
最佳归并树 381
8.8.6
磁带归并排序 382
小结 385
习题 386
附录A 实训作业要求与样例 391
A.1 实训作业要求 391
A.2 实训作业样例 392
附录B 词汇索引 397
参考文献 405
第1章 绪论 1
1.1 数据结构的概念及分类 1
1.1.1
为什么要学习数据结构 1
1.1.2
与数据结构相关的基本术语 2
1.1.3
数据结构的分类 5
1.1.4
数据结构的存储结构 6
1.1.5
定义在数据结构上的操作 7
1.1.6 “好”数据结构 7
1.2 使用C语言描述数据结构 7
1.2.1
C语言的数据类型 8
1.2.2
算法的控制结构 9
1.2.3
算法的函数结构 10
1.2.4
动态存储分配 12
1.2.5
逻辑和关系运算的约定 12
1.2.6
输入与输出 13
1.3 算法和算法设计 13
1.3.1
算法的定义和特性 13
1.3.2
算法的设计步骤 14
1.3.3
算法设计的基本方法 15
1.4 算法分析与度量 18
1.4.1
算法的评价标准 18
1.4.2
算法的时间和空间复杂度度量 18
1.4.3
算法的渐近分析 21
小结 24
习题 24
第2章 线性表 27
2.1 线性表 27
2.1.1
线性表的定义和特点 27
2.1.2
线性表的主要操作 28
2.2 顺序表 29
2.2.1
顺序表的定义和特点 29
2.2.2
顺序表的结构定义 30
2.2.3
顺序表查找操作的实现 31
2.2.4
顺序表插入和删除操作的实现 32
2.2.5
顺序表的应用：集合运算 34
2.3 单链表 35
2.3.1
单链表的定义和特点 35
2.3.2
单链表的结构定义 36
2.3.3
单链表中的插入与删除 36
2.3.4
带头结点的单链表 40
2.3.5
单链表的遍历与创建 42
2.3.6
单链表的应用：集合运算 44
2.3.7
循环链表 46
2.3.8
双向链表 50
2.3.9
静态链表 53
2.4 顺序表与线性链表的比较 54
2.5 线性表的应用：一元多项式及其运算 56
2.5.1
一元多项式的表示 56
2.5.2
多项式的结构定义 57
2.5.3
多项式的加法 59
2.5.4
扩展阅读：多项式的乘法 60
小结 62
习题 63
第3章 栈和队列 66
3.1 栈 66
3.1.1
栈的概念 66
3.1.2
顺序栈 67
3.1.3
扩展阅读：多栈处理 70
3.1.4
链式栈 73
3.1.5
扩展阅读：栈的混洗 74
3.2 队列 76
3.2.1
队列的概念 76
3.2.2
循环队列 76
3.2.3
链式队列 80
3.3 栈的应用 82
3.3.1
数制转换 82
3.3.2
括号匹配 83
3.3.3
表达式的计算与优先级处理 84
3.3.4
栈与递归的实现 88
3.4 队列的应用 91
3.5 在算法设计中使用递归 92
3.5.1
汉诺塔问题与分治法 92
3.5.2
直接把递归过程改为非递归过程 94
3.5.3
扩展阅读：递归过程的非递归模拟算法 95
3.5.4
迷宫问题与回溯法 98
3.5.5
计算组合数与动态规划 101
3.6 扩展阅读：双端队列 102
3.6.1
双端队列的概念 102
3.6.2
输入受限的双端队列 103
3.6.3
输出受限的双端队列 104
3.6.4
双端队列的存储表示 104
3.7 扩展阅读：优先队列 106
3.7.1
优先队列的概念 106
3.7.2
优先队列的实现 107
小结 108
习题 108
第4章 数组、串和广义表 112
4.1 数组 112
4.1.1
一维数组 112
4.1.2
多维数组 114
4.2 特殊矩阵的压缩存储 116
4.2.1
对称矩阵的压缩存储 117
4.2.2
三对角矩阵的压缩存储 118
4.2.3
扩展阅读：w对角矩阵的压缩存储 119
4.3 稀疏矩阵 120
4.3.1
稀疏矩阵的概念 120
4.3.2
稀疏矩阵的顺序存储表示 121
4.3.3
稀疏矩阵的链表表示 124
4.4 字符串 125
4.4.1
字符串的概念 126
4.4.2
字符串的初始化和赋值 126
4.4.3
自定义字符串的存储表示 128
4.4.4
串的模式匹配 132
4.5 广义表 140
4.5.1
广义表的概念 140
4.5.2
广义表的性质 141
4.5.3
广义表的链接表示 141
4.5.4
扩展阅读：三元多项式的表示 147
小结 148
习题 149
第5章 树与二叉树 152
5.1 树的基本概念 152
5.1.1
树的定义和术语 152
5.1.2
树的基本操作 154
5.2 二叉树及其存储表示 155
5.2.1
二叉树的概念 155
5.2.2
二叉树的性质 156
5.2.3
二叉树的主要操作 158
5.2.4
二叉树的顺序存储表示 159
5.2.5
二叉树的链表存储表示 160
5.3 二叉树的遍历 161
5.3.1
二叉树遍历的递归算法 162
5.3.2
递归遍历算法的应用举例 163
5.3.3
二叉树遍历的非递归算法 166
5.3.4
利用队列实现二叉树的层次序遍历 169
5.3.5
非递归遍历算法的应用举例 170
5.3.6
二叉树的计数 171
5.4 线索二叉树 174
5.4.1
线索二叉树的概念 174
5.4.2
线索二叉树的种类 175
5.4.3
中序线索二叉树的建立和遍历 176
5.4.4
先序与后序线索二叉树 178
5.5 树与森林 180
5.5.1
树的存储表示 180
5.5.2
森林与二叉树的转换 184
5.5.3
树与森林的深度优先遍历 185
5.5.4
树与森林的广度优先遍历 187
5.5.5
树遍历算法的应用举例 188
5.6
Huffman树 190
5.6.1
带权路径长度的概念 190
5.6.2
Huffman树的概念 191
5.6.3
扩展阅读：最优判定树 194
5.6.4
Huffman编码 196
5.7 堆 198
5.7.1
小根堆和大根堆 198
5.7.2
堆的建立 199
5.7.3
堆的插入 201
5.7.4
堆的删除 202
5.8 等价类与并查集 202
5.8.1
等价关系与等价类 202
5.8.2
确定等价类的方法 203
5.8.3
并查集的定义及其实现 203
5.8.4
并查集操作的分析和改进 205
5.9 扩展阅读：八皇后问题与树的剪枝 207
5.9.1
八皇后问题的提出 207
5.9.2
八皇后问题的状态树 208
5.9.3
八皇后问题算法 210
小结 211
习题 212
第6章 图 216
6.1 图的基本概念 216
6.1.1
与图有关的若干概念 216
6.1.2
图的基本操作 219
6.2 图的存储结构 221
6.2.1
图的邻接矩阵表示 221
6.2.2
图的邻接表表示 225
6.2.3
邻接矩阵表示与邻接表表示的比较 229
6.2.4
图的邻接多重表和十字链表表示 230
6.3 图的遍历 231
6.3.1
深度优先搜索 232
6.3.2
广度优先搜索 234
6.3.3
连通分量 235
6.3.4
双连通图 237
6.3.5
有向图的强连通分量 238
6.4 最小生成树 240
6.4.1
最小生成树求解和贪心法 240
6.4.2
Kruskal算法 242
6.4.3
Prim算法 244
6.4.4
扩展阅读：其他建立最小生成树的方法 246
6.5 最短路径 248
6.5.1
非负权值的单源最短路径 248
6.5.2
扩展阅读：边上权值为任意值的单源最短路径问题 252
6.5.3
所有顶点之间的最短路径 254
6.5.4
无权值的最短路径 257
6.6 活动网络 259
6.6.1
AOV网络与拓扑排序 259
6.6.2
AOE网络与关键路径法 262
小结 267
习题 268
第7章 查找 273
7.1 查找的概念及简单查找方法 273
7.1.1
查找的基本概念 273
7.1.2
顺序查找法 274
7.1.3
折半查找法 276
7.1.4
扩展阅读：次优查找树 279
7.1.5
扩展阅读：斐波那契查找和插值查找 282
7.1.6
扩展阅读：跳表 283
7.2 二叉查找树 284
7.2.1
二叉查找树的概念 285
7.2.2
二叉查找树的查找 285
7.2.3
二叉查找树的插入 286
7.2.4
二叉查找树的删除 288
7.2.5
二叉查找树的性能分析 289
7.3
AVL树 292
7.3.1
AVL树的概念 292
7.3.2
平衡化旋转 293
7.3.3
AVL树的插入 295
7.3.4
AVL树的删除 296
7.3.5
AVL树的性能分析 299
7.4
B树 300
7.4.1
索引顺序表与分块查找 300
7.4.2
多级索引结构与m叉查找树 301
7.4.3
B树的概念 302
7.4.4
B树上的查找 304
7.4.5
B树上的插入 305
7.4.6
B树上的删除 306
7.4.7
B 树 308
7.5 扩展阅读：其他查找树 311
7.5.1
红黑树 311
7.5.2
伸展树 313
7.5.3
字典树 315
7.6 散列表及其查找 317
7.6.1
散列的概念 318
7.6.2
常见的散列函数 318
7.6.3
解决冲突的开地址法 321
7.6.4
解决冲突的链地址法 327
7.6.5
散列法分析 329
小结 330
习题 330
第8章 排序 335
8.1 排序的概念 335
8.1.1
排序的相关概念 335
8.1.2
排序算法的性能分析 336
8.1.3
数据表的结构定义 337
8.2 插入排序 338
8.2.1
直接插入排序 338
8.2.2
基于静态链表的直接插入排序 339
8.2.3
折半插入排序 341
8.2.4
希尔排序 342
8.3 交换排序 343
8.3.1
起泡排序 344
8.3.2
快速排序 345
8.3.3
快速排序的改进算法 348
8.4 选择排序 350
8.4.1
简单选择排序 350
8.4.2
锦标赛排序 351
8.4.3
堆排序 352
8.5 归并排序 356
8.5.1
二路归并排序的设计思路 356
8.5.2
二路归并排序的递归算法 356
8.5.3
扩展阅读：基于链表的归并排序算法 358
8.5.4
扩展阅读：迭代的归并排序算法 359
8.6 基数排序 361
8.6.1
基数排序 362
8.6.2
MSD基数排序 362
8.6.3
LSD基数排序 364
8.7 内排序算法的分析和比较 367
8.7.1
排序方法的下界 367
8.7.2
各种内排序方法的比较 368
8.8 外排序 371
8.8.1
常用的外存储器与缓冲区 371
8.8.2
基于磁盘的外排序过程 372
8.8.3
m路平衡归并的过程 374
8.8.4
初始归并段的生成 378
8.8.5
最佳归并树 381
8.8.6
磁带归并排序 382
小结 385
习题 386
附录A 实训作业要求与样例 391
A.1 实训作业要求 391
A.2 实训作业样例 392
附录B 词汇索引 397
参考文献 405
