齣版者的話
前言
第1章 引論1
1.1 本書討論的內容1
1.2 數學知識復習2
1.2.1 指數2
1.2.2 對數2
1.2.3 級數2
1.2.4 模運算4
1.2.5 證明的方法4
1.3 遞歸簡論5
1.4 實現泛型構件pre-Java 57
1.4.1 使用Object錶示泛型8
1.4.2 基本類型的包裝9
1.4.3 使用接口類型錶示泛型9
1.4.4 數組類型的兼容性10
1.5 利用Java 5泛型特性實現泛型構件11
1.5.1 簡單的泛型類和接口11
1.5.2 自動裝箱/拆箱11
1.5.3 菱形運算符12
1.5.4 帶有限製的通配符12
1.5.5 泛型static方法14
1.5.6 類型限界14
1.5.7 類型擦除15
1.5.8 對於泛型的限製15
1.6 函數對象16
小結18
練習18
參考文獻19
第2章 算法分析20
2.1 數學基礎20
2.2 模型22
2.3 要分析的問題22
2.4 運行時間計算24
2.4.1 一個簡單的例子24
2.4.2 一般法則24
2.4.3 最大子序列和問題的求解26
2.4.4 運行時間中的對數31
2.4.5 分析結果的準確性33
小結33
練習34
參考文獻37
第3章 錶、棧和隊列39
3.1 抽象數據類型39
3.2 錶ADT39
3.2.1 錶的簡單數組實現40
3.2.2 簡單鏈錶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方法對LinkedList類的使用44
3.3.5 關於ListIterator接口46
3.4 ArrayList類的實現46
3.4.1 基本類46
3.4.2 迭代器、Java嵌套類和內部類49
3.5 LinkedList類的實現52
3.6 棧ADT58
3.6.1 棧模型58
3.6.2 棧的實現59
3.6.3 應用59
3.7 隊列ADT65
3.7.1 隊列模型65
3.7.2 隊列的數組實現65
3.7.3 隊列的應用66
小結67
練習67
第4章 樹71
4.1 預備知識71
4.1.1 樹的實現72
4.1.2 樹的遍曆及應用72
4.2 二叉樹75
4.2.1 實現76
4.2.2 例子：錶達式樹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 單鏇轉87
4.4.2 雙鏇轉89
4.5 伸展樹94
4.5.1 一個簡單的想法（不能直接使用）95
4.5.2 展開96
4.6 再探樹的遍曆100
4.7 B樹101
4.8 標準庫中的集閤與映射105
4.8.1 關於Set接口105
4.8.2 關於Map接口105
4.8.3 TreeSet類和TreeMap類的實現106
4.8.4 使用多個映射的實例106
小結111
練習111
參考文獻115
第5章 散列117
5.1 一般想法117
5.2 散列函數117
5.3 分離鏈接法119
5.4 不用鏈錶的散列錶123
5.4.1 綫性探測法123
5.4.2 平方探測法124
5.4.3 雙散列129
5.5 再散列130
5.6 標準庫中的散列錶132
5.7 最壞情形下O(1)訪問的散列錶 133
5.7.1 完美散列133
5.7.2 布榖鳥散列135
5.7.3 跳房子散列143
5.8 通用散列法146
5.9 可擴散列148
小結149
練習150
參考文獻153
第6章 優先隊列（堆）156
6.1 模型156
6.2 一些簡單的實現156
6.3 二叉堆157
6.3.1 結構性質157
6.3.2 堆序性質157
6.3.3 基本的堆操作158
6.3.4 其他的堆操作162
6.4 優先隊列的應用164
6.4.1 選擇問題164
6.4.2 事件模擬165
6.5 d-堆166
6.6 左式堆167
6.6.1 左式堆性質167
6.6.2 左式堆操作168
6.7 斜堆172
6.8 二項隊列173
6.8.1 二項隊列結構174
6.8.2 二項隊列操作174
6.8.3 二項隊列的實現176
6.9 標準庫中的優先隊列180
小結180
練習181
參考文獻184
第7章 排序186
7.1 預備知識186
7.2 插入排序186
7.2.1 算法186
7.2.2 插入排序的分析187
7.3 一些簡單排序算法的下界187
7.4 希爾排序188
7.5 堆排序191
7.6 歸並排序193
7.7 快速排序198
7.7.1 選取樞紐元199
7.7.2 分割策略200
7.7.3 小數組202
7.7.4 實際的快速排序例程202
7.7.5 快速排序的分析203
7.7.6 選擇問題的綫性期望時間算法206
7.8 排序算法的一般下界207
7.9 選擇問題的決策樹下界209
7.10 對手下界210
7.11 綫性時間的排序：桶排序和基數排序212
7.12 外部排序216
7.12.1 為什麼需要一些新的算法217
7.12.2 外部排序模型217
7.12.3 簡單算法217
7.12.4 多路閤並218
7.12.5 多相閤並219
7.12.6 替換選擇219
小結220
練習221
參考文獻225
第8章 不相交集類227
8.1 等價關係227
8.2 動態等價性問題227
8.3 基本數據結構229
8.4 靈巧求並算法231
8.5 路徑壓縮233
8.6 路徑壓縮和按秩求並的最壞情形234
8.6.1 緩慢增長的函數235
8.6.2 利用遞歸分解的分析235
8.6.3 O(M log*N)界240
8.6.4 O(Mα(M,N))界240
8.7 一個應用241
小結243
練習243
參考文獻244
第9章 圖論算法246
9.1 若乾定義246
9.2 拓撲排序248
9.3 最短路徑算法250
9.3.1 無權最短路徑251
9.3.2 Dijkstra算法254
9.3.3 具有負邊值的圖258
9.3.4 無圈圖259
9.3.5 所有點對最短路徑261
9.3.6 最短路徑的例子261
9.4 網絡流問題262
9.5 最小生成樹267
9.5.1 Prim算法267
9.5.2 Kruskal算法269
9.6 深度優先搜索的應用270
9.6.1 無嚮圖270
9.6.2 雙連通性271
9.6.3 歐拉迴路273
9.6.4 有嚮圖275
9.6.5 查找強分支276
9.7 NP-完全性介紹277
9.7.1 難與易278
9.7.2 NP類278
9.7.3 NP-完全問題279
小結280
練習280
參考文獻284
第10章 算法設計技巧288
10.1 貪婪算法288
10.1.1 一個簡單的調度問題288
10.1.2 哈夫曼編碼290
10.1.3 近似裝箱問題293
10.2 分治算法298
10.2.1 分治算法的運行時間298
10.2.2 最近點問題300
10.2.3 選擇問題302
10.2.4 一些算術問題的理論改進304
10.3 動態規劃307
10.3.1 用一個錶代替遞歸307
10.3.2 矩陣乘法的順序安排309
10.3.3 最優二叉查找樹311
10.3.4 所有點對最短路徑312
10.4 隨機化算法314
10.4.1 隨機數發生器315
10.4.2 跳躍錶319
10.4.3 素性測試320
10.5 迴溯算法322
10.5.1 收費公路重建問題323
10.5.2 博弈326
小結331
練習331
參考文獻336
第11章 攤還分析340
11.1 一個無關的智力問題340
11.2 二項隊列340
11.3 斜堆344
11.4 斐波那契堆345
11.4.1 切除左式堆中的節點346
11.4.2 二項隊列的懶惰閤並347
11.4.3 斐波那契堆操作349
11.4.4 時間界的證明350
11.5 伸展樹351
小結354
練習354
參考文獻355
第12章 高級數據結構及其實現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 後綴數組與後綴樹370
12.4.1 後綴數組371
12.4.2 後綴樹373
12.4.3 綫性時間的後綴數組和後綴樹的構建375
12.5 k-d樹385
12.6 配對堆387
小結392
練習393
參考文獻396
索引399
· · · · · · (收起)
前言
第1章 引論1
1.1 本書討論的內容1
1.2 數學知識復習2
1.2.1 指數2
1.2.2 對數2
1.2.3 級數2
1.2.4 模運算4
1.2.5 證明的方法4
1.3 遞歸簡論5
1.4 實現泛型構件pre-Java 57
1.4.1 使用Object錶示泛型8
1.4.2 基本類型的包裝9
1.4.3 使用接口類型錶示泛型9
1.4.4 數組類型的兼容性10
1.5 利用Java 5泛型特性實現泛型構件11
1.5.1 簡單的泛型類和接口11
1.5.2 自動裝箱/拆箱11
1.5.3 菱形運算符12
1.5.4 帶有限製的通配符12
1.5.5 泛型static方法14
1.5.6 類型限界14
1.5.7 類型擦除15
1.5.8 對於泛型的限製15
1.6 函數對象16
小結18
練習18
參考文獻19
第2章 算法分析20
2.1 數學基礎20
2.2 模型22
2.3 要分析的問題22
2.4 運行時間計算24
2.4.1 一個簡單的例子24
2.4.2 一般法則24
2.4.3 最大子序列和問題的求解26
2.4.4 運行時間中的對數31
2.4.5 分析結果的準確性33
小結33
練習34
參考文獻37
第3章 錶、棧和隊列39
3.1 抽象數據類型39
3.2 錶ADT39
3.2.1 錶的簡單數組實現40
3.2.2 簡單鏈錶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方法對LinkedList類的使用44
3.3.5 關於ListIterator接口46
3.4 ArrayList類的實現46
3.4.1 基本類46
3.4.2 迭代器、Java嵌套類和內部類49
3.5 LinkedList類的實現52
3.6 棧ADT58
3.6.1 棧模型58
3.6.2 棧的實現59
3.6.3 應用59
3.7 隊列ADT65
3.7.1 隊列模型65
3.7.2 隊列的數組實現65
3.7.3 隊列的應用66
小結67
練習67
第4章 樹71
4.1 預備知識71
4.1.1 樹的實現72
4.1.2 樹的遍曆及應用72
4.2 二叉樹75
4.2.1 實現76
4.2.2 例子：錶達式樹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 單鏇轉87
4.4.2 雙鏇轉89
4.5 伸展樹94
4.5.1 一個簡單的想法（不能直接使用）95
4.5.2 展開96
4.6 再探樹的遍曆100
4.7 B樹101
4.8 標準庫中的集閤與映射105
4.8.1 關於Set接口105
4.8.2 關於Map接口105
4.8.3 TreeSet類和TreeMap類的實現106
4.8.4 使用多個映射的實例106
小結111
練習111
參考文獻115
第5章 散列117
5.1 一般想法117
5.2 散列函數117
5.3 分離鏈接法119
5.4 不用鏈錶的散列錶123
5.4.1 綫性探測法123
5.4.2 平方探測法124
5.4.3 雙散列129
5.5 再散列130
5.6 標準庫中的散列錶132
5.7 最壞情形下O(1)訪問的散列錶 133
5.7.1 完美散列133
5.7.2 布榖鳥散列135
5.7.3 跳房子散列143
5.8 通用散列法146
5.9 可擴散列148
小結149
練習150
參考文獻153
第6章 優先隊列（堆）156
6.1 模型156
6.2 一些簡單的實現156
6.3 二叉堆157
6.3.1 結構性質157
6.3.2 堆序性質157
6.3.3 基本的堆操作158
6.3.4 其他的堆操作162
6.4 優先隊列的應用164
6.4.1 選擇問題164
6.4.2 事件模擬165
6.5 d-堆166
6.6 左式堆167
6.6.1 左式堆性質167
6.6.2 左式堆操作168
6.7 斜堆172
6.8 二項隊列173
6.8.1 二項隊列結構174
6.8.2 二項隊列操作174
6.8.3 二項隊列的實現176
6.9 標準庫中的優先隊列180
小結180
練習181
參考文獻184
第7章 排序186
7.1 預備知識186
7.2 插入排序186
7.2.1 算法186
7.2.2 插入排序的分析187
7.3 一些簡單排序算法的下界187
7.4 希爾排序188
7.5 堆排序191
7.6 歸並排序193
7.7 快速排序198
7.7.1 選取樞紐元199
7.7.2 分割策略200
7.7.3 小數組202
7.7.4 實際的快速排序例程202
7.7.5 快速排序的分析203
7.7.6 選擇問題的綫性期望時間算法206
7.8 排序算法的一般下界207
7.9 選擇問題的決策樹下界209
7.10 對手下界210
7.11 綫性時間的排序：桶排序和基數排序212
7.12 外部排序216
7.12.1 為什麼需要一些新的算法217
7.12.2 外部排序模型217
7.12.3 簡單算法217
7.12.4 多路閤並218
7.12.5 多相閤並219
7.12.6 替換選擇219
小結220
練習221
參考文獻225
第8章 不相交集類227
8.1 等價關係227
8.2 動態等價性問題227
8.3 基本數據結構229
8.4 靈巧求並算法231
8.5 路徑壓縮233
8.6 路徑壓縮和按秩求並的最壞情形234
8.6.1 緩慢增長的函數235
8.6.2 利用遞歸分解的分析235
8.6.3 O(M log*N)界240
8.6.4 O(Mα(M,N))界240
8.7 一個應用241
小結243
練習243
參考文獻244
第9章 圖論算法246
9.1 若乾定義246
9.2 拓撲排序248
9.3 最短路徑算法250
9.3.1 無權最短路徑251
9.3.2 Dijkstra算法254
9.3.3 具有負邊值的圖258
9.3.4 無圈圖259
9.3.5 所有點對最短路徑261
9.3.6 最短路徑的例子261
9.4 網絡流問題262
9.5 最小生成樹267
9.5.1 Prim算法267
9.5.2 Kruskal算法269
9.6 深度優先搜索的應用270
9.6.1 無嚮圖270
9.6.2 雙連通性271
9.6.3 歐拉迴路273
9.6.4 有嚮圖275
9.6.5 查找強分支276
9.7 NP-完全性介紹277
9.7.1 難與易278
9.7.2 NP類278
9.7.3 NP-完全問題279
小結280
練習280
參考文獻284
第10章 算法設計技巧288
10.1 貪婪算法288
10.1.1 一個簡單的調度問題288
10.1.2 哈夫曼編碼290
10.1.3 近似裝箱問題293
10.2 分治算法298
10.2.1 分治算法的運行時間298
10.2.2 最近點問題300
10.2.3 選擇問題302
10.2.4 一些算術問題的理論改進304
10.3 動態規劃307
10.3.1 用一個錶代替遞歸307
10.3.2 矩陣乘法的順序安排309
10.3.3 最優二叉查找樹311
10.3.4 所有點對最短路徑312
10.4 隨機化算法314
10.4.1 隨機數發生器315
10.4.2 跳躍錶319
10.4.3 素性測試320
10.5 迴溯算法322
10.5.1 收費公路重建問題323
10.5.2 博弈326
小結331
練習331
參考文獻336
第11章 攤還分析340
11.1 一個無關的智力問題340
11.2 二項隊列340
11.3 斜堆344
11.4 斐波那契堆345
11.4.1 切除左式堆中的節點346
11.4.2 二項隊列的懶惰閤並347
11.4.3 斐波那契堆操作349
11.4.4 時間界的證明350
11.5 伸展樹351
小結354
練習354
參考文獻355
第12章 高級數據結構及其實現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 後綴數組與後綴樹370
12.4.1 後綴數組371
12.4.2 後綴樹373
12.4.3 綫性時間的後綴數組和後綴樹的構建375
12.5 k-d樹385
12.6 配對堆387
小結392
練習393
參考文獻396
索引399
· · · · · · (收起)
具體描述
本書是國外數據結構與算法分析方麵的經典教材，使用卓越的Java編程語言作為實現工具討論瞭數據結構(組織大量數據的方法)和算法分析(對算法運行時間的估計)。本書把算法分析與有效率的Java程序的開發有機地結閤起來，深入分析每種算法，內容全麵、縝密嚴格，並細緻講解精心構造程序的方法。
用戶評價
評分
##I hate this book. 這本書的英文其實就很蹩腳，中文版的翻譯可能加深瞭對讀者的荼毒。 這本書有很多缺點：他就不想把東西給你解釋明白，隨便說一個定理，然後後麵引齣的結論就說是前麵東西很清楚的證明瞭，沒有任何中間思維過程，what？？；有的時候又會莫名的囉嗦，比如前後兩段，都說一次“我們把這個集閤叫做R”之類的；有時候像是概述類論文，就楞給個公式，然後提兩句相關內容；cross reference就是一坨shit，對其他章節的引述太隨意，通常你不知道他在引用什麼；對遞歸有一種謎一樣的偏見；code不完全，讓你online去看；排版相當糟糕，code和對應的解釋通常不在一頁上，得跳來跳去的翻頁，看過stevens的unix係列，這個編輯隻能負分。 看這本書真是煎熬，爛書。
評分
##粗略讀過一遍
評分
##前前後後，花瞭一個多月，總算把它啃完。總的來說，這本近400頁的書還是很不錯，比國內很多本科教材好多。佩服作者。看是看完瞭，但是很多內容還有待消化，尤其是後麵的一些內容。還需要很長一段時間反嚼。比較燒腦。
評分
##這翻譯是真的爛啊
評分
##【2022/工具書】翻譯得真是晦澀難懂....心好纍....
評分
##這本書難度挺高的，然後翻譯方麵也有點拗口，不過總體來看還不錯吧。
評分
##大學的時候好好磕一頓，也不至於現在這樣
評分
##啃瞭一周，啃完瞭前九章。真的不是給新手寫的，把讀書筆記寫完迴頭在啃後三章。
##大學的時候好好磕一頓，也不至於現在這樣