從算法到程序：從應用問題編程實踐全面體驗算法理論

定　價：￥59.00

作　者：	徐子珊著
出版社：	清華大學出版社
叢編項：
標　簽：	計算機/網(wǎng)絡計算機理論

購買這本書可以去

ISBN：	9787302304746	出版時間：	2013-03-01	包裝：	平裝
開本：	16開	頁數(shù)：	572	字數(shù)：

內(nèi)容簡介

　　《從算法到程序》第1章討論算法設計、分析的基本概念，第2章討論算法設計中最常用的幾個數(shù)據(jù)結(jié)構(gòu)，包括鏈表、棧、隊列、二叉搜索數(shù)、散列表等。第3章討論了算法設計的兩個基本策略：漸增策略與分支策略。這3章的內(nèi)容，為讀者閱讀本書以后的內(nèi)容奠定了基礎。第4章討論了幾個代數(shù)計算的基本問題及其算法，包括矩陣運算、解線性方程組、多項式運算等。第5章討論了幾個關于計算幾何的基本問題及其算法，包括線段的相交判斷、平面點集的凸包計算、最鄰近點對問題等。第6章討論了關于整數(shù)運算的基本問題，包括大整數(shù)的表示與運算、最大公約數(shù)計算、模運算、素數(shù)判定及整數(shù)因數(shù)分解等。這3章內(nèi)容為讀者深入學習解決各種復雜問題奠定了解決數(shù)學計算問題的基礎。第7~9章分別用回溯策略、動態(tài)規(guī)劃策略及貪婪策略研究、解決計算機應用面臨的最普遍最典型的問題組合優(yōu)化問題。第10章討論圖的搜索算法及其應用。包括深度優(yōu)先搜索、拓撲排序、有向圖的強連通分支計算、關節(jié)點計算、廣度優(yōu)先搜索、網(wǎng)絡最大流及二部圖的最大匹配等問題。對所有的的經(jīng)典算法及數(shù)據(jù)結(jié)構(gòu)，書中給出C語言的實現(xiàn)函數(shù)，形成一個通用的函數(shù)庫，并詳盡地加以解析。伴隨各種算法的設計、分析及程序?qū)崿F(xiàn)，書中給出了豐富多彩的應用問題及其解決方案的討論，并給出了完整的程序代碼。所有程序代碼都經(jīng)過反復調(diào)試，第十一章介紹這些代碼的使用方法。所有代碼都以隨書光盤的方式提供給讀者方便使用。本書無論是對初學算法及程序設計入門大學生讀者還是對已經(jīng)在職場打拼多年的程序員并有著提高自身理論修養(yǎng)及技術(shù)水平愿望的讀者都有著開卷有益的意義。

作者簡介

　　徐子珊男，副教授。數(shù)學專業(yè)出身，長期從事高校數(shù)學、算法和程序設計教學，深受學生喜愛。曾擔任ACM/ICPC競賽教練，指導過多屆ITAT競賽。2003年在復旦大學計算機科學系做國內(nèi)訪問學者，師從國內(nèi)算法界前輩朱洪教授。2010年曾出版《算法設計、分析與實現(xiàn)》一書，受到讀者好評。該書遠銷中國臺灣地區(qū)，曾有多人來函索要書中相關代碼。2012年出版該書修訂版。

圖書目錄

