数据结构

本书以专业基础能力培养为目标，承续计算机程序设计基础课程，接近遵照教育部计算机科学与技术教学指导委员会关于《高等学校计算机专业人才专业能力构成与培养》的要求编写而成，旨在培养学生的基本计算思维能力，提高学生的算法设计和程序实现能力，并为学生提高系统开发能力打下良好的基础。全书共分10章，主要介绍了数据结构基本概念与基本知识、线性表及其基本操作、栈和队列、字符串、数组和广义表、树与二叉树的概念和应用、图、查找和排序。本书可以作为计算机科学与技术及相关专业本科生的教材，也可以作为计算机专业考研(硕士、工程硕士、博士)的复习教材，还可以供使用计算机进行系统开发的人员学习使用。

殷人昆，清华大学计算机系教授。1970年清华大学计算数学专业毕业，1980年获清华大学计算机系工学硕士学位，1985年赴日本东京理科大学做访问学者，研究方向为软件工程过程的质量管理和软件产品的质量评价。主要讲授大学本科“数据结构”、“软件工程”和研究生“软件工程”、“软件项目管理”，其中，本科“数据结构”和工程硕士“软件工程”是清华大学精品课程，此外还主持了教育部-微软精品课程“数据结构”的建设。

前言
教学建议
第1章 绪论1
1.1 数据结构的概念及分类1
1.1.1 为什么要学习数据结构1
1.1.2 与数据结构相关的基本术语2
1.1.3 数据结构的分类4
1.1.4 数据结构的存储结构6
1.1.5 定义在数据结构上的操作7
1.2 使用C语言描述数据结构7
1.2.1 数据类型7
1.2.2 算法的控制结构8
1.2.3 算法的函数结构9
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 算法分析与度量19
1.4.1 算法的评价标准19
1.4.2 算法的时间和空间复杂度度量20
1.4.3 算法的渐近分析23
小结25
习题25
第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 顺序表的应用举例33
2.3 单链表34
2.3.1 单链表的定义和特点34
2.3.2 单链表的结构定义35
2.3.3 单链表中的插入与删除36
2.3.4 带头结点的单链表38
2.3.5 单链表的顺序访问与尾递归40
2.3.6 单链表的应用举例42
2.3.7 循环单链表44
2.3.8 双向链表47
2.3.9 静态链表51
2.4 顺序表与单链表的比较52
2.5 单链表的应用：一元多项式及其运算53
2.5.1 一元多项式的表示53
2.5.2 多项式的结构定义54
2.5.3 多项式的加法56
2.5.4 多项式的乘法57
小结59
习题59
第3章 栈和队列62
3.1 栈62
3.1.1 栈的概念62
3.1.2 顺序栈63
3.1.3 链式栈67
3.1.4 栈的混洗69
3.2 队列70
3.2.1 队列的概念71
3.2.2 循环队列72
3.2.3 链式队列75
3.3 栈的应用77
3.3.1 数制转换77
3.3.2 括号匹配78
3.3.3 表达式的计算与优先级处理79
3.3.4 栈与递归的实现84
3.4 队列的应用87
3.4.1 打印杨辉三角形与逐行处理87
3.4.2 电路布线与两点间的短路径89
3.5 在算法设计中使用递归91
3.5.1 汉诺塔问题与分治法91
3.5.2 迷宫问题与回溯法94
3.6 双端队列96
3.6.1 双端队列的概念97
3.6.2 输入受限的双端队列97
3.6.3 输出受限的双端队列98
3.6.4 双端队列的存储表示98
3.7 优先队列100
3.7.1 优先队列的概念100
3.7.2 优先队列的实现100
小结101
习题102
第4章 字符串105
4.1 字符串的概念105
4.1.1 字符串的基本概念105
4.1.2 字符串的初始化和赋值106
4.1.3 C语言中有关字符串的库函数107
4.1.4 字符串的自定义操作108
4.2 字符串的实现109
4.2.1 定长顺序存储表示109
4.2.2 堆分配存储表示110
4.2.3 块链存储表示112
4.3 字符串的模式匹配113
4.3.1 BF模式匹配算法113
4.3.2 无回溯的KMP模式匹配算法114
4.3.3 BM模式匹配算法119
小结121
习题121
第5章 多维数组和广义表123
5.1 数组123
5.1.1 一维数组123
5.1.2 多维数组125
5.2 特殊矩阵126
5.2.1 对称矩阵的压缩存储127
5.2.2 三对角矩阵的压缩存储128
5.2.3 w对角矩阵的压缩存储129
5.3 稀疏矩阵130
5.3.1 稀疏矩阵的概念130
5.3.2 稀疏矩阵的顺序存储表示130
5.3.3 稀疏矩阵的链接存储表示137
5.4 广义表140
5.4.1 广义表的概念140
5.4.2 广义表的性质141
5.4.3 广义表的头尾表示法142
5.4.4 广义表的扩展线性链表表示145
5.4.5 广义表的层次表示法146
5.4.6 广义表的应用举例：三元多项式的表示148
小结150
习题151
第6章 树与二叉树153
6.1 树的基本概念153
6.1.1 树的定义和术语153
6.1.2 树的基本操作155
6.2 二叉树及其存储表示 156
6.2.1 二叉树的概念156
6.2.2 二叉树的性质157
6.2.3 二叉树的主要操作159
6.2.4 二叉树的顺序存储表示160
6.2.5 二叉树的链接存储表示161
6.3 二叉树的遍历163
6.3.1 二叉树遍历的递归算法163
6.3.2 递归遍历算法的应用举例164
6.3.3 二叉树遍历的非递归算法167
6.3.4 利用队列实现二叉树的层次序遍历170
6.3.5 二叉树的计数171
6.4 线索二叉树173
6.4.1 线索二叉树的概念173
6.4.2 线索二叉树的种类174
6.4.3 中序线索二叉树的建立和遍历174
6.4.4 先序与后序线索二叉树176
6.5 树与森林178
6.5.1 树的存储表示178
6.5.2 森林与二叉树的转换183
6.5.3 树与森林的深度优先遍历184
6.5.4 树与森林的广度优先遍历187
6.5.5 树遍历算法的应用举例188
小结189
习题190
第7章 树与二叉树的应用193
7.1 Huffman树193
7.1.1 带权路径长度的概念193
7.1.2 Huffman树的概念194
7.1.3 优判定树197
7.1.4 Huffman编码199
7.2 堆200
7.2.1 小根堆和大根堆200
7.2.2 堆的建立201
7.2.3 堆的插入202
7.2.4 堆的删除203
7.3 二叉查找树204
7.3.1 二叉查找树的概念204
7.3.2 二叉查找树的查找205
7.3.3 二叉查找树的插入206
7.3.4 二叉查找树的删除207
7.3.5 二叉查找树的性能分析208
7.4 AVL树211
7.4.1 AVL树的概念211
7.4.2 平衡化旋转211
7.4.3 AVL树的插入213
7.4.4 AVL树的删除215
7.4.5 AVL树的性能分析217
7.5 表达式树218
7.5.1 从中缀表达式建立表达式树218
7.5.2 从后缀表达式建立表达式树221
7.5.3 利用表达式树求值222
7.6 等价类与并查集223
7.6.1 等价关系与等价类223
7.6.2 确定等价类的方法223
7.6.3 并查集的定义及其实现224
7.6.4 并查集操作的分析和改进226
7.7 八皇后问题与树的剪枝228
7.7.1 八皇后问题的提出228
7.7.2 八皇后问题的状态树228
7.7.3 八皇后问题的算法230
小结231
习题231
第8章 图234
8.1 图的基本概念234
8.1.1 与图有关的若干概念234
8.1.2 图的基本操作237
8.2 图的存储结构238
8.2.1 图的邻接矩阵表示238
8.2.2 图的邻接表表示241
8.2.3 邻接矩阵表示与邻接表表示的比较245
8.2.4 无向图的邻接多重表表示246
8.2.5 有向图的十字链表表示247
8.3 图的遍历247
8.3.1 深度优先搜索248
8.3.2 广度优先搜索249
8.3.3 连通分量250
8.3.4 双连通图251
8.3.5 有向图的强连通分量253
8.4 小生成树254
8.4.1 小生成树求解和贪心法255
8.4.2 Kruskal算法256
8.4.3 Prim算法258
8.4.4 Rosenstiehl和管梅谷算法260
8.5 短路径261
8.5.1 非负权值的单源短路径261
8.5.2 边上权值为任意值的单源短路径问题264
8.5.3 所有顶点之间的短路径266
8.5.4 无权有向图的短路径269
8.5.5 无权有向图的传递闭包270
8.6 活动网络271
8.6.1 AOV网络和拓扑排序271
8.6.2 AOE网络与关键路径274
小结278
习题279
第9章 查找282
9.1 查找的基本概念282
9.1.1 查找的概念282
9.1.2 查找算法的性能分析283
9.2 顺序查找283
9.2.1 在普通顺序表上的顺序查找算法283
9.2.2 在有序顺序表上的顺序查找算法284
9.3 折半查找285
9.3.1 折半查找方法285
9.3.2优二叉查找树288
9.3.3 次优二叉查找树289
9.3.4 斐波那契查找和插值查找292
9.3.5 跳表293
9.4 B树294
9.4.1 索引顺序表与分块查找294
9.4.2 多级索引结构与m叉查找树296
9.4.3 B树的概念297
9.4.4 B树上的查找298
9.4.5 B树上的插入299
9.4.6 B树上的删除301
9.4.7 B+树303
9.5 其他查找树306
9.5.1 红黑树306
9.5.2 伸展树308
9.5.3 键树310
9.6 散列法312
9.6.1 散列的概念312
9.6.2 常见的散列函数313
9.6.3 解决冲突的开地址法316
9.6.4 解决冲突的链地址法323
9.6.5 散列法分析325
小结326
习题327
第10章 排序330
10.1 排序的概念与算法性能330
10.1.1 排序的概念330
10.1.2 排序算法的性能331
10.1.3 数据表的结构定义332
10.2 插入排序333
10.2.1 直接插入排序333
10.2.2 基于静态链表的直接插入排序335
10.2.3 折半插入排序336
10.2.4 希尔排序337
10.3 交换排序338
10.3.1 起泡排序338
10.3.2 快速排序340
10.3.3 快速排序的改进算法343
10.4 选择排序344
10.4.1 简单选择排序344
10.4.2 锦标赛排序346
10.4.3 堆排序348
10.5 归并排序350
10.5.1 二路归并排序的设计思路350
10.5.2 二路归并排序的递归算法351
10.5.3 二路归并排序的迭代算法352
10.6 基数排序354
10.6.1 基数排序的概念354
10.6.2 MSD基数排序355
10.6.3 LSD基数排序357
10.7 内部排序算法的分析和比较359
10.7.1 排序算法的下界359
10.7.2 各种内部排序算法的比较360
10.8 外部排序362
10.8.1 常用的外存储器与缓冲区362
10.8.2 基于磁盘的外部排序过程363
10.8.3 m路平衡归并的过程365
10.8.4 初始归并段的生成369
10.8.5 佳归并树371
10.8.6 磁带归并排序374
小结376
习题377
附录 实训作业要求与样例380
参考文献385

