算法基礎：Python和C#語言實現（原書第2版）

購買商店

算法基礎：Python和C#語言實現（原書第2版）

$714.00

馬上購買

內容描述

本書是一本算法入門教程，第2版添加了Python語言代碼示例，更加易於學習。書中不僅介紹重要的經典算法，而且闡述通用的問題求解技巧，幫助讀者在理解算法性能的基礎上學會將算法靈活地應用於新問題。書中每章都包含大量練習題，並配有參考答案。此外，本書網站還免費提供Python和C#語言的源代碼，鼓勵讀者通過編程實踐加深對算法的理解，進而提升應用算法解決問題的能力。

本書特色
涵蓋大量實用算法，如隨機化、因子分解等數值算法，鏈表、樹、網絡、堆等數據結構算法，選擇排序、二分查找等排序和查找算法，以及最短路徑、生成樹等網絡算法。
深入講解問題求解技巧，如窮舉搜索算法、分而治之法、遞歸法、分支定界法、貪婪算法、啟發式算法等，幫助讀者舉一反三，掌握設計新算法的技能。
針對參加編程面試的讀者，分析了IT公司的常見算法類面試題，使其不僅能夠掌握求解思路，而且瞭解不同題目所考查的側重之處。

目錄大綱

出版者的話
譯者序
前言
作者簡介
第1章　算法基礎 1
1.1　方法 1
1.2　算法和數據結構 2
1.3　偽代碼 2
1.4　算法的特點 4
1.4.1　大O符號 5
1.4.2　常用的運行時間函數 7
1.4.3　運行時間函數的可視化比較 11
1.5　實際考慮 12
1.6　本章小結 13
1.7　練習題 14
第2章　數值算法 16
2.1　數據隨機化 16
2.1.1　隨機數生成器 16
2.1.2　隨機化數組 20
2.1.3　生成非均勻分佈 21
2.1.4　隨機行走 22
2.2　查找最大公約數 25
2.2.1　計算最大公約數 25
2.2.2　最大公約數算法的擴展應用 27
2.3　計算乘冪 28
2.4　處理素數 29
2.4.1　查找素數因子 29
2.4.2　查找素數 31
2.4.3　素性檢驗 32
2.5　計算數值積分 33
2.5.1　矩形法則 34
2.5.2　梯形法則 34
2.5.3　自適應積分算法 35
2.5.4　蒙特卡羅積分法 37
2.6　方程求解 38
2.7　高斯消元法 40
2.7.1　前向消元 40
2.7.2　後向代換 41
2.7.3　算法實現 42
2.8　最小二乘法擬合 42
2.8.1　線性最小二乘法 43
2.8.2　多項式最小二乘法 44
2.9　本章小結 45
2.10　練習題 46
第3章　鏈表 48
3.1　基本概念 48
3.2　單向鏈表 49
3.2.1　遍歷鏈表 49
3.2.2　查找節點 49
3.2.3　使用哨兵 50
3.2.4　在頂部添加節點 51
3.2.5　在尾部添加節點 51
3.2.6　在指定節點後插入節點 52
3.2.7　刪除節點 52
3.3　雙向鏈表 53
3.4　有序鏈表 54
3.5　自組織鏈表 55
3.5.1　前移方法 56
3.5.2　交換方法 56
3.5.3　計數方法 56
3.5.4　混合方法 56
3.5.5　偽代碼 57
3.6　鏈表算法 57
3.6.1　復制鏈表 58
3.6.2　插入排序 58
3.6.3　選擇排序 60
3.7　多線鏈表 61
3.8　循環鏈表 61
3.8.1　標記節點 62
3.8.2　使用哈希表 63
3.8.3　鏈表回溯 64
3.8.4　鏈表反轉 65
3.8.5　龜兔賽跑算法 66
3.8.6　雙向鏈表中的環路 68
3.9　本章小結 68
3.10　練習題 68
第4章　數組 70
4.1　基本概念 70
4.2　一維數組 72
4.2.1　查找數組元素 72
4.2.2　查找最大值、最小值和平均值 72
4.2.3　查找中值 73
4.2.4　查找眾數 74
4.2.5　插入數組元素 76
4.2.6　刪除數組元素 77
4.3　非零數組下界 77
4.3.1　二維數組 78
4.3.2　高維數組 78
4.4　三角形數組 81
4.5　稀疏數組 83
4.5.1　查找行或列 84
4.5.2　獲取元素的值 85
4.5.3　設置元素的值 86
4.5.4　刪除數組元素 87
4.6　矩陣 89
4.7　本章小結 91
4.8　練習題 91
第5章　堆棧和隊列 93
5.1　堆棧 93
5.1.1　鏈表堆棧 94
5.1.2　數組堆棧 95
5.1.3　雙堆棧 96
5.1.4　堆棧算法 97
5.2　隊列 101
5.2.1　鏈表隊列 101
5.2.2　數組隊列 102
5.2.3　特殊隊列 104
5.3　二項堆 105
5.3.1　二項樹的定義 105
5.3.2　二項堆的定義 106
5.3.3　合並樹 107
5.3.4　合並堆 108
5.3.5　入隊操作 111
5.3.6　出隊操作 111
5.3.7　運行時間分析 112
5.4　本章小結 113
5.5　練習題 113
第6章　排序 115
6.1　O(N 2)算法 115
6.1.1　數組的插入排序算法 115
6.1.2　數組的選擇排序算法 116
6.1.3　冒泡排序算法 117
6.2　O(NlogN)算法 119
6.2.1　堆排序算法 120
6.2.2　快速排序算法 124
6.2.3　合並排序算法 130
6.3　小於O(NlogN)的算法 132
6.3.1　計數排序算法 132
6.3.2　鴿巢排序算法 133
6.3.3　桶排序算法 135
6.4　本章小結 136
6.5　練習題 137
第7章　查找 139
7.1　線性查找算法 139
7.2　二分查找算法 140
7.3　插值查找算法 141
7.4　多數投票算法 142
7.5　本章小結 143
7.6　練習題 144
第8章　哈希表 145
8.1　哈希表的基本概念 145
8.2　鏈接哈希表 146
8.3　開放尋址哈希表 147
8.3.1　刪除數據項 148
8.3.2　線性探測 149
8.3.3　二次探測 150
8.3.4　偽隨機探測 151
8.3.5　雙重哈希 151
8.3.6　有序哈希 152
8.4　本章小結 154
8.5　練習題 154
第9章　遞歸 156
9.1　基本算法 156
9.1.1　階乘 156
9.1.2　斐波那契數 158
9.1.3　棒料切割問題 159
9.1.4　漢諾塔 161
9.2　圖形算法 163
9.2.1　科赫曲線 163
9.2.2　希爾伯特曲線 165
9.2.3　謝爾賓斯基曲線 166
9.2.4　墊圈圖案 168
9.2.5　天際線問題 168
9.3　回溯算法 172
9.3.1　八皇後問題 173
9.3.2　騎士巡游問題 175
9.4　組合與排列 177
9.4.1　基於循環的組合 178
9.4.2　允許重復項的組合 179
9.4.3　不允許重復項的組合 180
9.4.4　允許重復項的排列 181
9.4.5　不允許重復項的排列 182
9.4.6　輪詢調度算法 183
9.5　遞歸的刪除 188
9.5.1　尾部遞歸的刪除 188
9.5.2　動態規劃 189
9.5.3　自底向上編程 190
9.5.4　刪除遞歸的通用方法 191
9.6　本章小結 193
9.7　練習題 194
第10章　樹 196
10.1　有關樹的術語 196
10.2　二叉樹的性質 198
10.3　樹的表示 200
10.3.1　構建常規樹 200
10.3.2　構建完全樹 203
10.4　樹的遍歷 203
10.4.1　前序遍歷 204
10.4.2　中序遍歷 206
10.4.3　後序遍歷 206
10.4.4　廣度優先遍歷 207
10.4.5　遍歷的應用 207
10.4.6　遍歷的運行時間分析 208
10.5　有序樹 208
10.5.1　添加節點 209
10.5.2　查找節點 210
10.5.3　刪除節點 211
10.6　最小共同祖先 212
10.6.1　在有序樹中查找最小共同祖先 212
10.6.2　使用指向父節點的指針 213
10.6.3　使用指向父節點的指針和深度字段 214
10.6.4　常規樹 214
10.6.5　歐拉環游 216
10.6.6　所有節點對的最小共同祖先 217
10.7　線索樹 217
10.7.1　構建線索樹 218
10.7.2　線索樹的應用 220
10.8　特殊的樹算法 221
10.8.1　動物游戲 221
10.8.2　表達式求值 223
10.9　區間樹 224
10.9.1　構建區間樹 225
10.9.2　與點相交 226
10.9.3　與區間相交 226
10.9.4　四叉樹 228
10.9.5　字符串樹 231
10.10　本章小結 235
10.11　練習題 235
第11章　平衡樹 239
11.1　AVL樹 239
11.1.1　添加值 239
11.1.2　刪除值 240
11.2　2-3樹 241
11.2.1　添加值 242
11.2.2　刪除值 242
11.3　B樹 244
11.3.1　添加值 245
11.3.2　刪除值 245
11.4　平衡樹的變種 246
11.4.1　自頂向下的B樹 246
11.4.2　B+樹 247
11.5　本章小結 248
11.6　練習題 248
第12章　決策樹 250
12.1　搜索博弈樹 250
12.1.1　極小極大算法 251
12.1.2　初始移動和響應 254
12.1.3　博弈樹啟發式算法 254
12.2　搜索常規決策樹 255
12.2.1　優化問題 256
12.2.2　窮舉搜索 257
12.2.3　分支定界搜索 258
12.2.4　決策樹啟發式算法 259
12.2.5　其他決策樹問題 264
12.3　群集智能 267
12.3.1　蟻群優化算法 268
12.3.2　蜂群算法 268
12.3.3　群集模擬 269
12.4　本章小結 270
12.5　練習題 271
第13章　基本網絡算法 274
13.1　有關網絡的術語 274
13.2　網絡的表示 276
13.3　遍歷 278
13.3.1　深度優先遍歷 278
13.3.2　廣度優先遍歷 280
13.3.3　連通性測試 281
13.3.4　生成樹 282
13.3.5　最小生成樹 283
13.3.6　歐幾里得最小生成樹 284
13.3.7　構建迷宮 284
13.4　強連通組件 285
13.4.1　Kosaraju算法 285
13.4.2　關於Kosaraju算法的討論 286
13.5　查找路徑 288
13.5.1　查找任意路徑 288
13.5.2　標簽設置最短路徑 289
13.5.3　標簽修正最短路徑 291
13.5.4　所有節點對的最短路徑 292
13.6　傳遞性 295
13.6.1　傳遞閉包 295
13.6.2　傳遞歸約 296
13.7　最短路徑算法的改進 298
13.7.1　形狀點 298
13.7.2　提前終止 299
13.7.3　雙向搜索 299
13.7.4　最佳優先搜索 299
13.7.5　轉彎懲罰和禁行 299
13.8　本章小結 302
13.9　練習題 302
第14章　高級網絡算法 304
14.1　拓撲排序 304
14.2　迴路檢測 306
14.3　地圖著色 307
14.3.1　雙色地圖 307
14.3.2　三色地圖 308
14.3.3　四色地圖 309
14.3.4　五色地圖 309
14.3.5　其他地圖著色算法 312
14.4　最大流量 312
14.4.1　工作分配 314
14.4.2　最小流量切割 314
14.5　網絡克隆 316
14.5.1　字典 316
14.5.2　克隆引用 317
14.6　節點團 318
14.6.1　暴力破解方法 318
14.6.2　Bron-Kerbosch算法 319
14.6.3　查找三角形節點團 323
14.7　社區檢測 324
14.7.1　極大節點團 325
14.7.2　Girvan-Newman算法 325
14.7.3　派系過濾法 326
14.8　歐拉路徑和歐拉迴路 326
14.8.1　暴力破解方法 327
14.8.2　弗萊里算法 327
14.8.3　Hierholzer算法 327
14.9　本章小結 328
14.10　練習題 329
第15章　字符串算法 331
15.1　匹配括號 331
15.1.1　算術表達式求值 332
15.1.2　構建解析樹 332
15.2　模式匹配 333
15.2.1　DFA 333
15.2.2　為正則表達式構建DFA 335
15.2.3　NFA 336
15.3　字符串搜索 337
15.4　計算編輯距離 340
15.5　語音算法 342
15.5.1　Soundex 342
15.5.2　Metaphone 343
15.6　本章小結 344
15.7　練習題 344
第16章　密碼學 347
16.1　術語 347
16.2　置換加密算法 348
16.2.1　行/列置換加密算法 348
16.2.2　列置換加密算法 349
16.2.3　路由加密算法 351
16.3　替換加密算法 351
16.3.1　愷撒替換加密算法 351
16.3.2　維吉尼亞加密算法 352
16.3.3　簡單替換加密算法 354
16.3.4　一次性便箋加密器 354
16.4　分組加密算法 355
16.4.1　替換-置換網絡加密算法 355
16.4.2　菲斯特爾加密算法 356
16.5　公開密鑰加密與RSA 357
16.5.1　歐拉函數 358
16.5.2　乘法逆元 358
16.5.3　RSA示例 358
16.5.4　實際考慮 359
16.6　密碼學的其他應用場景 359
16.7　本章小結 360
16.8　練習題 360
第17章　計算復雜性理論 362
17.1　標記法 362
17.2　算法復雜性類別 363
17.3　歸約 365
17.3.1　3SAT 366
17.3.2　二分圖匹配 366
17.4　NP難問題 367
17.5　檢測問題、報告問題和優化問題 367
17.5.1　檢測問題≤p報告問題 368
17.5.2　報告問題≤p優化問題 368
17.5.3　報告問題≤p檢測問題 368
17.5.4　優化問題≤p報告問題 369
17.5.5　近似優化 369
17.6　NP完全問題 369
17.7　本章小結 371
17.8　練習題 372
第18章　分佈式算法 374
18.1　並行計算的類型 374
18.1.1　脈動陣列 374
18.1.2　分佈式計算 376
18.1.3　多CPU處理 378
18.1.4　競爭條件 378
18.1.5　死鎖 381
18.1.6　量子計算 382
18.2　分佈式算法 382
18.2.1　調試分佈式算法 383
18.2.2　密集並行算法 383
18.2.3　合並排序算法 384
18.2.4　哲學家就餐問題 385
18.2.5　兩個將軍問題 387
18.2.6　拜占庭將軍問題 388
18.2.7　一致性問題 390
18.2.8　領導選舉 393
18.2.9　快照技術 393
18.2.10　時鐘同步 394
18.3　本章小結 395
18.4　練習題 395
第19章　面試難題 397
19.1　面試官提出面試難題 398
19.2　應聘者回答面試難題 399
19.3　本章小結 402
19.4　練習題 403
附錄　練習題參考答案

作者介紹

羅德·斯蒂芬斯（Rod Stephens） 連續15年被評為Microsoft Visual Basic最有價值專家（MVP），長期在ITT技術學院教授編程入門課程。
他已經撰寫了超過30本技術書籍，這些書被翻譯成多種語言在世界範圍內出版。
他還撰寫了超過250篇雜誌文章，內容涵蓋C#、Visual Basic、Delphi和Java等。