數據結構（C語言版）（第2版）(2017年清華大學出版社出版的圖書)

成書過程

修訂過程

該教材是根據教育部《高等學校計算機科學與技術專業公共核心知識體系與課程》編寫的數據結構主教材。該教材的編寫得到清華大學2015年精品教材建設項目的資助。

該教材的初稿完成於2015年12月，作為另一本教材《數據結構精講與習題詳解（第2版）》的寫作參照，相互補充，首先完成了《數據結構精講與習題詳解（第2版）》，再回過頭來第二次修改該教材。

該教材修改部分包括：

在結構上從第1版的10章改為8章，雖然章數壓縮了，但敘述內容不減反增；增加的知識點大多作為“擴展閱讀”出現，它們不作為考核內容，主要是拓展視野；
各章的“想想看”改為“思考題”，目的是增加一些互動環節；這些思考題觸及的都是可聯想的內容，或者是對理解正文有用的知識“點撥”；
書中所有使用C語言書寫的算法，重新使用VC++6.0編譯程式調試過，有的還按照軟體工程的要求做了邊界值測試；因為書中算法的正確運行需要構建運行環境，所以對於書中所涉及的主要數據結構的存儲表示，絕大多數都在第2版給出了結構定義、初始化或創建算法、輸出算法等；
第3章增加了多棧共享同一存儲時的棧浮動技術、遞歸程式的非遞歸模擬方法、優先佇列的內容；第4章增加了w對角矩陣的壓縮存儲、稀疏矩陣的鍊表存儲、串的BM模式匹配算法的內容；第5章增加了等價類與並查集的內容；第6章增加了構造最小生成樹的破圈法、Dijkstra算法的內容；第7章增加了跳表、紅黑樹、伸展樹、字典樹的內容；此外對保留的內容有部分增刪；
附錄增加了辭彙索引，書中出現的重要概念都收錄在索引中。

出版工作

2017年5月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
龍啟銘、戰曉雷	常雪影	梁毅	楊艷

內容簡介

全書共8章。第1章介紹數據結構的地位和主要知識點，數據結構和算法的基本概念和算法分析的簡單方法，以及C語言編程的要點。第2～8章分別介紹了線性表、棧和佇列及其套用、多維數組、特殊矩陣、稀疏矩陣、字元串和廣義表、樹與二叉樹、圖、查找、排序，並做了適當延伸。此外，附錄還包含實訓作業要求與樣例（實訓作業要求和實訓作業樣例）、辭彙索引。

教材目錄

