內容簡介
本書第二版及其配套教材為普通高等教育“十一五”國家級規劃教材。本次修訂除保留上版中的經典數據結構知識外，還增加了伸展樹跳表等新內容。本書結構嚴謹，內容深入淺出，反映了抽象、封裝和信息隱蔽等現代軟體設計理念，重視算法的時間和空間分析，包括搜尋和排序時間的下界分析。本書使用C語言描述。
本書重視實踐性和程式設計。書中算法都有完整的C程式，程式代碼構思精巧、結構清晰、注釋詳細，所有程式都已在TC 2.01下編譯通過並能正確運行。這些程式既是學習數據結構和算法的很好示例，也是很好的C程式設計示例。本書最後一章是實習指導和實習題，指導學生按軟體工程學的方法設計算法、編寫程式和書寫文檔。本書配有大量的實例和圖示，並有豐富的習題和實習題，易教易學。本書涵蓋計算機學科專業考研大綱數據結構部分的考查內容。
本書可作為計算機類、電子信息類、電氣類、自動化類、電子商務、信息管理與信息系統等相關專業數據結構課程的教材和考研參考書，也可供從事計算機軟體和套用工作的工程技術人員參考。
本書與西安電子科技大學出版社出版的《〈數據結構——C語言描述〉學習指導和習題解析》一書配合使用，效果更佳。
目錄
第1章 概論 1
1.1 什麼是數據結構 1
1.1.1 基本概念 1
1.1.2 數據的邏輯結構 2
1.1.3 數據的存儲結構 3
1.1.4 數據結構的運算 4
1.2 數據抽象和抽象數據類型 5
1.2.1 抽象、數據抽象和過程抽象 5
1.2.2 封裝與信息隱蔽 5
1.2.3 數據類型和抽象數據類型 5
1.2.4 數據結構與抽象數據類型 6
1.3 描述數據結構 7
1.3.1 數據結構的規範 7
1.3.2 實現數據結構 7
1.4 算法和算法分析 9
1.4.1 算法及其性能標準 9
1.4.2 算法的時間複雜度 10
1.4.3 漸近時間複雜度 12
1.4.4 最壞、最好和平均情況時間複雜度 13
1.4.5 算法的空間複雜度 13
小結 13
習題1 14
第2章 數組和鍊表 16
2.1 結構與聯合 16
2.1.1 結構 16
2.1.2 聯合 17
2.2 數組 18
2.2.1 一維數組 18
2.2.2 二維數組 18
2.2.3 多維數組 20
2.3 鍊表 20
2.3.1 指針 20
2.3.2 單鍊表 24
2.3.3 帶表頭結點的單鍊表 30
2.3.4 循環鍊表 31
2.3.5 雙向鍊表 31
小結 33
習題2 33
第3章 堆疊和佇列 35
3.1 堆疊 35
3.1.1 堆疊ADT 35
3.1.2 堆疊的順序表示 36
3.1.3 堆疊的連結表示 38
3.2 佇列 39
3.2.1 佇列ADT 39
3.2.2 佇列的順序表示 40
3.2.3 佇列的連結表示 43
*3.3 表達式的計算 43
3.3.1 表達式 43
3.3.2 中綴表達式轉換為後綴表達式 44
3.3.3 計算後綴表達式的值 48
*3.4 遞歸和遞歸過程 50
3.4.1 遞歸的概念 50
3.4.2 遞歸的實現 51
*3.5 演示和測試 53
小結 55
習題3 55
第4章 線性表和數組ADT 57
4.1 線性表 57
4.1.1 線性表ADT 57
4.1.2 線性表的順序表示 58
4.1.3 線性表的連結表示 61
4.1.4 兩種存儲表示的比較 65
*4.2 多項式的算術運算 65
4.2.1 多項式ADT 65
4.2.2 多項式的連結表示 66
4.2.3 多項式的輸入和輸出 67
4.2.4 多項式相加 69
4.3 數組作為抽象數據類型 70
4.4 特殊矩陣 71
4.4.1 對稱矩陣 71
*4.4.2 帶狀矩陣 72
4.5 稀疏矩陣 73
4.5.1 稀疏矩陣ADT 73
4.5.2 稀疏矩陣的順序表示 74
4.5.3 稀疏矩陣轉置 75
*4.5.4 稀疏矩陣相乘 78
4.5.5 稀疏矩陣的正交鍊表表示 81
*4.5.6 建立正交鍊表 83
*4.5.7 列印正交鍊表 84
小結 85
習題4 85
第5章 字元串和廣義表 87
5.1 字元串 87
5.1.1 字元串ADT 87
5.1.2 字元串的存儲表示 88
5.1.3 簡單模式匹配算法 89
*5.1.4 模式匹配的KMP算法 92
*5.2 廣義表 96
5.2.1 廣義表的概念 96
5.2.2 廣義表ADT 97
5.2.3 廣義表的存儲表示 98
5.2.4 廣義表的算法 99
小結 100
習題5 100
第6章 樹 101
6.1 樹的基本概念 101
6.1.1 樹的定義 101
6.1.2 基本術語 102
6.2 二叉樹 103
6.2.1 二叉樹的定義和性質 103
6.2.2 二叉樹ADT 105
6.2.3 二叉樹的存儲表示 106
6.2.4 二叉樹的遍歷 109
*6.2.5 二叉樹遍歷的非遞歸算法 113
*6.2.6 二叉樹遍歷的套用實例 115
*6.2.7 線索二叉樹 117
6.3 樹和森林 121
6.3.1 森林與二叉樹的轉換 121
6.3.2 樹和森林的存儲表示 122
6.3.3 樹和森林的遍歷 124
*6.4 堆和優先權佇列 125
6.4.1 堆 125
6.4.2 優先權佇列 128
6.5 哈夫曼樹和哈夫曼編碼 131
6.5.1 樹的路徑長度 131
6.5.2 哈夫曼樹和哈夫曼算法 132
6.5.3 哈夫曼編碼 134
*6.6 並查集和等價關係 136
6.6.1 並查集 136
6.6.2 並查集的實現 136
6.6.3 集合按等價關係分組 139
小結 140
習題6 140
第7章 集合和搜尋 142
7.1 集合及其表示 142
7.1.1 集合和搜尋 142
7.1.2 集合ADT 143
7.1.3 集合的表示 144
7.2 順序搜尋 144
7.3 二分搜尋 146
7.3.1 對半搜尋 147
7.3.2 二叉判定樹 148
*7.3.3 斐波那契搜尋 150
7.3.4 插值搜尋 151
7.4 分塊搜尋 152
*7.5 搜尋算法的時間下界 153
小結 154
習題7 154
第8章 搜尋樹 155
8.1 二叉搜尋樹 155
8.1.1 二叉搜尋樹的定義 155
8.1.2 二叉搜尋樹的搜尋 155
8.1.3 二叉搜尋樹的插入 156
8.1.4 二叉搜尋樹的刪除 158
*8.1.5 二叉搜尋樹的高度 160
8.2 二叉平衡樹 161
8.2.1 二叉平衡樹的定義 161
8.2.2 二叉平衡樹的平衡旋轉 162
8.2.3 二叉平衡樹的插入 168
8.2.4 二叉平衡樹的刪除 171
8.2.5 二叉平衡樹的高度 174
8.3 B-樹 174
8.3.1 m叉搜尋樹 174
8.3.2 B-樹的定義 176
8.3.3 B-樹的高度 176
8.3.4 B-樹的搜尋 177
8.3.5 B-樹的插入 177
8.3.6 B-樹的刪除 180
*8.4 鍵樹 182
8.4.1 鍵樹的定義 182
8.4.2 雙鏈樹 183
8.4.3 Trie樹 184
*8.5 伸展樹 185
小結 187
習題8 188
第9章 跳表和散列表 189
9.1 字典 189
*9.2 跳表 189
9.2.1 什麼是跳表 190
9.2.2 跳表的搜尋 193
9.2.3 跳表的插入 194
9.2.4 跳表的刪除 195
9.3 散列表 196
9.3.1 散列技術 196
9.3.2 散列函式 197
9.3.3 解決衝突的拉鏈法 198
9.3.4 解決衝突的線性探查法 199
9.3.5 解決衝突的其他開地址法 203
9.3.6 性能分析 205
小結 206
習題9 206
第10章 圖 207
10.1 圖的基本概念 207
10.1.1 圖的定義與術語 207
10.1.2 圖ADT 209
10.2 圖的存儲結構 210
10.2.1 矩陣表示法 210
10.2.2 鄰接表表示法 214
*10.2.3 正交鍊表和多重表表示法 217
10.3 圖的遍歷 219
10.3.1 深度優先遍歷 219
10.3.2 寬度優先遍歷 221
10.4 拓撲排序和關鍵路徑 223
10.4.1 拓撲排序 223
*10.4.2 關鍵路徑 227
10.5 最小代價生成樹 230
10.5.1 普里姆算法 231
*10.5.2 克魯斯卡爾算法 232
*10.6 最短路徑 234
10.6.1 單源最短路徑 235
10.6.2 所有頂點之間的最短路徑 238
小結 240
習題10 241
第11章 內排序 243
11.1 排序的基本概念 243
11.2 插入排序 244
11.2.1 直接插入排序 244
*11.2.2 希爾排序 248
11.2.3 對半插入排序 249
11.3 交換排序 249
11.3.1 冒泡排序 250
11.3.2 快速排序 251
11.4 合併排序 256
11.4.1 兩路合併排序 256
11.4.2 合併排序的疊代算法 256
*11.4.3 鍊表上的合併排序 258
11.5 選擇排序 261
11.5.1 簡單選擇排序 262
*11.5.2 堆排序 263
*11.6 排序算法的時間下界 264
*11.7 基數排序 265
小結 269
習題11 269
第12章 檔案和外排序 271
*12.1 輔助存儲器簡介 271
12.1.1 主存儲器和輔助存儲器 271
12.1.2 磁碟存儲器 271
12.2 檔案 273
12.2.1 檔案的基本概念 273
12.2.2 檔案的組織方式 273
12.2.3 C語言檔案 277
12.3 檔案的索引結構 278
12.3.1 靜態索引結構 278
12.3.2 動態索引結構 279
*12.4 外排序 280
12.4.1 外排序的基本過程 280
12.4.2 初始遊程的生成 280
12.4.3 多路合併 282
12.4.4 最佳合併樹 284
小結 285
習題12 286
第13章 實習指導和實習題 287
13.1 實習目的和要求 287
13.1.1 實習目的 287
13.1.2 實習要求 287
13.2 實習步驟 288
13.3 實習報告 288
13.4 實習題 289
實習1 數組操作 289
實習2 鍊表操作 290
實習3 表達式計算 290
實習4 佇列運算和用戶界面設計 291
實習5 線性表運算及套用 291
實習6 一元多項式的相加和相乘 291
實習7 對稱矩陣的壓縮存儲 292
實習8 稀疏矩陣的三元組表 292
實習9 稀疏矩陣的正交鍊表 292
實習10 字元串運算和文本處理 293
實習11 二叉樹的基本運算和套用 293
實習12 哈夫曼編碼和解碼系統 294
實習13 B-樹檢索 294
實習14 散列表檢索 295
實習15 圖運算及其套用 295
實習16 內排序算法及其性能比較 296
實習17 外排序 296
13.5 實習報告範例 297
13.5.1 實習題：表達式計算 297
13.5.2 實習報告 297
13.6 上機考核 303
13.6.1 考核目的 303
13.6.2 考核目標 303
13.6.3 考核要求 303
13.6.4 軟體環境 303
13.6.5 考核方式 303
13.6.6 試題樣例 303
附錄A 軟體工程概述 305
附錄B 考研大綱和教材內容 312
附錄C 專用名詞中英文對照表 316
參考文獻 322
