數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問題解析（原書第2版）

譯者序

前言

第1章　緒論1

　1.1　變量1

　1.2　數(shù)據(jù)類型1

　1.3　數(shù)據(jù)結(jié)構(gòu)2

　1.4　抽象數(shù)據(jù)類型2

　1.5　什么是算法3

　1.6　為什么需要分析算法3

　1.7　算法分析的目的3

　1.8　什么是運行時間分析3

　1.9　如何比較算法4

　1.10　什么是增長率4

　1.11　常用的增長率4

　1.12　算法分析的類型5

　1.13　漸近符號5

　1.14　O符號6

　1.15　Ω符號7

　1.16　Θ符號8

　1.17　為什么稱為漸近分析9

　1.18　漸近分析的準(zhǔn)則9

　1.19　漸近符號的性質(zhì)11

　1.20　常用的對數(shù)公式和求和公式11

　1.21　分治法的主定理11

　1.22　與分治法主定理相關(guān)的問題12

　1.23　減治遞推的主定理13

　1.24　減治主定理的另一種形式13

　1.25　猜測與確認(rèn)的方法13

　1.26　平攤分析15

　1.27　關(guān)于算法分析的問題集15

第2章　遞歸與回溯28

　2.1　引言28

　2.2　什么是遞歸28

　2.3　為什么需要遞歸28

　2.4　遞歸函數(shù)的格式28

　2.5　遞歸與內(nèi)存(圖形化演示)29

　2.6　遞歸與迭代30

　2.7　遞歸的要點30

　2.8　遞歸算法舉例30

　2.9　關(guān)于遞歸的問題集31

　2.10　什么是回溯32

　2.11　回溯算法舉例32

　2.12　關(guān)于回溯的問題集32

第3章　鏈表35

　3.1　什么是鏈表35

　3.2　鏈表的抽象數(shù)據(jù)類型35

　3.3　為什么需要鏈表35

　3.4　數(shù)組回顧35

　3.5　鏈表與數(shù)組、動態(tài)數(shù)組的比較37

　3.6　單鏈表37

　3.7　雙鏈表43

　3.8　循環(huán)鏈表48

　3.9　一種存儲高效的雙鏈表54

　3.10　松散鏈表55

　3.11　跳表61

　3.12　關(guān)于鏈表的問題集64

第4章　棧87

　4.1　什么是棧87

　4.2　如何使用棧87

　4.3　棧的抽象數(shù)據(jù)類型87

　4.4　棧的應(yīng)用88

　4.5　棧的實現(xiàn)88

　4.6　棧實現(xiàn)的比較94

　4.7　關(guān)于棧的問題集94

第5章　隊列114

　5.1　什么是隊列114

　5.2　如何使用隊列114

　5.3　隊列的抽象數(shù)據(jù)類型114

　5.4　操作異常115

　5.5　隊列的應(yīng)用115

　5.6　隊列的實現(xiàn)115

　5.7　關(guān)于隊列的問題集121

第6章　樹127

　6.1　什么是樹127

　6.2　相關(guān)術(shù)語127

　6.3　二叉樹128

　6.4　幾種特殊的二叉樹128

　6.5　二叉樹的性質(zhì)129

　6.6　二叉樹的遍歷131

　6.7　一般的樹(N叉樹)153

　6.8　線索二叉樹的遍歷(與棧/隊列無關(guān)的遍歷)159

　6.9　表達(dá)樹166

　6.10　XOR樹168

　6.11　二叉搜索樹169

　6.12　平衡二叉搜索樹184

　6.13　AVL樹184

　6.14　其他形式的樹200

第7章　優(yōu)先隊列和堆204

　7.1　什么是優(yōu)先隊列204

　7.2　優(yōu)先隊列的抽象數(shù)據(jù)類型204

　7.3　優(yōu)先隊列的應(yīng)用205

　7.4　優(yōu)先隊列的實現(xiàn)205

　7.5　堆和二項堆206

　7.6　二項堆207

　7.7　堆排序213

　7.8　關(guān)于優(yōu)先隊列(堆)的問題集214

第8章　不相交集226

　8.1　引言226

　8.2　等價關(guān)系和等價類226

　8.3　不相交集的抽象數(shù)據(jù)類型227

　8.4　不相交集的應(yīng)用227

　8.5　不相交集實現(xiàn)的折中方案227

　8.6　快速查找Fast FIND的實現(xiàn)(Quick FIND)227

　8.7　快速合并Fast UNION的實現(xiàn)(Quick UNION)228

　8.8　快速合并Fast UNION的實現(xiàn)(Slow FIND)228

　8.9　快速合并Fast UNION的實現(xiàn)(Quick FIND)231

　8.10　小結(jié)234

　8.11　關(guān)于不相交集的問題集234

第9章　圖算法235

　9.1　引言235

　9.2　相關(guān)術(shù)語235

　9.3　圖的應(yīng)用238

　9.4　圖的表示238

　9.5　圖的遍歷242

　9.6　拓?fù)渑判?49

　9.7　最短路徑算法250

　9.8　最小生成樹256

　9.9　關(guān)于圖算法的問題集259

第10章　排序280

　10.1　什么是排序280

　10.2　為什么需要排序280

　10.3　排序算法的分類280

　10.4　其他分類方式281

　10.5　冒泡排序281

　10.6　選擇排序282

　10.7　插入排序283

　10.8　希爾排序285

　10.9　歸并排序287

　10.10　堆排序289

　10.11　快速排序289

　10.12　樹排序292

　10.13　排序算法的比較292

　10.14　線性排序算法292

　10.15　計數(shù)排序293

　10.16　桶排序(或箱排序)293

　10.17　基數(shù)排序294

　10.18　拓?fù)渑判?95

　10.19　外部排序295

　10.20　關(guān)于排序的問題集296

第11章　搜索306

　11.1　什么是搜索306

　11.2　為什么需要搜索306

　11.3　搜索的類型306

　11.4　無序線性搜索306

　11.5　排序/有序線性搜索307

　11.6　二分搜索307

　11.7　基本搜索算法的比較308

　11.8　符號表和散列308

　11.9　字符串搜索算法308

　11.10　關(guān)于搜索的問題集308

第12章　選擇算法(中位數(shù))333

　12.1　什么是選擇算法333

　12.2　基于排序的選擇333

　12.3　基于劃分的選擇算法333

　12.4　線性選擇算法——Median of Median算法333

　12.5　按序?qū)ふ业趉小元素333

　12.6　關(guān)于選擇算法的問題集334

第13章　符號表343

　13.1　引言343

　13.2　什么是符號表343

　13.3　符號表的實現(xiàn)343

　13.4　符號表實現(xiàn)的比較344

第14章　散列法346

　14.1　什么是散列法346

　14.2　為什么需要散列法346

　14.3　散列表的抽象數(shù)據(jù)類型346

　14.4　理解散列法346

　14.5　散列法的構(gòu)成要素347

......