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

第一部分　算法和構件塊
第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
小結　20
關鍵概念　20
常見錯誤　21
網(wǎng)上資源　21
習題　21
參考文獻　26
第2章　集合類API　27
2.1　引言　27
2.2　迭代器模式　28
2.2.1　基本的迭代器設計　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　棧　44
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
小結　57
關鍵概念　57
常見錯誤　58
網(wǎng)上資源　58
習題　59
參考文獻　61
第3章　遞歸　62
3.1　什么是遞歸　62
3.2　背景：數(shù)學歸納法證明　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　樹的預習　70
3.3.6　其他實例　71
3.4　數(shù)值應用　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
小結　92
關鍵概念　92
常見錯誤　93
網(wǎng)上資源　93
習題　94
參考文獻　96
第4章　排序算法　97
4.1　排序為什么重要　97
4.2　預備知識　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
小結　119
關鍵概念　119
常見錯誤　120
網(wǎng)上資源　120
習題　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
小結　135
關鍵概念　135
常見錯誤　136
網(wǎng)上資源　136
習題　136
參考文獻　138
第二部分　應用
第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
小結　152
關鍵概念　152
常見錯誤　152
網(wǎng)上資源　152
習題　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　中綴到后綴的轉化　165
7.2.3　實現(xiàn)　166
7.2.4　表達式樹　172
小結　173
關鍵概念　173
常見錯誤　174
網(wǎng)上資源　174
習題　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
小結　194
關鍵概念　194
常見錯誤　195
網(wǎng)上資源　195
習題　195
參考文獻　197
第9章　模擬　198
9.1　約瑟夫問題　198
9.1.1　簡單實現(xiàn)方案　199
9.1.2　更高效的算法　200
9.2　事件驅動模擬　202
9.2.1　基本思路　202
9.2.2　實例：調制解調器銀行的模擬　203
小結　209
關鍵概念　209
常見錯誤　209
網(wǎng)上資源　209
習題　209
第10章　圖和路徑　211
10.1　圖的定義　211
10.2　非加權的最短路徑問題　221
10.2.1　理論　221
10.2.2　Java實現(xiàn)　223
10.3　非負權值的最短路徑算法　224
10.3.1　理論：Dijkstra算法　224
10.3.2　Java實現(xiàn)　227
10.4　含負權值的最短路徑問題　228
10.4.1　理論　228
10.4.2　Java實現(xiàn)　229
10.5　無環(huán)圖的路徑問題　230
10.5.1　拓撲排序　230
10.5.2　無環(huán)圖最短路徑算法的理論　232
10.5.3　Java實現(xiàn)　233
10.5.4　應用：關鍵路徑分析　234
小結　236
關鍵概念　236
常見錯誤　237
網(wǎng)上資源　237
習題　238
參考文獻　240
第三部分　實現(xiàn)
第11章　內部類和ArrayList的實現(xiàn)　242
11.1　迭代器與嵌套類　242
11.2　迭代器和內部類　244
11.3　AbstractCollection類　246
11.4　StringBuilder　249
11.5　使用迭代器的ArrayList的實現(xiàn)　250
小結　254
關鍵概念　254
常見錯誤　254
網(wǎng)上資源　254
習題　255
第12章　棧和隊列　257
12.1　動態(tài)數(shù)組的實現(xiàn)　257
12.1.1　?！?57
12.1.2　隊列　260
12.2　鏈表實現(xiàn)　265
12.2.1　棧　265
12.2.2　隊列　267
12.3　兩種實現(xiàn)方式的比較　270
12.4　java.util.Stack類　270
12.5　雙向隊列　271
小結　271
關鍵概念　272
常見錯誤　272
網(wǎng)上資源　272
習題　272
第13章　鏈表　273
13.1　基本思想　273
13.1.1　頭結點　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
小結　292
關鍵概念　292
常見錯誤　293
網(wǎng)上資源　293
習題　293
第14章　樹　296
14.1　普通的樹　296
14.1.1　定義　296
14.1.2　實現(xiàn)　297
14.1.3　應用：文件系統(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
小結　317
關鍵概念　317
常見錯誤　318
網(wǎng)上資源　318
習題　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　性質　335
15.4.2　單旋轉　337
15.4.3　雙旋轉　339
15.4.4　AVL插入小結　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
小結　376
關鍵概念　376
常見錯誤　377
網(wǎng)上資源　377
習題　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　散列表的應用　400
小結　400
關鍵概念　400
常見錯誤　401
網(wǎng)上資源　401
習題　401
參考文獻　403
第17章　優(yōu)先級隊列：二叉堆　404
17.1　基本概念　404
17.1.1　結構性　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操作：線性時間的堆構造　411
17.4　高級操作：decreaseKey和merge　414
17.5　內排序：堆排序　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
小結　421
關鍵概念　422
常見錯誤　422
網(wǎng)上資源　422
習題　422
參考文獻　425
第四部分　高級數(shù)據(jù)結構
第18章　伸展樹　428
18.1　自調整和均攤法的分析　428
18.1.1　均攤法時間限度　429
18.1.2　簡單的自調整策略(并不管用)　429
18.2　基本的自底向上的伸展樹　430
18.3　基本的伸展樹操作　432
18.4　自底向上伸展的分析　432
18.5　自頂向下的伸展樹　436
18.6　自頂向下伸展樹的實現(xiàn)　439
18.7　伸展樹與其他搜索樹的比較　442
小結　442
關鍵概念　443
常見錯誤　443
網(wǎng)上資源　443
習題　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　應用：Dijkstra最短加權路徑算法　455
小結　457
關鍵概念　457
常見錯誤　457
網(wǎng)上資源　457
習題　457
參考文獻　458
第20章　不相交集類　459
20.1　等價關系　459
20.2　動態(tài)等價及應用　459
20.2.1　應用：生成迷宮　460
20.2.2　應用：最小生成樹　462
20.2.3　應用：最近的共同祖先問題　463
20.3　快速查找算法　466
20.4　快速并算法　466
20.4.1　智能并算法　468
20.4.2　路徑壓縮　469
20.5　Java實現(xiàn)　470
20.6　按秩并和路徑壓縮的最壞情況　471
小結　476
關鍵概念　477
常見錯誤　478
網(wǎng)上資源　478
習題　478
參考文獻　479
附錄A　運算符　481
附錄B　位運算符　482