內容簡介
本書為普通高等教育“十一五”國家級規劃教材。
本書保留經典數據結構知識，並引入伸展樹和跳表等新內容，反映抽象、封裝和信息隱蔽等現代軟體設計理念，重視算法的時間和空間分析，包括搜尋和排序時間的下界分析。本書使用C語言描述，內容新舊取捨恰當，廣度和深度適中。
本書為普通高等教育“十一五”國家級規劃教材。
本書保留經典數據結構知識，並引入伸展樹和跳表等新內容，反映抽象、封裝和信息隱蔽等現代軟體設計理念，重視算法的時間和空間分析，包括搜尋和排序時間的下界分析。本書使用C語言描述，內容新舊取捨恰當，廣度和深度適中。
本書重視實踐性和程式設計。書中算法都有完整的C程式，程式代碼注釋詳細，結構清晰，構思精巧，所有程式都已在TC 2.01下編譯通過並能正確運行。這些程式既是學習數據結構和算法的很好示例，也是很好的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 實現數據結構 8
1.4 算法和算法分析 9
1.4.1 算法及其性能標準 9
1.4.2 算法的時間複雜度 10
1.4.3 漸近時間複雜度 12
1.4.4 最壞、最好和平均情況時間複雜度 13
1.4.5 算法的空間複雜度 13
小結 14
習題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 數組作為抽象數據類型 71
4.4 特殊矩陣 72
4.4.1 對稱矩陣 72
*4.4.2 帶狀矩陣 72
4.5 稀疏矩陣 74
4.5.1 稀疏矩陣ADT 74
4.5.2 稀疏矩陣的順序表示 74
4.5.3 稀疏矩陣轉置 76
*4.5.4 稀疏矩陣相乘 78
4.5.5 稀疏矩陣的正交鍊表表示 81
*4.5.6 建立正交鍊表 84
*4.5.7 列印正交鍊表 85
小結 86
習題4 86
第5章 字元串和廣義表 88
5.1 字元串 88
5.1.1 字元串ADT 88
5.1.2 字元串的存儲表示 89
5.1.3 簡單模式匹配算法 90
*5.1.4 模式匹配的KMP算法 93
*5.2 廣義表 97
5.2.1 廣義表的概念 97
5.2.2 廣義表ADT 98
5.2.3 廣義表的存儲表示 99
5.2.4 廣義表的算法 100
小結 101
習題5 101
第6章 樹 102
6.1 樹的基本概念 102
6.1.1 樹的定義 102
6.1.2 基本術語 103
6.2 二叉樹 104
6.2.1 二叉樹的定義和性質 104
6.2.2 二叉樹ADT 106
6.2.3 二叉樹的存儲表示 107
6.2.4 二叉樹的遍歷 111
*6.2.5 二叉樹遍歷的非遞歸算法 114
*6.2.6 二叉樹遍歷的套用實例 117
*6.2.7 線索二叉樹 119
6.3 樹和森林 122
6.3.1 森林與二叉樹的轉換 122
6.3.2 樹和森林的存儲表示 123
6.3.3 樹和森林的遍歷 125
*6.4 堆和優先權佇列 126
6.4.1 堆 127
6.4.2 優先權佇列 129
6.5 哈夫曼樹和哈夫曼編碼 132
6.5.1 樹的路徑長度 132
6.5.2 哈夫曼樹和哈夫曼算法 134
6.5.3 哈夫曼編碼 136
*6.6 並查集和等價關係 137
6.6.1 並查集 137
6.6.2 並查集的實現 138
6.6.3 集合按等價關係分組 141
小結 142
習題6 142
第7章 集合和搜尋 145
7.1 集合及其表示 145
7.1.1 集合和搜尋 145
7.1.2 集合ADT 146
7.1.3 集合的表示 147
7.2 順序搜尋 147
7.3 二分搜尋 149
7.3.1 對半搜尋 150
7.3.2 二叉判定樹 151
*7.3.3 斐波那契搜尋 153
*7.4 搜尋算法的時間下界 154
小結 155
習題7 156
第8章 搜尋樹 157
8.1 二叉搜尋樹 157
8.1.1 二叉搜尋樹的定義 157
8.1.2 二叉搜尋樹的搜尋 157
8.1.3 二叉搜尋樹的插入 158
8.1.4 二叉搜尋樹的刪除 160
*8.1.5 二叉搜尋樹的高度 162
8.2 二叉平衡樹 163
8.2.1 二叉平衡樹的定義 163
8.2.2 二叉平衡樹的平衡旋轉 164
8.2.3 二叉平衡樹的插入 170
8.2.4 二叉平衡樹的刪除 173
8.2.5 二叉平衡數的高度 176
8.3 B - 樹 176
8.3.1 m叉搜尋樹 176
8.3.2 B -樹的定義 178
8.3.3 B -樹的高度 179
8.3.4 B -樹的搜尋 179
8.3.5 B -樹的插入 179
8.3.6 B -樹的刪除 182
*8.4 鍵樹 184
8.4.1 鍵樹的定義 184
8.4.2 雙鏈樹 185
8.4.3 Trie樹 186
*8.5 伸展樹 187
小結 190
習題8 190
第9章 跳表和散列表 192
9.1 字典 192
*9.2 跳表 192
9.2.1 什麼是跳表 193
9.2.2 跳表的搜尋 196
9.2.3 跳表的插入 197
9.2.4 跳表的刪除 198
9.3 散列表 199
9.3.1 散列技術 199
9.3.2 散列函式 200
9.3.3 解決衝突的拉鏈法 202
9.3.4 解決衝突的線性探查法 203
9.3.5 解決衝突的其他開地址法 207
9.3.6 性能分析 209
小結 209
習題9 210
第10章 圖 211
10.1 圖的基本概念 211
10.1.1 圖的定義與術語 211
10.1.2 圖ADT 214
10.2 圖的存儲結構 215
10.2.1 矩陣表示法 215
10.2.2 鄰接表表示法 218
*10.2.3 多重表表示法 221
10.3 圖的遍歷 222
10.3.1 深度優先遍歷 222
10.3.2 寬度優先遍歷 224
10.4 拓撲排序和關鍵路徑 226
10.4.1 拓撲排序 226
*10.4.2 關鍵路徑 230
10.5 最小代價生成樹 233
10.5.1 普里姆算法 234
*10.5.2 克魯斯卡爾算法 235
*10.6 最短路徑 237
10.6.1 單源最短路徑 238
10.6.2 所有頂點之間的最短路徑 241
小結 244
習題10 244
第11章 內排序 247
11.1 排序的基本概念 247
11.2 插入排序 248
11.2.1 直接插入排序 248
11.2.2* 希爾排序 252
11.3 交換排序 253
11.3.1 冒泡排序 253
11.3.2 快速排序 255
11.4 合併排序 260
11.4.1 兩路合併排序 260
11.4.2 合併排序的疊代算法 260
*11.4.3 鍊表上的合併排序 262
11.5 選擇排序 265
11.5.1 簡單選擇排序 266
*11.5.2 堆排序 267
*11.6 排序算法的時間下界 268
*11.7 基數排序 269
小結 273
習題11 273
第12章 檔案和外排序 275
*12.1 輔助存儲器簡介 275
12.1.1 主存儲器和輔助存儲器 275
12.1.2 磁碟存儲器 275
12.2 檔案 277
12.2.1 檔案的基本概念 277
12.2.2 檔案的組織方式 277
12.2.3 C語言檔案 281
12.3 檔案的索引結構 282
12.3.1 靜態索引結構 282
12.3.2 動態索引結構 283
*12.4 外排序 283
12.4.1 外排序的基本過程 284
12.4.2 初始遊程的生成 284
12.4.3 多路合併 286
12.4.4 最佳合併樹 288
小結 289
習題12 290
第13章 實習指導和實習題 291
13.1 實習目的和要求 291
13.1.1 實習目的 291
13.1.2 實習要求 291
13.2 實習步驟 292
13.3 實習報告 292
13.4 實習題 293
實習1 數組操作 293
實習2 鍊表操作 294
實習3 表達式計算 294
實習4 佇列運算和用戶界面設計 295
實習5 線性表運算及套用 295
實習6 一元多項式的相加和相乘 295
實習7 對稱矩陣的壓縮存儲 296
實習8 稀疏矩陣的三元組表 296
實習9 稀疏矩陣的正交鍊表 296
實習10 字元串運算和文本處理 297
實習11 二叉樹的基本運算 297
實習12 哈夫曼編碼和解碼系統 298
實習13 B-樹檢索 298
實習14 散列表檢索 299
實習15 圖運算及其套用 299
實習16 內排序算法及其性能比較 300
實習17 外排序 300
13.5 實習報告範例 301
13.5.1 實習題：表達式計算 301
13.5.2 實習報告 301
附錄A 軟體工程概述 307
A.1 軟體開發方法 307
A.2 軟體文檔寫作 309
A.3 系統測試方法 310
附錄B 專用名詞中英文對照表 314
參考文獻 320
