本書把算法分析與最有效率的Java程式的開發有機地結合起來，深入分析每種算法，內容全面、縝密嚴格，並細緻講解精心構造程式的方法。
基本介紹
- 書名：數據結構與算法分析 java語言描述（原書第3版）
- 作者：[美]馬克·艾倫·維斯
- 原版名稱：Data Structures and Algorithm Analysis in Java，Third Edition
- 譯者：陳越
- ISBN：9787111528395
- 頁數：403
- 定價：69
- 出版社：機械工業出版社
- 出版時間：2016-10-31
- 開本：16
內容簡介,圖書目錄,
內容簡介
本書是國外數據結構與算法分析方面的經典教材，使用卓越的Java程式語言作為實現工具討論了數據結構(組織大量數據的方法)和算法分析(對算法運行時間的估計)。本書把算法分析與最有效率的Java程式的開發有機地結合起來，深入分析每種算法，內容全面、縝密嚴格，並細緻講解精心構造程式的方法。
圖書目錄
出版者的話
前言
第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.3Java Collections API中的表41
3.3.1Collection接口41
3.3.2Iterator接口42
3.3.3List接口、ArrayList類和LinkedList類43
3.3.4例子：remove方法對LinkedList類的使用44
3.3.5關於ListIterator接口46
3.4ArrayList類的實現46
3.4.1基本類46
3.4.2疊代器、Java嵌套類和內部類49
3.5LinkedList類的實現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.1contains方法79
4.3.2findMin方法和findMax方法80
4.3.3insert方法80
4.3.4remove方法82
4.3.5平均情況分析83
4.4AVL樹86
4.4.1單旋轉87
4.4.2雙旋轉89
4.5伸展樹94
4.5.1一個簡單的想法（不能直接使用）95
4.5.2展開96
4.6再探樹的遍歷100
4.7B樹101
4.8標準庫中的集合與映射105
4.8.1關於Set接口105
4.8.2關於Map接口105
4.8.3TreeSet類和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.5d-堆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.3O(M log*N)界240
8.6.4O(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.2Dijkstra算法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.1Prim算法267
9.5.2Kruskal算法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.7NP-完全性介紹277
9.7.1難與易278
9.7.2NP類278
9.7.3NP-完全問題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.3treap樹368
12.4後綴數組與後綴樹370
12.4.1後綴數組371
12.4.2後綴樹373
12.4.3線性時間的後綴數組和後綴樹的構建375
12.5k-d樹385
12.6配對堆387
小結392
練習393
參考文獻396
索引399
