本書介紹了數據結構的基本概念和基本算法。全書共分為10章，包括概論，線性表及其順序存儲，線性表的鏈式存儲，字符串、集合和特殊數組，遞歸，樹型結構，二叉樹，圖，檢索，排序等內容。
本書內容豐富，邏輯性強，文字清晰流暢，既注重理論知識，又強調工程實用。書中既體現了抽象數據類型的觀點，又對每個算法的具體實現給出了完整的C語言源代碼描述。本書配套資源豐富，包含代碼、PPT課件、教案、教學大綱、實驗詳細指導、習題答案及解析等教學資源，同時重點內容錄制了微課視頻，支持線上線下混合教學。
本書可作為高等院校計算機專業及相關專業本科生數據結構課程的教材，也可以作為從事計算機工程與應用的廣大讀者的參考書。
【內容特點】
（1）內容全面，結構合理：每章有本章小結、習題，配有整門課程微課教學視頻，設置實驗和課程設計。
（2）圖文并茂，案例豐富：大題量、案例多，貼近實際
【資源特點】配套PPT、程序源代碼、大綱、教案、試卷、實驗詳細指導等
【服務特點】作者提供QQ服務群等支持。
李云清， 教授，碩士研究生導師。江西省高等學校中、青年骨干教師，江西省教育廳認定的江西省高等學校首批首級優質精品課程《數據結構》課程負責人。獨立系統地為計算機本科專業的學生開設了《數據結構》、《程序設計方法學》、《高級程序設計語言》（如BASIC語言、PASCAL語言）、《程序設計選講》等專業課程。獨立系統地講授了《面向對象技術》和《軟件自動化》等計算機專業碩士研究生課程。為研究課程進修班和助教進修班講授《人工智能》、《面向對象技術》和《軟件自動化》等課程。（合作）主持完成教改項目1項，主持（完成）江西省教育廳科技項目2項，并且作為第二成員完成了3項國家級科研項目（1項國家863計劃，2項國家自然科學基金）和1項江西省跨世紀人才項目。另外，主持完成江西省教育廳省級教學研究項目1項，主持完成3項江西師大科研和教學研究課題。合編出版教材三部。 獲得省級優秀教學成果二等獎1次，三等獎2次。獲得校級優秀教學成果一等獎1次、二等獎1次，校首屆教師CAI課件大賽一等獎1次。
第 1 章 概論 ............................................... 1
1.1 數據結構的基本概念與術語 .................................. 1
1.1.1 數據結構的基本概念..................................................1
1.1.2 數據的邏輯結構.........................................................2
1.1.3 數據的存儲結構.........................................................3
1.1.4 數據的運算集合.........................................................5
1.2 數據類型和抽象數據類型..................................... 5
1.2.1 數據類型....................................................................6
1.2.2 抽象數據類型.............................................................6
1.2.3 抽象數據類型的描述和實現........................................7
1.3 算法和算法分析 ................................................ 8
1.3.1 算法的基本概念和基本特征........................................8
1.3.2 算法的時間復雜度和空間復雜度.................................8
本章小結 ................................................................ 9
習題.....................................................................10
第 2 章 線性表及其順序存儲.......................... 12
2.1 線性表...........................................................12
2.2 順序表 ..........................................................12
2.2.1 順序表的基本概念及描述 .........................................12
2.2.2 順序表的實現...........................................................13
2.3 棧 ................................................................17
2.3.1 棧的基本概念及描述 ................................................17
2.3.2 順序棧及其實現 .......................................................18
2.3.3 棧的應用之一括號匹配......................................20
2.3.4 棧的應用之二算術表達式求值 ...........................22
2.4 隊列 .............................................................26
2.4.1 隊列的基本概念及描述.............................................26
2.4.2 順序隊列及其實現....................................................27
2.4.3 順序循環隊列及其實現.............................................30
2.4.4 隊列的應用..............................................................31
本章小結 ...............................................................32
習題.....................................................................32
第 3 章 線性表的鏈式存儲 ............................ 34
3.1 鏈式存儲........................................................34
3.2 單鏈表 ..........................................................35
3.2.1 單鏈表的基本概念及描述 .........................................35
3.2.2 單鏈表的實現...........................................................36
3.3 帶頭節點的單鏈表 ........................................... 39
3.3.1 帶頭節點的單鏈表的基本概念及描述........................39
3.3.2 帶頭節點的單鏈表的實現 .........................................40
3.4 循環單鏈表.....................................................43
3.4.1 循環單鏈表的基本概念及描述..................................43
3.4.2 循環單鏈表的實現....................................................44
3.5 雙鏈表 ......................................................... 49
3.5.1 雙鏈表的基本概念及描述.........................................49
3.5.2 雙鏈表的實現...........................................................49
3.6 鏈式棧 ......................................................... 54
3.6.1 鏈式棧的基本概念及描述.........................................54
3.6.2 鏈式棧的實現...........................................................54
3.7 鏈式隊列........................................................57
3.7.1 鏈式隊列的基本概念及描述......................................57
3.7.2 鏈式隊列的實現 .......................................................57
本章小結 .............................................................. 60
習題.....................................................................61
第 4 章 字符串、集合和特殊數組.................... 63
4.1 字符串...........................................................63
4.1.1 字符串的基本概念....................................................63
4.1.2 字符串類的定義.......................................................64
4.1.3 字符串的存儲結構及其實現......................................65
4.2 字符串的模式匹配 ............................................71
4.2.1 樸素模式匹配算法....................................................71
4.2.2 快速模式匹配算法....................................................72
4.3 集合 .............................................................75
4.3.1 集合的定義和性質....................................................75
4.3.2 集合類的定義...........................................................76
4.3.3 集合的存儲結構及其實現.........................................76
4.4 數組 ............................................................ 84
4.4.1 數組和數組元素.......................................................84
4.4.2 數組類的定義...........................................................85
4.4.3 數組的順序存儲及其實現.........................................86
4.5 特殊矩陣....................................................... 89
4.5.1 對稱矩陣的壓縮存儲................................................89
2
4.5.2 三角矩陣的壓縮存儲................................................90
4.5.3 帶狀矩陣的壓縮存儲................................................92
4.6 稀疏矩陣....................................................... 93
4.6.1 稀疏矩陣類的定義....................................................93
4.6.2 稀疏矩陣的順序存儲及其實現..................................94
4.6.3 稀疏矩陣的鏈式存儲及其實現..................................96
本章小結 .............................................................100
習題...................................................................100
第 5 章 遞歸 ........................................... 102
5.1 遞歸的基本概念與遞歸程序設計 .........................102
5.2 遞歸程序執行過程的分析..................................104
5.3 遞歸程序到非遞歸程序的轉換 ............................106
5.3.1 簡單遞歸程序到非遞歸程序的轉換.........................107
5.3.2 復雜遞歸程序到非遞歸程序的轉換 .........................109
5.4 遞歸程序設計的應用實例.................................. 114
本章小結 ............................................................. 116
習題...................................................................116
第 6 章 樹狀結構...................................... 118
6.1 樹的基本概念 ................................................ 118
6.2 樹類的定義...................................................120
6.3 樹的存儲結構................................................120
6.3.1 雙親表示法............................................................120
6.3.2 孩子表示法............................................................121
6.3.3 孩子兄弟表示法.....................................................124
6.4 樹的遍歷......................................................125
6.5 樹的線性表示................................................128
6.5.1 樹的括號表示.........................................................128
6.5.2 樹的層號表示.........................................................130
6.6 并查集 ........................................................ 131
6.6.1 并查集的定義.........................................................131
6.6.2 并查集的構建.........................................................132
6.6.3 基于樹狀結構的并查集實現....................................132
本章小結 .............................................................137
習題...................................................................138
3
第 7 章 二叉樹 ........................................ 139
7.1 二叉樹的基本概念 ..........................................139
7.2 二叉樹的基本操作 .......................................... 141
7.3 二叉樹的存儲結構 .......................................... 141
7.3.1 順序存儲結構.........................................................142
7.3.2 鏈式存儲結構.........................................................143
7.4 二叉樹的遍歷................................................145
7.4.1 二叉樹遍歷的定義..................................................145
7.4.2 二叉樹遍歷的遞歸實現...........................................145
7.4.3 二叉樹遍歷的非遞歸實現.......................................147
7.5 二叉樹其他運算的實現.....................................150
7.6 線索二叉樹...................................................152
7.6.1 線索二叉樹的定義..................................................152
7.6.2 中序線索二叉樹的基本操作....................................153
7.6.3 中序線索二叉樹的存儲結構及其實現......................154
7.7 樹、森林和二叉樹的轉換..................................156
7.7.1 樹、森林到二叉樹的轉換.......................................156
7.7.2 二叉樹到樹、森林的轉換 .......................................157
本章小結 .............................................................158
習題...................................................................158
第 8 章 圖 .............................................. 160
8.1 圖的基本概念 ................................................160
8.2 圖的基本操作................................................163
8.3 圖的基本存儲結構 ..........................................164
8.3.1 鄰接矩陣及其實現..................................................164
8.3.2 鄰接表及其實現.....................................................167
8.3.3 鄰接多重表............................................................169
8.4 圖的遍歷......................................................170
8.4.1 深度優先遍歷 ........................................................170
8.4.2 廣度優先遍歷.........................................................172
8.5 生成樹與最小生成樹 .......................................173
8.5.1 最小生成樹的定義 .................................................175
8.5.2 最小生成樹的 Prim 算法 ........................................176
8.5.3 最小生成樹的 Kruskal 算法 ...................................179
8.6 最短路徑......................................................182
8.6.1 單源最短路徑 ........................................................182
4
8.6.2 所有頂點對的最短路徑...........................................185
8.7 拓撲排序......................................................188
8.8 關鍵路徑...................................................... 191
本章小結 .............................................................196
習題...................................................................196
第 9 章 查找 ........................................... 200
9.1 查找的基本概念 .............................................200
9.2 線性表的查找................................................201
9.2.1 順序查找................................................................201
9.2.2 二分查找................................................................203
9.2.3 分塊查找................................................................205
9.3 二叉排序樹...................................................207
9.4 豐滿樹和平衡樹 .............................................213
9.4.1 豐滿樹...................................................................214
9.4.2 平衡二叉排序樹.....................................................215
9.4.3 擴充二叉樹............................................................222
9.5 紅黑樹 ........................................................223
9.5.1 紅黑樹的定義.........................................................224
9.5.2 紅黑樹的插入.........................................................224
9.5.3 紅黑樹的刪除.........................................................227
9.6 最佳二叉排序樹和 Huffman 樹 .........................230
9.6.1 最佳二叉排序樹.....................................................230
9.6.2 Huffman 樹...........................................................235
9.7 B 樹 ...........................................................238
9.7.1 B-樹的定義 ...........................................................238
9.7.2 B-樹的基本操作 ....................................................239
9.7.3 B 樹 .....................................................................243
9.8 散列表查找...................................................245
9.8.1 散列存儲 ...............................................................245
9.8.2 散列函數的構造.....................................................246
9.8.3 沖突處理 ...............................................................247
本章小結 .............................................................251
習題...................................................................251
第 10 章 排序.......................................... 255
10.1 排序的基本概念 ...........................................255
5
10.2 插入排序....................................................256
10.2.1 直接插入排序 ......................................................256
10.2.2 二分法插入排序...................................................259
10.2.3 表插入排序..........................................................260
10.2.4 Shell 插入排序 ....................................................262
10.3 選擇排序....................................................263
10.3.1 直接選擇排序 ......................................................263
10.3.2 樹狀選擇排序 ......................................................265
10.3.3 堆排序.................................................................267
10.4 交換排序....................................................271
10.4.1 冒泡排序 .............................................................271
10.4.2 快速排序 .............................................................272
10.5 歸并排序....................................................274
10.6 基數排序....................................................278
10.6.1 多排序碼的排序...................................................278
10.6.2 靜態鏈式基數排序 ...............................................278
10.7 外部排序....................................................281
10.7.1 磁盤排序 .............................................................282
10.7.2 多路平衡歸并 ......................................................283
10.7.3 置換-選擇排序.....................................................285
10.7.4 最佳歸并樹..........................................................288
本章小結 .............................................................290
習題...................................................................291
附錄 1 基礎實驗 ...................................... 294
實驗 1 線性表的順序存儲實現 .................................294
實驗 2 不帶頭節點的單鏈表....................................297
實驗 3 帶頭節點的單鏈表.......................................301
實驗 4 棧與字符串 ...............................................303
實驗 5 遞歸........................................................306
實驗 6 樹...........................................................310
實驗 7 二叉樹.....................................................312
實驗 8 圖...........................................................315
實驗 9 查找........................................................317
實驗 10 排序 ......................................................318
附錄 2 綜合實驗
新書資訊