目录



第1章数据结构概述1
1.1基本概念1
1.1.1数据、数据元素、数据对象1
1.1.2数据结构2
1.2数据结构的分类3
1.3数据类型5
1.3.1基本类型和组合类型5
1.3.2抽象数据类型5
1.4算法和算法分析8
1.4.1算法概念8
1.4.2算法分析9
习题11

第2章向量、栈和队列13
2.1线性表13
2.1.1线性表的抽象数据类型13
2.1.2线性表的结构表示15
2.2向量18
2.2.1向量的抽象数据类型18
2.2.2向量的插入和删除20
2.2.3向量的应用22
2.3栈25
2.3.1栈的抽象数据类型及其实现25
2.3.2栈的应用27
2.4递归效率分析34
2.4.1递归方程求解34
2.4.2生成函数求解递归方程35
2.4.3特征方程求解递归方程36
2.4.4递归树方法37
2.5队列38
2.5.1队列的抽象数据类型及其实现39
2.5.2队列的应用——模拟银行活动44
习题51

第3章链表53
3.1单链表53
3.1.1基本概念53
3.1.2单链表结点结构54
3.1.3单链表结构56
3.1.4栈的单链表实现65
3.1.5队列的单链表实现66
3.1.6单链表的应用举例70
3.2循环链表74
3.3双链表76
习题78

第4章串81
4.1基本概念81
4.2串的存储82
4.3串结构和串的运算83
4.4模式匹配85
4.4.1朴素的模式匹配算法85
4.4.2KMP匹配算法86
4.4.3BM匹配算法89
习题91

第5章排序93
5.1基本概念93
5.2插入排序94
5.2.1直接插入排序94
5.2.2折半插入排序95
5.2.3Shell排序97
5.3选择排序99
5.3.1直接选择排序99
5.3.2树形选择排序100
5.4交换排序101
5.4.1起泡排序101
5.4.2快速排序103
5.5分配排序106
5.5.1基本思想106
5.5.2基数排序107
5.6归并排序110
5.7外部排序113
5.7.1二路合并排序113
5.7.2多路替代选择合并排序114
5.7.3最佳合并排序114
习题116

第6章查找117
6.1基本概念117
6.2顺序查找117
6.3折半查找119
6.4分块查找121
6.5散列查找123
6.5.1概述123
6.5.2散列函数124
6.5.3冲突的处理126
6.5.4散列查找的效率129
习题130

第7章树和二叉树132
7.1树的概念132
7.2二叉树133
7.2.1二叉树的概念133
7.2.2二叉树的性质133
7.2.3二叉树的存储方式136
7.2.4树(树林)与二叉树的相互转换138
7.3树(树林)、二叉树的遍历139
7.3.1树(树林)的遍历139
7.3.2二叉树的遍历139
7.4抽象数据类型BinaryTree以及BinaryTree结构140
7.4.1抽象数据类型BinaryTree140
7.4.2一个完整的包含构建二叉树与遍历实现的例子142
7.5二叉树的遍历算法143
7.5.1非递归(使用栈)的遍历算法143
7.5.2线索化二叉树的遍历145
习题148

第8章树结构的应用150
8.1二叉排序树150
8.1.1二叉排序树与BinarySTree结构150
8.1.2二叉排序树的检索、插入、删除运算151
8.1.3等概率查找对应的最佳二叉排序树154
8.2平衡的二叉排序树157
8.2.1平衡二叉排序树的定义157
8.2.2平衡二叉排序树的插入、删除157
8.2.3AVL树高度161
8.3B树、B+树161
8.4键树和23树165
8.4.1键树165
8.4.223树167
8.5Huffman最优树与树编码168
8.5.1Huffman最优树168
8.5.2树编码171
8.6堆排序173
8.7判定树178
8.8等价类和并查集179
8.8.1等价类179
8.8.2并查集180
8.9红黑树182
8.10跳表186
8.10.1跳表时间复杂度分析187
8.10.2跳表的空间复杂度分析187
8.10.3高效的动态插入和删除188
8.10.4小结189
习题189

