數(shù)據(jù)結(jié)構(gòu)與問題求解Java語言描述（第三版）

第一部分　算法和構(gòu)件塊
第1章　算法分析　2
1.1　什么是算法分析　2
1.2　算法運行時間的實例　5
1.3　連續(xù)子序列最大和的問題　6
1.3.1　簡單的O(N3)算法　7
1.3.2　改進的O(N2)算法　8
1.3.3　線性算法　9
1.4　一般的大O規(guī)則　11
1.5　對數(shù)　14
1.6　靜態(tài)查找問題　15
1.6.1　順序查找　15
1.6.2　二分搜索　16
1.6.3　插值查找　18
1.7　算法分析的檢查　18
1.8　大O分析的局限性　19
小結(jié)　20
關(guān)鍵概念　20
常見錯誤　21
網(wǎng)上資源　21
習(xí)題　21
參考文獻　26
第2章　集合類API　27
2.1　引言　27
2.2　迭代器模式　28
2.2.1　基本的迭代器設(shè)計　29
2.2.2　基于繼承的迭代器和工廠方法　30
2.3　集合類API：容器和迭代器　32
2.3.1　Collection接口　32
2.3.2　Iterator接口　35
2.4　泛型算法　36
2.4.1　Comparator函數(shù)對象　37
2.4.2　Collections類　37
2.4.3　二分搜索　39
2.4.4　排序　40
2.5　List接口　40
2.5.1　ListIterator接口　41
2.5.2　LinkedList類　42
2.6　棧和隊列　44
2.6.1　?！?4
2.6.2　棧與計算機語言　45
2.6.3　隊列　46
2.6.4　集合類API中的棧和隊列　46
2.7　集合　47
2.7.1　TreeSet類　48
2.7.2　HashSet類　48
2.8　映射　52
2.9　優(yōu)先級隊列　55
小結(jié)　57
關(guān)鍵概念　57
常見錯誤　58
網(wǎng)上資源　58
習(xí)題　59
參考文獻　61
第3章　遞歸　62
3.1　什么是遞歸　62
3.2　背景：數(shù)學(xué)歸納法證明　63
3.3　基本的遞歸　65
3.3.1　以任何數(shù)制打印數(shù)　66
3.3.2　為什么可行　67
3.3.3　原理解析　68
3.3.4　太多的遞歸可能是危險的　69
3.3.5　樹的預(yù)習(xí)　70
3.3.6　其他實例　71
3.4　數(shù)值應(yīng)用　74
3.4.1　模運算　74
3.4.2　模的冪運算　75
3.4.3　最大公因子和乘法逆元素　76
3.4.4　RSA密碼系統(tǒng)　78
3.5　分治算法　79
3.5.1　連續(xù)子序列最大和的問題　80
3.5.2　對一個基本的分治情況的分析　82
3.5.3　分治算法運行時間的通用上界　84
3.6　動態(tài)規(guī)劃　86
3.7　回溯　89
小結(jié)　92
關(guān)鍵概念　92
常見錯誤　93
網(wǎng)上資源　93
習(xí)題　94
參考文獻　96
第4章　排序算法　97
4.1　排序為什么重要　97
4.2　預(yù)備知識　98
4.3　插入排序及其他簡單排序算法的分析　98
4.4　謝爾排序　101
4.5　歸并排序　103
4.5.1　有序數(shù)組的線性時間合并　103
4.5.2　歸并排序算法　105
4.6　快速排序　106
4.6.1　快速排序算法　107
4.6.2　快速排序的分析　108
4.6.3　挑選中心點　111
4.6.4　一種劃分策略　112
4.6.5　鍵等于中心點　113
4.6.6　三個元素的中值劃分　114
4.6.7　小規(guī)模數(shù)組　114
4.6.8　Java快速排序程序　115
4.7　快速選擇　117
4.8　排序的下界　118
小結(jié)　119
關(guān)鍵概念　119
常見錯誤　120
網(wǎng)上資源　120
習(xí)題　120
參考文獻　123
第5章　隨機化　124
5.1　為什么需要隨機數(shù)　124
5.2　隨機數(shù)生成器　125
5.3　非均勻分布隨機數(shù)　129
5.4　產(chǎn)生隨機排列　130
5.5　隨機化算法　131
5.6　隨機化素數(shù)檢驗　133
小結(jié)　135
關(guān)鍵概念　135
常見錯誤　136
網(wǎng)上資源　136
習(xí)題　136
參考文獻　138
第二部分　應(yīng)用
第6章　娛樂和游戲　140
6.1　單詞搜索迷宮　140
6.1.1　理論　140
6.1.2　Java實現(xiàn)　142
6.2　Tic-Tac-Toe游戲　146
6.2.1 α-β剪枝　146
6.2.2　置換表　148
6.2.3　計算機象棋　151
小結(jié)　152
關(guān)鍵概念　152
常見錯誤　152
網(wǎng)上資源　152
習(xí)題　153
參考文獻　154
第7章　棧和編譯器　155
7.1　平衡符號檢查器　155
7.1.1　基本算法　155
7.1.2　實現(xiàn)　156
7.2　簡單計算器　163
7.2.1　后綴機　164
7.2.2　中綴到后綴的轉(zhuǎn)化　165
7.2.3　實現(xiàn)　166
7.2.4　表達式樹　172
小結(jié)　173
關(guān)鍵概念　173
常見錯誤　174
網(wǎng)上資源　174
習(xí)題　174
參考文獻　175
第8章　實用程序　176
8.1　文件壓縮　176
8.1.1　前綴編碼　177
8.1.2　赫夫曼算法　178
8.1.3　實現(xiàn)　180
8.2　交叉引用生成器　191
8.2.1　基本思想　191
8.2.2　Java實現(xiàn)　191
小結(jié)　194
關(guān)鍵概念　194
常見錯誤　195
網(wǎng)上資源　195
習(xí)題　195
參考文獻　197
第9章　模擬　198
9.1　約瑟夫問題　198
9.1.1　簡單實現(xiàn)方案　199
9.1.2　更高效的算法　200
9.2　事件驅(qū)動模擬　202
9.2.1　基本思路　202
9.2.2　實例：調(diào)制解調(diào)器銀行的模擬　203
小結(jié)　209
關(guān)鍵概念　209
常見錯誤　209
網(wǎng)上資源　209
習(xí)題　209
第10章　圖和路徑　211
10.1　圖的定義　211
10.2　非加權(quán)的最短路徑問題　221
10.2.1　理論　221
10.2.2　Java實現(xiàn)　223
10.3　非負(fù)權(quán)值的最短路徑算法　224
10.3.1　理論：Dijkstra算法　224
10.3.2　Java實現(xiàn)　227
10.4　含負(fù)權(quán)值的最短路徑問題　228
10.4.1　理論　228
10.4.2　Java實現(xiàn)　229
10.5　無環(huán)圖的路徑問題　230
10.5.1　拓?fù)渑判颉?30
10.5.2　無環(huán)圖最短路徑算法的理論　232
10.5.3　Java實現(xiàn)　233
10.5.4　應(yīng)用：關(guān)鍵路徑分析　234
小結(jié)　236
關(guān)鍵概念　236
常見錯誤　237
網(wǎng)上資源　237
習(xí)題　238
參考文獻　240
第三部分　實現(xiàn)
第11章　內(nèi)部類和ArrayList的實現(xiàn)　242
11.1　迭代器與嵌套類　242
11.2　迭代器和內(nèi)部類　244
11.3　AbstractCollection類　246
11.4　StringBuilder　249
11.5　使用迭代器的ArrayList的實現(xiàn)　250
小結(jié)　254
關(guān)鍵概念　254
常見錯誤　254
網(wǎng)上資源　254
習(xí)題　255
第12章　棧和隊列　257
12.1　動態(tài)數(shù)組的實現(xiàn)　257
12.1.1　棧　257
12.1.2　隊列　260
12.2　鏈表實現(xiàn)　265
12.2.1　?！?65
12.2.2　隊列　267
12.3　兩種實現(xiàn)方式的比較　270
12.4　java.util.Stack類　270
12.5　雙向隊列　271
小結(jié)　271
關(guān)鍵概念　272
常見錯誤　272
網(wǎng)上資源　272
習(xí)題　272
第13章　鏈表　273
13.1　基本思想　273
13.1.1　頭結(jié)點　274
13.1.2　迭代器類　275
13.2　Java實現(xiàn)　276
13.3　雙向鏈表和循環(huán)鏈表　281
13.4　有序鏈表　283
13.5　集合類API中LinkedList類的實現(xiàn)　284
小結(jié)　292
關(guān)鍵概念　292
常見錯誤　293
網(wǎng)上資源　293
習(xí)題　293
第14章　樹　296
14.1　普通的樹　296
14.1.1　定義　296
14.1.2　實現(xiàn)　297
14.1.3　應(yīng)用：文件系統(tǒng)　298
14.2　二叉樹　301
14.3　遞歸和樹　306
14.4　樹的遍歷：迭代器類　307
14.4.1　后序遍歷　310
14.4.2　中序遍歷　313
14.4.3　前序遍歷　314
14.4.4　層次遍歷　316
小結(jié)　317
關(guān)鍵概念　317
常見錯誤　318
網(wǎng)上資源　318
習(xí)題　318
第15章　二叉查找樹　321
15.1　基本思想　321
15.1.1　操作　322
15.1.2　Java實現(xiàn)　323
15.2　順序統(tǒng)計量　329
15.3　二叉查找樹操作的分析　332
15.4　AVL樹　335
15.4.1　性質(zhì)　335
15.4.2　單旋轉(zhuǎn)　337
15.4.3　雙旋轉(zhuǎn)　339
15.4.4　AVL插入小結(jié)　341
15.5　紅黑樹　341
15.5.1　自下而上的插入　342
15.5.2　自上而下的紅黑樹　344
15.5.3　Java實現(xiàn)　345
15.5.4　自上而下的刪除　350
15.6　AA樹　352
15.6.1　插入　353
15.6.2　刪除　354
15.6.3　Java實現(xiàn)　355
15.7　集合類API中TreeSet類和TreeMap類的實現(xiàn)　358
15.8　B樹　371
小結(jié)　376
關(guān)鍵概念　376
常見錯誤　377
網(wǎng)上資源　377
習(xí)題　378
參考文獻　379
第16章　散列表　382
16.1　基本概念　382
16.2　散列函數(shù)　383
16.3　線性探測法　385
16.3.1　線性探測法的直觀分析　386
16.3.2　實際上所發(fā)生的：初始聚類　386
16.3.3　find操作的分析　387
16.4　二次探測法　388
16.4.1　Java實現(xiàn)　392
16.4.2　二次探測法的分析　398
16.5　分別鏈接散列　399
16.6　散列表與二叉查找樹　399
16.7　散列表的應(yīng)用　400
小結(jié)　400
關(guān)鍵概念　400
常見錯誤　401
網(wǎng)上資源　401
習(xí)題　401
參考文獻　403
第17章　優(yōu)先級隊列：二叉堆　404
17.1　基本概念　404
17.1.1　結(jié)構(gòu)性　405
17.1.2　堆的有序性　406
17.1.3　允許的操作　406
17.2　基本操作的實現(xiàn)　408
17.2.1　插入　408
17.2.2　deleteMin操作　410
17.3　buildHeap操作：線性時間的堆構(gòu)造　411
17.4　高級操作：decreaseKey和merge　414
17.5　內(nèi)排序：堆排序　414
17.6　外排序　416
17.6.1　為什么需要新的算法　417
17.6.2　外排序模型　417
17.6.3　簡單算法　417
17.6.4　多路歸并　418
17.6.5　多階段歸并　419
17.6.6　置換選擇法　420
小結(jié)　421
關(guān)鍵概念　422
常見錯誤　422
網(wǎng)上資源　422
習(xí)題　422
參考文獻　425
第四部分　高級數(shù)據(jù)結(jié)構(gòu)
第18章　伸展樹　428
18.1　自調(diào)整和均攤法的分析　428
18.1.1　均攤法時間限度　429
18.1.2　簡單的自調(diào)整策略(并不管用)　429
18.2　基本的自底向上的伸展樹　430
18.3　基本的伸展樹操作　432
18.4　自底向上伸展的分析　432
18.5　自頂向下的伸展樹　436
18.6　自頂向下伸展樹的實現(xiàn)　439
18.7　伸展樹與其他搜索樹的比較　442
小結(jié)　442
關(guān)鍵概念　443
常見錯誤　443
網(wǎng)上資源　443
習(xí)題　443
參考文獻　444
第19章　歸并優(yōu)先級隊列　445
19.1　斜堆　445
19.1.1　歸并是基本操作　445
19.1.2　滿足堆有序性的樹的簡化歸并　446
19.1.3　斜堆：一個簡單的修改　446
19.1.4　斜堆的分析　447
19.2　偶堆　448
19.2.1　偶堆操作　449
19.2.2　偶堆的實現(xiàn)　450
19.2.3　應(yīng)用：Dijkstra最短加權(quán)路徑算法　455
小結(jié)　457
關(guān)鍵概念　457
常見錯誤　457
網(wǎng)上資源　457
習(xí)題　457
參考文獻　458
第20章　不相交集類　459
20.1　等價關(guān)系　459
20.2　動態(tài)等價及應(yīng)用　459
20.2.1　應(yīng)用：生成迷宮　460
20.2.2　應(yīng)用：最小生成樹　462
20.2.3　應(yīng)用：最近的共同祖先問題　463
20.3　快速查找算法　466
20.4　快速并算法　466
20.4.1　智能并算法　468
20.4.2　路徑壓縮　469
20.5　Java實現(xiàn)　470
20.6　按秩并和路徑壓縮的最壞情況　471
小結(jié)　476
關(guān)鍵概念　477
常見錯誤　478
網(wǎng)上資源　478
習(xí)題　478
參考文獻　479
附錄A　運算符　481
附錄B　位運算符　482