第1章 算法设计的基础知识 1
1.1 计算机与算法 1
1.1.1 计算机问题求解 1
1.1.2 算法的概念 2
1.1.3 算法的常用表示方法 3
1.2 算法的效率分析 6
1.2.1 算法效率的度量 6
1.2.2 函数增长的阶 7
1.2.3 计算复杂度的估算 10
1.3 习题 14
第2章 算法设计的基本策略 16
2.1 蛮力与贪心 16
2.1.1 蛮力法 16
2.1.2 贪心法 17
2.1.3 应用实例 17
2.2 递归与分治 21
2.2.1 递归法 21
2.2.2 分治法 23
2.2.3 应用实例 25
2.3 回溯与分支限界 30
2.3.1 回溯法 30
2.3.2 分支限界法 31
2.3.3 应用实例 32
2.4 动态规划 37
2.4.1 算法原理 37
2.4.2 应用实例 39
2.5 习题 44
第3章 排序算法设计与分析 46
3.1 基本排序算法 46
3.1.1 冒泡排序 46
3.1.2 插入排序 48
3.1.3 选择排序 51
3.2 进阶排序算法 54
3.2.1 归并排序 54
3.2.2 堆排序 58
3.2.3 快速排序 61
3.2.4 希尔排序 63
3.3 线性时间排序算法 65
3.3.1 计数排序 65
3.3.2 桶排序 66
3.3.3 基数排序 68
3.4 排序算法的应用 69
3.4.1 排序归约问题 69
3.4.2 合并果子问题 73
3.4.3 最优树的构造问题 77
3.5 习题 79
第4章 树模型及其算法设计 81
4.1 树的基本模型 81
4.1.1 树与二叉树 81
4.1.2 平衡树及其操作 83
4.1.3 红黑树及其操作 87
4.2 树的进阶模型 93
4.2.1 键树及其操作 93
4.2.2 B树及其操作 94
4.2.3 二项树及其操作 101
4.3 树模型的基本算法 105
4.3.1 树的递归遍历算法 106
4.3.2 树的非递归遍历算法 107
4.3.3 森林与树的转换 111
4.4 树模型的应用 115
4.4.1 找假币问题 115
4.4.2 串查找与排序问题 117
4.4.3 轮流摸牌问题 119
4.4.4 霍夫曼编码问题 121
4.5 习题 124
第5章 图模型及其算法设计 126
5.1 图模型的基础知识 126
5.1.1 图的基本概念 126
5.1.2 图的表示与存储 129
5.1.3 图的结构与性质 131
5.2 图模型的基本算法 133
5.2.1 图的遍历 133
5.2.2 最小生成树 137
5.2.3 最短路径 143
5.3 特殊图模型与算法 151
5.3.1 欧拉图及其应用 151
5.3.2 哈密顿图及其应用 154
5.3.3 偶图及其应用 157
5.3.4 平面图及其应用 162
5.4 图模型的应用 168
5.4.1 公共汽车通票问题 169
5.4.2 重型运输问题 171
5.4.3 中国邮路问题 173
5.4.4 关键路径问题 175
5.5 习题 179
第6章 网络流模型及其算法设计 182
6.1 最大网络流问题 182
6.1.1 网络与流的基本概念 182
6.1.2 Ford-Fulkerson算法 184
6.1.3 EK算法与Dinic算法 188
6.1.4 预流推进算法 194
6.2 最小费用流问题 196
6.2.1 最小费用流 196
6.2.2 消圈算法 197
6.2.3 最小费用路径算法 199
6.3 二分匹配问题 201
6.3.1 网络流解法 201
6.3.2 匈牙利算法 202
6.3.3 最佳匹配问题 205
6.4 网络流算法的应用 207
6.4.1 列车调度问题 208
6.4.2 毛巾供应问题 209
6.4.3 植物大战僵尸问题 210
6.4.4 稳定婚配问题 212
6.5 习题 215
第7章 查找算法设计与分析 217
7.1 静态表查找算法 217
7.1.1 顺序表查找 217
7.1.2 有序表查找 218
7.1.3 静态树表查找 222
7.1.4 索引顺序表查找 225
7.2 散列表查找算法 226
7.2.1 散列表的基本概念 226
7.2.2 散列函数的构造 227
7.2.3 常用的Hash冲突处理方法 228
7.2.4 散列表的查找及分析 230
7.3 搜索树查找算法 232
7.3.1 广度优先查找 233
7.3.2 深度优先查找 235
7.3.3 最佳优先查找 236
7.4 特殊树查找算法 238
7.4.1 二叉查找树查找算法 238
7.4.2 红黑树查找算法 243
7.4.3 键树查找算法 245
7.4.4 B树查找算法 248
7.5 查找算法的应用 252
7.5.1 运动员最佳配对问题 252
7.5.2 拼写检查器问题 254
7.5.3 八数码问题 255
7.5.4 骑士游历问题 259
7.6 习题 262
第8章 组合优化算法设计与分析 264
8.1 基本组合优化算法 264
8.1.1 线性规划算法 265
8.1.2 梯度法与共轭梯度法 269
8.1.3 牛顿法与拟牛顿法 272
8.2 启发式组合优化算法 276
8.2.1 禁忌搜索算法 276
8.2.2 模拟退火算法 279
8.2.3 遗传算法 282
8.3 深度学习模型与算法 287
8.3.1 浅层学习与深度学习 287
8.3.2 深度学习的系统架构 292
8.3.3 DBN模型及其学习算法 298
8.3.4 CNN模型及其学习算法 302
8.4 组合优化算法应用 306
8.4.1 顶点覆盖问题 306
8.4.2 最佳装箱问题 308
8.4.3 旅行商问题 311
8.4.4 手写字符识别问题 314
8.5 习题 317
第9章 专用算法设计技术 319
9.1 数据压缩算法 319
9.1.1 数据压缩概述 319
9.1.2 无损压缩算法 320
9.1.3 有损压缩算法 326
9.2 数据加密算法 331
9.2.1 数据加密概述 332
9.2.2 传统加密算法 332
9.2.3 非对称加密算法 336
9.3 字符串匹配算法 339
9.3.1 BF匹配算法 340
9.3.2 RK匹配算法 341
9.3.3 KMP匹配算法 343
9.3.4 BM匹配算法 348
9.4 习题 353
参考文献 354