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