趣學數據結構

陳小玉
南陽理工學院副教授，高級程序員，
研究方向為智能計算、數據挖掘與機器學習，主要講授“算法設計與分析”和“人工智能”等課程，
多次指導學生獲得ACM程序設計大賽亞洲區獎項。

第1章數據結構入門1 
1.1數據結構基礎知識2 
1.2算法複雜度10 
1.3一棋盤麥子17 
1.4神奇魔鬼序列18 
1.5本章要點23 

第2章線性表24 
2.1順序表25 
2.1.1靜態分配25 
2.1. 2動態分配26 
2.1.3順序表的基本操作28 
2.2單鍊錶35 
2.2.1單鍊錶的存儲方式35 
2.2.2單鍊錶的基本操作37 
2.3雙向鍊錶48 
2.3.1雙向鍊錶的存儲方式48 
2.3. 2雙向鍊錶的基本操作48 
2.4循環鍊錶54 
2.5線性表的應用55 
2.5.1合併有序順序表55 
2.5.2合併有序鍊錶60 
2.5.3就地逆置單鍊錶64 
2.5.4查找鍊錶的中間節點68 
2.5.5刪除鍊錶中的重複元素71 
2.6線性表學習秘籍75 

第3章棧和隊列78 
3.1順序棧79 
3.2鏈棧83 
3.3順序隊列87 
3.3.1順序隊列的定義88
3.3.2循環隊列的定義92 
3.3.3循環隊列的基本操作96 
3.4鏈隊列98 
3.5棧和隊列的應用102 
3.5.1數制的轉換102 
3.5.2回文判定104 
3.5.3雙端隊列106 
3.6棧和隊列學習秘籍116 

第4章字符串121 
4.1字符串122 
4.2模式匹配BF算法124 
4.3模式匹配KMP算法128 
4.4改進的KMP算法133 
4.5字符串的應用——病毒檢測135 
4.6字符串學習秘籍137 

第5章數組與廣義表139 
5.1數組的順序存儲140 
5.2特殊矩陣的壓縮存儲143 
5.2.1對稱矩陣143 
5.2.2三角矩陣145 
5.2.3對角矩陣146 
5.2.4稀疏矩陣150 
5.3廣義表151 
5.4好玩貪吃蛇——數字矩陣151 
5.5數組與廣義表學習秘籍156 

第6章樹158 
6.1樹159 
6.1.1樹的定義159 
6.1.2樹的存儲結構162 
6.1.3樹、森林與二叉樹的轉換165 
6.2二叉樹167
6.2.1二叉樹的性質168 
6.2.2二叉樹的存儲結構173 
6.2.3二叉樹的創建175 
6.3二叉樹的遍歷183 
6.3.1先序遍歷183 
6.3.2中序遍歷186 
6.3.3後序遍歷188 
6.3. 4層次遍歷192 
6.4線索二叉樹196 
6.4.1線索二叉樹存儲結構196 
6.4.2構造線索二叉樹197 
6.4.3遍歷線索二叉樹201 
6.5樹和森林的遍歷204 
6.5.1樹的遍歷204 
6.5.2森林的遍歷209 
6.6樹的應用212 
6.6.1二叉樹的深度212 
6.6.2二叉樹的葉子數213 
6.6.3三元組創建二叉樹214 
6.6.4遍歷序列還原樹218 
6.6.5哈夫曼樹223 
6.7樹學習秘籍239 

第7章圖241 
7.1圖的基本術語242 
7.2圖的存儲結構249 
7.2.1鄰接矩陣250 
7.2.2鄰接表256 
7.2.3十字鍊錶266 
7.2.4鄰接多重表268 
7.3圖的遍歷270
7.3.1廣度優先搜索270 
7.3.2深度優先搜索275 
7.4圖的應用279 
7.4.1單源最短路徑——Dijkstra 279 
7.4.2各頂點之間最短路徑——Floyd 287 
7.4.3最小生成樹— —prim 293 
7.4.4最小生成樹——kruskal 305 
7.4.5拓撲排序308 
7.4.6關鍵路徑316 
7.5圖學習秘籍324 

第8章查找327 
8.1線性表查找328 
8.1.1順序查找328 
8.1.2折半查找330 
8.2樹表查找335 
8.2.1二叉查找樹335 
8.2.2平衡二叉查找樹346 
8.3散列表的查找361 
8.3.1散列函數361 
8.3.2處理衝突的方法364 
8.3.3散列查找及性能分析376 
8.4查找學習秘籍378 

第9章排序379 
9.1插入排序381 
9.1.1直接插入排序381 
9.1.2希爾排序387 
9.2交換排序389 
9.2.1冒泡排序389 
9.2.2快速排序392 
9.3選擇排序401
9.3.1簡單選擇排序401 
9.3.2堆排序403 
9.4合併排序412 
9.5分配排序417 
9.5.1桶排序417 
9.5.2基數排序418 
9.6排序學習秘籍421 

第10章高級數據結構425 
10.1並查集426 
10.2優先隊列430 
10.2.1出隊431 
10.2.2入隊433 
10.2.3構建初始堆435 
10.3 B-樹437 
10.3.1樹高與性能439 
10.3.2查找440 
10.3.3插入441 
10.3.4刪除444 
10.4 B+樹449 
10.4.1查找450 
10.4.2插入451 
10.4.3刪除454 
10.5紅黑樹457 
10.5.1紅黑樹的定義457 
10.5.2樹高與性能458 
10.5.3紅黑樹與4階B樹459 
10.5.4查找460 
10.5.5插入460 
10.5.6刪除466
10.6 高級數據結構學習秘籍476