從算法到程序：從應(yīng)用問題編程實(shí)踐全面體驗(yàn)算法理論

第1章計(jì)算問題1
1.1計(jì)算問題及其算法1
1.1.1計(jì)算問題及其描述1
1.1.2算法及其描述2
1.1.3偽代碼的使用約定3
1.1.4算法分析4
1.1.5算法運(yùn)行時(shí)間的漸近表示5
1.2數(shù)據(jù)結(jié)構(gòu)6
1.2.1什么是數(shù)據(jù)結(jié)構(gòu)6
1.2.2數(shù)據(jù)結(jié)構(gòu)對算法效率的影響7
1.2.3字典與字典操作8
1.3程序設(shè)計(jì)10
1.3.1算法與程序10
1.3.2數(shù)據(jù)類型的抽象與代碼通用性11
1.4數(shù)據(jù)的輸入輸出13
1.4.1應(yīng)用問題13
1.4.2標(biāo)準(zhǔn)輸入輸出15
1.4.3文件輸入輸出20
1.5計(jì)數(shù)問題22
1.5.1簡單模擬23
1.5.2加法原理和乘法原理25
1.5.3整數(shù)序列31
第2章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)37
2.1線性表38
2.1.1線性表的鏈表表示38
2.1.2對鏈表的操作39
2.1.3鏈表的程序?qū)崿F(xiàn)42
2.1.4鏈表應(yīng)用47
2.2棧53
2.2.1棧的概念及其鏈表實(shí)現(xiàn)53
2.2.2棧的程序?qū)崿F(xiàn)54
2.2.3棧的應(yīng)用56
2.3隊(duì)列62
2.3.1隊(duì)列的概念及其鏈表實(shí)現(xiàn)62
2.3.2隊(duì)列的程序?qū)崿F(xiàn)63
2.3.3隊(duì)列的應(yīng)用64
2.4二叉搜索樹68
2.4.1二叉樹及其在計(jì)算機(jī)中的表示68
2.4.2二叉搜索樹76
2.4.3二叉搜索樹的查詢操作76
2.4.4二叉搜索樹中元素的增刪78
2.4.5紅?黑樹及其性質(zhì)80
2.4.6紅?黑樹的操作83
2.4.7紅?黑樹的程序?qū)崿F(xiàn)92
2.4.8二叉搜索樹的應(yīng)用102
2.5散列表102
2.5.1直接尋址表與散列表102
2.5.2用拉鏈解決沖突104
2.5.3散列表的程序?qū)崿F(xiàn)106
2.5.4散列表的應(yīng)用109
第3章基本算法設(shè)計(jì)策略112
3.1漸增型算法112
3.1.1有序序列的合并問題112
 3.1.2序列的劃分問題117
 3.2分治算法121
