數(shù)據(jù)結(jié)構(gòu)教程（C語言版）
本書共8章：第1章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型等基本概念；第2章～第6章從抽象數(shù)據(jù)類型的角度出發(fā)，分別討論線性表、棧、隊(duì)列、字符串、二叉樹以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用；第7章和第8章討論查找和排序，除了介紹各種實(shí)現(xiàn)方法，還著重從時(shí)間上進(jìn)行定性或定量的分析和比較。
更多科學(xué)出版社服務(wù)，請掃碼獲取。
目錄
第1章 緒論 1
1.1 組織數(shù)據(jù)的方法——數(shù)據(jù)結(jié)構(gòu) 1
1.2 解決問題的方法——算法 2
1.3 衡量算法優(yōu)劣的方式——復(fù)雜度分析 5
本章小結(jié) 9
練習(xí)題 11
上機(jī)實(shí)驗(yàn)題 12
第2章 線性表 14
2.1 基本概念與運(yùn)算 14
2.1.1 線性表的定義 14
2.1.2 線性表的運(yùn)算 15
2.2 線性表的順序存儲方式 15
2.2.1 順序表的結(jié)構(gòu) 15
2.2.2 順序表的運(yùn)算 17
2.2.3 順序表的實(shí)現(xiàn) 20
2.3 線性表的鏈?zhǔn)酱鎯Ψ绞?24
2.3.1 單鏈表 24
2.3.2 循環(huán)鏈表 38
2.3.3 雙向鏈表 41
2.4 線性表的應(yīng)用 42
2.4.1 單鏈表的應(yīng)用：單鏈表歸并問題 42
2.4.2 循環(huán)鏈表的應(yīng)用：求解約瑟夫問題 44
本章小結(jié) 46
練習(xí)題 48
上機(jī)實(shí)驗(yàn)題 50
第3章 棧和隊(duì)列 52
3.1 棧 52
3.1.1 棧的定義 52
3.1.2 棧的表示和實(shí)現(xiàn) 52
3.1.3 棧的應(yīng)用——進(jìn)制轉(zhuǎn)換 56
3.2 遞歸 59
3.2.1 遞歸的定義 59
3.2.2 遞歸的調(diào)用 60
3.2.3 棧與遞歸 65
3.3 隊(duì)列 68
3.3.1 隊(duì)列的定義 68
3.3.2 隊(duì)列的表示和實(shí)現(xiàn) 69
3.3.3 隊(duì)列的應(yīng)用 74
本章小結(jié) 80
練習(xí)題 82
上機(jī)實(shí)驗(yàn)題 83
第4章 字符串匹配 86
4.1 概述 86
4.2 蠻力匹配 87
4.3 KMP 算法 88
本章小結(jié) 92
練習(xí)題 93
上機(jī)實(shí)驗(yàn)題 94
第5章 二叉樹 96
5.1 二叉樹的概念和性質(zhì) 96
5.1.1 樹的概念 96
5.1.2 二叉樹的概念 98
5.1.3 二叉樹的性質(zhì) 100
5.2 二叉樹的存儲結(jié)構(gòu) 101
5.2.1 順序存儲結(jié)構(gòu) 101
5.2.2 鏈?zhǔn)酱鎯Y(jié)構(gòu) 102
5.3 二叉樹的遍歷 104
5.3.1 二叉樹的遞歸遍歷 104
5.3.2 二叉樹的非遞歸遍歷 107
5.4 二叉樹的構(gòu)造 113
5.5 二叉樹遍歷的應(yīng)用 113
5.5.1 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 113
5.5.2 計(jì)算二叉樹的高度 114
5.5.3 二叉樹重構(gòu) 114
5.6 霍夫曼樹 115
5.6.1 路徑和路徑長度 115
5.6.2 結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度 115
5.6.3 霍夫曼樹定義 115
5.6.4 構(gòu)造霍夫曼樹 116
5.7 并查集 117
5.7.1 并查集的概念 117
5.7.2 并查集的操作 118
5.7.3 并查集的存儲結(jié)構(gòu)及實(shí)現(xiàn) 118
5.7.4 合并和查找的改進(jìn)——Quick Union/Find 119
本章小結(jié) 120
練習(xí)題 121
上機(jī)實(shí)驗(yàn)題 122
第6章 圖 124
6.1 圖的定義 124
6.1.1 基本定義 124
6.1.2 圖的頂點(diǎn)與邊間關(guān)系 127
6.1.3 連通圖 129
6.2 圖的存儲結(jié)構(gòu) 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 多源點(diǎn)之間的最短路徑 167
6.7 拓?fù)渑判?175
6.7.1 拓?fù)渑判蚪榻B 175
6.7.2 拓?fù)渑判蛩惴?176
本章小結(jié) 176
練習(xí)題 177
上機(jī)實(shí)驗(yàn)題 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 重構(gòu)) 200
7.5 哈希表 203
7.5.1 哈希表的定義 203
7.5.2 哈希函數(shù)的構(gòu)造方法 204
7.5.3 處理哈希沖突的方法 206
7.5.4 哈希表查找性能 208
本章小結(jié) 208
練習(xí)題 211
上機(jī)實(shí)驗(yàn)題 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
練習(xí)題 236
上機(jī)實(shí)驗(yàn)題 237
參考文獻(xiàn) 239
書單推薦
