數據結構與算法經典問題解析(原書第2版)（簡體書）

本書以簡明易懂的方式介紹了數據結構與算法的基本知識，內容全面、系統。描述方式基於C/C++語言，對數據結構中容易混淆的問題進行了透徹的闡述，對每一個問題均給出了不同的解決方案。涵蓋入職面試中常見的數據結構與算法方面的問題，既可以作為數據結構課程的教材，也可以作為研究生考試的參考以及程序員的參考手冊。

納拉辛哈‧卡魯曼希，CareerMonk創始人，亞馬遜印度公司資深軟件開發工程師。

譯者序
前言
第1章　緒論1
　1.1　變量1
　1.2　數據類型1
　1.3　數據結構2
　1.4　抽象數據類型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　漸近分析的準則9
　1.19　漸近符號的性質11
　1.20　常用的對數公式和求和公式11
　1.21　分治法的主定理11
　1.22　與分治法主定理相關的問題12
　1.23　減治遞推的主定理13
　1.24　減治主定理的另一種形式13
　1.25　猜測與確認的方法13
　1.26　平攤分析15
　1.27　關於算法分析的問題集15
第2章　遞歸與回溯28
　2.1　引言28
　2.2　什麼是遞歸28
　2.3　為什麼需要遞歸28
　2.4　遞歸函數的格式28
　2.5　遞歸與內存(圖形化演示)29
　2.6　遞歸與迭代30
　2.7　遞歸的要點30
　2.8　遞歸算法舉例30
　2.9　關於遞歸的問題集31
　2.10　什麼是回溯32
　2.11　回溯算法舉例32
　2.12　關於回溯的問題集32
第3章　鏈表35
　3.1　什麼是鏈表35
　3.2　鏈表的抽象數據類型35
　3.3　為什麼需要鏈表35
　3.4　數組回顧35
　3.5　鏈表與數組、動態數組的比較37
　3.6　單鏈表37
　3.7　雙鏈表43
　3.8　循環鏈表48
　3.9　一種存儲高效的雙鏈表54
　3.10　鬆散鏈表55
　3.11　跳表61
　3.12　關於鏈表的問題集64
第4章　棧87
　4.1　什麼是棧87
　4.2　如何使用棧87
　4.3　棧的抽象數據類型87
　4.4　棧的應用88
　4.5　棧的實現88
　4.6　棧實現的比較94
　4.7　關於棧的問題集94
第5章　隊列114
　5.1　什麼是隊列114
　5.2　如何使用隊列114
　5.3　隊列的抽象數據類型114
　5.4　操作異常115
　5.5　隊列的應用115
　5.6　隊列的實現115
　5.7　關於隊列的問題集121
第6章　樹127
　6.1　什麼是樹127
　6.2　相關術語127
　6.3　二叉樹128
　6.4　幾種特殊的二叉樹128
　6.5　二叉樹的性質129
　6.6　二叉樹的遍歷131
　6.7　一般的樹(N叉樹)153
　6.8　線索二叉樹的遍歷(與棧/隊列無關的遍歷)159
　6.9　表達樹166
　6.10　XOR樹168
　6.11　二叉搜索樹169
　6.12　平衡二叉搜索樹184
　6.13　AVL樹184
　6.14　其他形式的樹200
第7章　優先隊列和堆204
　7.1　什麼是優先隊列204
　7.2　優先隊列的抽象數據類型204
　7.3　優先隊列的應用205
　7.4　優先隊列的實現205
　7.5　堆和二項堆206
　7.6　二項堆207
　7.7　堆排序213
　7.8　關於優先隊列(堆)的問題集214
第8章　不相交集226
　8.1　引言226
　8.2　等價關係和等價類226
　8.3　不相交集的抽象數據類型227
　8.4　不相交集的應用227
　8.5　不相交集實現的折中方案227
　8.6　快速查找Fast FIND的實現(Quick FIND)227
　8.7　快速合併Fast UNION的實現(Quick UNION)228
　8.8　快速合併Fast UNION的實現(Slow FIND)228
　8.9　快速合併Fast UNION的實現(Quick FIND)231
　8.10　小結234
　8.11　關於不相交集的問題集234
第9章　圖算法235
　9.1　引言235
　9.2　相關術語235
　9.3　圖的應用238
　9.4　圖的表示238
　9.5　圖的遍歷242
　9.6　拓撲排序249
　9.7　最短路徑算法250
　9.8　最小生成樹256
　9.9　關於圖算法的問題集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　計數排序293
　10.16　桶排序(或箱排序)293
　10.17　基數排序294
　10.18　拓撲排序295
　10.19　外部排序295
　10.20　關於排序的問題集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　關於搜索的問題集308
第12章　選擇算法(中位數)333
　12.1　什麼是選擇算法333
　12.2　基於排序的選擇333
　12.3　基於劃分的選擇算法333
　12.4　線性選擇算法――Median of Median算法333
　12.5　按序尋找第k小元素333
　12.6　關於選擇算法的問題集334
第13章　符號表343
　13.1　引言343
　13.2　什麼是符號表343
　13.3　符號表的實現343
　13.4　符號表實現的比較344
第14章　散列法346
　14.1　什麼是散列法346
　14.2　為什麼需要散列法346
　14.3　散列表的抽象數據類型346
　14.4　理解散列法346
　14.5　散列法的構成要素347
　14.