譯者序
前言
第1章緒論1
1.1變量1
1.2數據類型1
1.3數據結構2
1.4抽象數據類型2
1.5什麼是算法3
1.6為什麼需要算法分析3
1.7算法分析的目的3
1.8什麼是運行時間分析4
1.9如何比較算法4
1.10什麼是增長率4
1.11常用的增長率4
1.12分析的類型5
1.13漸近錶示6
1.14大O錶示法6
1.15Ω錶示法7
1.16Θ錶示法8
1.17重要說明9
1.18為什麼稱為漸近分析9
1.19漸近分析指南9
1.20漸近錶示法的性質11
1.21常用的對數和纍加公式11
1.22分治法主定理12
1.23分治法主定理的相關問題12
1.24問題規模減小和遞歸求解主定理13
1.25問題規模減小和遞歸求解主定理的變型13
1.26猜測和確認的方法14
1.27平攤分析15
1.28算法分析的相關問題15
第2章遞歸和迴溯28
2.1引言28
2.2什麼是遞歸28
2.3為什麼要用遞歸28
2.4遞歸函數的格式28
2.5遞歸和內存（可視化）29
2.6遞歸與迭代30
2.7遞歸說明30
2.8遞歸算法的經典用例30
2.9遞歸的相關問題31
2.10什麼是迴溯32
2.11迴溯算法的經典用例32
2.12迴溯的相關問題32
第3章鏈錶34
3.1什麼是鏈錶34
3.2鏈錶抽象數據類型34
3.3為什麼要用鏈錶35
3.4數組概述35
3.5鏈錶、數組和動態數組的比較36
3.6單嚮鏈錶36
3.7雙嚮鏈錶41
3.8循環鏈錶46
3.9一種存儲高效的雙嚮鏈錶51
3.10鬆散鏈錶52
3.11鏈錶的相關問題55
第4章棧72
4.1什麼是棧72
4.2如何使用棧72
4.3棧抽象數據類型73
4.4異常73
4.5應用73
4.6實現73
4.7棧的各種實現方法比較77
4.8棧的相關問題78
第5章隊列98
5.1什麼是隊列98
5.2如何使用隊列98
5.3隊列抽象數據類型99
5.4異常99
5.5應用99
5.6實現99
5.7隊列的相關問題104
第6章樹110
6.1什麼是樹110
6.2術語110
6.3二叉樹111
6.4二叉樹的遍曆114
6.5通用樹（N叉樹）135
6.6綫索（無棧或無隊列結構）二叉樹遍曆141
6.7錶達式樹147
6.8異或樹149
6.9二叉搜索樹150
6.10平衡二叉搜索樹164
6.11AVL樹165
6.12樹的其他形式178
6.12.1紅黑樹178
6.12.2伸展樹179
6.12.3增強樹179
6.12.4替罪羊樹179
6.12.5區間樹180
第7章優先隊列和堆181
7.1什麼是優先隊列181
7.2優先隊列ADT181
7.3優先隊列的應用182
7.4優先隊列的實現182
7.5堆和二叉堆183
7.6二叉堆184
7.7優先隊列（堆）的相關問題190
第8章並查集ADT201
8.1引言201
8.2等價關係和等價類201
8.3並查集ADT202
8.4應用202
8.5並查集ADT實現中的權衡202
8.6快速UNION實現（慢FIND）203
8.7快速UNION實現（快速FIND）206
8.8路徑壓縮208
8.9小結209
8.10並查集的相關問題209
第9章圖算法211
9.1引言211
9.2術語211
9.3圖的應用214
9.4圖的錶示214
9.5圖的遍曆217
9.6拓撲排序225
9.7最短路徑算法226
9.8最小生成樹231
9.9圖算法的相關問題235
第10章排序256
10.1什麼是排序256
10.2為什麼需要排序256
10.3排序的分類256
10.4其他分類方法257
10.5冒泡排序257
10.6選擇排序258
10.7插入排序259
10.8希爾排序261
10.9歸並排序262
10.10堆排序264
10.11快速排序264
10.12樹排序266
10.13排序算法比較267
10.14綫性排序算法267
10.15計數排序267
10.16桶排序268
10.17基數排序268
10.18拓撲排序269
10.19外部排序269
10.20排序的相關問題270
第11章查找279
11.1什麼是查找279
11.2為什麼需要查找279
11.3查找的類型279
11.4符號錶和散列281
11.5字符串查找算法281
11.6查找的相關問題281
第12章選擇算法(中位數)304
12.1什麼是選擇算法304
12.2基於排序的選擇算法304
12.3基於劃分的選擇算法304
12.4綫性選擇算法——中位數的中位數算法305
12.5按照排序順序查找K個最小元素305
12.6選擇算法的相關問題305
第13章符號錶314
13.1引言314
13.2什麼是符號錶314
13.3符號錶的實現315
13.4符號錶實現方法的比較315
第14章散列317
14.1什麼是散列317
14.2為什麼用散列317
14.3散列錶ADT317
14.4散列的例子317
14.5散列的組成部分319
14.6散列錶319
14.7散列函數319
14.8負載因子320
14.9衝突320
14.10衝突解決技術320
14.11分離鏈接法320
14.12開放定址法321
14.13衝突解決技術的比較322
14.14散列如何達到O(1)的時間復雜度322
14.15散列技術323
14.16不適用散列錶的問題323
14.17布魯姆過濾器323
14.18散列的相關問題325
第15章字符串算法335
15.1引言335
15.2字符串匹配算法335
15.3蠻力法336
15.4RobinKarp字符串匹配算法336
15.5基於有限自動機的字符串匹配算法337
15.6KMP算法338
15.7BoyceMoore算法342
15.8存儲字符串的數據結構342
15.9字符串的散列錶實現342
15.10字符串的二叉搜索樹實現343
15.11鍵樹343
15.12三叉搜索樹345
15.13二叉搜索樹、鍵樹和三叉搜索樹的比較349
15.14後綴樹349
15.15字符串的相關問題353
第16章算法設計技術361
16.1引言361
16.2分類361
16.3按實現方法分類361
16.4按設計方法分類362
16.5其他分類法363
第17章貪婪算法364
17.1引言364
17.2貪婪策略的定義364
17.3貪婪算法的要素364
17.4貪婪算法的適用範圍365
17.5貪婪算法的優缺點365
17.6貪婪算法的應用365
17.7貪婪思想365
17.8貪婪算法的相關問題368
第18章分治算法375
18.1引言375
18.2分治策略的定義375
18.3分治法的適用範圍375
18.4分治法的圖形化描述375
18.5分治思想376
18.6主定理377
18.7分治法的應用377
18.8分治法的相關問題378
第19章動態規劃算法390
19.1引言390
19.2動態規劃策略的定義390
19.3動態規劃策略的性質390
19.4動態規劃的適用範圍390
19.5動態規劃的實現方法391
19.6動態規劃算法的例子391
19.7動態規劃思想391
19.8動態規劃的相關問題396
第20章復雜度類型425
20.1引言425
20.2多項式/指數時間425
20.3決策問題的定義426
20.4決策過程426
20.5復雜度類型的定義426
20.6復雜度類型426
20.7歸約428
20.8復雜度類型的相關問題430
第21章雜談433
21.1引言433
21.2位運算的使用433
21.2.1按位與操作433
21.2.2按位或操作434
21.2.3按位異或操作434
21.2.4按位左移操作434
21.2.5按位右移操作434
21.2.6按位補操作434
21.2.7檢測第K位是否置位434
21.2.8第K位置位435
21.2.9第K位清零435
21.2.10切換第K位435
21.2.11切換值為1的最右位435
21.2.12隔離值為1的最右位435
21.2.13隔離值為0的最右位435
21.2.14檢查某個數是否是2的冪436
21.2.15將某個數乘以2的冪436
21.2.16將某個數除以2的冪436
21.2.17找到給定操作數的模436
21.2.18反轉二進製數436
21.2.19位值1的計數436
21.2.20創建末尾位為0的掩碼437
21.2.21交換奇偶位438
21.2.22不使用除法來計算平均數438
21.3其他編程問題438
參考文獻442
· · · · · · (收起)