第1章集腋成裘——渐增型算法 1
1.1算法设计与分析 1
1.2插入排序算法 4
1.2.1算法描述与分析 4
1.2.2程序实现 6
1.2.3应用——赢得舞伴 32
1.3两个有序序列的合并算法 33
1.3.1算法描述与分析 33
1.3.2程序实现 36
1.4序列的划分 47
1.4.1算法描述与分析 47
1.4.2程序实现 49
1.5小结 55
第2章化整为零——分治算法 56
2.1 Hanoi塔问题与递归算法 56
2.1.1算法的描述与分析 56
2.1.2程序实现 59
2.1.3应用——新Hanoi塔游戏 63
2.2归并排序算法 66
2.2.1算法描述与分析 66
2.2.2程序实现 67
2.2.3应用——让舞伴更开心 73
2.3快速排序算法 74
2.3.1算法描述与分析 74
2.3.2程序实现 77
2.4堆的实现 84
2.4.1堆的概念及其创建 84
2.4.2程序实现 89
2.5堆排序 95
2.5.1算法描述与分析 95
2.5.2程序实现 96
2.6基于二叉堆的优先队列 101
2.6.1算法描述与分析 101
2.6.2程序实现 102
2.7关于排序算法 114
2.7.1比较型排序算法的时间复杂度 114
2.7.2 C/C+++/Java提供的排序函数（方法） 116
2.7.3应用——环法自行车赛 117
2.8小结 118
第3章记表备查——动态规划 120
算法 120
3.1矩阵链乘法 121
3.1.1算法描述与分析 121
3.1.2程序实现 125
3.1.3应用——牛牛玩牌 131
3.2最长公共子序列 133
3.2.1算法描述与分析 133
3.2.2程序实现 136
3.2.3算法的应用 143
3.3 0-1背包问题 147
3.3.1算法描述与分析 147
3.3.2程序实现 149
3.3.3算法的应用 153
3.4带权有向图中任意两点间的最短路径 156
3.4.1算法描述与分析 156
3.4.2程序实现 160
3.4.3应用——牛牛聚会 166
3.5小结 168
第4章高效的选择——贪婪算法 169
4.1活动选择问题 169
4.1.1算法描述与分析 169
4.1.2程序实现 172
4.1.3贪婪算法与动态规划 177
4.1.4应用——海岸雷达 179
4.2 Huffman编码 181
4.2.1算法描述与分析 181
4.2.2程序实现 185
4.2.3应用——R-叉Huffman树 195
4.3最小生成树 199
4.3.1算法描述与分析 199
4.3.2程序实现 202
4.3.3应用——北方通信网 212
4.4单源最短路径问题 214
4.4.1算法描述与分析 214
4.4.2程序实现 217
4.4.3应用——西气东送 224
45小结 227
第5章艰苦卓绝——回溯算法 228
5.1组合问题与回溯算法 228
5.1.1 3-着色问题 228
5.1.2 n-皇后问题 231
5.1.3 Hamilton回路问题 234
5.1.4子集和问题 236
5.2解决组合问题的回溯算法框架 237
5.2.1算法框架 237
5.2.2程序实现 241
5.3排列树和子集树 253
5.3.1子集树问题 253
5.3.2排列树问题 258
5.4用回溯算法解决组合优化问题 261
5.4.1算法框架 261
5.4.2旅行商问题 263
5.4.3应用 268
5.5 P、NP和NP-完全问题 276
5.6小结 278
第6章图的搜索算法 280
6.1广度优先搜索 282
6.1.1算法描述与分析 282
6.1.2程序实现 285
6.1.3应用——攻城掠地 293
6.2深度优先搜索 296
6.2.1算法描述与分析 296
6.2.2程序实现 298
6.2.3有向无圈图的拓扑排序 301
6.2.4应用——全排序 309
6.3有向图的强连通分支 311
6.3.1算法描述与分析 311
6.3.2程序实现 315
6.3.3应用——亲情号 320
6.4无向图的双连通分支 323
6.4.1算法描述与分析 323
6.4.2程序实现 326
6.4.3应用——雌雄大盗 329
6.5流网络与最大流问题 331
6.5.1算法描述与分析 331
6.5.2程序实现 342
6.5.3应用 344
6.6小结 347
第7章集组合优化问题之大成——线性规划 348
7.1标准形式与松弛形式 351
7.1.1线性规划的标准形式 351
7.1.2线性规划的松弛形式 355
7.2单纯形算法 358
7.2.1单纯形算法的例子 358
7.2.2轴转操作 361
7.2.3正规的单纯形算法 364
7.3初始基本可行解 372
7.4应用——将组合优化问题形式化为线性规划 381
7.5小结 385
第8章图形学基础——计算几何 386
8.1线段的性质 386
8.1.1叉积及其应用 387
8.1.2程序实现 390
8.2判断是否存在线段相交 393
8.2.1算法描述与分析 394
8.2.2程序实现 397
8.3求凸壳 401
8.3.1 Graham扫描 402
8.3.2 Jarvis行进 409
8.4求最邻近点对 412
8.4.1算法描述与分析 413
8.4.2程序实现 416
8.5应用 418
8.5.1光导管 418
8.5.2最小边界矩形 420
8.5.3得克萨斯一日游 422
8.6小结 423
第9章实验指南 424
9.1实验平台的搭建 424
9.1.1 C、 C+++语言的实验平台 424
9.1.2 Java语言的实验平台 425
9.2代码验证 429
9.2.1 C语言代码验证 429
9.2.2 C+++语言代码验证 434
9.2.3 Java语言代码验证 435
9.3自主实验 436
9.3.1 C语言环境 436
9.3.2 C+++语言环境 438
9.3.3 Java语言环境 439
附录 442
参考文献 455