第1章 开胃菜：整数运算 1
1.1 加法 2
1.2 乘法：学校方法 2
1.3 结果检查 5
1.4 递归版的学校方法 6
1.5 Karatsuba乘法 7
1.6 算法工程 9
1.7 程序 10
1.8 引理1.5和定理1.7的证明 13
1.9 实现提示 14
1.9.1 C++ 14
1.9.2 Java 14
1.10 历史注释与进一步的读物 15
第2章 概述 16
2.1 渐近表示法 16
2.2 机器模型 19
2.2.1 外部存储器 20
2.2.2 并行处理 21
2.3 伪代码 21
2.3.1 变量和基本数据类型 21
2.3.2 语句 23
2.3.3 过程与函数 23
2.3.4 面向对象 25
2.4 设计正确的算法和程序 25
2.4.1 断言和不变量 26
2.4.2 循环不变量 26
2.4.3 数据结构不变量 27
2.4.4 验证算法 27
2.5 一个示例：二分查找 27
2.6 基本算法分析 29
2.6.1 求和 29
2.6.2 递推 30
2.6.3 全局参数 33
2.7 平均情况分析 33
2.7.1 递增计数器 33
2.7.2 从左到右的最大值 34
2.7.3 线性搜索 35
2.8 随机算法 36
2.8.1 形式模型 37
2.8.2 Las Vegas和Monte Carlo算法 38
2.9 图 39
2.9.1 第一个图算法 41
2.9.2 树 41
2.9.3 有序树 42
2.10 P与NP 43
2.11 实现提示 45
2.11.1 C++ 45
2.11.2 Java 46
2.12 历史注释与进一步的读物 46
第3章 用数组与链表表示序列 47
3.1 链表 48
3.1.1 双链表 48
3.1.2 单链表 51
3.2 无界数组 52
3.2.1 无界数组的平摊分析：全局参数 53
3.2.2 无界数组的平摊分析：局部参数 55
3.2.3 二进制计数器的平摊分析 55
3.3 平摊分析 56
3.3.1 平摊分析：势能方法或银行账户方法 57
3.3.2 势能方法的普遍性 58
3.4 栈与队列 58
3.5 链表与数组 60
3.6 实现提示 61
3.6.1 C++ 61
3.6.2 Java 62
3.7 历史注释与进一步的读物 62
第4章 散列表与关联数组 64
4.1 链接法散列 66
4.2 通用散列 67
4.3 线性探测散列 71
4.4 链接法与线性探测法 72
4.5 完全散列 73
4.6 实现提示 75
4.6.1 C++ 76
4.6.2 Java 76
4.7 历史注释与进一步的读物 76
第5章 排序与选择 78
5.1 简单排序 80
5.2 归并排序——O（nlogn）的排序算法 81
5.3 下界 83
5.4 快速排序 85
5.4.1 分析 85
5.4.2 细化 87
5.5 选择 89
5.6 打破下界 91
5.7 外部排序 93
5.7.1 多路归并 94
5.7.2 采样排序 94
5.8 实现提示 96
5.8.1 C/C++ 97
5.8.2 Java 97
5.9 历史注释与进一步的读物 97
第6章 优先级队列 99
6.1 二叉堆 100
6.2 可寻址的优先级队列 104
6.2.1 配对堆 104
6.2.2 斐波那契堆 106
6.3 外部存储器 109
6.4 实现提示 110
6.4.1 C++ 110
6.4.2 Java 110
6.5 历史注释与进一步的读物 111
第7章 有序序列 112
7.1 二叉搜索树 113
7.2 （a,b）-树与红黑树 115
7.3 更多的操作 121
7.3.1 连接 121
7.3.2 拆分 122
7.4 更新操作的平摊分析 123
7.5 增强搜索树 124
7.5.1 父指针 125
7.5.2 子树大小 125
7.6 实现提示 126
7.6.1 C++ 127
7.6.2 Java 127
7.7 历史注释与进一步的读物 128
第8章 图的表示 130
8.1 无序的边序列 131
8.2 邻接数组——静态图 132
8.3 邻接表——动态图 132
8.4 邻接矩阵表示 133
8.5 隐式表示 134
8.6 实现提示 134
8.6.1 C++ 135
8.6.2 Java 135
8.7 历史注释与进一步的读物 135
第9章 图的遍历 137
9.1 广度优先搜索 137
9.2 深度优先搜索 139
9.2.1 DFS编号、完成时间和拓扑排序 140
9.2.2 强连通分量 142
9.3 实现提示 147
9.3.1 C++ 147
9.3.2 Java 148
9.4 历史注释与进一步的读物 148
第10章 最短路径 149
10.1 从基本概念到遗传算法 150
10.2 有向无环图 153
10.3 非负边代价（Dijkstra算法） 153
10.4 Dijkstra算法的平均情况分析 156
10.5 单调整数优先级队列 157
10.5.1 桶队列 157
10.5.2 基数堆 158
10.6 任意边代价（Bellman-Ford算法） 161
10.7 所有点对最短路径和节点的势 162
10.8 最短路径查询 163
10.8.1 目标定向搜索 164
10.8.2 等级 166
10.8.3 中转节点路线 166
10.9 实现提示 167
10.9.1 C++ 167
10.9.2 Java 167
10.10 历史注释与进一步的读物 168
第11章 最小生成树 169
11.1 割和环的性质 170
11.2 Jarník-Prim算法 171
11.3 Kruskal算法 172
11.4 并-查数据结构 173
11.5 外部存储器 176
11.5.1 Semiexternal的Kruskal算法 176
11.5.2 边收缩 176
11.5.3 Sibeyn算法 176
11.6 应用程序 178
11.6.1 Steiner树问题 178
11.6.2 旅行推销员之旅 179
11.7 实现提示 180
11.7.1 C++ 180
11.7.2 Java 180
11.8 历史注释与进一步的读物 180
第12章 遗传方法优化 182
12.1 线性规划：黑盒求解器 183
12.1.1 整数线性规划 185
12.2 贪婪算法：永不回头 186
12.3 动态规划：子问题的构建 189
12.4 系统搜索：有疑问，用蛮力 192
12.4.1 求解整数线性规划 194
12.5 局部搜索：全局思考，局部行动 194
12.5.1 爬山 195
12.5.2 模拟退火：从自然中学习 196
12.5.3 局部搜索的优化 201
12.6 进化算法 201
12.7 实现提示 203
12.8 历史注释与进一步的读物 204
附录A 205
A.1 数学符号 205
A.2 数学概念 206
A.3 概率论基础 207
A.4 有用的公式 210
A.4.1 证明 211
参考文献 213