第1章 概论 1
1.1 算法的概念 1
1.1.1 什么是算法 1
1.1.2 算法描述 3
1.1.3 算法和数据结构 5
1.1.4 算法设计的基本步骤 5
1.2 算法分析 5
1.2.1 算法时间复杂度分析 6
1.2.2 算法空间复杂度分析 12
1.3 计算复杂性理论简介 13
1.3.1 图灵机模型 14
1.3.2 P类和NP类问题 19
1.3.3 NPC问题 19
上机实验题1——统计求最大、最小元素的平均比较次数 20
练习题1 20
第2章 递归算法设计技术 22
2.1 什么是递归 22
2.1.1 递归的定义 22
2.1.2 何时使用递归 23
2.1.3 递归模型 25
2.1.4 递归算法的执行过程 25
2.2 递推式的计算 29
2.2.1 用特征方程求解递归方程 30
2.2.2 用递归树方法求解递归方程 32
2.3 递归算法设计 33
2.3.1 递归与数学归纳法 33
2.3.2 递归算法设计的一般步骤 35
2.3.3 基于递归数据结构的递归算法设计 36
2.3.4 基于归纳思想的递归算法设计 40
2.4 递归算法设计示例 41
2.4.1 简单选择排序和冒泡排序 41
2.4.2 求解n皇后问题 43
2.4.3 求解简单装载问题 45
2.5 递归算法转化为非递归算法 47
2.5.1 用循环结构替代递归过程 47
2.5.2 用栈消除递归过程 48
上机实验题2——删除二叉树的子树 52
练习题2 52
第3章 穷举法 55
3.1 穷举法概述 55
3.2 穷举法的基本应用 56
3.2.1 直接采用穷举法的一般格式 56
3.2.2 简单选择排序和冒泡排序 59
3.2.3 求解幂集问题 62
3.2.4 求解0/1背包问题 65
3.2.5 求解全排列问题 67
3.2.6 求解最大连续子序列和问题 69
3.3 递归在穷举法中的应用 71
3.3.1 用递归方法求解幂集问题 71
3.3.2 用递归方法求解全排列问题 73
3.3.3 用递归方法求解组合问题 74
上机实验题3——钱币兑换问题 75
练习题3 76
第4章 分治法 78
4.1 分治法概述 78
4.1.1 分治法的设计思想 78
4.1.2 分治法的求解过程 79
4.2 求解排序问题 80
4.2.1 快速排序 80
4.2.2 归并排序 82
4.3 求解查找问题 85
4.3.1 折半查找 85
4.3.2 寻找一个序列中第k小元素 87
4.3.3 寻找两个等长有序序列的中位数 89
4.4 求解最大连续子序列和问题 91
4.5 求解大整数乘法问题 93
4.6 求解矩阵乘法问题 96
4.7 并行计算简介 97
4.7.1 并行计算概述 97
4.7.2 并行计算模型 97
4.7.3 快速排序的并行算法 98
上机实验题4——求序列的最大元素和次大元素 99
练习题4 99
第5章 贪心法 101
5.1 贪心法概述 101
5.1.1 什么是贪心法 101
5.1.2 贪心法求解的问题应具有的性质 103
5.1.3 贪心法的一般求解过程 103
5.2 求解区间问题 104
5.2.1 求解区间覆盖问题 104
5.2.2 求解最大不相交区间问题 106
5.2.3 求解活动安排问题 109
5.3 求解背包问题 111
5.4 求解多机调度问题 115
5.5 哈夫曼编码 118
5.6 求解磁盘排序问题 122
上机实验题5——求解删数问题 128
练习题5 128
第6章 动态规划 131
6.1 动态规划概述 131
6.1.1 动态规划的原理 131
6.1.2 动态规划求解的基本步骤 135
6.1.3 动态规划与其他方法的比较 136
6.2 求解整数拆分问题 136
6.3 求解最长公共子序列问题 137
6.4 求解0/1背包问题 140
6.5 求解完全背包问题 145
6.6 求解最大连续子序列和问题 147
6.7 求解资源分配问题 148
上机实验题6——求最长单调递增子序列 151
练习题6 152
第7章 回溯法 154
7.1 回溯法概述 154
7.1.1 问题的解空间 154
7.1.2 什么是回溯法 157
7.1.3 回溯法的算法框架 157
7.1.4 回溯法算法的时间分析 160
7.2 求解0/1背包问题 162
7.3 求解子集和问题 167
7.4 求解排列和组合问题 168
7.4.1 求解全排列问题 168
7.4.2 求解组合问题 171
7.5 求解迷宫问题 173
7.5.1 采用回溯法递归框架求解迷宫问题 174
7.5.2 采用回溯法非递归框架求解迷宫问题 176
7.6 求解n皇后问题 178
7.6.1 不采用栈求解n皇后问题 178
7.6.2 采用栈求解n皇后问题 180
上机实验题7——求解装载问题 182
练习题7 182
第8章 分枝限界法 184
8.1 分枝限界法概述 184
8.1.1 什么是分枝限界法 184
8.1.2 分枝限界法的设计思想 185
8.1.3 分枝限界法的时间性能 187
8.2 求解0/1背包问题 187
8.2.1 采用队列式分枝限界法求解 188
8.2.2 采用优先队列式分枝限界法求解 194
上机实验题8——求解最优装载问题 197
练习题8 198
第9章 图搜索算法设计 199
9.1 图的表示 199
9.1.1 图的定义 199
9.1.2 图的存储结构 199
9.2 图的搜索方法 202
9.2.1 图搜索的概念 202
9.2.2 深度优先搜索 202
9.2.3 广度优先搜索 207
9.3 最小生成树 209
9.3.1 最小生成树的概念 209
9.3.2 普里姆算法构造最小生成树 210
9.3.3 克鲁斯卡尔算法 212
9.4 最短路径 215
9.4.1 狄克斯特拉算法 215
9.4.2 贝尔曼-福特算法 219
9.4.3 弗洛伊德算法 222
9.5 利用STL设计算法 225
9.5.1 什么是容器 226
9.5.2 什么是算法 227
9.5.3 什么是迭代器 227
9.5.4 常用STL容器的使用 228
9.6 求解TSP问题 239
9.6.1 TSP问题描述 239
9.6.2 采用穷举法求解TSP问题 239
9.6.3 采用动态规划求解TSP问题 241
9.6.4 采用回溯法求解TSP问题 244
9.6.5 采用分枝限界法求解TSP问题 246
9.6.6 采用贪心法求解TSP问题 247
9.7 求多段图的关键路径 248
9.8 网络流 253
9.8.1 相关概念 253
9.8.2 求最大流 254
9.8.3 割集与割量 257
9.8.4 求最小费用最大流 258
上机实验题9——求图着色问题 262
练习题9 262
第10章 计算几何 265
10.1 矢量运算 265
10.1.1 矢量的基本运算 266
10.1.2 判断一个点是否在一个矩形内 269
10.1.3 判断一个点是否在一条线段上 270
10.1.4 判断两条线段是否平行 270
10.1.5 判断两线段是否相交 271
10.1.6 判断一个点是否在多边形内 271
10.2 求解凸包问题 273
10.2.1 礼品包裹算法 273
10.2.2 Graham扫描算法 275
10.3 求解最近点对问题 278
10.3.1 用穷举法求最近点对 278
10.3.2 用分治法求最近点对 278
10.4 求解最远点对问题 281
10.4.1 用穷举法求最远点对 281
10.4.2 用旋转卡壳法求最远点对 282
上机实验题10——求凸多边形的直径 284
练习题10 284
附录A 部分练习题参考答案 287
附录B 上机实验题参考程序 300
附录C 书中部分算法清单 319
参考文献 322