第9章图191
9.1基本概念191
9.2图的存储表示193
9.2.1相邻矩阵表示图193
9.2.2图的邻接表表示194
9.2.3邻接多重表195
9.3基于邻接表表示的Graph结构197
9.4图的遍历197
9.4.1深度优先遍历198
9.4.2广度优先遍历200
9.5最小代价生成树201
9.6单源最短路径问题205
9.7每一对顶点间的最短路径问题208
9.8有向无回路图209
9.8.1DAG图和AOV、AOE网209
9.8.2AOV网的拓扑排序211
9.8.3AOE网的关键路径213
习题215

第10章算法设计与分析217
10.1递归与分治217
10.1.1递归方法设计217
10.1.2分治法218
10.2回溯法220
10.3分支限界法225
10.4贪心算法231
10.5动态规划法232
10.6数据结构中的Catalan数235
10.6.1问题描述235
10.6.2问题解析235
10.6.3递归方程求解236
习题237

关键词索引239

参考文献242
第1章数据结构概述1
1.1基本概念1
1.1.1数据、数据元素、数据对象1
1.1.2数据结构2
1.2数据结构的分类3
1.3数据类型5
1.3.1基本类型、组合类型5
1.3.2抽象数据类型5
1.4算法和算法分析8
1.4.1算法概念8
1.4.2算法分析9
习题11第2章向量、栈和队列13
2.1线性表13
2.1.1线性表的抽象数据类型13
2.1.2线性表的结构表示15
2.2向量18
2.2.1向量的抽象数据类型18
2.2.2向量的插入和删除20
2.2.3向量的应用23
2.3栈26
2.3.1栈的抽象数据类型及其实现26
2.3.2栈的应用29
2.4递归效率分析36
2.4.1递归方程求解36
2.4.2生成函数求解递归方程37
2.4.3特征方程求解递归方程38
2.4.4递归树方法39
2.5队列40
2.5.1队列的抽象数据类型及其实现40
2.5.2队列的应用——模拟银行活动46
习题54第3章链表56
3.1单链表56
3.1.1基本概念56
3.1.2单链表结点结构57
3.1.3单链表结构59
3.1.4栈的单链表实现70
3.1.5队列的单链表实现71
3.1.6单链表的应用举例75
3.2循环链表80
3.3双链表82
习题84第4章串87
4.1基本概念87
4.2串的存储88
4.3串结构和串的运算89
4.4模式匹配91
4.4.1朴素的模式匹配算法91
4.4.2KMP匹配算法92
4.4.3BM匹配算法95
习题98第5章排序99
5.1基本概念99
5.2插入排序100
5.2.1直接插入排序100
5.2.2折半插入排序102
5.2.3Shell排序104
5.3选择排序105
5.3.1直接选择排序105
5.3.2树形选择排序107
5.4交换排序108
5.4.1起泡排序108
5.4.2快速排序109
5.5分配排序113
5.5.1基本思想113
5.5.2基数排序114
5.6归并排序117
5.7外部排序120
5.7.1二路合并排序120
5.7.2多路替代选择合并排序121
5.7.3最佳合并排序122
习题123第6章查找125
6.1基本概念125
6.2顺序查找125
6.3折半查找127
6.4分块查找129
6.5散列查找131
6.5.1概述131
6.5.2散列函数132
6.5.3冲突的处理134
6.5.4散列查找的效率137
习题138第7章树和二叉树140
7.1树的概念140
7.2二叉树141
7.2.1二叉树的概念141
7.2.2二叉树的性质141
7.2.3二叉树的存储方式144
7.2.4树(树林)与二叉树的相互转换146
7.3树(树林)、二叉树的遍历147
7.3.1树(树林)的遍历147
7.3.2二叉树的遍历147
7.4抽象数据类型BinaryTree以及BinaryTree结构148
7.4.1抽象数据类型BinaryTree148
7.4.2一个完整的包含构建二叉树与遍历实现的例子150
7.5二叉树的遍历算法151
7.5.1非递归(使用栈)的遍历算法151
7.5.2线索化二叉树的遍历153
习题157第8章树状结构的应用159
8.1二叉排序树159
8.1.1二叉排序树与BinarySTree结构159
8.1.2二叉排序树的检索、插入、删除运算160
8.1.3等概率查找对应的最佳二叉排序树164
8.2平衡的二叉排序树166
8.2.1平衡二叉排序树的定义166
8.2.2平衡二叉排序树的插入、删除167
8.2.3AVL树高度170
8.3B树、B+树171
8.4键树和23树175
8.4.1键树175
8.4.223树177
8.5Huffman最优树与树编码178
8.5.1Huffman最优树178
8.5.2树编码181
8.6堆排序183
8.7判定树189
8.8等价类和并查集190
8.8.1等价类190
8.8.2并查集190
8.9红黑树193
8.10跳表197
8.10.1跳表时间复杂度分析198
8.10.2跳表的空间复杂度分析198
8.10.3高效的动态插入和删除199
8.10.4小结200
习题201第9章图203
9.1基本概念203
9.2图的存储表示205
9.2.1相邻矩阵表示图205
9.2.2图的邻接表表示206
9.2.3邻接多重表207
9.3基于邻接表表示的Graph结构209
9.4图的遍历210
9.4.1深度优先遍历210
9.4.2广度优先遍历212
9.5最小代价生成树213
9.6单源最短路径问题217
9.7每一对顶点间的最短路径问题220
9.8有向无回路图222
9.8.1DAG图和AOV、AOE网222
9.8.2AOV网的拓扑排序224
9.8.3AOE网的关键路径226
习题228第10章算法设计与分析230
10.1递归与分治230
10.1.1递归方法设计230
10.1.2分治法231
10.2回溯法233
10.3分支限界法238
10.4贪心算法245
10.5动态规划法246
10.6数据结构中的Catalan数249
10.6.1问题描述249
10.6.2问题解析249
10.6.3递归方程求解251
习题252关键词索引254
参考文献257
第1章数据结构概述/1
1.1基本概念/1
1.1.1数据、数据元素、数据对象/1
1.1.2数据结构/2
1.2数据结构的分类/3
1.3数据类型/5
1.3.1基本类型、组合类型/5
1.3.2抽象数据类型/5
1.4算法和算法分析/8
1.4.1算法概念/8
1.4.2算法分析/9
习题/11第2章向量、栈和队列/13
2.1线性表/13
2.1.1线性表的抽象数据类型/13
2.1.2线性表的结构表示/15
2.2向量/18
2.2.1向量的抽象数据类型/18
2.2.2向量的插入和删除/20
2.2.3向量的应用/23
2.3栈/26
2.3.1栈的抽象数据类型及其实现/26
2.3.2栈的应用/29
2.4递归效率分析/36
2.4.1递归方程求解/36
2.4.2生成函数求解递归方程/37
2.4.3特征方程求解递归方程/38
2.4.4递归树方法/39
2.5队列/40
2.5.1队列的抽象数据类型及其实现/40
2.5.2队列的应用——模拟银行活动/46
习题/54
第3章链表/56
3.1单链表/56
3.1.1基本概念/56
3.1.2单链表结点结构/57
3.1.3单链表结构/59
3.1.4栈的单链表实现/70
3.1.5队列的单链表实现/71
3.1.6单链表的应用举例/75
3.2循环链表/80
3.3双链表/82
习题/84第4章串/87
4.1基本概念/87
4.2串的存储/88
4.3串结构和串的运算/89
4.4模式匹配/91
4.4.1朴素的模式匹配算法/91
4.4.2KMP匹配算法/92
4.4.3BM匹配算法/95
习题/98第5章排序/99
5.1基本概念/99
5.2插入排序/100
5.2.1直接插入排序/100
5.2.2折半插入排序/102
5.2.3Shell排序/104
5.3选择排序/105
5.3.1直接选择排序/105
5.3.2树形选择排序/107
5.4交换排序/108
5.4.1起泡排序/108
5.4.2快速排序/109
5.5分配排序/113
5.5.1基本思想/113
5.5.2基数排序/114
5.6归并排序/117
5.7外部排序/120
5.7.1二路合并排序/120
5.7.2多路替代选择合并排序/121
5.7.3最佳合并排序/122
习题/123第6章查找/125
6.1基本概念/125
6.2顺序查找/125
6.3折半查找/127
6.4分块查找/129
6.5散列查找/131
6.5.1概述/131
6.5.2散列函数/132
6.5.3冲突的处理/134
6.5.4散列查找的效率/137
习题/138第7章树和二叉树/140
7.1树的概念/140
7.2二叉树/141
7.2.1二叉树的概念/141
7.2.2二叉树的性质/141
7.2.3二叉树的存储方式/144
7.2.4树(树林)与二叉树的相互转换/146
7.3树(树林)、二叉树的遍历/147
7.3.1树(树林)的遍历/147
7.3.2二叉树的遍历/147
7.4抽象数据类型BinaryTree以及BinaryTree
结构/148
7.4.1抽象数据类型BinaryTree/148
7.4.2一个完整的包含构建二叉树与遍历
实现的例子/150
7.5二叉树的遍历算法/151
7.5.1非递归(使用栈)的遍历算法/151
7.5.2线索化二叉树的遍历/153
习题/157第8章树状结构的应用/159
8.1二叉排序树/159
8.1.1二叉排序树与BinarySTree结构/159
8.1.2二叉排序树的检索、插入、删除
运算/160
8.1.3等概率查找对应的最佳二叉排
序树/164
8.2平衡的二叉排序树/166
8.2.1平衡二叉排序树的定义/166
8.2.2平衡二叉排序树的插入、
删除/167
8.2.3AVL树高度/170
8.3B树、B+树/171
8.4键树和23树/175
8.4.1键树/175
8.4.223树/176
8.5Huffman最优树与树编码/178
8.5.1Huffman最优树/178
8.5.2树编码/181
8.6堆排序/183
8.7判定树/189
8.8等价类和并查集/190
8.8.1等价类/190
8.8.2并查集/190
8.9红黑树/193
习题/197第9章图/199
9.1基本概念/199
9.2图的存储表示/201
9.2.1相邻矩阵表示图/201
9.2.2图的邻接表表示/202
9.2.3邻接多重表/203
9.3基于邻接表表示的Graph结构/205
9.4图的遍历/206
9.4.1深度优先遍历/206
9.4.2广度优先遍历/208
9.5最小代价生成树/209
9.6单源最短路径问题/213
9.7每一对顶点间的最短路径问题/216
9.8有向无回路图/218
9.8.1DAG图和AOV、AOE网/218
9.8.2AOV网的拓扑排序/220
9.8.3AOE网的关键路径/222
习题/224第10章算法设计与分析/226
10.1递归与分治/226
10.1.1递归方法设计/226
10.1.2分治法/227
10.2回溯法/229
10.3分支限界法/234
10.4贪心算法/241
10.5动态规划法/242
习题/245图目录/247算法目录/252关键词索引/247参考文献/250图目录
图1.1基本的逻辑结构3
图1.2基本存储方法4
图1.3游泳池及环形过道8
图2.1向量的顺序存储19
图2.2顺序存储的栈26
图2.3中缀表达式的计值过程30
图2.4后缀表达式的计值30
图2.5中缀表达式转换成后缀表达式的过程31
图2.6汉诺塔问题的递归求解过程33
图2.7活动记录的进栈情况35
图2.8活动记录的退栈情况36
图2.9式(2.1)的递归树39
图2.10式(2.2)的递归树40
图2.11顺序存储的队列40
图2.12队列的操作41
图2.13循环队列的队空和队满41
图3.1单链表56
图3.2从链表中删除一个结点56
图3.3往链表中插入一个结点56
图3.4附加头结点的单链表57
图3.5一个实际的单链表结构65
图3.6空的循环链表80
图3.7双链表结点82
图3.8双链表82
图3.9往双链表中插入一个结点82
图3.10从双链表中删除一个结点82
图3.11题3.2用图85
图4.1串的顺序存储88图4.2串的紧缩顺序存储88
图4.3串的链接存储89
图4.4第1趟比较91
图4.5第2趟比较92
图4.6朴素的模式匹配算法执行过程92
图4.7模式P="abcabcd"的next数组的计算过程95
图4.8基于KMP匹配算法的模式匹配过程96
图5.1直接插入排序的过程100
图5.2折半查找过程102
图5.3Shell排序过程104
图5.4直接选择排序106
图5.5第一次树形选择排序选出最小排序码13107
图5.6第二次树形选择排序选出最小排序码14107
图5.7起泡排序过程108
图5.8第1趟快速排序的比较过程110
图5.9基数排序的分配和收集过程115
图5.10二路归并过程118
图5.11二路归并排序示意121
图5.12实现五路合并败者树122
图5.13实现五路合并一次替代选择后的败者树122
图5.14顺序合并的三路合并树122
图5.15三路最佳合并树123
图6.1折半查找过程128
图6.2分块查找过程130
图6.3用分离的同义词子表解决冲突137
图6.4用结合的同义词子表解决冲突137
图6.5几种不同的解决碰撞方法时的平均检索长度（横坐标为负载因子的
取值）138
图6.6题6.8用图139
图7.1家族树140
图7.2二叉树的五种基本形态141
图7.3表达式二叉树142
图7.4深度为3的满二叉树142
图7.5特殊的二叉树143
图7.6i与i+1在同一层的完全二叉树143
图7.7i与i+1不在同一层的完全二叉树143
图7.8完全二叉树的顺序存储144
图7.9非完全二叉树的顺序存储144
图7.10二叉树的LeftChildRightChild表示145
图7.11树(树林)与二叉树之间相互转换146
图7.12树林的例子147
图7.13图7.12对应的二叉树148
图7.14二叉树遍历实例150
图7.15对称序线索树153
图7.16在对称序线索化二叉树中插入新结点156
图7.17题7.5用图157
图7.18题7.7用图157
图7.19题7.14用图158
图7.20题7.15用图158
图8.1二叉排序树159
图8.2构造二叉排序树162
图8.3二叉排序树中删除一个结点164
图8.4删除结点11后的另一种形式164
图8.5两种不同的二叉排序树164
图8.6两棵扩充二叉树164
图8.7最佳二叉排序树的构造165
图8.8二叉树与结点的平衡因子167
图8.9平衡的二叉排序的生成过程(带★的点为插入后引起不平衡的点)168
图8.10二叉排序树的平衡旋转169
图8.11AVL二叉排序树结点的删除(结点中右边数字代表平衡因子)170
图8.12一棵7阶的B树171
图8.13B树的插入173
图8.14图8.13中删除元素80173
图8.15图8.13中删除元素4173
图8.16在图8.15中删除元素60174
图8.17在图8.16中删除元素70174
图8.18一棵3阶的B+树174
图8.19键树示例175
图8.20由图8.19压缩后的键树176
图8.21键树中插入记录176
图8.22两棵不同形式的23树177
图8.2323树的插入177
图8.24在图8.22(b)中插入8后23树的变化图178
图8.2523树的删除178
图8.26一棵扩充的二叉树178
图8.27赫夫曼最优树的构造过程179
图8.28Huffman编码树182
图8.29堆对应的完全二叉树183
图8.30堆中插入新结点183
图8.31堆中根结点的删除184
图8.32筛法建堆过程184
图8.33堆排序过程185
图8.34三个元素排序的判定树189
图8.35鉴别伪币的判定树189
图8.36用父指针表示的树状结构存储的并查集191
图8.37并查集的查找、合并过程191
图8.38Union加权规则示意图192
图8.39路径压缩的例子193
图8.40一棵阶为2的红黑树194
图8.41红黑树的生长过程194
图8.42一棵2阶红黑树195
图8.43红黑树中删除元素88195
图8.44图8.43调整后的红黑树196
图8.45图8.44中删除元素71196
图8.46图8.45调整后的红黑树196
图8.47图8.46中删除元素63196
图8.48调整图8.47后的红黑树197
图8.49题8.15用图198
图9.1无向图和有向图199
图9.2图G4=(V,E)200
图9.3图G3的强连通分量201
图9.4G1的生成树201
图9.5G3的生成树林201
图9.6图G5(网络)201
图9.7图的邻接表表示203
图9.8G5的邻接表表示204
图9.9图9.7(a)的邻接多重表表示204
图9.10图9.7(c)的多重链表表示205
图9.11有向图深度优先搜索过程206
图9.12无向图深度方向优先遍历207
图9.13广度优先生成树(树林)209
图9.14T的变化图210
图9.15Prim算法构造最小生成树的过程211
图9.16Kruskal构造最小生成树的过程213
图9.17有向图G213
图9.18含三个顶点的有向网络217
图9.19表达式树 218
图9.20共享结点后的表达式树219
图9.21表示各课程优先关系的AOV网219
图9.22一个AOV网的例子220
图9.23图9.22的关键路径为(a1,a4,a8,a11)或(a1,a4,a7,a10)222
图9.24题9.1用图224
图9.25题9.2用图224
图9.26题9.3用图224
图9.27题9.5用图224
图9.28题9.6用图225
图9.29题9.7用图225
图9.30题9.10用图225
图9.31题9.12用图225
图10.1用01矩阵表示的迷宫230
图10.201背包问题的解空间树235
图10.3树T241
图10.4树T0241
图10.5树T1242
图10.6内部结点构造图242
图10.7题10.5用图245
算 法 目 录
算法1.1计算修建游泳池工程造价8
算法1.2计算两个n×n矩阵的乘积10
算法2.1线性表运算15
算法2.2向量运算19
算法2.3向量的插入21
算法2.4向量的删除22
算法2.5集合并运算23
算法2.6集合交运算24
算法2.7约瑟夫问题25
算法2.8堆栈运算27
算法2.9后缀表达式计值31
算法2.10求和与阶乘的递归算法33
算法2.11汉诺塔问题的递归求解实现34
算法2.12阶乘的递归调用35
算法2.13队列的运算42
算法2.14优先级队列45
算法2.15事件驱动模拟49
算法3.1单链表结点及操作58
算法3.2单链表中的运算60
算法3.3用Nodelib中的函数实现单链表的建立和查找68
算法3.4基于单链表结构的操作方法实现单链表的建立和查找69
算法3.5链栈运算70
算法3.6链队列运算72
算法3.7打印缓冲池76
算法3.8模拟打印缓冲池的实现主函数78
算法3.9循环链表运算81
算法3.10双链表中的运算83算法4.1串运算90
算法4.2KMP匹配算法93
算法4.3计算next数组94
算法5.1直接插入排序101
算法5.2折半插入排序102
算法5.3Shell排序105
算法5.4直接选择排序106
算法5.5起泡排序108
算法5.6快速排序111
算法5.7基数排序115
算法5.8归并排序118
算法5.9一趟两组归并119
算法5.10两组归并119
算法6.1顺序查找126
算法6.2折半查找128
算法6.3线性探测法解决冲突135
算法6.4用双散列函数解决冲突136
算法7.1二叉树构建与遍历150
算法7.2使用栈的二叉树前序遍历151
算法7.3使用栈的二叉树对称序遍历152
算法7.4使用栈的二叉树后序遍历152
算法7.5对称序线索化二叉树154
算法7.6在对称序线索树中找指定结点的对称序后继155
算法7.7对称序遍历对称序线索化二叉树155
算法7.8在对称序线索化二叉树中插入一新结点156
算法8.1将p所指结点插入以q为根结点指针的二叉排序树中160
算法8.2构造二叉排序树161
算法8.3二叉排序树中结点的删除162
算法8.4构造Huffman树180
算法8.5大根堆185
算法9.1基于邻接表表示图的深度优先遍历算法207
算法9.2Prim算法211
算法9.3Dijkstra算法215
算法9.4Floyd算法求网络中任意两顶点间的最短路径217
算法9.5拓扑排序221
算法10.1整数划分227
算法10.2迷宫问题230
算法10.3n皇后问题233
算法10.4背包问题的分支限界法算法236
算法10.5求两字符串的最长公共子序列243