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

納拉辛哈·卡魯曼希（Narasimha Karumanchi）在尼赫魯科技大學獲得計算機科學科技學士學位，在印度理工學院孟買分校獲得計算機科學科技碩士學位。他是亞馬遜印度公司的軟件開發工程師，之前曾就職於IBM和微軟公司。他善於用輕鬆、淺顯的方式編寫技術書籍，出版了多部著作，其作品在亞馬遜上深受好評，目前已被翻譯為中文、韓文和日文等。他在各種培訓中心和大學教授過數據結構和算法。

譯者序
前言
第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