前言 1
第1章 算法及其复杂度 1
1.1 计算机与算法 1
1.1.1 过指定垂足的直角边 1
1.1.2 三等分线段 2
1.1.3 排序 3
1.1.4 算法的定义 5
1.2.2 时间复杂度及其度量 6
1.2.1 三个层次 6
1.2 算法性能的分析与评价 6
1.2.3 空间复杂度 8
1.3 算法复杂度及其分析 8
1.3.1 O(1)——取非极端元素 8
1.3.2 O(logn)——进制转换 9
1.3.3 O(n)——数组求和 10
1.3.4 O(n2)——起泡排序 10
1.4 计算模型 11
1.4.1 可解性 11
1.3.5 O(2r)——幂函数 11
1.4.2 有效可解 12
1.4.3 下界 12
1.5 递归 12
1.5.1 线性递归 13
1.5.2 递归算法的复杂度分析 16
1.5.3 二分递归 17
1.5.4 多分支递归 20
2.1 栈 23
第2章 栈与队列 23
2.1.1 栈ADT 24
2.1.2 基于数组的简单实现 25
2.1.3 Java虚拟机中的栈 28
2.1.4 栈应用实例 30
2.2 队列 34
2.2.1 队列ADT 34
2.2.2 基于数组的实现 36
2.2.3 队列应用实例 38
2.3.1 单链表 39
2.3 链表 39
2.3.2 基于单链表实现栈 43
2.3.3 基于单链表实现队列 44
2.4 位置 45
2.4.1 位置ADT 45
2.4.2 位置接口 46
2.5 双端队列 46
2.5.1 双端队列ADT 46
2.5.2 双端队列接口 47
2.5.3 双向链表 48
2.5.4 基于双向链表实现的双端队列 49
第3章 向量、列表与序列 55
3.1 向量与数组 55
3.1.1 向量ADT 56
3.1.2 基于数组的简单实现 58
3.1.3 基于可扩充数组的实现 59
3.1.4 java.util.ArrayList类和java.util.Vector类 62
3.2.2 由秩到位置 63
3.2.1 基于节点的操作 63
3.2 列表 63
3.2.3 列表ADT 64
3.2.4 基于双向链表实现的列表 67
3.3 序列 72
3.3.1 序列ADT 72
3.3.2 基于双向链表实现序列 73
3.3.3 基于数组实现序列 75
3.4 迭代器 75
3.4.1 迭代器ADT 76
3.4.2 迭代器接口 77
3.4.3 迭代器的实现 77
3.4.4 Java中的列表及迭代器 79
第4章 树 81
4.1 术语及性质 81
4.1.1 节点的深度、树的深度与高度 82
4.1.2 节点的度与内部节点、外部节点 82
4.1.4 祖先、后代、子树和节点的高度 83
4.1.3 路径 83
4.1.5 共同祖先及最低共同祖先 84
4.1.6 有序树、m叉树 84
4.1.7 二叉树 85
4.1.8 满二叉树与完全二叉树 85
4.2 树ADT及其实现 86
4.2.1 “父亲－长子－弟弟”模型 86
4.2.2 树ADT 87
4.2.4 基于链表实现树 88
4.2.3 树的Java接口 88
4.3 树的基本算法 90
4.3.1 getSize()——统计（子）树的规模 90
4.3.2 getHeight()——计算节点的高度 90
4.3.3 getDepth()——计算节点的深度 90
4.3.4 前序、后序遍历 91
4.3.5 层次遍历 92
4.3.6 树迭代器 93
4.4.2 二叉树的Java接口 95
4.4 二叉树ADT及其实现 95
4.4.1 二叉树ADT 95
4.4.3 二叉树类的实现 98
4.5 二叉树的基本算法 103
4.5.1 getSize()、getHeight()和getDepth() 103
4.5.2 updateSize() 103
4.5.3 updateHeight() 104
4.5.4 updateDepth() 105
4.5.5 secede() 105
4.5.6 attachL()和attachR() 106
4.5.7 二叉树的遍历 107
4.5.8 直接前驱、直接后继的定位算法 107
4.6 完全二叉树的Java实现 108
4.6.1 完全二叉树的Java接口 108
4.6.2 基于向量的实现 109
第5章 优先队列 113
5.1 优先级、关键码、全序关系与优先队列 113
5.2.1 条目 114
5.2 条目与比较器 114
5.2.2 比较器 115
5.2.3 Comparator接口及其实现 116
5.3 优先队列ADT及其Java接口 117
5.3.1 优先队列的ADT描述 117
5.3.2 优先队列的Java接口 118
5.3.3 基于优先队列的排序器 119
5.5.1 基于无序列表的实现及分析 120
5.5 用列表实现优先队列 120
5.4 用向量实现优先队列 120
5.5.2 基于有序列表的实现及分析 122
5.6 选择排序与插入排序 124
5.6.1 选择排序 124
5.6.2 插入排序 124
5.6.3 效率比较 125
5.7 堆的定义及性质 125
5.7.1 堆结构 125
5.8 用堆实现优先队列 126
5.7.2 完全性 126
5.8.1 基于堆的优先队列及其实现 127
5.8.2 插入与上滤 129
5.8.3 删除与下滤 130
5.8.4 改变任意节点的关键码 132
5.8.5 建堆 132
5.9 堆排序 133
5.9.1 直接堆排序 133
5.9.2 就地堆排序 134
5.10.1 二叉编码树 136
5.10 Huffman编码树 136
5.10.2 最优编码树 137
5.10.3 Huffman编码与Huffman编码树 138
5.10.4 Huffman编码树的构造算法 141
5.10.5 基于优先队列的Huffman编码树构造算法 143
第6章 映射与词典 145
6.1 映射 145
6.1.1 映射的ADT描述 146
6.1.2 映射的Java接口 147
6.1.3 判等器 148
6.1.4 java.util包中的映射类 149
6.1.5 基于列表实现映射类 149
6.2 散列表 151
6.2.1 桶及桶数组 151
6.2.2 散列函数 151
6.2.3 散列码 152
6.2.4 压缩函数 154
6.2.5 冲突的普遍性 154
6.2.6 解决冲突 155
6.2.7 基于散列表实现映射类 159
6.2.8 装填因子与重散列 161
6.3 无序词典 162
6.3.1 无序词典的ADT描述 162
6.3.2 无序词典的Java接口 163
6.3.3 列表式无序词典及其实现 164
6.3.4 散列表式无序词典及其实现 166
6.4 有序词典 168
6.4.2 二分查找 169
6.4.1 全序关系与有序查找表 169
6.4.3 有序词典的ADT描述 170
6.4.4 有序词典的Java接口 171
6.4.5 基于有序查找表实现有序词典 171
第7章 查找树 175
7.1 二分查找树 176
7.1.1 定义 176
7.1.2 查找算法 176
7.1.3 完全查找算法 179
7.1.4 插入算法 180
7.1.5 删除算法 182
7.1.6 二分查找树节点类的实现 183
7.1.7 二分查找树类的实现 184
7.1.8 二分查找树的平均性能 187
7.2 AVL树 188
7.2.1 平衡二分查找树 188
7.2.2 等价二分查找树 188
7.2.3 等价变换 189
7.2.4 AVL树 190
7.2.5 插入节点后的重平衡 191
7.2.6 节点删除后的重平衡 195
7.2.7 AVL树的Java实现 198
7.3 伸展树 201
7.3.1 数据局部性 201
7.3.2 逐层伸展 201
7.3.3 双层伸展 203
7.3.4 分摊复杂度 205
7.3.5 伸展树的Java实现 207
7.3.6 插入 210
7.3.7 删除 211
7.4 B－树 212
7.4.1 分级存储 212
7.4.2 B－树的定义 213
7.4.3 关键码的查找 214
7.4.4 性能分析 214
7.4.5 上溢节点的处理 216
7.4.6 关键码的插入 217
7.4.7 下溢节点的处理 220
7.4.8 关键码的删除 221
第8章 排序 223
8.1 归并排序 223
8.1.1 分治策略 223
8.1.2 时间复杂度 224
8.1.3 归并算法 225
8.1.4 Mergesort的Java实现 226
8.2 快速排序 227
8.2.1 分治策略 227
8.2.2 轴点 228
8.2.3 划分算法 228
8.2.4 Quicksort的Java实现 229
8.2.5 时间复杂度 230
8.3复杂 度下界 231
8.3.1 比较树与基于比较的算法 232
8.3.2 下界 232
9.1 串及其ADT描述 235
第9章 串 235
9.2 串模式匹配 236
9.2.1 概念与记号 236
9.2.2 问题 237
9.2.3 算法效率的测试与评价 238
9.3 蛮力算法 238
9.3.1 算法描述 238
9.3.2 算法实现 239
9.4.1 蛮力算法的改进 240
9.3.3 算法分析 240
9.4 KMP算法 240
9.4.2 next[]表的定义及含义 242
9.4.3 KMP算法描述 243
9.4.4 next[]表的特殊情况 243
9.4.5 next[]表的构造 243
9.4.6 next[]表的改进 244
9.4.7 KMP算法的Java实现 245
9.5 BM算法 247
9.4.8 性能分析 247
9.5.1 坏字符策略 248
9.5.2 好后缀策略 250
9.5.3 BM算法 251
9.5.4 BM算法的Java实现 252
9.5.5 性能 255
第10章 图 257
10.1 概述 257
10.1.3 简单图 258
10.1.2 度 258
10.1.1 无向图、混合图及有向图 258
10.1.4 图的复杂度 259
10.1.5 子图、生成子图与限制子图 259
10.1.6 通路、环路及可达分量 260
10.1.7 连通性、等价类与连通分量 261
10.1.8 森林、树以及无向图的生成树 262
10.1.9 有向图的生成树 263
10.1.10 带权网络 263
10.2.1 图 264
10.2 抽象数据类型 264
10.2.2 顶点 265
10.2.3 边 267
10.3 邻接矩阵 268
10.3.1 表示方法 268
10.3.2 时间性能 268
10.3.3 空间性能 269
10.4 邻接表 270
10.4.1 顶点表和边表 270
10.4.2 顶点与邻接边表 271
10.4.3 边 273
10.4.4 基于邻接表实现图结构 275
10.5 图遍历及其算法模板 277
10.6 深度优先遍历 279
10.6.1 深度优先遍历算法 279
10.6.2 边分类 280
10.6.3 可达分量与DFS树 281
10.6.4 深度优先遍历算法模板 282
10.6.5 可达分量算法 284
10.6.6 单强连通分量算法 285
10.6.7 强连通分量分解算法 286
10.6.8 浓缩图与弱连通性 286
10.7 广度优先遍历 287
10.7.1 广度优先遍历算法 287
10.7.2 边分类 288
10.7.3 可达分量与BFS树 289
10.7.4 广度优先遍历算法模板 289
10.7.5 最短距离算法 290
10.8 最佳优先遍历 291
10.8.1 最佳优先遍历算法 291
10.8.2 最佳优先遍历算法模板 292
10.8.3 最短路径 294
10.8.4 最短路径序列 296
10.8.5 Dijkstra算法 297
10.8.6 最小生成树 300
10.8.7 Prim-Jarnik算法 302
DSA类关系图 307