[美] 馬克·艾倫·維斯 著,陳越 譯
本書是國(guó)外數(shù)據(jù)結(jié)構(gòu)與算法分析方面的經(jīng)典教材,使用卓越的Java編程語言作為實(shí)現(xiàn)工具,討論數(shù)據(jù)結(jié)構(gòu)(組織大量數(shù)據(jù)的方法)和算法分析(對(duì)算法運(yùn)行時(shí)間的估計(jì))。隨著計(jì)算機(jī)速度的不斷增加和功能的日益強(qiáng)大,人們對(duì)有效編程和算法分析的要求也不斷增長(zhǎng)。本書將算法分析與*有效率的Java程序的開發(fā)有機(jī)結(jié)合起來,深入分析每種算法,并細(xì)致講解精心構(gòu)造程序的方法,內(nèi)容全面,縝密嚴(yán)格。第3版的主要更新如下:第4章包含AVL樹刪除算法的實(shí)現(xiàn)。第5章進(jìn)行了全面修訂和擴(kuò)充,現(xiàn)在包含兩種較新的算法——布谷鳥散列和跳房子散列。第7章包含基數(shù)排序的相關(guān)內(nèi)容,并給出了下界證明。第12章增加了后綴樹和后綴數(shù)組的相關(guān)材料,包括Karkkainen和Sanders的線性時(shí)間后綴數(shù)組構(gòu)造算法。更新書中的代碼,使用了Java 7中的菱形運(yùn)算符。
馬克·艾倫·維斯(MarkAllenWeiss)佛羅里達(dá)國(guó)際大學(xué)計(jì)算與信息科學(xué)學(xué)院教授、副院長(zhǎng),本科教育主任和研究生教育主任。他于1987年獲得普林斯頓大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位,師從BobSedgewick。他曾經(jīng)擔(dān)任全美AP(AdvancedPlacement)考試計(jì)算機(jī)學(xué)科委員會(huì)的主席(2000-2004)。他的主要研究興趣是數(shù)據(jù)結(jié)構(gòu)、算法和教育學(xué)。
出版者的話
前言
第1章 引論1
1.1 本書討論的內(nèi)容1
1.2 數(shù)學(xué)知識(shí)復(fù)習(xí)2
1.2.1 指數(shù)2
1.2.2 對(duì)數(shù)2
1.2.3 級(jí)數(shù)2
1.2.4 模運(yùn)算4
1.2.5 證明的方法4
1.3 遞歸簡(jiǎn)論5
1.4 實(shí)現(xiàn)泛型構(gòu)件pre-Java 57
1.4.1 使用Object表示泛型8
1.4.2 基本類型的包裝9
1.4.3 使用接口類型表示泛型9
1.4.4 數(shù)組類型的兼容性10
1.5 利用Java 5泛型特性實(shí)現(xiàn)泛型構(gòu)件11
1.5.1 簡(jiǎn)單的泛型類和接口11
1.5.2 自動(dòng)裝箱/拆箱11
1.5.3 菱形運(yùn)算符12
1.5.4 帶有限制的通配符12
1.5.5 泛型static方法14
1.5.6 類型限界14
1.5.7 類型擦除15
1.5.8 對(duì)于泛型的限制15
1.6 函數(shù)對(duì)象16
小結(jié)18
練習(xí)18
參考文獻(xiàn)19
第2章 算法分析20
2.1 數(shù)學(xué)基礎(chǔ)20
2.2 模型22
2.3 要分析的問題22
2.4 運(yùn)行時(shí)間計(jì)算24
2.4.1 一個(gè)簡(jiǎn)單的例子24
2.4.2 一般法則24
2.4.3 最大子序列和問題的求解26
2.4.4 運(yùn)行時(shí)間中的對(duì)數(shù)31
2.4.5 分析結(jié)果的準(zhǔn)確性33
小結(jié)33
練習(xí)34
參考文獻(xiàn)37
第3章 表、棧和隊(duì)列39
3.1 抽象數(shù)據(jù)類型39
3.2 表ADT39
3.2.1 表的簡(jiǎn)單數(shù)組實(shí)現(xiàn)40
3.2.2 簡(jiǎn)單鏈表40
3.3 Java Collections API中的表41
3.3.1 Collection接口41
3.3.2 Iterator接口42
3.3.3 List接口、ArrayList類和LinkedList類43
3.3.4 例子:remove方法對(duì)LinkedList類的使用44
3.3.5 關(guān)于ListIterator接口46
3.4 ArrayList類的實(shí)現(xiàn)46
3.4.1 基本類46
3.4.2 迭代器、Java嵌套類和內(nèi)部類49
3.5 LinkedList類的實(shí)現(xiàn)52
3.6 棧ADT58
3.6.1 棧模型58
3.6.2 棧的實(shí)現(xiàn)59
3.6.3 應(yīng)用59
3.7 隊(duì)列ADT65
3.7.1 隊(duì)列模型65
3.7.2 隊(duì)列的數(shù)組實(shí)現(xiàn)65
3.7.3 隊(duì)列的應(yīng)用66
小結(jié)67
練習(xí)67
第4章 樹71
4.1 預(yù)備知識(shí)71
4.1.1 樹的實(shí)現(xiàn)72
4.1.2 樹的遍歷及應(yīng)用72
4.2 二叉樹75
4.2.1 實(shí)現(xiàn)76
4.2.2 例子:表達(dá)式樹76
4.3 查找樹ADT——二叉查找樹78
4.3.1 contains方法79
4.3.2 findMin方法和findMax方法80
4.3.3 insert方法80
4.3.4 remove方法82
4.3.5 平均情況分析83
4.4 AVL樹86
4.4.1 單旋轉(zhuǎn)87
4.4.2 雙旋轉(zhuǎn)89
4.5 伸展樹94
4.5.1 一個(gè)簡(jiǎn)單的想法(不能直接使用)95
4.5.2 展開96
4.6 再探樹的遍歷100
4.7 B樹101
4.8 標(biāo)準(zhǔn)庫中的集合與映射105
4.8.1 關(guān)于Set接口105
4.8.2 關(guān)于Map接口105
4.8.3 TreeSet類和TreeMap類的實(shí)現(xiàn)106
4.8.4 使用多個(gè)映射的實(shí)例106
小結(jié)111
練習(xí)111
參考文獻(xiàn)115
第5章 散列117
5.1 一般想法117
5.2 散列函數(shù)117
5.3 分離鏈接法119
5.4 不用鏈表的散列表123
5.4.1 線性探測(cè)法123
5.4.2 平方探測(cè)法124
5.4.3 雙散列129
5.5 再散列130
5.6 標(biāo)準(zhǔn)庫中的散列表132
5.7 最壞情形下O(1)訪問的散列表 133
5.7.1 完美散列133
5.7.2 布谷鳥散列135
5.7.3 跳房子散列143
5.8 通用散列法146
5.9 可擴(kuò)散列148
小結(jié)149
練習(xí)150
參考文獻(xiàn)153
第6章 優(yōu)先隊(duì)列(堆)156
6.1 模型156
6.2 一些簡(jiǎn)單的實(shí)現(xiàn)156
6.3 二叉堆157
6.3.1 結(jié)構(gòu)性質(zhì)157
6.3.2 堆序性質(zhì)157
6.3.3 基本的堆操作158
6.3.4 其他的堆操作162
6.4 優(yōu)先隊(duì)列的應(yīng)用164
6.4.1 選擇問題164
6.4.2 事件模擬165
6.5 d-堆166
6.6 左式堆167
6.6.1 左式堆性質(zhì)167
6.6.2 左式堆操作168
6.7 斜堆172
6.8 二項(xiàng)隊(duì)列173
6.8.1 二項(xiàng)隊(duì)列結(jié)構(gòu)174
6.8.2 二項(xiàng)隊(duì)列操作174
6.8.3 二項(xiàng)隊(duì)列的實(shí)現(xiàn)176
6.9 標(biāo)準(zhǔn)庫中的優(yōu)先隊(duì)列180
小結(jié)180
練習(xí)181
參考文獻(xiàn)184
第7章 排序186
7.1 預(yù)備知識(shí)186
7.2 插入排序186
7.2.1 算法186
7.2.2 插入排序的分析187
7.3 一些簡(jiǎn)單排序算法的下界187
7.4 希爾排序188
7.5 堆排序191
7.6 歸并排序193
7.7 快速排序198
7.7.1 選取樞紐元199
7.7.2 分割策略200
7.7.3 小數(shù)組202
7.7.4 實(shí)際的快速排序例程202
7.7.5 快速排序的分析203
7.7.6 選擇問題的線性期望時(shí)間算法206
7.8 排序算法的一般下界207
7.9 選擇問題的決策樹下界209
7.10 對(duì)手下界210
7.11 線性時(shí)間的排序:桶排序和基數(shù)排序212
7.12 外部排序216
7.12.1 為什么需要一些新的算法217
7.12.2 外部排序模型217
7.12.3 簡(jiǎn)單算法217
7.12.4 多路合并218
7.12.5 多相合并219
7.12.6 替換選擇219
小結(jié)220
練習(xí)221
參考文獻(xiàn)225
第8章 不相交集類227
8.1 等價(jià)關(guān)系227
8.2 動(dòng)態(tài)等價(jià)性問題227
8.3 基本數(shù)據(jù)結(jié)構(gòu)229
8.4 靈巧求并算法231
8.5 路徑壓縮233
8.6 路徑壓縮和按秩求并的最壞情形234
8.6.1 緩慢增長(zhǎng)的函數(shù)235
8.6.2 利用遞歸分解的分析235
8.6.3 O(M log*N)界240
8.6.4 O(Mα(M,N))界240
8.7 一個(gè)應(yīng)用241
小結(jié)243
練習(xí)243
參考文獻(xiàn)244
第9章 圖論算法246
9.1 若干定義246
9.2 拓?fù)渑判?48
9.3 最短路徑算法250
9.3.1 無權(quán)最短路徑251
9.3.2 Dijkstra算法254
9.3.3 具有負(fù)邊值的圖258
9.3.4 無圈圖259
9.3.5 所有點(diǎn)對(duì)最短路徑261
9.3.6 最短路徑的例子261
9.4 網(wǎng)絡(luò)流問題262
9.5 最小生成樹267
9.5.1 Prim算法267
9.5.2 Kruskal算法269
9.6 深度優(yōu)先搜索的應(yīng)用270
9.6.1 無向圖270
9.6.2 雙連通性271
9.6.3 歐拉回路273
9.6.4 有向圖275
9.6.5 查找強(qiáng)分支276
9.7 NP-完全性介紹277
9.7.1 難與易278
9.7.2 NP類278
9.7.3 NP-完全問題279
小結(jié)280
練習(xí)280
參考文獻(xiàn)284
第10章 算法設(shè)計(jì)技巧288
10.1 貪婪算法288
10.1.1 一個(gè)簡(jiǎn)單的調(diào)度問題288
10.1.2 哈夫曼編碼290
10.1.3 近似裝箱問題293
10.2 分治算法298
10.2.1 分治算法的運(yùn)行時(shí)間298
10.2.2 最近點(diǎn)問題300
10.2.3 選擇問題302
10.2.4 一些算術(shù)問題的理論改進(jìn)304
10.3 動(dòng)態(tài)規(guī)劃307
10.3.1 用一個(gè)表代替遞歸307
10.3.2 矩陣乘法的順序安排309
10.3.3 最優(yōu)二叉查找樹311
10.3.4 所有點(diǎn)對(duì)最短路徑312
10.4 隨機(jī)化算法314
10.4.1 隨機(jī)數(shù)發(fā)生器315
10.4.2 跳躍表319
10.4.3 素性測(cè)試320
10.5 回溯算法322
10.5.1 收費(fèi)公路重建問題323
10.5.2 博弈326
小結(jié)331
練習(xí)331
參考文獻(xiàn)336
第11章 攤還分析340
11.1 一個(gè)無關(guān)的智力問題340
11.2 二項(xiàng)隊(duì)列340
11.3 斜堆344
11.4 斐波那契堆345
11.4.1 切除左式堆中的節(jié)點(diǎn)346
11.4.2 二項(xiàng)隊(duì)列的懶惰合并347
11.4.3 斐波那契堆操作349
11.4.4 時(shí)間界的證明350
11.5 伸展樹351
小結(jié)354
練習(xí)354
參考文獻(xiàn)355
第12章 高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)356
12.1 自頂向下伸展樹356
12.2 紅黑樹362
12.2.1 自底向上的插入362
12.2.2 自頂向下紅黑樹363
12.2.3 自頂向下的刪除367
12.3 treap樹368
12.4 后綴數(shù)組與后綴樹370
12.4.1 后綴數(shù)組371
12.4.2 后綴樹373
12.4.3 線性時(shí)間的后綴數(shù)組和后綴樹的構(gòu)建375
12.5 k-d樹385
12.6 配對(duì)堆387
小結(jié)392
練習(xí)393
參考文獻(xiàn)396
索引399
本書目標(biāo)本書新的Java版論述數(shù)據(jù)結(jié)構(gòu)——組織大量數(shù)據(jù)的方法,以及算法分析——算法運(yùn)行時(shí)間的估計(jì)。隨著計(jì)算機(jī)的速度越來越快,對(duì)于能夠處理大量輸入數(shù)據(jù)的程序的需求變得日益迫切??墒?,由于在輸入量很大的時(shí)候程序的低效率變得非常明顯,因此這又要求對(duì)效率問題給予更仔細(xì)的關(guān)注。通過在實(shí)際編程之前對(duì)算法的分析,我們可以確定某個(gè)特定的解法是否可行。例如,查閱本書中一些特定的問題,可以看到我們?nèi)绾瓮ㄟ^巧妙的實(shí)現(xiàn),將其處理大量數(shù)據(jù)的時(shí)間限制從幾個(gè)世紀(jì)減至不到1秒。因此,我們?cè)谔岢鏊兴惴ê蛿?shù)據(jù)結(jié)構(gòu)時(shí)都會(huì)闡釋其運(yùn)行時(shí)間。在某些情況下,對(duì)于影響實(shí)現(xiàn)的運(yùn)行時(shí)間的一些微小細(xì)節(jié)都需要認(rèn)真探究。
一旦確定了解法,接著就要編寫程序。隨著計(jì)算機(jī)功能的日益強(qiáng)大,它們必須解決的問題也變得更加龐大和復(fù)雜,這就要求我們開發(fā)更加復(fù)雜的程序。本書的目的是同時(shí)教授學(xué)生良好的程序設(shè)計(jì)技巧和算法分析能力,使得他們能夠以最高的效率開發(fā)出這種程序?! ”緯m用于高級(jí)數(shù)據(jù)結(jié)構(gòu)(CS7)課程或是第一年研究生的算法分析課程。學(xué)生應(yīng)該掌握一些中級(jí)編程知識(shí),包括基于對(duì)象的程序設(shè)計(jì)和遞歸等內(nèi)容,并具備一些離散數(shù)學(xué)的背景。 第3版中最顯著的變化第3版訂正了大量的錯(cuò)誤,也修改了很多地方,以使內(nèi)容更加清晰。此外還有以下修訂:
●第4章包括了AVL樹的刪除算法——這也是讀者經(jīng)常需要的內(nèi)容。
●第5章進(jìn)行了大量修改和擴(kuò)充,現(xiàn)在包含兩種新算法:布谷鳥散列(cuckoohashing)和跳房子散列(hopscotchhashing)。此外還增加了一節(jié)討論通用散列法。
●第7章現(xiàn)在包含了基數(shù)排序的內(nèi)容,并且增加了一節(jié)討論下界的證明。
●第8章用到Seidel和Sharir提出的新的并查集分析,并且證明了O(Mα(MN))界,而不是前一版中比較弱的O(Mlog*N)界。
●第12章增加了后綴樹和后綴數(shù)組的內(nèi)容,包括Karkkainen和Sanders提出的構(gòu)造后綴數(shù)組的線性時(shí)間算法(附帶實(shí)現(xiàn))。關(guān)于確定性跳躍表和AA樹的章節(jié)被刪除。
●通篇代碼已做更新,使用了Java7的菱形運(yùn)算符。
處理方法雖然本書的內(nèi)容大部分都與語言無關(guān),但是,程序設(shè)計(jì)還是需要使用某種特定的語言。正如書名所示,我們?yōu)楸緯x擇了Java。
人們常常將Java和C++比較。Java具有許多優(yōu)點(diǎn),程序員常常把Java看成是一種比C++更安全、更具有可移植性并且更容易使用的語言。因此,這使得它成為討論和實(shí)現(xiàn)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的一種優(yōu)秀的核心語言。Java的其他重要的方面,諸如線程和GUI(圖形用戶界面),雖然很重要,但是本書并不需要,因此也就不再討論。
完整的Java和C++版數(shù)據(jù)結(jié)構(gòu)均在互聯(lián)網(wǎng)上提供。我們采用相似的編碼約定以使得這兩種語言之間的對(duì)等性更加明顯。
內(nèi)容概述第1章包含離散數(shù)學(xué)和遞歸的一些復(fù)習(xí)材料。我相信熟練掌握遞歸的唯一辦法是反復(fù)不斷地研讀一些好的用法。因此,除第5章外,遞歸遍及本書每一章的例子之中。第1章還介紹了一些相關(guān)內(nèi)容,作為對(duì)Java中“繼承”的復(fù)習(xí),包括對(duì)Java泛型的討論。
第2章討論算法分析,闡述漸近分析及其主要缺點(diǎn),提供了許多例子,包括對(duì)對(duì)數(shù)級(jí)運(yùn)行時(shí)間的深入分析。我們通過直觀地把遞歸程序轉(zhuǎn)變成迭代程序,對(duì)一些簡(jiǎn)單遞歸程序進(jìn)行了分析。更復(fù)雜的分治程序也在此介紹,不過有些分析(求解遞推關(guān)系)要推遲到第7章再進(jìn)行詳細(xì)討論。
第3章介紹表、棧和隊(duì)列。包括對(duì)CollectionsAPIArrayList類和LinkedList類的討論,提供了CollectionsAPIArrayList類和LinkedList類的一個(gè)重要子集的若干實(shí)現(xiàn)。
.第4章討論樹,重點(diǎn)是查找樹,包括外部查找樹(B-樹)。UNIX文件系統(tǒng)和表達(dá)式樹是作為例子來介紹的。這一章還介紹了AVL樹和伸展樹。查找樹實(shí)現(xiàn)細(xì)節(jié)的更仔細(xì)的處理可在第12章找到。樹的另外一些內(nèi)容(如文件壓縮和博弈樹)推遲到第10章討論。外部介質(zhì)上的數(shù)據(jù)結(jié)構(gòu)作為若干章中的最后論題來考慮。對(duì)于CollectionsAPITreeSet類和TreeMap類的討論,則通過一個(gè)重要的例子來展示三種單獨(dú)的映射在求解同一個(gè)問題中的使用。
第5章討論散列表,既包括經(jīng)典算法,如分離鏈接法和線性及平方探測(cè)法,同時(shí)也包括幾個(gè)新算法,如布谷鳥散列和跳房子散列。本章還討論了通用散列法,并且在章末討論了可擴(kuò)散列。
第6章是關(guān)于優(yōu)先隊(duì)列的。二叉堆也在這里講授,還有些附加的材料論述優(yōu)先隊(duì)列某些理論上有趣的實(shí)現(xiàn)方法。斐波那契堆在第11章討論,配對(duì)堆在第12章討論。
第7章論述排序。這一章特別關(guān)注編程細(xì)節(jié)和分析。所有重要的通用排序算法均在該章進(jìn)行了討論和比較。此外,還對(duì)四種排序算法做了詳細(xì)的分析,它們是插入排序、希爾排序、堆排序以及快速排序。這一版新增的是基數(shù)排序以及對(duì)選擇類問題的下界的證明。本章末尾討論了外部排序。
第8章討論不相交集算法并證明其運(yùn)行時(shí)間。分析部分是新的。這是簡(jiǎn)短且特殊的一章,如果不討論Kruskal算法則可跳過該章。
第9章講授圖論算法。圖論算法之所以有趣,不僅因?yàn)樗鼈冊(cè)趯?shí)踐中經(jīng)常出現(xiàn),而且還因?yàn)樗鼈兊倪\(yùn)行時(shí)間強(qiáng)烈地依賴于數(shù)據(jù)結(jié)構(gòu)的恰當(dāng)使用。實(shí)際上,所有標(biāo)準(zhǔn)算法都和適用的數(shù)據(jù)結(jié)構(gòu)、偽代碼以及運(yùn)行時(shí)間的分析一起介紹。為了恰當(dāng)?shù)乩斫膺@些問題,我們對(duì)復(fù)雜性理論(包括NP-完全性和不可判定性)進(jìn)行了簡(jiǎn)短的討論。
第10章通過考察一般性的問題求解技術(shù)來介紹算法設(shè)計(jì)。本章通過大量的例子來增強(qiáng)理解。這一章及后面各章使用的偽代碼使得讀者在理解例子時(shí)不會(huì)被實(shí)現(xiàn)的細(xì)節(jié)所困擾。
第11章處理攤還分析,主要分析三種數(shù)據(jù)結(jié)構(gòu),它們分別在第4章、第6章以及本章(斐波那契堆)介紹。 第12章討論查找樹算法、后綴樹和數(shù)組、k-d樹和配對(duì)堆。不同于其他各章,本章給出了查找樹和配對(duì)堆完整且仔細(xì)的實(shí)現(xiàn)。材料的安排使得教師可以把一些內(nèi)容納入其他各章的討論之中。例如,第12章中的自頂向下紅黑樹可以和(第4章的)AVL樹一起討論。
第1~9章為大多數(shù)一學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程提供了足夠的材料。如果時(shí)間允許,那么第10章也可以包括進(jìn)來。研究生的算法分析課程可以使用第7~11章的內(nèi)容。第11章所分析的高級(jí)數(shù)據(jù)結(jié)構(gòu)可以很容易地被前面各章所提及。第9章里所討論的NP-完全性太過簡(jiǎn)短,不適用于這樣的課程。另外再用一部NP-完全性方面的著作作為本教材的補(bǔ)充可能是比較有益的。
練習(xí)每章末尾提供的練習(xí)與正文中所述內(nèi)容的順序相一致。最后的一些練習(xí)是對(duì)應(yīng)整章而不是針對(duì)特定的某一節(jié)的。難度較大的練習(xí)標(biāo)有一個(gè)星號(hào),更具挑戰(zhàn)的練習(xí)標(biāo)有兩個(gè)星號(hào)。
參考文獻(xiàn)參考文獻(xiàn)列于每章的最后。通常,這些參考文獻(xiàn)或者是具有歷史意義的、給出書中材料的原始出處,或者闡述對(duì)書中給出的結(jié)果的擴(kuò)展和改進(jìn)。有些文獻(xiàn)為一些練習(xí)提供了解法。
補(bǔ)充材料下面的補(bǔ)充材料在www.pearsonhighered.com/cssupport對(duì)所有讀者公開:
●例子程序的源代碼此外,下述材料僅提供給經(jīng)培生教師資源中心(Pearson’sInstructorResourceCenter,IRC)(www.pearsonhighered.com/irc)認(rèn)可的教師。有意者請(qǐng)?jiān)L問IRC或聯(lián)系培生的校園代表以獲得訪問權(quán)限。關(guān)于本書教輔資源,用書教師可向培生教育出版集團(tuán)北京代表處申請(qǐng),電話:010-57355169/57355171,電子郵件:service.cn@pearson.com?!庉嬜?/p>
●部分練習(xí)的解答
●來自本書的一些附圖致謝在本書的準(zhǔn)備過程中,我得到了許多人的幫助,有些已在本書的其他版本中列出,感謝大家?! ∫蝗缂韧?,培生的專家們的努力使得本書的寫作過程更加輕松。我愿在此感謝我的編輯MichaelHirsch以及制作編輯PatBrown。我還要感謝AbinayaRajendran和她在IntegraSoftwareServices的同事,感謝他們使最后的散稿成書的出色工作。賢妻Jill所做的每一件事情都值得我特別感謝。
最后,我還想感謝發(fā)來E-mail并指出前面各版中錯(cuò)誤和矛盾之處的廣大讀者。我的網(wǎng)頁www.cis.fiu.edu/~weiss包含更新后的源代碼(用Java和C++編寫)、勘誤表以及提交問題報(bào)告的鏈接。
M.A.W.佛羅里達(dá)州邁阿密市
更多建議: