算法設計、分析與實現(xiàn)從入門到精通：C、C++和Java

第1章 集腋成裘——漸增型算法 1
1.1 算法設計與分析 1
1.2 插入排序算法 4
1.2.1 算法描述與分析 4
1.2.2 程序?qū)崿F(xiàn) 6
1.2.3 應用——贏得舞伴 30
1.3 兩個有序序列的合并算法 32
1.3.1 算法描述與分析 32
1.3.2 程序?qū)崿F(xiàn) 34
1.4 序列的劃分 45
1.4.1 算法描述與分析 45
1.4.2 程序?qū)崿F(xiàn) 46
1.5 小結(jié) 52
第2章 化整為零——分治算法 53
2.1 Hanoi塔問題與遞歸算法 53
2.1.1 算法的描述與分析 53
2.1.2 程序?qū)崿F(xiàn) 56
2.1.3 應用——新Hanoi塔游戲 59
2.2 歸并排序算法 62
2.2.1 算法描述與分析 62
2.2.2 程序?qū)崿F(xiàn) 63
2.2.3 應用——讓舞伴更開心 69
2.3 快速排序算法 70
2.3.1 算法描述與分析 70
2.3.2 程序?qū)崿F(xiàn) 72
2.4 堆的實現(xiàn) 79
2.4.1 堆的概念及其創(chuàng)建 79
2.4.2 程序?qū)崿F(xiàn) 83
2.5 堆排序 88
2.5.1 算法描述與分析 88
2.5.2 程序?qū)崿F(xiàn) 89
2.6 基于二叉堆的優(yōu)先隊列 94
2.6.1 算法描述與分析 94
2.6.2 程序?qū)崿F(xiàn) 95
2.7 關(guān)于排序算法 105
2.7.1 比較型排序算法的時間復雜度 105
2.7.2 C/C++/Java提供的排序函數(shù)(方法) 107
2.7.3 應用——環(huán)法自行車賽 108
2.8 小結(jié) 109
第3章 記表備查——動態(tài)規(guī)劃算法 111
3.1 矩陣鏈乘法 112
3.1.1 算法描述與分析 112
3.1.2 程序?qū)崿F(xiàn) 115
3.1.3 應用——牛牛玩牌 121
3.2 最長公共子序列 123
3.2.1 算法描述與分析 123
3.2.2 程序?qū)崿F(xiàn) 126
3.2.3 算法的應用 132
3.3 0-1背包問題 136
3.3.1 算法描述與分析 136
3.3.2 程序?qū)崿F(xiàn) 138
3.3.3 算法的應用 142
3.4 帶權(quán)有向圖中任意兩點間的最短路徑 144
3.4.1 算法描述與分析 144
3.4.2 程序?qū)崿F(xiàn) 148
3.4.3 應用——牛牛聚會 153
3.5 小結(jié) 155
第4章 高效的選擇——貪婪算法 156
4.1 活動選擇問題 156
4.1.1 算法描述與分析 156
4.1.2 程序?qū)崿F(xiàn) 158
4.1.3 貪婪算法與動態(tài)規(guī)劃 163
4.1.4 應用——海岸雷達 165
4.2 Huffman編碼 166
4.2.1 算法描述與分析 166
4.2.2 程序?qū)崿F(xiàn) 170
4.2.3 應用——Huffman樹 180
4.3 最小生成樹 183
4.3.1 算法描述與分析 183
4.3.2 程序?qū)崿F(xiàn) 187
4.3.3 應用——北方通信網(wǎng) 196
4.4 單源最短路徑問題 197
4.4.1 算法描述與分析 197
4.4.2 程序?qū)崿F(xiàn) 200
4.4.3 應用——西氣東送 207
4.5 小結(jié) 210
第5章 艱苦卓絕——回溯算法 211
5.1 組合問題與回溯算法 211
5.1.1 3-著色問題 211
5.1.2 n-皇后問題 214
5.1.3 Hamilton回路問題 216
5.1.4 子集和問題 218
5.2 解決組合問題的回溯算法框架 219
5.2.1 算法框架 219
5.2.2 程序?qū)崿F(xiàn) 223
5.3 排列樹和子集樹 235
5.3.1 子集樹問題 236
5.3.2 排列樹問題 241
5.4 用回溯算法解決組合優(yōu)化問題 245
5.4.1 算法框架 245
5.4.2 旅行商問題 247
5.4.3 應用 253
5.5 PNP和NP-完全問題 260
5.6 小結(jié) 262
第6章 圖的搜索算法 264
6.1 廣度優(yōu)先搜索 265
6.1.1 算法描述與分析 265
6.1.2 程序?qū)崿F(xiàn) 268
6.1.3 應用——攻城略地 276
6.2 深度優(yōu)先搜索 278
6.2.1 算法描述與分析 278
6.2.2 程序?qū)崿F(xiàn) 280
6.2.3 有向無圈圖的拓撲排序 283
6.2.4 應用——全排序 290
6.3 有向圖的強連通分支 292
6.3.1 算法描述與分析 292
6.3.2 程序?qū)崿F(xiàn) 295
6.3.3 應用——親情號 300
6.4 無向圖的雙連通分支 303
6.4.1 算法描述與分析 303
6.4.2 程序?qū)崿F(xiàn) 306
6.4.3 應用——雌雄大盜 308
6.5 流網(wǎng)絡與最大流問題 310
6.5.1 算法描述與分析 310
6.5.2 程序?qū)崿F(xiàn) 319
6.5.3 應用 321
6.6 小結(jié) 324
第7章 集組合優(yōu)化問題之大成——線性規(guī)劃 325
7.1 標準形式與松弛形式 328
7.1.1 線性規(guī)劃的標準形式 328
7.1.2 線性規(guī)劃的松弛形式 331
7.2 單純形算法 334
7.2.1 單純形算法的例子 334
7.2.2 軸轉(zhuǎn)操作 337
7.2.3 正規(guī)的單純形算法 340
7.3 初始基本可行解 347
7.4 應用——將組合優(yōu)化問題形式化為線性規(guī)劃 355
7.5 小結(jié) 359
第8章 圖形學基礎——計算幾何 360
8.1 線段的性質(zhì) 360
8.1.1 叉積及其應用 361
8.1.2 程序?qū)崿F(xiàn) 364
8.2 判斷是否存在線段相交 367
8.2.1 算法描述與分析 367
8.2.2 程序?qū)崿F(xiàn) 370
8.3 求凸殼 374
8.3.1 Graham掃描 375
8.3.2 Jarvis行進 381
8.4 求最鄰近點對 384
8.4.1 算法描述與分析 385
8.4.2 程序?qū)崿F(xiàn) 387
8.5 應用 389
8.5.1 光導管 389
8.5.2 最小邊界矩形 391
8.5.3 得克薩斯一日游 392
8.6 小結(jié) 394
附錄 395
參考文獻 410