前言2013年，ACM、IEEE发布了Computer Science Curricula 2013（简称CS2013），对新时期计算机学科的核心知识体系做了梳理。在此之前，为适应计算机科学与技术专业人才培养的需求，教育部高等学校计算机科学与技术教学指导委员会颁发了《高等学校计算机科学与技术专业公共核心知识体系与课程》规范，从问题空间、知识取向、能力要求等方面，给出了教育改革和专业能力培养的要求。按照知识取向的不同，把计算机科学与技术学科划分为计算机科学（CS）、计算机工程（CE）、软件工程（SE）和信息技术（IT）4个方向。从问题空间划分，计算机科学属于科学型，计算机工程和软件工程属于工程型，信息技术属于应用型。    综合上述两个规范，数据结构课程涵盖的知识单元有5个：基本算法（AL3）、算法与问题求解（PF2）、基本数据结构（PF3）、递归（PF4）和分布式算法（AL4）。教学大纲包括：1）算法、算法的时间复杂度和空间复杂度、最坏和平均时间复杂度等概念；2）算法描述；3）常用算法设计方法，包括迭代法、穷举搜索法、递推法、算法的递归描述技术；4）数据结构的基本概念和术语，包括数据结构、数据类型、抽象数据类型、信息隐藏；5）线性表与线性表的存储结构，包括顺序表、链接表；6）栈、队列；7）串；8）多维数组和广义表；9）树形结构及其应用，包括树、森林、二叉树、线索二叉树、Huffman树；10）图及其应用，包括图的基本概念、图的存储结构、图的遍历、生成树和最小生成树、最短路径、拓扑排序；11）常用排序算法，包括插入排序、交换排序、选择排序；12）常用查找技术，包括线性表上的查找、树的查找、散列技术；13）文件，包括顺序文件、索引文件、索引顺序文件、散列文件。    不同的学科方向对以上知识单元的侧重点有所不同，见下表。    学科方向涵盖知识点学时（课堂教学+上机实习（大作业））计算机科学  算法分析基础、算法策略、基本算法、分布式算法、可计算性理论基础、算法与问题求解、基本数据结构、递归48+16计算机工程  基本算法分析、算法策略、计算算法、分布式算法、算法复杂性、算法与问题求解、基本数据结构、递归48+16软件工程    计算机科学基础［程序设计基础、算法及数据结构／表示、抽象(使用和支持)程序设计语言基础］、测试(异常处理)48+16信息技术    基本数据结构、算法和问题解决、递归48+16作者从1987年开始，在清华大学多年配合严蔚敏老师讲授数据结构课程，从1996年开始参与研究生（硕、博）入学考试的命题并批改试卷。多年的授课实践，积累了一些心得与体会，深感现有的许多教材虽然看上去叙述清晰、思路严密，但往往比较表面化，忽略了许多知识点深层隐藏的东西，使得学生陷入“一学就会，一用就错，一考就糊”的尴尬境地。有鉴于此，作者决心基于多年的教学经验和知识积累，编写一本适合的教材，以便广大学生学好数据结构课程。    本书以专业基础能力培养为目标，承续计算机程序设计基础课程，遵照CS2013和教育部计算机科学与技术教学指导委员会关于《高等学校计算机专业人才专业能力构成与培养》的要求编写而成，旨在培养学生的基本计算思维能力，提高学生的算法设计和程序实现能力，并为学生提高系统开发能力打下良好的基础。也就是说，本书的宗旨是培养学生从对问题的理解入手，运用已掌握的算法和数据结构知识寻找解决途径，构建适当的算法和基本程序，以求得问题的解决。在从简单到复杂讨论数据结构的过程中逐步引入常用的算法设计策略，通过编程上机实验到工程实践，使学生初步掌握分析问题、解决问题的方法。    全书共分10章，各章内容如下：    第1章介绍了数据、数据结构及算法等基本概念与基本知识，学习数据结构所需要掌握的C语言程序设计预备知识，简单的算法性能分析，包括最坏和平均时间复杂度估计。    第2章介绍了线性表及其基本操作内容，并给出基于数组与链表表示的线性表基本操作函数的实现方法。在介绍线性表的应用时，讨论了集合与多项式的实现。    第3章介绍了栈、队列、双端队列、优先队列的概念和常用存储方法，以及栈和队列的应用举例，还讨论了递归、分治、回溯等算法设计的策略。    第4章介绍了字符串的基本概念，字符串的顺序、堆式、链式存储表示，字符串的模式匹配算法，主要包括BF和KMP算法。    第5章介绍了数组和广义表的概念，包括一维数组的存储表示和多维数组的存储表示，数组元素存储位置的计算，特殊矩阵，包括对称矩阵、三对角矩阵和w对角矩阵的压缩存储方法，稀疏矩阵的压缩存储及其矩阵转置、相加、相乘的实现，广义表的特性、存储表示及广义表的递归算法。    第6章介绍了树与二叉树的概念、表示方法及其常用操作的实现，还介绍了线索二叉树等特殊的二叉树结构，树与森林的常用表示方法及其基本操作的实现方法。    第7章介绍了树与二叉树的应用，包括Huffman树、二叉查找（排序）树、AVL树（高度平衡的二叉查找树）、堆、并查集等。特别地，本章借讨论八皇后问题，进一步讨论了回溯法，并引入了状态树和剪枝方法。    第8章介绍了图的概念、图的基本表示方法及其常用操作的实现，