第1章計算問題1
1.1計算問題及其算法1
1.1.1計算問題及其描述1
1.1.2算法及其描述2
1.1.3偽代碼的使用約定3
1.1.4算法分析4
1.1.5算法運行時間的漸近表示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程序設計10
1.3.1算法與程序10
1.3.2數(shù)據(jù)類型的抽象與代碼通用性11
1.4數(shù)據(jù)的輸入輸出13
1.4.1應用問題13
1.4.2標準輸入輸出15
1.4.3文件輸入輸出20
1.5計數(shù)問題22
1.5.1簡單模擬23
1.5.2加法原理和乘法原理25
1.5.3整數(shù)序列31
第2章數(shù)據(jù)結(jié)構(gòu)基礎37
2.1線性表38
2.1.1線性表的鏈表表示38
2.1.2對鏈表的操作39
2.1.3鏈表的程序?qū)崿F(xiàn)42
2.1.4鏈表應用47
2.2棧53
2.2.1棧的概念及其鏈表實現(xiàn)53
2.2.2棧的程序?qū)崿F(xiàn)54
2.2.3棧的應用56
2.3隊列62
2.3.1隊列的概念及其鏈表實現(xiàn)62
2.3.2隊列的程序?qū)崿F(xiàn)63
2.3.3隊列的應用64
2.4二叉搜索樹68
2.4.1二叉樹及其在計算機中的表示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二叉搜索樹的應用102
2.5散列表102
2.5.1直接尋址表與散列表102
2.5.2用拉鏈解決沖突104
2.5.3散列表的程序?qū)崿F(xiàn)106
2.5.4散列表的應用109
第3章基本算法設計策略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)計與選擇問題130
3.3排序問題的討論132
3.3.1排序的性質(zhì)132
3.3.2比較型排序算法的時間復雜度133
3.3.3應用136
3.4堆與基于堆的優(yōu)先隊列141
3.4.1堆的概念及其創(chuàng)建141
3.4.2基于二叉堆的優(yōu)先隊列149
3.4.3應用153
第4章代數(shù)計算169
4.1矩陣及其計算169
4.1.1矩陣與向量169
4.1.2矩陣的運算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計算LUP分解179
4.2.4程序?qū)崿F(xiàn)182
4.3解線性方程組183
4.3.1前代法和回代法183
4.3.2用LUP分解計算矩陣的逆185
4.3.3程序?qū)崿F(xiàn)186
4.4多項式及其計算188
4.4.1多項式及其表示188
4.4.2多項式的運算190
4.4.3FFT191
4.4.4程序?qū)崿F(xiàn)199
4.5應用204
4.5.1多項式的泰勒展開式204
4.5.2完善序列208
4.5.3函數(shù)的有理式逼近211
第5章計算幾何218
5.1線段的性質(zhì)218
5.1.1叉積及其應用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求最鄰近點對242
5.4.1算法描述與分析242
5.4.2程序?qū)崿F(xiàn)245
5.5應用248
5.5.1光導管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ù)運算264
6.1.3程序?qū)崿F(xiàn)269
6.1.4應用275
6.2初等數(shù)論的概念277
6.3最大公約數(shù)283
6.3.1Euclid算法284
6.3.2EUCLID算法的運行時間284
6.3.3Euclid算法的迭代版本286
6.3.4程序?qū)崿F(xiàn)287
6.3.5應用289
6.4模運算294
6.4.1模加法和乘法295
6.4.2解模線性方程296
6.4.3元素的冪299
6.4.4應用303
6.5素數(shù)檢測305
6.5.1偽素數(shù)檢測305
6.5.2Miller?Rabin的隨機素數(shù)檢測308
6.5.3Miller?Rabin素數(shù)檢測的錯誤率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應用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應用349
7.4用回溯算法解決組合優(yōu)化問題360
7.4.1組合優(yōu)化問題360
7.4.2用回溯策略解決組合優(yōu)化問題362
7.4.3應用365
第8章動態(tài)規(guī)劃策略37
8.1組裝線調(diào)度問題376
8.1.1問題描述376
8.1.2算法設計與分析378
8.1.3應用——牛牛玩牌381
8.2最長公共子序列386
8.2.1問題描述386
8.2.2算法設計與分析386
8.2.3程序?qū)崿F(xiàn)389
8.2.4應用390
8.30?1背包問題398
8.3.1問題描述398
8.3.2算法設計與分析398
8.3.3程序?qū)崿F(xiàn)401
8.3.4應用402
8.4帶權(quán)有向圖中任意兩點間的最短路徑409
8.4.1問題描述409
8.4.2算法設計與分析410
8.4.3程序?qū)崿F(xiàn)413
8.4.4應用——牛牛聚會415
第9章貪婪策略419
9.1活動選擇問題419
9.1.1算法描述與分析419
9.1.2程序?qū)崿F(xiàn)423
9.1.3貪婪算法與動態(tài)規(guī)劃424
9.1.4應用——海岸雷達425
9.2Huffman編碼428
9.2.1算法描述與分析428
9.2.2應用——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應用——北方通信網(wǎng)448
9.4單源最短路徑問題453
9.4.1算法描述與分析453
9.4.2程序?qū)崿F(xiàn)456
9.4.3應用——西氣東送458
第10章圖的搜索算法465
10.1深度優(yōu)先搜索466
10.1.1算法描述與分析466
10.1.2程序?qū)崿F(xiàn)469
10.1.3有向無圈圖的拓撲排序472
10.1.4應用——全排序478
10.2有向圖的強連通分支482
10.2.1算法描述與分析482
10.2.2程序?qū)崿F(xiàn)486
10.2.3應用——親情號489
10.3無向圖的雙連通分支494
10.3.1算法描述與分析494
10.3.2程序?qū)崿F(xiàn)497
10.3.3應用——雌雄大盜498
10.4廣度優(yōu)先搜索504
10.4.1算法描述與分析504
10.4.2程序?qū)崿F(xiàn)507
10.4.3應用——攻城掠地508
10.5流網(wǎng)絡與最大流問題512
10.5.1算法描述與分析512
10.5.2程序?qū)崿F(xiàn)521
10.5.3應用523
第11章代碼實驗528
11.1頭文件清單528
11.1.1基本應用類函數(shù)528
11.1.2數(shù)據(jù)結(jié)構(gòu)類531
11.1.3代數(shù)記算類函數(shù)534
11.1.4計算幾何類函數(shù)536
11.1.5數(shù)論計算類函數(shù)537
11.1.6回溯搜索類函數(shù)539
11.1.7動態(tài)規(guī)劃類函數(shù)540
11.1.8貪婪策略類函數(shù)540
11.1.9圖的搜索類函數(shù)541
11.2實驗平臺的搭建542
11.2.1集成開發(fā)環(huán)境的安裝542
11.2.2實驗項目的建立542
11.3應用問題程序的運行實例544
11.3.1加載程序文件544
11.3.2調(diào)試程序545
11.3.3各應用問題加載文件清單546
11.4函數(shù)庫的擴展554
11.4.1向已有的源文件中添加新函數(shù)554
11.4.2創(chuàng)建新的源文件555
參考文獻557