第1章緒論 11.1 數據結構的概念及分類 1
1.1.1 為什麼要學習數據結構 1
1.1.2 與數據結構相關的基本術語 2
1.1.3 數據結構的分類 5
1.1.4 數據結構的存儲結構 6
1.1.5 定義在數據結構上的操作 7
1.1.6 “好”數據結構 7
1.2 使用C語言描述數據結構 7
1.2.1 C語言的數據類型 8
1.2.2 算法的控制結構 9
1.2.3 算法的函式結構 10
1.2.4 動態存儲分配 12
1.2.5 邏輯和關係運算的約定 12
1.2.6 輸入與輸出 13
1.3 算法和算法設計 13
1.3.1 算法的定義和特性 13
1.3.2 算法的設計步驟 14
1.3.3 算法設計的基本方法 15
1.4 算法分析與度量 18
1.4.1 算法的評價標準 18
1.4.2 算法的時間和空間複雜度度量 18
1.4.3 算法的漸近分析 21
小結 24
習題 24
第2章線性表 27
2.1 線性表 27
2.1.1 線性表的定義和特點 27
2.1.2 線性表的主要操作 28
2.2 順序表 29
2.2.1 順序表的定義和特點 29
2.2.2 順序表的結構定義 30
2.2.3 順序表查找操作的實現 31
2.2.4 順序表插入和刪除操作的實現 32
2.2.5 順序表的套用：集合運算 34
2.3 單鍊表 35
2.3.1 單鍊表的定義和特點 35
2.3.2 單鍊表的結構定義 36
2.3.3 單鍊表中的插入與刪除 36
2.3.4 帶頭結點的單鍊表 40
2.3.5 單鍊表的遍歷與創建 42
2.3.6 單鍊表的套用：集合運算 44
2.3.7 循環鍊表 46
2.3.8 雙向鍊表 50
2.3.9 靜態鍊表 53
2.4 順序表與線性鍊表的比較 54
2.5 線性表的套用：一元多項式及其運算 56
2.5.1 一元多項式的表示 56
2.5.2 多項式的結構定義 57
2.5.3 多項式的加法 59
2.5.4 擴展閱讀：多項式的乘法 60
小結 62
習題 63
第3章棧和佇列 66
3.1 棧 66
3.1.1 棧的概念 66
3.1.2 順序棧 67
3.1.3 擴展閱讀：多棧處理 70
3.1.4 鏈式棧 73
3.1.5 擴展閱讀：棧的混洗 74
3.2 佇列 76
3.2.1 佇列的概念 76
3.2.2 循環佇列 76
3.2.3 鏈式佇列 80
3.3 棧的套用 82
3.3.1 數制轉換 82
3.3.2 括弧匹配 83
3.3.3 表達式的計算與優先權處理 84
3.3.4 棧與遞歸的實現 88
3.4 佇列的套用 91
3.5 在算法設計中使用遞歸 92
3.5.1 漢諾塔問題與分治法 92
3.5.2 直接把遞歸過程改為非遞歸過程 94
3.5.3 擴展閱讀：遞歸過程的非遞歸模擬算法 95
3.5.4 迷宮問題與回溯法 98
3.5.5 計算組合數與動態規劃 101
3.6 擴展閱讀：雙端佇列 102
3.6.1 雙端佇列的概念 102
3.6.2 輸入受限的雙端佇列 103
3.6.3 輸出受限的雙端佇列 104
3.6.4 雙端佇列的存儲表示 104
3.7 擴展閱讀：優先佇列 106
3.7.1 優先佇列的概念 106
3.7.2 優先佇列的實現 107
小結 108
習題 108
第4章數組、串和廣義表 112
4.1 數組 112
4.1.1 一維數組 112
4.1.2 多維數組 114
4.2 特殊矩陣的壓縮存儲 116
4.2.1 對稱矩陣的壓縮存儲 117
4.2.2 三對角矩陣的壓縮存儲 118
4.2.3 擴展閱讀：w對角矩陣的壓縮存儲 119
4.3 稀疏矩陣 120
4.3.1 稀疏矩陣的概念 120
4.3.2 稀疏矩陣的順序存儲表示 121
4.3.3 稀疏矩陣的鍊表表示 124
4.4 字元串 125
4.4.1 字元串的概念 126
4.4.2 字元串的初始化和賦值 126
4.4.3 自定義字元串的存儲表示 128
4.4.4 串的模式匹配 132
4.5 廣義表 140
4.5.1 廣義表的概念 140
4.5.2 廣義表的性質 141
4.5.3 廣義表的連結表示 141
4.5.4 擴展閱讀：三元多項式的表示 147
小結 148
習題 149
第5章樹與二叉樹 152
5.1 樹的基本概念 152
5.1.1 樹的定義和術語 152
5.1.2 樹的基本操作 154
5.2 二叉樹及其存儲表示 155
5.2.1 二叉樹的概念 155
5.2.2 二叉樹的性質 156
5.2.3 二叉樹的主要操作 158
5.2.4 二叉樹的順序存儲表示 159
5.2.5 二叉樹的鍊表存儲表示 160
5.3 二叉樹的遍歷 161
5.3.1 二叉樹遍歷的遞歸算法 162
5.3.2 遞歸遍歷算法的套用舉例 163
5.3.3 二叉樹遍歷的非遞歸算法 166
5.3.4 利用佇列實現二叉樹的層次序遍歷 169
5.3.5 非遞歸遍歷算法的套用舉例 170
5.3.6 二叉樹的計數 171
5.4 線索二叉樹 174
5.4.1 線索二叉樹的概念 174
5.4.2 線索二叉樹的種類 175
5.4.3 中序線索二叉樹的建立和遍歷 176
5.4.4 先序與後序線索二叉樹 178
5.5 樹與森林 180
5.5.1 樹的存儲表示 180
5.5.2 森林與二叉樹的轉換 184
5.5.3 樹與森林的深度優先遍歷 185
5.5.4 樹與森林的廣度優先遍歷 187

