數(shù)據(jù)結(jié)構教程（C語言版）
本書共8章：第1章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構和抽象數(shù)據(jù)類型等基本概念；第2章～第6章從抽象數(shù)據(jù)類型的角度出發(fā)，分別討論線性表、棧、隊列、字符串、二叉樹以及圖等基本類型的數(shù)據(jù)結(jié)構及其應用；第7章和第8章討論查找和排序，除了介紹各種實現(xiàn)方法，還著重從時間上進行定性或定量的分析和比較。
更多科學出版社服務，請掃碼獲取。
目錄
第1章 緒論 1
1.1 組織數(shù)據(jù)的方法——數(shù)據(jù)結(jié)構 1
1.2 解決問題的方法——算法 2
1.3 衡量算法優(yōu)劣的方式——復雜度分析 5
本章小結(jié) 9
練習題 11
上機實驗題 12
第2章 線性表 14
2.1 基本概念與運算 14
2.1.1 線性表的定義 14
2.1.2 線性表的運算 15
2.2 線性表的順序存儲方式 15
2.2.1 順序表的結(jié)構 15
2.2.2 順序表的運算 17
2.2.3 順序表的實現(xiàn) 20
2.3 線性表的鏈式存儲方式 24
2.3.1 單鏈表 24
2.3.2 循環(huán)鏈表 38
2.3.3 雙向鏈表 41
2.4 線性表的應用 42
2.4.1 單鏈表的應用：單鏈表歸并問題 42
2.4.2 循環(huán)鏈表的應用：求解約瑟夫問題 44
本章小結(jié) 46
練習題 48
上機實驗題 50
第3章 棧和隊列 52
3.1 棧 52
3.1.1 棧的定義 52
3.1.2 棧的表示和實現(xiàn) 52
3.1.3 棧的應用——進制轉(zhuǎn)換 56
3.2 遞歸 59
3.2.1 遞歸的定義 59
3.2.2 遞歸的調(diào)用 60
3.2.3 棧與遞歸 65
3.3 隊列 68
3.3.1 隊列的定義 68
3.3.2 隊列的表示和實現(xiàn) 69
3.3.3 隊列的應用 74
本章小結(jié) 80
練習題 82
上機實驗題 83
第4章 字符串匹配 86
4.1 概述 86
4.2 蠻力匹配 87
4.3 KMP 算法 88
本章小結(jié) 92
練習題 93
上機實驗題 94
第5章 二叉樹 96
5.1 二叉樹的概念和性質(zhì) 96
5.1.1 樹的概念 96
5.1.2 二叉樹的概念 98
5.1.3 二叉樹的性質(zhì) 100
5.2 二叉樹的存儲結(jié)構 101
5.2.1 順序存儲結(jié)構 101
5.2.2 鏈式存儲結(jié)構 102
5.3 二叉樹的遍歷 104
5.3.1 二叉樹的遞歸遍歷 104
5.3.2 二叉樹的非遞歸遍歷 107
5.4 二叉樹的構造 113
5.5 二叉樹遍歷的應用 113
5.5.1 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 113
5.5.2 計算二叉樹的高度 114
5.5.3 二叉樹重構 114
5.6 霍夫曼樹 115
5.6.1 路徑和路徑長度 115
5.6.2 結(jié)點的權及帶權路徑長度 115
5.6.3 霍夫曼樹定義 115
5.6.4 構造霍夫曼樹 116
5.7 并查集 117
5.7.1 并查集的概念 117
5.7.2 并查集的操作 118
5.7.3 并查集的存儲結(jié)構及實現(xiàn) 118
5.7.4 合并和查找的改進——Quick Union/Find 119
本章小結(jié) 120
練習題 121
上機實驗題 122
第6章 圖 124
6.1 圖的定義 124
6.1.1 基本定義 124
6.1.2 圖的頂點與邊間關系 127
6.1.3 連通圖 129
6.2 圖的存儲結(jié)構 130
6.2.1 鄰接矩陣 130
6.2.2 鄰接表 132
6.3 圖的創(chuàng)建、輸出及刪除 134
6.3.1 創(chuàng)建圖 134
6.3.2 輸出圖 136
6.3.3 刪除圖 137
6.4 圖的遍歷 144
6.4.1 深度優(yōu)先遍歷 144
6.4.2 廣度優(yōu)先遍歷 145
6.5 最小生成樹 151
6.5.1 生成樹的概念 151
6.5.2 最小生成樹的概念 151
6.5.3 蠻力算法 152
6.5.4 普里姆(Prim)算法 152
6.5.5 克魯斯卡爾( Kruskal )算法 155
6.6 最短路徑 162
6.6.1 路徑的概念 163
6.6.2 單源最短路徑 163
6.6.3 多源點之間的最短路徑 167
6.7 拓撲排序 175
6.7.1 拓撲排序介紹 175
6.7.2 拓撲排序算法 176
本章小結(jié) 176
練習題 177
上機實驗題 178
第7章 查找 181
7.1 查找概述 181
7.2 線性表的查找 182
7.2.1 順序查找 182
7.2.2 折半查找 184
7.2.3 斐波那契查找 186
7.3 二叉排序樹 188
7.3.1 二叉排序樹的插入和創(chuàng)建 190
7.3.2 二叉排序樹的查找 191
7.3.3 二叉排序樹的刪除 191
7.4 平衡二叉樹 194
7.4.1 定義及性質(zhì) 194
7.4.2 插入操作 195
7.4.3 刪除操作 198
7.4.4 統(tǒng)一調(diào)整(3+4 重構) 200
7.5 哈希表 203
7.5.1 哈希表的定義 203
7.5.2 哈希函數(shù)的構造方法 204
7.5.3 處理哈希沖突的方法 206
7.5.4 哈希表查找性能 208
本章小結(jié) 208
練習題 211
上機實驗題 212
第8章 排序 213
8.1 冒泡排序 213
8.2 插入排序 215
8.3 選擇排序 217
8.4 歸并排序 219
8.5 快速排序 221
8.6 桶排序 226
8.7 基數(shù)排序 227
本章小結(jié) 235
練習題 236
上機實驗題 237
參考文獻 239
書單推薦
