內容簡介
本書主要包括數據結構的基本概念、基本的數據結構（線性表、棧和佇列、串、數組與廣義表、樹、圖）和基本技術（查找方法與排序方法）三個部分。本書除重點介紹了數據的組織技術外，還貫穿了程式設計中應掌握的技術，如參數傳遞技術、動態處理的指針技術、數組技術、遞歸技術與佇列技術等。另外，本書給出了許多經典的查找與排序算法，為讀者繼續拓展思路提供線索。
本書是在第一版的基礎上修訂而成的，內容豐富，概念清晰，技術實用，同時還配有大量的例題、習題和實習題。本書將讀者熟悉的標準C語言作為算法描述的語言，採用了面向對象的方法來講述數據結構中的技術，這種描述體系也是本書特色之一。
本書既可作為大專院校計算機等專業數據結構課程的教材，也可供從事計算機開發和套用的工程技術人員學習和參考。
需要本書所列結構定義函式原型定義及每章演示示例的讀者可通過西北大學校園網下載獲取。本書同時配有多媒體教學課件，可供教師助教使用，需要者可與作者聯繫。
★本書配有電子教案，需要的教師可與出版社聯繫，免費提供。
目錄
第1章 緒論 1
1.1 什麼是數據結構（定義） 1
1.2 數據結構的內容 9
1.3 算法 10
1.4 算法描述的工具 12
1.5 對算法作性能評價 16
1.6 關於數據結構的學習 20
習題 22
實習題 23
第2章 線性表 24
2.1 線性表的概念及運算 24
2.1.1 線性表的邏輯結構 24
2.1.2 線性表的抽象數據類型定義 25
2.2 線性表的順序存儲 26
2.2.1 線性表的順序存儲結構 26
2.2.2 線性表順序存儲結構上的基本運算 27
2.3 線性表的鏈式存儲 32
2.3.1 單鍊表 32
2.3.2 單鍊表上的基本運算 33
2.3.3 循環鍊表 40
2.3.4 雙向鍊表 42
*2.3.5 靜態鍊表 44
2.3.6 順序表和鍊表的比較 47
2.4 一元多項式的表示及相加 48
習題 52
實習題 54
第3章 限定性線性表——棧和佇列 55
3.1 棧 55
3.1.1 棧的定義 55
3.1.2 棧的表示和實現 56
3.1.3 棧的套用舉例 61
3.1.4 棧與遞歸的實現 67
3.2 佇列 73
3.2.1 佇列的定義 73
3.2.2 佇列的表示和實現 74
3.2.3 佇列的套用舉例 78
習題 80
實習題 82
第4章 串 83
4.1 串的定義 83
4.2 抽象數據類型串的實現 85
4.2.1 定長順序串 85
4.2.2 堆串 89
4.2.3 塊鏈串 94
4.3 串的套用舉例： 文本編輯 95
習題 96
實習題 97
第5章 數組和廣義表 98
5.1 數組的定義和運算 98
5.2 數組的順序存儲和實現 99
5.3 特殊矩陣的壓縮存儲 101
5.3.1 三角矩陣 102
5.3.2 帶狀矩陣 103
5.3.3 稀疏矩陣 104
5.4 廣義表 113
習題 117
實習題 118
第6章 樹和二叉樹 119
6.1 樹的概念與定義 119
6.2 二叉樹 121
6.2.1 二叉樹的定義與基本操作 121
6.2.2 二叉樹的性質 122
6.2.3 二叉樹的存儲結構 124
6.3 二叉樹的遍歷與線索化 126
6.3.1 二叉樹的遍歷 126
6.3.2 基於棧的遞歸消除 129
6.3.3 遍歷算法套用 132
6.3.4 線索二叉樹 137
6.4 樹、 森林和二叉樹的關係 141
6.4.1 樹的存儲結構 141
6.4.2 樹、 森林與二叉樹的相互轉換 143
6.4.3 樹與森林的遍歷 146
6.5 哈夫曼樹及其套用 147
6.5.1 哈夫曼樹 147
6.5.2 哈夫曼編碼 149
6.5.3 哈夫曼編碼算法的實現 152
習題 153
實習題 155
第7章 圖 156
7.1 圖的定義與基本術語 156
7.1.1 圖的定義 156
7.1.2 基本術語 158
7.2 圖的存儲結構 160
7.2.1 鄰接矩陣表示法 160
7.2.2 鄰接表表示法 163
7.2.3 十字鍊表 165
7.2.4 鄰接多重表 167
7.3 圖的遍歷 168
7.3.1 深度優先搜尋 169
7.3.2 廣度優先搜尋 172
7.4 圖的連通性問題 174
7.4.1 無向圖的連通分量 174
7.4.2 最小生成樹 175
7.5 有向無環圖的套用 179
7.5.1 拓撲排序 179
7.5.2 關鍵路徑 182
7.6 最短路徑 187
7.6.1 求某一頂點到其它各頂點的最短路徑 188
7.6.2 求任意一對頂點間的最短路徑 190
習題 192
實習題 195
第8章 查找 196
8.1 查找的基本概念 196
8.2 基於線性表的查找法 197
8.2.1 順序查找法 197
8.2.2 折半查找法 198
8.2.3 分塊查找法 200
8.3 基於樹的查找法 201
8.3.1 二叉排序樹 201
8.3.2 平衡二叉排序樹 207
8.3.3 B-樹 215
8.4 計算式查找法——哈希法 224
8.4.1 哈希函式的構造方法 224
8.4.2 處理衝突的方法 226
8.4.3 哈希表的查找過程 228
8.4.4 哈希法性能分析 229
習題 231
實習題 232
第9章 內部排序 234
9.1 排序的基本概念 234
9.2 插入類排序 235
9.2.1 直接插入排序 235
9.2.2 折半插入排序 237
9.2.3 表插入排序 238
9.2.4 希爾排序 239
9.3 交換類排序法 241
9.3.1 冒泡排序（相鄰比序法） 241
9.3.2 快速排序 243
9.4 選擇類排序法 246
9.4.1 簡單選擇排序 246
9.4.2 樹形選擇排序 247
9.4.3 堆排序 248
9.5 歸併排序 253
9.6 分配類排序 255
9.6.1 多關鍵字排序 255
9.6.2 鏈式基數排序 255
9.6.3 基數排序的順序表結構 259
9.7 各種排序方法的綜合比較 259
習題 260
實習題 262
第10章 外部排序 263
10.1 外存信息的特性 263
10.1.1 磁帶存儲器 263
10.1.2 磁碟存儲器 264
10.2 外排序的基本方法 266
10.2.1 磁碟排序 266
10.2.2 磁帶排序 271
習題 274
附錄 數據結構試題選編 275
附錄A 樣卷一 275
附錄B 樣卷二 278
附錄C 樣卷三 282
附錄D 樣卷四 283
附錄E 樣卷五 285
附錄F 樣卷六 287
附錄G 樣卷七 290
參考文獻 293
