本書是國外數(shù)據(jù)結(jié)構(gòu)與算法分析方面的標(biāo)準(zhǔn)教材,介紹了數(shù)據(jù)結(jié)構(gòu)(大量數(shù)據(jù)的組織方法)以及算法分析(算法運行時間的估算)。本書的編寫目標(biāo)是同時講授好的程序設(shè)計和算法分析技巧,使讀者可以開發(fā)出具有*高效率的程序。
本書可作為高級數(shù)據(jù)結(jié)構(gòu)課程或研究生一年級算法分析課程的教材,使用本書需具有一些中級程序設(shè)計知識,還需要離散數(shù)學(xué)的一些背景知識。

出版者的話
譯者序
前言
第1章　引論┊1
1.1　本書討論的內(nèi)容┊2
1.2　數(shù)學(xué)知識復(fù)習(xí)┊3
1.2.1　指數(shù)┊3
1.2.2　對數(shù)┊3
1.2.3　級數(shù)┊4
1.2.4　模運算┊5
1.2.5　證明方法┊5
1.3　遞歸簡論┊7
總結(jié)┊10
練習(xí)┊10
參考文獻(xiàn)┊11
第2章　算法分析┊13
2.1　數(shù)學(xué)基礎(chǔ)┊14
2.2　模型┊16
2.3　要分析的問題┊16
2.4　運行時間計算┊18
2.4.1　一個簡單的例子┊18
2.4.2　一般法則┊19
2.4.3　最大子序列和┊20
2.4.4　運行時間中的對數(shù)┊24
2.4.5　檢驗?zāi)愕姆治雯?7
2.4.6　分析結(jié)果的準(zhǔn)確性┊28
總結(jié)┊28
練習(xí)┊29
參考文獻(xiàn)┊32
第3章　表、棧和隊列┊35
3.1　抽象數(shù)據(jù)類型┊36
3.2　表ADT┊36
3.2.1　表的簡單數(shù)組實現(xiàn)┊37
3.2.2　鏈表┊37
3.2.3　程序設(shè)計細(xì)節(jié)┊38
3.2.4　常見的錯誤┊42
3.2.5　雙鏈表┊43
3.2.6　循環(huán)鏈表┊43
3.2.7　例子┊43
3.2.8　鏈表的游標(biāo)實現(xiàn)┊47
3.3　棧ADT┊50
3.3.1　棧模型┊50
3.3.2　棧的實現(xiàn)┊51
3.3.3　應(yīng)用┊56
3.4　隊列ADT┊62
3.4.1　隊列模型┊62
3.4.2　隊列的數(shù)組實現(xiàn)┊62
3.4.3　隊列的應(yīng)用┊65
總結(jié)┊66
練習(xí)┊66
第4章　樹┊71
4.1　預(yù)備知識┊72
4.1.1　樹的實現(xiàn)┊73
4.1.2　樹的遍歷及應(yīng)用┊74
4.2　二叉樹┊76
4.2.1　實現(xiàn)┊77
4.2.2　表達(dá)式樹┊77
4.3　查找樹ADT——二叉查找樹┊80
4.3.1　MakeEmpty┊80
4.3.2　Find┊81
4.3.3　FindMin和FindMax┊81
4.3.4　Insert┊81
4.3.5　Delete┊83
4.3.6　平均情形分析┊84
4.4　AVL樹┊86
4.4.1　單旋轉(zhuǎn)┊88
4.4.2　雙旋轉(zhuǎn)┊90
4.5　伸展樹┊95
4.5.1　一個簡單的想法┊96
4.5.2　展開┊97
4.6　樹的遍歷┊102
4.7　B樹┊103
總結(jié)┊107
練習(xí)┊108
參考文獻(xiàn)┊113
第5章　散列┊117
5.1　一般想法┊118
5.2　散列函數(shù)┊118
5.3　分離鏈接法┊120
5.4　開放定址法┊123
5.4.1　線性探測法┊124
5.4.2　平方探測法┊125
5.4.3　雙散列┊129
5.5　再散列┊130
5.6　可擴(kuò)散列┊132
總結(jié)┊133
練習(xí)┊134
參考文獻(xiàn)┊137
第6章　優(yōu)先隊列（堆）┊139
6.1　模型┊140
6.2　一些簡單的實現(xiàn)┊141
6.3　二叉堆┊141
6.3.1　結(jié)構(gòu)性質(zhì)┊141
6.3.2　堆序性質(zhì)┊142
6.3.3　基本的堆操作┊143
6.3.4　其他的堆操作┊146
6.4　優(yōu)先隊列的應(yīng)用┊149
6.4.1　選擇問題┊149
6.4.2　事件模擬┊150
6.5　d-堆┊151
6.6　左式堆┊152
6.6.1　左式堆的性質(zhì)┊152
6.6.2　左式堆的操作┊153
6.7　斜堆┊158
6.8　二項隊列┊159
6.8.1　二項隊列結(jié)構(gòu)┊159
6.8.2　二項隊列操作┊160
6.8.3　二項隊列的實現(xiàn)┊162
總結(jié)┊165
練習(xí)┊166
參考文獻(xiàn)┊169
第7章　排序┊173
7.1　預(yù)備知識┊174
7.2　插入排序┊174
7.2.1　算法┊174
7.2.2　插入排序的分析┊175
7.3　一些簡單排序算法的下界┊175
7.4　希爾排序┊176
7.5　堆排序┊179
7.6　歸并排序┊182
7.7　快速排序┊186
7.7.1　選取樞紐元┊187
7.7.2　分割策略┊188
7.7.3　小數(shù)組┊190
7.7.4　實際的快速排序例程┊190
7.7.5　快速排序的分析┊192
7.7.6　選擇的線性期望時間算法┊194
7.8　大型結(jié)構(gòu)的排序┊195
7.9　排序的一般下界┊196
7.10　桶式排序┊198
7.11　外部排序┊198
7.11.1　為什么需要新的算法┊198
7.11.2　外部排序模型┊199
7.11.3　簡單算法┊199
7.11.4　多路合并┊200
7.11.5　多相合并┊201
7.11.6　替換選擇┊202
總結(jié)┊203
練習(xí)┊204
參考文獻(xiàn)┊207
第8章　不相交集ADT┊209
8.1　等價關(guān)系┊210
8.2　動態(tài)等價性問題┊210
8.3　基本數(shù)據(jù)結(jié)構(gòu)┊212
8.4　靈巧求并算法┊214
8.5　路徑壓縮┊216
8.6　按秩求并和路徑壓縮的最壞情形┊217
8.7　一個應(yīng)用┊221
總結(jié)┊222
練習(xí)┊222
參考文獻(xiàn)┊223
第9章　圖論算法┊225
9.1　若干定義┊226
9.2　拓?fù)渑判颟?28
9.3　最短路徑算法┊230
9.3.1　無權(quán)最短路徑┊232
9.3.2　Dijkstra算法┊235
9.3.3　具有負(fù)邊值的圖┊240
9.3.4　無圈圖┊241
9.3.5　所有點對最短路徑┊243
9.4　網(wǎng)絡(luò)流問題┊243
9.5　最小生成樹┊247
9.5.1　Prim算法┊248
9.5.2　Kruskal算法┊250
9.6　深度優(yōu)先搜索的應(yīng)用┊251
9.6.1　無向圖┊252
9.6.2　雙連通性┊253
9.6.3　歐拉回路┊256
9.6.4　有向圖┊259
9.6.5　查找強分支┊260
9.7　NP-完全性介紹┊262
9.7.1　難與易┊262
9.7.2　NP類┊263
9.7.3　NP-完全問題┊264
總結(jié)┊266
練習(xí)┊266
參考文獻(xiàn)┊270
第10章　算法設(shè)計技巧┊273
10.1　貪婪算法┊274
10.1.1　一個簡單的調(diào)度問題┊274
10.1.2　Huffman編碼┊276
10.1.3　近似裝箱問題┊280
10.2　分治算法┊286
10.2.1　分治算法的運行時間┊287
10.2.2　最近點問題┊289
10.2.3　選擇問題┊291
10.2.4　一些運算問題的理論改進(jìn)┊294
10.3　動態(tài)規(guī)劃┊297
10.3.1　用一個表代替遞歸┊298
10.3.2　矩陣乘法的順序安排┊300
10.3.3　最優(yōu)二叉查找樹┊301
10.3.4　所有點對最短路徑┊304
10.4　隨機化算法┊306
10.4.1　隨機數(shù)發(fā)生器┊307
10.4.2　跳躍表┊310
10.4.3　素性測試┊312
10.5　回溯算法┊314
10.5.1　收費公路重建問題┊314
10.5.2　博弈┊318
總結(jié)┊323
練習(xí)┊323
參考文獻(xiàn)┊329
第11章　攤還分析┊333
11.1　一個無關(guān)的智力問題┊334
11.2　二項隊列┊335
11.3　斜堆┊339
11.4　斐波那契堆┊341
11.4.1　切除左式堆中的節(jié)點┊341
11.4.2　二項隊列的懶惰合并┊343
11.4.3　斐波那契堆操作┊346
11.4.4　時間界的證明┊346
11.5　伸展樹┊348
總結(jié)┊351
練習(xí)┊351
參考文獻(xiàn)┊353
第12章　高級數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)┊355
12.1　自頂向下伸展樹┊356
12.2　紅黑樹┊361
12.2.1　自底向上插入┊362
12.2.2　自頂向下紅黑樹┊363
12.2.3　自頂向下刪除┊367
12.3　確定性跳躍表┊368
12.4　AA樹┊373
12.5　treap樹┊378
12.6　k-d樹┊379
12.7　配對堆┊383
總結(jié)┊387
練習(xí)┊387
參考文獻(xiàn)┊389
索引┊391