3.2.1歸并排序算法122
3.2.2快速排序算法126
3.2.3序統(tǒng)計(jì)與選擇問題130
3.3排序問題的討論132
3.3.1排序的性質(zhì)132
3.3.2比較型排序算法的時(shí)間復(fù)雜度133
3.3.3應(yīng)用136
3.4堆與基于堆的優(yōu)先隊(duì)列141
3.4.1堆的概念及其創(chuàng)建141
3.4.2基于二叉堆的優(yōu)先隊(duì)列149
3.4.3應(yīng)用153
第4章代數(shù)計(jì)算169
4.1矩陣及其計(jì)算169
4.1.1矩陣與向量169
4.1.2矩陣的運(yùn)算171
4.1.3矩陣的性質(zhì)173
4.1.4矩陣的程序?qū)崿F(xiàn)174
4.2矩陣的LUP分解176
4.2.1LUP分解法概述177
4.2.2LU分解178
4.2.3計(jì)算LUP分解179
4.2.4程序?qū)崿F(xiàn)182
4.3解線性方程組183
4.3.1前代法和回代法183
4.3.2用LUP分解計(jì)算矩陣的逆185
4.3.3程序?qū)崿F(xiàn)186
4.4多項(xiàng)式及其計(jì)算188
4.4.1多項(xiàng)式及其表示188
4.4.2多項(xiàng)式的運(yùn)算190
4.4.3FFT191
4.4.4程序?qū)崿F(xiàn)199
4.5應(yīng)用204
4.5.1多項(xiàng)式的泰勒展開式204
4.5.2完善序列208
4.5.3函數(shù)的有理式逼近211
第5章計(jì)算幾何218
5.1線段的性質(zhì)218
5.1.1叉積及其應(yīng)用219
5.1.2向量的極角222
5.1.3程序?qū)崿F(xiàn)223
5.2判斷是否存在線段相交226
5.2.1算法描述與分析227
5.2.2程序?qū)崿F(xiàn)230
5.3求凸殼234
5.3.1Graham掃描235
5.3.2程序?qū)崿F(xiàn)239
5.4求最鄰近點(diǎn)對242
5.4.1算法描述與分析242
5.4.2程序?qū)崿F(xiàn)245
5.5應(yīng)用248
5.5.1光導(dǎo)管248
5.5.2最小邊界矩形255
5.5.3德克薩斯一日游260
第6章數(shù)論算法264
6.1整數(shù)的表示264
6.1.1整數(shù)的表示264
6.1.2整數(shù)的算術(shù)運(yùn)算264
6.1.3程序?qū)崿F(xiàn)269
6.1.4應(yīng)用275
6.2初等數(shù)論的概念277
6.3最大公約數(shù)283
6.3.1Euclid算法284
6.3.2EUCLID算法的運(yùn)行時(shí)間284
6.3.3Euclid算法的迭代版本286
6.3.4程序?qū)崿F(xiàn)287
6.3.5應(yīng)用289
6.4模運(yùn)算294
6.4.1模加法和乘法295
6.4.2解模線性方程296
6.4.3元素的冪299
6.4.4應(yīng)用303
6.5素?cái)?shù)檢測305
6.5.1偽素?cái)?shù)檢測305
6.5.2Miller?Rabin的隨機(jī)素?cái)?shù)檢測308
6.5.3Miller?Rabin素?cái)?shù)檢測的錯(cuò)誤率310
6.5.4程序?qū)崿F(xiàn)310
6.6整數(shù)分解313
6.6.1Pollard的ρ探索法313
6.6.2程序?qū)崿F(xiàn)317
6.6.3應(yīng)用320
第7章回溯策略323
7.1組合問題323
7.1.1組合問題的例子323
7.1.2組合問題的形式化描述325
7.2組合問題的回溯算法326
7.2.1解空間的樹狀結(jié)構(gòu)326
7.2.2解決組合問題的回溯算法328
7.2.3回溯算法的框架333
7.3子集樹和排列樹339
7.3.1子集樹問題339
7.3.2排列樹問題343
7.3.3應(yīng)用349
7.4用回溯算法解決組合優(yōu)化問題360
7.4.1組合優(yōu)化問題360
7.4.2用回溯策略解決組合優(yōu)化問題362
7.4.3應(yīng)用365
第8章動(dòng)態(tài)規(guī)劃策略37
8.1組裝線調(diào)度問題376
8.1.1問題描述376
8.1.2算法設(shè)計(jì)與分析378
8.1.3應(yīng)用——牛牛玩牌381
8.2最長公共子序列386
8.2.1問題描述386
8.2.2算法設(shè)計(jì)與分析386
8.2.3程序?qū)崿F(xiàn)389
8.2.4應(yīng)用390
8.30?1背包問題398
8.3.1問題描述398
8.3.2算法設(shè)計(jì)與分析398
8.3.3程序?qū)崿F(xiàn)401
8.3.4應(yīng)用402
8.4帶權(quán)有向圖中任意兩點(diǎn)間的最短路徑409
8.4.1問題描述409
8.4.2算法設(shè)計(jì)與分析410
8.4.3程序?qū)崿F(xiàn)413
8.4.4應(yīng)用——牛牛聚會(huì)415
第9章貪婪策略419
9.1活動(dòng)選擇問題419
9.1.1算法描述與分析419
9.1.2程序?qū)崿F(xiàn)423
9.1.3貪婪算法與動(dòng)態(tài)規(guī)劃424
9.1.4應(yīng)用——海岸雷達(dá)425
9.2Huffman編碼428
9.2.1算法描述與分析428
9.2.2應(yīng)用——R叉Huffman樹433
9.2.3程序?qū)崿F(xiàn)437
9.3最小生成樹443
9.3.1算法描述與分析443
9.3.2程序?qū)崿F(xiàn)446
9.3.3應(yīng)用——北方通信網(wǎng)448
9.4單源最短路徑問題453
9.4.1算法描述與分析453
9.4.2程序?qū)崿F(xiàn)456
9.4.3應(yīng)用——西氣東送458
第10章圖的搜索算法465
10.1深度優(yōu)先搜索466
10.1.1算法描述與分析466
10.1.2程序?qū)崿F(xiàn)469
10.1.3有向無圈圖的拓?fù)渑判?72
10.1.4應(yīng)用——全排序478
10.2有向圖的強(qiáng)連通分支482
10.2.1算法描述與分析482
10.2.2程序?qū)崿F(xiàn)486
10.2.3應(yīng)用——親情號(hào)489
10.3無向圖的雙連通分支494
10.3.1算法描述與分析494
10.3.2程序?qū)崿F(xiàn)497
10.3.3應(yīng)用——雌雄大盜498
10.4廣度優(yōu)先搜索504
10.4.1算法描述與分析504
10.4.2程序?qū)崿F(xiàn)507
10.4.3應(yīng)用——攻城掠地508
10.5流網(wǎng)絡(luò)與最大流問題512
10.5.1算法描述與分析512
10.5.2程序?qū)崿F(xiàn)521
10.5.3應(yīng)用523
第11章代碼實(shí)驗(yàn)528
11.1頭文件清單528
11.1.1基本應(yīng)用類函數(shù)528
11.1.2數(shù)據(jù)結(jié)構(gòu)類531
11.1.3代數(shù)記算類函數(shù)534
11.1.4計(jì)算幾何類函數(shù)536
11.1.5數(shù)論計(jì)算類函數(shù)537
11.1.6回溯搜索類函數(shù)539
11.1.7動(dòng)態(tài)規(guī)劃類函數(shù)540
11.1.8貪婪策略類函數(shù)540
11.1.9圖的搜索類函數(shù)541
11.2實(shí)驗(yàn)平臺(tái)的搭建542
11.2.1集成開發(fā)環(huán)境的安裝542
11.2.2實(shí)驗(yàn)項(xiàng)目的建立542
11.3應(yīng)用問題程序的運(yùn)行實(shí)例544
11.3.1加載程序文件544
11.3.2調(diào)試程序545
11.3.3各應(yīng)用問題加載文件清單546
11.4函數(shù)庫的擴(kuò)展554
11.4.1向已有的源文件中添加新函數(shù)554
11.4.2創(chuàng)建新的源文件555
參考文獻(xiàn)557