從算法到程式（第2版）

《從算法到程式（第2版）》是2015年6月清華大學出版社出版的圖書，作者是徐子珊。

基本介紹

• 中文名：從算法到程式（第2版）
• 作者：徐子珊
• 出版社：清華大學出版社
• 出版時間：2015年6月
• 定價：69.5 元
• ISBN：9787302400769

內容簡介

本書第1章討論算法設計、分析的基本概念。第2章討論算法設計中最常用的幾個數據結構，包括鍊表、棧、佇列、二叉搜尋樹、散列表等。第3章討論了算法設計的兩個基本策略：漸增策略與分支策略。第1～3章的內容，為讀者閱讀本書以後的內容奠定了基礎。第4章討論幾個代數計算的基本問題及其算法，包括矩陣運算、解線性方程組、多項式運算等。第5章討論幾個關於計算幾何的基本問題及其算法，包括線段的相交判斷、平麵點集的凸包計算、最鄰近點對問題等。第6章討論了關於整數運算的基本問題，包括大整數的表示與運算、最大公約數計算、模運算、素數判定及整數因數分解等。第4～6章的內容為讀者深入學習解決各種複雜問題奠定了解決數學計算問題的基礎。第7~9章分別用回溯策略、動態規劃策略及貪婪策略研究、解決計算機套用面臨的最普遍、最典型的組合最佳化問題。第10章討論圖的搜尋算法及其套用，包括深度優先搜尋、拓撲排序、有向圖的強連通分支計算、關節點計算、廣度優先搜尋、網路最大流及二部圖的最大匹配等問題。第11章討論了幾個文本搜尋的有趣算法，包括著名的KMP模式匹配算法、線性時間計算字元串中最長回文子串的Manacher算法、用動態規劃策略尋求字元串中指定模式的最佳近似匹配的算法。

本書無論是對初學算法及程式設計入門的大學生讀者還是對已經在職場打拚多年的程式設計師並有提高自身理論修養及技術水平願望的讀者都有開卷有益的意義。

圖書目錄

第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.2MillerRabin的隨機素數檢測308

6.5.3MillerRabin素數檢測的錯誤率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.301背包問題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