目录 1
第1章 绪言 1
1.1 章节结构 1
1.2 变量的命名 3
1.3 概率 4
1.4 渐近符号 5
1.5 关于程序设计语言 6
1.6 关于算法的代码 7
1.7 复杂性度量和实际计时 8
第2章 基本概念 10
2.1 数据结构的描述 10
2.1.1 数据对象的文法 10
2.1.2 对数据对象的约束 14
2.2 算法描述 16
2.2.1 基本（或原子）操作 17
2.2.2 构造过程 19
2.2.3 互换性 26
第3章 搜索算法 28
3.1 顺序搜索 28
3.1.1 基本的顺序搜索 28
3.1.2 自组织顺序搜索：移至表首法 30
3.1.3 自组织顺序搜索：置换法 34
3.1.4 最佳顺序搜索 36
3.1.5 跳跃搜索 36
3.2 有序数组的搜索 38
3.2.1 二分搜索 39
3.2.2 插值搜索 41
3.2.3 插值顺序搜索 43
3.3 散列算法 45
3.3.1 均匀探测散列法 48
3.3.2 随机探测散列法 50
3.3.3 线性探测散列法 51
3.3.4 双散列法 55
3.3.5 二次散列法 58
3.3.6 有序散列法 60
3.3.7 均匀探测法的重构方案：Brent算法 62
3.3.8 均匀探测法的重构方案：二叉树散列法 65
3.3.9 最佳散列法 68
3.3.10 直接链散列法 70
3.3.11 分离链散列法 72
3.3.12 共生散列法 74
3.3.13 可扩充散列法 77
3.3.14 线性散列法 80
3.3.15 使用最少内部存储器的外部散列法 82
3.4 递归结构搜索 85
3.4.1 二叉树搜索 85
3.4.2 B树 111
3.4.3 索引顺序文件和被索引顺序文件 124
3.4.4 数字树 127
3.5 多维搜索 138
3.5.1 四叉树 139
3.5.2 K维树 141
4.1.1 气泡排序 146
4.1 数组排序技术 146
第4章 排序算法 146
4.1.2 线性插入排序 148
4.1.3 快速排序 150
4.1.4 Shell排序 153
4.1.5 堆排序 157
4.1.6 插值排序 159
4.1.7 线性探测排序 161
4.1.8 小结 164
4.2 对其他数据结构排序 165
4.2.1 合并排序 166
4.2.2 链表的快速排序 168
4.2.3 组桶排序 171
4.2.4 基数排序 173
4.2.5 混合方法排序 175
4.2.6 树排序 177
4.3 合并 178
4.3.1 链表合并 179
4.3.2 数组合并 180
4.3.3 最少比较合并 182
4.4 外部排序 183
4.4.1 平衡合并排序 189
4.4.2 串联合并排序 191
4.4.3 多步合并排序 192
4.4.4 摆动合并排序 197
4.4.5 外部快速排序 199
5.1 优先队列 203
第5章 选择算法 203
5.1.1 有序／无序链表 204
5.1.2 P树 207
5.1.3 堆 209
5.1.4 VanEmde-Boas优先队列 214
5.1.5 宝塔 216
5.1.6 用作优先队列的二叉树 220
5.1.7 二项式队列 225
5.1.8 小结 226
5.2 第k个元素的选择 227
5.2.1 用排序进行选择 229
5.2.2 用尾部递归进行选择 229
5.2.3 模式的选择 231
6.1 基本运算、乘法／除法 233
第6章 算术算法 233
6.2 其它算术函数 239
6.2.1 二分求幂 239
6.2.2 算术-几何平均 241
6.2.3 超越函数 242
6.3 矩阵乘法 244
6.3.1 Strassen矩阵乘法 246
6.3.2 渐近算法的进一步改进 247
6.4 多项式计算 248
附录Ⅰ 由经验观察导出的分布 251
附录Ⅱ 渐近展开式 257
附录Ⅲ 参考资料 266
附录Ⅳ 用Pascal和C编码的算法 302