本書以系統(tǒng)能力培養(yǎng)為宗旨，基于C語言，介紹了數(shù)據(jù)結(jié)構相關知識。本書各章均以實例引入，使學生理解不同數(shù)據(jù)結(jié)構應用于哪些場景。針對每種數(shù)據(jù)結(jié)構，均以理解和實現(xiàn)物理世界里各種聯(lián)系在信息世界中的邏輯表示和在計算機中實現(xiàn)數(shù)據(jù)結(jié)構的存儲和操作兩條主線進行講授。并配有大量的實踐練習和教學資源，適合作為高校數(shù)據(jù)結(jié)構課程的教材。
“數(shù)據(jù)結(jié)構”是計算機類專業(yè)的基礎課程，也是相關理工類專業(yè)的熱門選修課程。本書是為該課程編寫的教材，適合計算機類專業(yè)和相關理工類專業(yè)的本科生學習。
本書主要介紹如何合理地組織數(shù)據(jù)、有效地存儲和處理數(shù)據(jù)、正確地設計算法以及對算法的復雜度進行分析和評價。通過深入理解各種基本數(shù)據(jù)結(jié)構的邏輯關系、物理存儲和基本操作，初步建立數(shù)據(jù)結(jié)構設計、實現(xiàn)和運用的概念。同時，結(jié)合各種典型案例，討論不同數(shù)據(jù)結(jié)構的特點、適用范圍以及基本算法復雜度的分析方法，為后續(xù)的專業(yè)課程學習提供必要的基礎知識。
本書的學習目標如下。
目標1：掌握線性表、棧和隊列、數(shù)組和廣義表、樹和二叉樹、圖等各種基本數(shù)據(jù)結(jié)構的邏輯表達、物理存儲和基本操作；掌握查找、排序的經(jīng)典算法。
目標2：能夠針對具體應用問題，根據(jù)問題的約束條件分析各種可選方案在數(shù)據(jù)存儲、算法效率上的利弊，并選擇恰當?shù)臄?shù)據(jù)結(jié)構、存儲表示和與之對應的操作方法。
目標3：能夠結(jié)合具體應用案例，合理選擇和改進經(jīng)典的數(shù)據(jù)結(jié)構，使之針對具體應用能夠有效地存儲和處理數(shù)據(jù)，能夠在此基礎上正確地設計算法，并對算法進行有效的分析和評價。
本書共分為8章。第1章主要介紹數(shù)據(jù)結(jié)構相關的概念及術語，以及算法的定義、特性和算法設計的目標。第2～4章主要討論各種基本結(jié)構的抽象數(shù)據(jù)類型、順序和鏈式表示與實現(xiàn)，以及相關的應用。第5章和第6章在討論樹和圖的抽象數(shù)據(jù)類型、順序和鏈式表示與實現(xiàn)的基礎上，重點討論樹和圖的遍歷方法以及基于此的典型應用。第7章和第8章分別討論查找和排序的經(jīng)典算法與改進策略。
對于廣大讀者來說，學習數(shù)據(jù)結(jié)構課程的關鍵是把握兩條主線。
一條主線是如何理解和實現(xiàn)物理世界中的各種聯(lián)系在信息世界中的邏輯表示。物理世界中的萬般聯(lián)系都是形象而具體的，需要通過抽象建模抓住這些聯(lián)系的本質(zhì)，即線性、樹形或者圖狀結(jié)構，從而將其轉(zhuǎn)換為信息世界中的邏輯表示。例如：生活中的各種排隊可以抽象成線性結(jié)構中的隊列，家族譜可以映射為樹形結(jié)構，專業(yè)課程的先修/后修關系可以構成有向的圖結(jié)構。抽象建模與表示能力是工科類專業(yè)學生必須具備的基本能力。不論是不是計算機類專業(yè)的學生，在學習這門課程時，都必須牢牢把握這條主線。
另一條主線是如何在計算機中實現(xiàn)數(shù)據(jù)結(jié)構的存儲和操作。存儲的方式主要分為順序存儲和鏈式存儲兩大類�；静僮饕话惆ǔ跏蓟颁N毀操作、訪問型操作和加工型操作三大類。這三類操作在兩種不同存儲模式下的算法的效率是有差異的，需要進行比較分析，總結(jié)各自的優(yōu)勢和不足，從而針對具體的現(xiàn)實問題，選擇恰當?shù)拇鎯Ψ绞絹肀ＷC操作執(zhí)行的效率。在比較分析基礎上得到有效結(jié)論是這條主線中的能力訓練要求。
此外，算法設計與優(yōu)化也是值得關注的問題，本書中的查找和排序部分將展示算法設計與優(yōu)化的思路。例如，排序算法如何從時間復雜度O(n2)的經(jīng)典算法開始，通過對恰當結(jié)構的引入將算法時間復雜度降到O(nlogn)；查找算法如何從時間復雜度O(n)的窮舉算法開始，通過對數(shù)據(jù)的排序約束和樹形結(jié)構的引入，將時間復雜度降到O(logn)，甚至在一些特殊規(guī)則的約束下能夠接近O(1)。我們不僅要掌握經(jīng)典算法本身，更要關注算法優(yōu)化的策略和方向，以便在解決實際問題時能夠設計出高效的算法。
最后，從不同學習者的角度來討論一下如何學習本門課程。
對于計算機類專業(yè)的學生，本書所涉及的內(nèi)容均需掌握。在此基礎上，學生需要大量的訓練，以具備抽象建模能力，能夠就實際問題選擇或設計恰當?shù)臄?shù)據(jù)結(jié)構。此外，在編程實現(xiàn)過程中，能夠基于問題的約束，在比較、分析的基礎上選擇恰當?shù)拇鎯Ψ绞胶退惴ǖ膶崿F(xiàn)方式，能夠?qū)λ惴ǖ臅r間和空間復雜度進行合理的分析，能夠?qū)λ惴ǖ母倪M和優(yōu)化有恰當?shù)乃悸�，從而為實際問題提供高效的解決方案。
對于其他理工類專業(yè)的學生，希望通過本門課程的學習達成兩點目標：一是具備抽象建模能力，能夠?qū)ξ锢硎澜缰械膯栴}描述進行抽象建模，從而在信息世界里進行合理表達；二是具備算法選擇能力，能夠根據(jù)輸入數(shù)據(jù)的表現(xiàn)形式、數(shù)據(jù)結(jié)構的存儲方式和基于此的算法效率特征，選擇相應的數(shù)據(jù)結(jié)構和算法來高效地解決實際問題。
本書在構思和準備過程中參考了國內(nèi)外相關的數(shù)據(jù)結(jié)構教材，特別是嚴蔚敏、殷人昆、陳越、鄧俊輝等老師編寫的教材，這些經(jīng)典教材的內(nèi)容、寫法給了作者很多啟發(fā)。在本書的編寫過程中，南京航空航天大學的秦小麟老師給予了很多指導意見。在此一并向這些老師表示感謝。本書第1～3章由孫涵編寫，第4章和第8章由高航老師編寫，第5～7章由黃元元老師編寫，全書由孫涵負責統(tǒng)稿和審定。
盡管本書是作者多年教學經(jīng)驗的總結(jié)，但限于作者的學識，書中難免有疏漏與不足之處，敬請各位同行與讀者批評指正，以利于我們不斷提升教學水平、豐富課程內(nèi)容。
孫涵
南京航空航天大學計算機科學與技術學院
2019年12月
前言
第1章 概論 1
1.1 引言 1
1.2 數(shù)據(jù)結(jié)構相關概念及術語 1
1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn) 3
1.4 算法與算法分析 6
1.4.1 算法 6
1.4.2 算法分析與度量 8
1.5 小結(jié) 10
1.6 練習 10
第2章 線性表 11
2.1 引言 11
2.2 線性表的抽象數(shù)據(jù)類型 11
2.3 線性表的順序表示與實現(xiàn) 15
2.3.1 順序表的定義和特點 15
2.3.2 順序表的存儲結(jié)構 15
2.3.3 順序表基本操作的實現(xiàn)與性能分析 16
2.4 線性表的鏈式表示與實現(xiàn) 19
2.4.1 單鏈表 20
2.4.2 其他形式的鏈表 24
2.5 線性表的應用舉例 27
2.6 小結(jié) 31
2.7 練習 31
第3章 棧和隊列 32
3.1 引言 32
3.2 棧的抽象數(shù)據(jù)類型 32
3.3 棧的順序表示與實現(xiàn) 33
3.4 棧的鏈式表示與實現(xiàn) 36
3.5 棧的應用舉例 37
3.5.1 逆序輸出問題 37
3.5.2 最近匹配與比較問題 38
3.5.3 遞歸與回溯問題 43
3.6 隊列的抽象數(shù)據(jù)類型 47
3.7 隊列的順序表示與實現(xiàn) 48
3.8 隊列的鏈式表示與實現(xiàn) 50
3.9 隊列的應用舉例 52
3.10 小結(jié) 53
3.11 練習 53
第4章 數(shù)組、廣義表和字符串 54
4.1 引言 54
4.2 數(shù)組 54
4.2.1 一維數(shù)組 54
4.2.2 二維數(shù)組 55
4.3 特殊矩陣的壓縮存儲 56
4.3.1 對稱矩陣 56
4.3.2 對角矩陣 57
4.4 稀疏矩陣的壓縮存儲 57
4.4.1 稀疏矩陣的三元組表示 57
4.4.2 三元組的順序表表示 58
4.4.3 三元組的十字鏈表表示 61
4.5 廣義表 62
4.5.1 廣義表的概念 62
4.5.2 廣義表的抽象數(shù)據(jù)類型 63
4.5.3 廣義表的存儲結(jié)構 64
4.6 字符串 66
4.6.1 字符串的抽象數(shù)據(jù)類型 66
4.6.2 字符串的存儲結(jié)構與子串定位 67
4.7 小結(jié) 68
4.8 練習 68
第5章 樹和二叉樹 70
5.1 引言 70
5.2 樹的定義和基本術語 70
5.2.1 樹的定義 70
5.2.2 樹的邏輯表示 71
5.2.3 樹的基本術語 72
5.2.4 樹的抽象數(shù)據(jù)類型 72
5.3 二叉樹 73
5.3.1 二叉樹的定義 73
5.3.2 二叉樹的抽象數(shù)據(jù)類型 74
5.3.3 二叉樹的性質(zhì) 76
5.3.4 二叉樹的存儲結(jié)構 77
5.3.5 二叉樹的遍歷 79
5.3.6 二叉樹遍歷算法的
應用舉例 81
5.4 樹和森林 85
5.4.1 樹與二叉樹的轉(zhuǎn)換 85
5.4.2 森林與二叉樹的轉(zhuǎn)換 86
5.4.3 樹和森林的遍歷 87
5.5 霍夫曼樹 88
5.5.1 霍夫曼樹的定義 88
5.5.2 霍夫曼樹的構造 90
5.5.3 霍夫曼編碼 90
5.5.4 霍夫曼樹和霍夫曼編碼的算法實現(xiàn) 92
5.6 小結(jié) 94
5.7 練習 94
第6章 圖 95
6.1 引言 95
6.2 圖的定義、基本術語和抽象數(shù)據(jù)類型 95
6.3 圖的存儲方式 97
6.3.1 鄰接矩陣 97
6.3.2 鄰接表 99
6.4 圖的遍歷 101
6.4.1 深度優(yōu)先遍歷 101
6.4.2 廣度優(yōu)先遍歷 102
6.4.3 圖的遍歷算法的應用舉例 103
6.5 最小生成樹 107
6.5.1 最小生成樹的定義 107
6.5.2 普里姆算法 108
6.5.3 克魯斯卡爾算法 111
6.6 拓撲排序與關鍵路徑 112
6.6.1 拓撲排序 112
6.6.2 AOE網(wǎng)與關鍵路徑 113
6.7 最短路徑問題 116
6.7.1 單源最短路徑問題 116
6.7.2 所有頂點對之間的最短路徑 119
6.8 小結(jié) 121
6.9 練習 122
第7章 查找 123
7.1 引言 123
7.2 查找表的定義與抽象數(shù)據(jù)類型 123
7.3 順序表的靜態(tài)查找 124
7.3.1 順序查找 125
7.3.2 折半查找 126
7.3.3 索引查找 129
7.4 樹表的動態(tài)查找 130
7.4.1 二叉排序樹 130
7.4.2 平衡二叉排序樹 138
7.4.3 B-樹 141
7.4.4 B+樹 146
7.5 哈希表的查找 147
7.5.1 哈希表的定義 147
7.5.2 哈希函數(shù)的構造方法 148
7.5.3 處理沖突的方式 150
7.5.4 哈希表的查找 152
7.5.5 性能分析 153
7.6 小結(jié) 155
7.7 練習 156
第8章 排序 157
8.1 引言 157
8.2 排序的定義與分類 157
8.2.1 排序的定義 157
8.2.2 排序的分類 157
8.2.3 排序的數(shù)據(jù)類型 158
8.3 插入排序 158
8.3.1 直接插入排序 158
8.3.2 希爾排序 160
8.4 交換排序 162
8.4.1 簡單交換排序 162
8.4.2 快速排序 164
8.5 選擇排序 166
8.5.1 簡單選擇排序 167
8.5.2 樹形選擇排序 168
8.5.3 堆排序 169
8.6 歸并排序 173
8.7 基數(shù)排序 175
8.7.1 多關鍵字的排序 175
8.7.2 基數(shù)排序的實現(xiàn) 176
8.8 各種內(nèi)部排序方法的比較 178
8.9 小結(jié) 179
8.10 練習 179
書單推薦
