《從算法到程序（第2版）》第1章討論算法設計、分析的基本概念。第2章討論算法設計中最常用的幾個數據結構，包括鏈表、棧、隊列、二叉搜索樹、散列表等。第3章討論了算法設計的兩個基本策略：漸增策略與分支策略。第1～3章的內容，為讀者閱讀本書以后的內容奠定了基礎。第4章討論幾個代數計算的基本問題及其算法，包括矩陣運算、解線性方程組、多項式運算等。第5章討論幾個關于計算幾何的基本問題及其算法，包括線段的相交判斷、平面點集的凸包計算、最鄰近點對問題等。第6章討論了關于整數運算的基本問題，包括大整數的表示與運算、最大公約數計算、模運算、素數判定及整數因數分解等。第4～6章的內容為讀者深入學習解決各種復雜問題奠定了解決數學計算問題的基礎。第7~9章分別用回溯策略、動態規劃策略及貪婪策略研究、解決計算機應用面臨的最普遍、最典型的組合優化問題。第10章討論圖的搜索算法及其應用，包括深度優先搜索、拓撲排序、有向圖的強連通分支計算、關節點計算、廣度優先搜索、網絡最大流及二部圖的最大匹配等問題。第11章討論了幾個文本搜索的有趣算法，包括著名的KMP模式匹配算法、線性時間計算字符串中最長回文子串的Manacher算法、用動態規劃策略尋求字符串中指定模式的最佳近似匹配的算法。對所有的的經典算法及數據結構，書中給出C語言的實現函數，形成一個通用的函數庫，并詳盡地加以解析。伴隨各種算法的設計、分析及程序實現，書中給出了豐富多彩的應用問題及其解決方案的討論，并給出了完整的程序代碼。所有程序代碼都經過反復調試，第12章介紹這些代碼的使用方法。所有代碼都以網絡資源的方式提供給讀者。
本書無論是對初學算法及程序設計入門的大學生讀者還是對已經在職場打拼多年的程序員并有提高自身理論修養及技術水平愿望的讀者都有開卷有益的意義。
本書第1版已經面世近2年了。承蒙讀者厚愛及清華大學出版社的大力支持，遂有了今天第2版的問世。
根據廣大讀者的意見反饋，在第1版的基礎上，除對原有內容中所含明顯錯漏之處進行修改以外，第2版增加了關于文本搜索的一些有趣的算法，包括著名的KMP模式匹配算法、線性時間內計算給定字符串中最長回文子串的Manacher算法和文本串中模式最佳近似匹配的動態規劃算法。所有這些算法都涵蓋于第11章中。考慮到原來的第11章介紹了驗證運行本書各章應用問題程序時需加載文件等細節，這對喜歡動手的讀者來說是很有幫助的，所以保留了原來的內容并將第11章討論的3個應用問題程序的運行加載信息也補充了進去，作為第12章。所有這些添加、改動都是為了對讀者閱讀本書有所幫助，并且能通過對本書的閱讀能讓更多的年輕朋友在信息時代具有良好的計算思維能力和操控計算機的能力。
網絡已經成為人們獲取信息、數據的最方便快捷的工具了。本書第1版中源代碼是以傳統的光盤形式提供給讀者，本意是方便讀者隨手可用。第2版將以網絡資源形式提供給讀者，具體的訪問地址是www.tup.com.cn。
為使作者和讀者之間更方便、直接地交流溝通，作者的QQ號及空間地址公布如下。
QQ號：513410359。
空間地址：user.qzone.qq.com/513410359?ptlang=2052。
再次感謝清華大學出版社的白立軍先生，沒有他的支持和幫助，無論是本書的第1版還是今天的第2版都不會如此順利地送到讀者的面前。
徐子珊
2015年3月
第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數據結構6
1.2.1什么是數據結構6
1.2.2數據結構對算法效率的影響7
1.2.3字典與字典操作8
1.3程序設計10
1.3.1算法與程序10
1.3.2數據類型的抽象與代碼通用性11
1.4數據的輸入輸出13
1.4.1應用問題13
1.4.2標準輸入輸出15
1.4.3文件輸入輸出20
1.5計數問題22
1.5.1簡單模擬23
1.5.2加法原理和乘法原理25
1.5.3計算四邊形個數31第2章數據結構基礎37
2.1線性表38
2.1.1線性表的鏈表表示38
2.1.2對鏈表的操作39
2.1.3鏈表的程序實現42
2.1.4鏈表應用47
2.2棧53
2.2.1棧的概念及其鏈表實現53
2.2.2棧的程序實現54
2.2.3棧的應用56
2.3隊列62
2.3.1隊列的概念及其鏈表實現62
2.3.2隊列的程序實現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紅黑樹及其性質80
2.4.6紅黑樹的操作83
2.4.7紅黑樹的程序實現92
2.4.8二叉搜索樹的應用102
2.5散列表102
2.5.1直接尋址表與散列表102
2.5.2用拉鏈法解決沖突104
2.5.3散列表的程序實現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序統計與選擇問題130
3.3排序問題的討論132
3.3.1排序的性質132
3.3.2比較型排序算法的時間復雜度133
3.3.3應用136
3.4堆與基于堆的優先隊列141
3.4.1堆的概念及其創建141
3.4.2基于二叉堆的優先隊列149
3.4.3應用153第4章代數計算169
4.1矩陣及其計算169
4.1.1矩陣與向量169
4.1.2矩陣的運算171
4.1.3矩陣的性質173
4.1.4矩陣的程序實現174
4.2矩陣的LUP分解176
4.2.1LUP分解法概述177
4.2.2LU分解178
4.2.3計算LUP分解179
4.2.4程序實現182
4.3解線性方程組183
4.3.1前代法和回代法183
4.3.2用LUP分解計算矩陣的逆185
4.3.3程序實現186
4.4多項式及其計算188
4.4.1多項式及其表示188
4.4.2多項式的運算190
4.4.3FFT191
4.4.4程序實現199
4.5應用204
4.5.1多項式的泰勒展開式204
4.5.2完善序列208
4.5.3函數的有理式逼近211第5章計算幾何218
5.1線段的性質218
5.1.1叉積及其應用219
5.1.2向量的極角222
5.1.3程序實現223
5.2判斷是否存在線段相交226
5.2.1算法描述與分析227
5.2.2程序實現230
5.3求凸殼234
5.3.1Graham掃描235
5.3.2程序實現239
5.4求最鄰近點對242
5.4.1算法描述與分析242
5.4.2程序實現245
5.5應用248
5.5.1光導管248
5.5.2最小邊界矩形255
5.5.3德克薩斯一日游260第6章數論算法264
6.1整數的表示264
6.1.1整數的表示264
6.1.2整數的算術運算264
6.1.3程序實現269
6.1.4應用275
6.2初等數論的概念277
6.3最大公約數283
6.3.1Euclid算法284
6.3.2EUCLID算法的運行時間284
6.3.3Euclid算法的迭代版本286
6.3.4程序實現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素數檢測305
6.5.1偽素數檢測305
6.5.2MillerRabin的隨機素數檢測308
6.5.3MillerRabin素數檢測的錯誤率310
6.5.4程序實現310
6.6整數分解313
6.6.1Pollard的ρ探索法313
6.6.2程序實現317
6.6.3應用320第7章回溯策略323
7.1組合問題323
7.1.1組合問題的例子323
7.1.2組合問題的形式化描述325
7.2組合問題的回溯算法326
7.2.1解空間的樹狀結構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用回溯算法解決組合優化問題360
7.4.1組合優化問題360
7.4.2用回溯策略解決組合優化問題362
7.4.3應用365第8章動態規劃策略375
8.1組裝線調度問題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程序實現389
8.2.4應用390
8.301背包問題398
8.3.1問題描述398
8.3.2算法設計與分析398
8.3.3程序實現401
8.3.4應用402
8.4帶權有向圖中任意兩點間的最短路徑409
8.4.1問題描述409
8.4.2算法設計與分析410
8.4.3程序實現413
8.4.4應用——牛牛聚會415第9章貪婪策略419
9.1活動選擇問題419
9.1.1算法描述與分析419
9.1.2程序實現423
9.1.3貪婪算法與動態規劃424
9.1.4應用——海岸雷達425
9.2Huffman編碼428
9.2.1算法描述與分析428
9.2.2應用——R叉Huffman樹433
9.2.3程序實現437
9.3最小生成樹443
9.3.1算法描述與分析443
9.3.2程序實現446
9.3.3應用——北方通信網448
9.4單源最短路徑問題453
9.4.1算法描述與分析453
9.4.2程序實現456
9.4.3應用——西氣東送458第10章圖的搜索算法465
10.1深度優先搜索466
10.1.1算法描述與分析466
10.1.2程序實現469
10.1.3有向無圈圖的拓撲排序472
10.1.4應用——全排序478
10.2有向圖的強連通分支482
10.2.1算法描述與分析482
10.2.2程序實現486
10.2.3應用——親情號489
10.3無向圖的雙連通分支494
10.3.1算法描述與分析494
10.3.2程序實現497
10.3.3應用——雌雄大盜498
10.4廣度優先搜索504
10.4.1算法描述與分析504
10.4.2程序實現507
10.4.3應用——攻城掠地508
10.5流網絡與最大流問題512
10.5.1算法描述與分析512
10.5.2程序實現521
10.5.3應用523第11章文本搜索528
11.1固定模式的串匹配528
11.1.1強力算法528
11.1.2KMP算法530
11.1.3程序實現535
11.1.4應用535
11.2最長回文子串問題541
11.2.1強力算法542
11.2.2Manacher算法543
11.2.3程序實現547
11.2.4應用549
11.3近似匹配550
11.3.1最小編輯距離550
11.3.2最佳近似匹配552
11.3.3程序實現555
11.3.4應用556第12章代碼實驗560
12.1頭文件清單560
12.1.1基本應用類函數560
12.1.2數據結構類563
12.1.3代數記算類函數566
12.1.4計算幾何類函數568
12.1.5數論計算類函數569
12.1.6回溯搜索類函數571
12.1.7動態規劃類函數572
12.1.8貪婪策略類函數572
12.1.9圖的搜索類函數573
12.1.10文本搜索類函數574
12.2實驗平臺的搭建574
12.2.1集成開發環境的安裝574
12.2.2實驗項目的建立575
12.3應用問題程序的運行實例576
12.3.1加載程序文件576
12.3.2調試程序578
12.3.3各應用問題加載文件清單579
12.4函數庫的擴展587
12.4.1向已有的源文件中添加新函數587
12.4.2創建新的源文件588
參考文獻589第11章代碼實驗528
11.1頭文件清單528
11.1.1基本應用類函數528
11.1.2數據結構類531
11.1.3代數記算類函數534
11.1.4計算幾何類函數536
11.1.5數論計算類函數537
11.1.6回溯搜索類函數539
11.1.7動態規劃類函數540
11.1.8貪婪策略類函數540
11.1.9圖的搜索類函數541
11.2實驗平臺的搭建542
11.2.1集成開發環境的安裝542
11.2.2實驗項目的建立542
11.3應用問題程序的運行實例544
11.3.1加載程序文件544
11.3.2調試程序545
11.3.3各應用問題加載文件清單546
11.4函數庫的擴展554
11.4.1向已有的源文件中添加新函數554
11.4.2創建新的源文件555
參考文獻557
新書資訊