算法（第4版）

目錄
第1章　 基礎(chǔ)　　1
1.1　基礎(chǔ)編程模型　　4
1.1.1　Java程序的基本結(jié)構(gòu)　　4
1.1.2　原始數(shù)據(jù)類(lèi)型與表達(dá)式　　6
1.1.3　 語(yǔ)句　　8
1.1.4　 簡(jiǎn)便記法　　9
1.1.5　 數(shù)組　　10
1.1.6　 靜態(tài)方法　　12
1.1.7　 API　　16
1.1.8　 字符串　　20
1.1.9　 輸入輸出　　21
1.1.10　 二分查找　　28
1.1.11　 展望　　30
1.2　 數(shù)據(jù)抽象　　38
1.2.1　 使用抽象數(shù)據(jù)類(lèi)型　　38
1.2.2　 抽象數(shù)據(jù)類(lèi)型舉例　　45
1.2.3　 抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)　　52
1.2.4　 更多抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)　　55
1.2.5　 數(shù)據(jù)類(lèi)型的設(shè)計(jì)　　60
1.3　 背包、隊(duì)列和棧　　74
1.3.1　 API　　74
1.3.2　 集合類(lèi)數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)　　81
1.3.3　 鏈表　　89
1.3.4　 綜述　　98
1.4　 算法分析　　108
1.4.1　 科學(xué)方法　　108
1.4.2　 觀察　　108
1.4.3　 數(shù)學(xué)模型　　112
1.4.4　 增長(zhǎng)數(shù)量級(jí)的分類(lèi)　　117
1.4.5　 設(shè)計(jì)更快的算法　　118
1.4.6　 倍率實(shí)驗(yàn)　　121
1.4.7　 注意事項(xiàng)　　123
1.4.8　 處理對(duì)于輸入的依賴(lài)　　124
1.4.9　 內(nèi)存　　126
1.4.10　 展望　　129
1.5　案例研究：union-find算法　　136
1.5.1　 動(dòng)態(tài)連通性　　136
1.5.2　 實(shí)現(xiàn)　　140
1.5.3　 展望　　148
第2章　 排序　　152
2.1　 初級(jí)排序算法　　153
2.1.1　 游戲規(guī)則　　153
2.1.2　 選擇排序　　155
2.1.3　 插入排序　　157
2.1.4　 排序算法的可視化　　159
2.1.5　 比較兩種排序算法　　159
2.1.6　 希爾排序　　162
2.2　 歸并排序　　170
2.2.1　 原地歸并的抽象方法　　170
2.2.2　 自頂向下的歸并排序　　171
2.2.3　 自底向上的歸并排序　　175
2.2.4　 排序算法的復(fù)雜度　　177
2.3　 快速排序　　182
2.3.1　 基本算法　　182
2.3.2　 性能特點(diǎn)　　185
2.3.3　 算法改進(jìn)　　187
2.4　 優(yōu)先隊(duì)列　　195
2.4.1　 API　　195
2.4.2　 初級(jí)實(shí)現(xiàn)　　197
2.4.3　 堆的定義　　198
2.4.4　 堆的算法　　199
2.4.5　 堆排序　　205
2.5　 應(yīng)用　　214
2.5.1　 將各種數(shù)據(jù)排序　　214
2.5.2　我應(yīng)該使用哪種排序算法　　218
2.5.3　 問(wèn)題的歸約　　219
2.5.4　 排序應(yīng)用一覽　　221
第3章　查找　　227
3.1　符號(hào)表　　228
3.1.1　API　　228
3.1.2　有序符號(hào)表　　230
3.1.3　用例舉例　　233
3.1.4　無(wú)序鏈表中的順序查找　　235
3.1.5　有序數(shù)組中的二分查找　　238
3.1.6　對(duì)二分查找的分析　　242
3.1.7　預(yù)覽　　244
3.2　二叉查找樹(shù)　　250
3.2.1　基本實(shí)現(xiàn)　　250
3.2.2　分析　　255
3.2.3　有序性相關(guān)的方法與刪除操作　　257
3.3　平衡查找樹(shù)　　269
3.3.1　2-3查找樹(shù)　　269
3.3.2　紅黑二叉查找樹(shù)　　275
3.3.3　實(shí)現(xiàn)　　280
3.3.4　刪除操作　　282
3.3.5　紅黑樹(shù)的性質(zhì)　　284
3.4　散列表　　293
3.4.1　散列函數(shù)　　293
3.4.2　基于拉鏈法的散列表　　297
3.4.3　基于線性探測(cè)法的散列表　　300
3.4.4　調(diào)整數(shù)組大小　　304
3.4.5　內(nèi)存使用　　306
3.5　應(yīng)用　　312
3.5.1　我應(yīng)該使用符號(hào)表的哪種實(shí)現(xiàn)　　312
3.5.2　集合的API　　313
3.5.3　字典類(lèi)用例　　315
3.5.4　索引類(lèi)用例　　318
3.5.5　稀疏向量　　322
第4章　 圖　　329
4.1　 無(wú)向圖　　331
4.1.1　 術(shù)語(yǔ)表　　331
4.1.2　 表示無(wú)向圖的數(shù)據(jù)類(lèi)型　　333
4.1.3　 深度優(yōu)先搜索　　338
4.1.4　 尋找路徑　　342
4.1.5　 廣度優(yōu)先搜索　　344
4.1.6　 連通分量　　349
4.1.7　 符號(hào)圖　　352
4.1.8　 總結(jié)　　358
4.2　 有向圖　　364
4.2.1　 術(shù)語(yǔ)　　364
4.2.2　 有向圖的數(shù)據(jù)類(lèi)型　　365
4.2.3　 有向圖中的可達(dá)性　　367
4.2.4　 環(huán)和有向無(wú)環(huán)圖　　369
4.2.5　 有向圖中的強(qiáng)連通性　　378
4.2.6　 總結(jié)　　385
4.3　 最小生成樹(shù)　　390
4.3.1　 原理　　391
4.3.2　 加權(quán)無(wú)向圖的數(shù)據(jù)類(lèi)型　　393
4.3.3　最小生成樹(shù)的API和測(cè)試用例　　396
4.3.4　 Prim算法　　398
4.3.5　Prim算法的即時(shí)實(shí)現(xiàn)　　401
4.3.6　 Kruskal算法　　404
4.3.7　 展望　　407
4.4　 最短路徑　　412
4.4.1　 最短路徑的性質(zhì)　　413
4.4.2　 加權(quán)有向圖的數(shù)據(jù)結(jié)構(gòu)　　414
4.4.3　最短路徑算法的理論基礎(chǔ)　　420
4.4.4　 Dijkstra算法　　421
4.4.5　無(wú)環(huán)加權(quán)有向圖中的最短路徑算法　　425
4.4.6　一般加權(quán)有向圖中的最短路徑問(wèn)題　　433
4.4.7　 展望　　445
第5章　 字符串　　451
5.1　 字符串排序　　455
5.1.1　 鍵索引計(jì)數(shù)法　　455
5.1.2　 低位優(yōu)先的字符串排序　　458
5.1.3　 高位優(yōu)先的字符串排序　　461
5.1.4　 三向字符串快速排序　　467
5.1.5　 字符串排序算法的選擇　　470
5.2　 單詞查找樹(shù)　　474
5.2.1　 單詞查找樹(shù)　　475
5.2.2　 單詞查找樹(shù)的性質(zhì)　　483
5.2.3　 三向單詞查找樹(shù)　　485
5.2.4　 三向單詞查找樹(shù)的性質(zhì)　　487
5.2.5　應(yīng)該使用字符串符號(hào)表的哪種實(shí)現(xiàn)　　489
5.3　 子字符串查找　　493
5.3.1　 歷史簡(jiǎn)介　　493
5.3.2　 暴力子字符串查找算法　　494
5.3.3　Knuth-Morris-Pratt子字符串查找算法　　496
5.3.4　Boyer-Moore字符串查找算法　　502
5.3.5　Rabin-Karp指紋字符串查找算法　　505
5.3.6　 總結(jié)　　509
5.4　 正則表達(dá)式　　514
5.4.1　使用正則表達(dá)式描述模式　　514
5.4.2　 縮略寫(xiě)法　　516
5.4.3　 正則表達(dá)式的實(shí)際應(yīng)用　　517
5.4.4　 非確定有限狀態(tài)自動(dòng)機(jī)　　518
5.4.5　 模擬NFA的運(yùn)行　　520
5.4.6　 構(gòu)造與正則表達(dá)式對(duì)應(yīng)的
5.5　 數(shù)據(jù)壓縮　　529