5.5.5 樹遍歷算法的套用舉例 188
5.6 Huffman樹 190
5.6.1 帶權路徑長度的概念 190
5.6.2 Huffman樹的概念 191
5.6.3 擴展閱讀：最優判定樹 194
5.6.4 Huffman編碼 196
5.7 堆 198
5.7.1 小根堆和大根堆 198
5.7.2 堆的建立 199
5.7.3 堆的插入 201
5.7.4 堆的刪除 202
5.8 等價類與並查集 202
5.8.1 等價關係與等價類 202
5.8.2 確定等價類的方法 203
5.8.3 並查集的定義及其實現 203
5.8.4 並查集操作的分析和改進 205
5.9 擴展閱讀：八皇后問題與樹的剪枝 207
5.9.1 八皇后問題的提出 207
5.9.2 八皇后問題的狀態樹 208
5.9.3 八皇后問題算法 210
小結 211
習題 212
第6章圖 216
6.1 圖的基本概念 216
6.1.1 與圖有關的若干概念 216
6.1.2 圖的基本操作 219
6.2 圖的存儲結構 221
6.2.1 圖的鄰接矩陣表示 221
6.2.2 圖的鄰接表表示 225
6.2.3 鄰接矩陣表示與鄰接表表示的比較 229
6.2.4 圖的鄰接多重表和十字鍊表表示 230
6.3 圖的遍歷 231
6.3.1 深度優先搜尋 232
6.3.2 廣度優先搜尋 234
6.3.3 連通分量 235
6.3.4 雙連通圖 237
6.3.5 有向圖的強連通分量 238
6.4 最小生成樹 240
6.4.1 最小生成樹求解和貪心法 240
6.4.2 Kruskal算法 242
6.4.3 Prim算法 244
6.4.4 擴展閱讀：其他建立最小生成樹的方法 246
6.5 最短路徑 248
6.5.1 非負權值的單源最短路徑 248
6.5.2 擴展閱讀：邊上權值為任意值的單源最短路徑問題 252
6.5.3 所有頂點之間的最短路徑 254
6.5.4 無權值的最短路徑 257
6.6 活動網路 259
6.6.1 AOV網路與拓撲排序 259
6.6.2 AOE網路與關鍵路徑法 262
小結 267
習題 268
第7章查找 273
7.1 查找的概念及簡單查找方法 273
7.1.1 查找的基本概念 273
7.1.2 順序查找法 274
7.1.3 折半查找法 276
7.1.4 擴展閱讀：次優查找樹 279
7.1.5 擴展閱讀：斐波那契查找和插值查找 282
7.1.6 擴展閱讀：跳表 283
7.2 二叉查找樹 284
7.2.1 二叉查找樹的概念 285
7.2.2 二叉查找樹的查找 285
7.2.3 二叉查找樹的插入 286
7.2.4 二叉查找樹的刪除 288
7.2.5 二叉查找樹的性能分析 289
7.3 AVL樹 292
7.3.1 AVL樹的概念 292
7.3.2 平衡化旋轉 293
7.3.3 AVL樹的插入 295
7.3.4 AVL樹的刪除 296
7.3.5 AVL樹的性能分析 299
7.4 B樹 300
7.4.1 索引順序表與分塊查找 300
7.4.2 多級索引結構與m叉查找樹 301
7.4.3 B樹的概念 302
7.4.4 B樹上的查找 304
7.4.5 B樹上的插入 305
7.4.6 B樹上的刪除 306
7.4.7 B+ 樹 308
7.5 擴展閱讀：其他查找樹 311
7.5.1 紅黑樹 311
7.5.2 伸展樹 313
7.5.3 字典樹 315
7.6 散列表及其查找 317
7.6.1 散列的概念 318
7.6.2 常見的散列函式 318
7.6.3 解決衝突的開地址法 321
7.6.4 解決衝突的鏈地址法 327
7.6.5 散列法分析 329
小結 330
習題 330
第8章排序 335
8.1 排序的概念 335
8.1.1 排序的相關概念 335
8.1.2 排序算法的性能分析 336
8.1.3 數據表的結構定義 337
8.2 插入排序 338
8.2.1 直接插入排序 338
8.2.2 基於靜態鍊表的直接插入排序 339
8.2.3 折半插入排序 341
8.2.4 希爾排序 342
8.3 交換排序 343
8.3.1 起泡排序 344
8.3.2 快速排序 345
8.3.3 快速排序的改進算法 348
8.4 選擇排序 350
8.4.1 簡單選擇排序 350
8.4.2 錦標賽排序 351
8.4.3 堆排序 352
8.5 歸併排序 356
8.5.1 二路歸併排序的設計思路 356
8.5.2 二路歸併排序的遞歸算法 356
8.5.3 擴展閱讀：基於鍊表的歸併排序算法 358
8.5.4 擴展閱讀：疊代的歸併排序算法 359
8.6 基數排序 361
8.6.1 基數排序 362
8.6.2 MSD基數排序 362
8.6.3 LSD基數排序 364
8.7 內排序算法的分析和比較 367
8.7.1 排序方法的下界 367
8.7.2 各種內排序方法的比較 368
8.8 外排序 371
8.8.1 常用的外存儲器與緩衝區 371
8.8.2 基於磁碟的外排序過程 372
8.8.3 m路平衡歸併的過程 374
8.8.4 初始歸併段的生成 378
8.8.5 最佳歸併樹 381
8.8.6 磁帶歸併排序 382
小結 385
習題 386
附錄A 實訓作業要求與樣例 391
A.1 實訓作業要求 391
A.2 實訓作業樣例 392
附錄B 辭彙索引 397
參考文獻 405

數據結構（C語言版）（第2版）(2017年清華大學出版社出版的圖書)

基本介紹

成書過程

修訂過程

出版工作

內容簡介

教材目錄

教學資源

教材特色

作者簡介

相關詞條

熱門詞條