第1章 绪论 1
1.1利用计算机解决问题的几个步骤 1
1.2基本概念和术语 2
1.3算法及其复杂度分析 4
1.4算法的描述语言 5
第2章 算法分析技术 7
2.1无穷大的阶 7
2.2若干序列和函数的渐进性质 8
2.2.1调和级数 8
2.2.2 Fibonacci序列 8
2.2.3 log2函数 9
2.2.4基本定理 9
2.2.5 Catalan数 10
2.2.6一个特别序列 11
2.3算法的时间复杂度 11
2.4算法的空间复杂度 13
2.5冒泡排序算法复杂度分析 13
2.6分摊复杂度分析 14
2.6.1累计法 15
2.6.2势函数法 16
2.6.3捐款记账法 17
习题 17
第3章 线性表 21
3.1顺序线性表：向量 21
3.1.1 Vector类模板的成员变量 21
3.1.2向量的迭代子 22
3.1.3获取向量的成员 22
3.1.4向量元素的删除 22
3.1.5向量的存储管理 22
3.1.6添加函数 23
3.1.7完整的Vector类 23
3.2单链表 25
3.2.1单链表迭代子类 26
3.2.2添加和删除操作 26
3.3其他形式的单链表 27
3.4双链表 27
3.5静态链表 29
3.6动态内存管理 31
3.7矩阵 35
3.8对称矩阵 36
3.9稀疏矩阵 36
习题 39
第4章 栈与队列 40
4.1栈的定义与实现 40
4.2栈与函数调用 41
4.2.1 函数调用框架 42
4.2.2汉诺塔问题 43
4.2.3间接递归调用 44
4.3广义栈 44
4.4回溯法 45
4.4.1八皇后问题 46
4.4.2八皇后问题回溯法的改进 47
4.5队列 48
4.5.1用链表实现队列 49
4.5.2用循环数组实现队列 49
4.6双端队列 51
4.7基数排序 51
习题 53
第5章 字符串与模式匹配算法 54
5.1字符集与字符 54
5.2字符串 54
5.3简单模式匹配算法 55
5.4 KMP算法 55
5.4.1 KMP算法的改进 59
5.4.2 KMP类 61
5.5有限状态自动机模式匹配算法 62
5.5.1有限状态自动机 62
5.5.2模式匹配有限状态自动机 62
5.6 Boyer-Moore模式匹配算法 63
5.7 BM- KMP模式匹配算法 65
习题 65
第6章 树与二叉树 66
6.1树与森林 66
6.2二叉树 67
6.3二叉树的二叉链表表示 71
6.4二叉树的递归遍历 72
6.5二叉树的非递归遍历 73
6.5.1非递归先序遍历 73
6.5.2非递归中序遍历 74
6.5.3非递归后序遍历 74
6.5.4二叉树的构造 75
6.5.5二叉树的显示 76
6.6中序线索化二叉树 76
6.6.1中序线索化二叉树的实现 76
6.6.2遍历中序线索化二叉树 77
6.7二叉树的其他存储表示 77
6.7.1三叉链表表示法 77
6.7.2完全二叉树表示 78
6.7.3三元组表示法 78
6.7.4双亲表示法 78
6.7.5带右链的先根序表示法 78
6.7.6双标志先根序表示法 79
6.8森林与二叉树的对应 80
6.9树与森林的遍历 80
6.10树与森林的存储表示 81
6.10.1树与森林的孩子、兄弟表示法 83
6.10.2无序树的双亲表示法 83
6.11并查集 83
6.11.1复杂度分析 85
6.11.2加权合并 85
6.11.3按秩合并 85
6.11.4折叠查找及其分摊复杂度分析 86
6.11.5并查集的完整实现 88
6.11.6迷宫设计 88
6.12 Huffman树 89
6.12.1无前缀编码与扩充二叉树 89
6.12.2 Huffman算法 89
6.12.3 Huffman压缩 90
习题 91
第7章 选择 94
7.1用数组实现的堆 94
7.1.1极大堆与极小堆 94
7.1.2极大极小堆 96
7.1.3双端堆 100
7.1.4d叉堆 101
7.1.5置换选择 101
7.2用二叉树或树实现的堆 103
7.2.1左堆 103
7.2.2扁堆 106
7.2.3二项式堆 109
7.2.4 Fibonacci堆 110
7.2.5配对堆 116
习题 119
第8章 查找 122
8.1查找结构 122
8.2顺序查找 122
8.2.1顺序查找表类模板 123
8.2.2顺序表的性能分析 123
8.2.3自适应顺序查找 124
8.3哈希表 124
8.3.1哈希函数的设计 124
8.3.2哈希表长M的选取 126
8.3.3冲突处理 126
8.3.4哈希表的性能分析 129
8.4二分查找 131
8.5跳跃表 132
8.5.1随机跳跃表 133
8.5.2 1-2-3跳跃表 134
8.6排序二叉树 135
8.6.1查找、添加和删除操作 136
8.6.2排序二叉树类模板 137
8.6.3查找的性能分析 138
8.7 AVL树 139
8.7.1 AVL树的添加 139
8.7.2 AVL树的删除 141
8.7.3 AVL树的实现及其复杂度 141
8.8 B树 142
8.8.1 B树的查找 142
8.8.2 B树的添加 142
8.8.3 B树的删除 143
8.8.4 B树 144
8.9 AA树 144
8.9.1 AA树的添加 145
8.9.2 AA树的实现 145
8.9.3 AA树类模板 147
8.10红黑树 148
8.10.1红黑树的添加 148
8.10.2红黑树的删除 149
8.10.3自上而下的添加和删除 151
8.11排序二叉堆 152
8.11.1排序二叉堆的添加 152
8.11.2排序二叉堆类模板 153
8.12最佳排序二叉树 153
8.13 Splay树 155
8.13.1Splay运算 156
8.13.2查找操作的分摊复杂度分析 156
8.14多关键字查找 158
8.14.1双链树 158
8.14.2 Trie树 159
8.15索引结构 160
习题 161
第9章 排序 163
9.1插入排序 164
9.1.1插入排序的实现 164
9.1.2插入排序算法的复杂度分析 165
9.1.3插入排序的改进 165
9.2选择排序 166
9.3 Shell排序 166
9.4堆排序 169
9.4.1极大堆及堆排序的实现 169
9.4.2堆排序的性能分析 170
9.5快速排序 171
9.5.1快速排序的性能分析 171
9.5.2快速排序的初步实现 173
9.5.3快速排序的改进 173
9.5.4中位数 175
9.6自省排序 177
9.7间接排序 177
9.8归并排序 179
9.8.1归并的工作量 180
9.8.2归并排序及其性能分析 180
9.8.3数组的归并排序及其性能分析 180
9.8.4单链表的归并 181
9.9基于比较的排序算法的时间复杂度下界 183
9.10基数排序 184
9.11外部排序 185
9.11.1初始序串的生成：双堆实现 185
9.11.2 K路归并的实现：败者树 186
9.11.3最佳归并树 187
习题 188
第10章 图 190
10.1图的定义及相关基本术语 190
10.2图的存储与表示 191
10.2.1单重图的邻接矩阵表示法 191
10.2.2有向图的邻接表表示法 191
10.2.3有向图的逆邻接表表示法 191
10.2.4无向图的多重邻接表表示法 192
10.3图的抽象界面 192
10.3.1弧边的界面 193
10.3.2图的构造函数 193
10.3.3弧边迭代子 193
10.4抽象界面的邻接矩阵实现 194
10.4.1 Weight-traits类模板 194
10.4.2矩阵模板 195
10.4.3弧边类型的定义 196
10.4.4弧边迭代子基类 197
10.4.5有向图弧边迭代子基类 197
10.4.6无向图弧边迭代子基类 197
10.4.7无向图弧边迭代子 199
10.4.8图的基类 200
10.4.9有向图类模板 200
10.4.10无向图类模板 201
10.4.11应用例子 201
10.5图的遍历及其应用 202
10.5.1深度优先遍历及其应用 202
10.5.2深度优先遍历的非递归程序 204
10.5.3深度优先遍历的复杂度 205
10.5.4 Kosaraju算法 205
10.5.5 Tarjan算法 206
10.5.6无向图的深度优先遍历 208
10.5.7重连通图 208
10.5.8宽度优先遍历及其应用 210
10.6有向无圈图 211
10.6.1集合上的偏序 211
10.6.2拓扑排序 211
10.6.3 AOE网和关键路径 212
10.7最小代价生成树 214
10.7.1 Kruskal算法 215
10.7.2 Prim算法 216
10.8最短路径问题 219
10.8.1 Dijkstra算法 219
10.8.2 Peter算法 221
10.8.3 Bellman-Ford算法 221
10.8.4 Floyd算法 224
10.9最大流问题 224
10.9.1广义路径法 225
10.9.2预置推送法 228
习题 232
第11章 STL简介 234
11.1迭代子 234
11.1.1半开半闭区间 235
11.1.2自白迭代子类 236
11.2泛函 240
11.2.1纯泛函 241
11.2.2拟序泛函 241
11.2.3自白泛函类 241
11.2.4自白泛函转换模板 243
11.3算法 245
11.3.1几个实用的函数模板 245
11.3.2日常事务类算法 246
11.3.3查找类算法 250
11.3.4排序类算法 251
11.3.5工作类算法 253
11.3.6已排序区间上的算法 256
11.3.7有关堆的算法 260
11.3.8处理未经初始化的内存 260
11.4容器 261
11.4.1 STL容器的共有界面 261
11.4.2顺序容器 262
11.4.3排序容器 265
11.4.4哈希容器 267
11.5适配器 268
11.5.1容器适配器 268
11.5.2迭代子适配器 270
11.5.3泛函适配器 274
11.5.4应用举例 276
11.5.5后记 277
第12章 C＋＋语言概要 279
12.1注释 279
12.2变量 280
12.3引用 280
12.4常量 281
12.5强制类型转换 282
12.6名字空间 284
12.7动态内存分配 287
12.8输入／输出 287
12.9函数原型声明、函数名重载及默认参数 288
12.10类 289
12.11类模板 291
12.12函数模板 292
第13章 伪随机数产生与高精度计时器 294
13.1线性同余方法 294
13.2加法方法 296
13.3抽牌技术 298
13.4高精度计时器 298
参考文献 301
索引 303