算法基礎：Python和C#語言實現(第2版)（簡體書）

本書第2版進行了全面修訂與更新，更加易於學習。書中描述了那些重要且經典的算法，並且說明了不同算法的適用情境。跟隨作者的講解，讀者將學會分析既有算法，進而理解算法背後的原理。同時，讀者也將學習創建新的算法，以適應未來的新需求。這些有用的算法包括：操作常用數據結構的方法，高級數據結構，網絡算法，以及數值算法。此外，書中還包含通用的問題求解技巧。除了描述算法，作者還詳細介紹了如何分析算法的性能。書中提供大量練習，讀者可以自己探索修改算法的方法，以便將其應用於新的情境。

新增Python代碼示例，全面涵蓋經典算法、問題求解技巧和麵試指南，在理解算法性能的基礎上學會解決新問題

出版者的話
譯者序
前言
作者簡介
第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