第1章 數(shù)據(jù)結(jié)構(gòu)與算法概述 / 1
1.1 數(shù)據(jù)結(jié)構(gòu) / 1
1.1.1 什么是數(shù)據(jù)結(jié)構(gòu) / 1
1.1.2 數(shù)據(jù)結(jié)構(gòu)的分類 / 3
1.1.3 數(shù)據(jù)類型與抽象數(shù)據(jù)類型 / 6
1.2 算法 / 7
1.3 算法分析 / 9
1.3.1 算法的時(shí)間復(fù)雜度 / 10
1.3.2 算法的空間復(fù)雜度 / 13
1.4 本章習(xí)題 / 13

第2章 線性表 / 15
2.1 什么是線性表 / 15
2.2 順序表 / 16
2.2.1 順序表的定義 / 16
2.2.2 順序表的實(shí)現(xiàn) / 17
2.3 單鏈表 / 24
2.3.1 單鏈表的定義 / 24
2.3.2 單鏈表的實(shí)現(xiàn) / 25
2.4 雙向鏈表 / 34
2.4.1 雙向鏈表的定義 / 34
2.4.2 雙向鏈表的實(shí)現(xiàn) / 34
2.5 循環(huán)鏈表 / 38
2.5.1 循環(huán)鏈表的定義 / 38
2.5.2 循環(huán)鏈表的實(shí)現(xiàn) / 39
2.6 線性表的比較 / 42
2.6.1 順序表與鏈表的比較 / 42
2.6.2 鏈?zhǔn)酱鎯?chǔ)方式的比較 / 42
2.7 線性表的應(yīng)用 / 43
2.7.1 一元多項(xiàng)式的表示及相加 / 43
2.7.2 約瑟夫環(huán) / 47
2.8 本章實(shí)驗(yàn)：線性表初探 / 49
2.9 本章習(xí)題 / 50

第3章 棧與隊(duì)列 / 53
3.1 什么是棧 / 53
3.2 棧的實(shí)現(xiàn) / 54
3.2.1 順序棧存儲(chǔ)實(shí)現(xiàn) / 54
3.2.2 雙端棧存儲(chǔ)實(shí)現(xiàn) / 57
3.2.3 鏈棧存儲(chǔ)實(shí)現(xiàn) / 59
3.3 棧與遞歸 / 61
3.3.1 遞歸的概念 / 61
3.3.2 棧的應(yīng)用 / 63
3.4 什么是隊(duì)列 / 66
3.5 隊(duì)列的實(shí)現(xiàn) / 66
3.5.1 順序隊(duì)列的實(shí)現(xiàn) / 66
3.5.2 循環(huán)隊(duì)列的實(shí)現(xiàn) / 68
3.5.3 鏈?zhǔn)疥?duì)列的實(shí)現(xiàn) / 71
3.6 隊(duì)列的應(yīng)用 / 74
3.7 討論課：如何選擇合適的線性表解決實(shí)際問(wèn)題 / 75
3.8 本章實(shí)驗(yàn)：棧的定義與應(yīng)用 / 75
3.9 本章習(xí)題 / 76

第4章 串 / 78
4.1 什么是串 / 78
4.2 串的存儲(chǔ)結(jié)構(gòu) / 78
4.2.1 串的順序存儲(chǔ)實(shí)現(xiàn) / 78
4.2.2 串的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn) / 83
4.3 串的模式匹配算法 / 83
4.3.1 樸素的模式匹配算法 / 83
4.3.2 KMP算法 / 85
4.4 綜合實(shí)驗(yàn)：校友通訊錄—線性表的應(yīng)用 / 89
4.5 本章習(xí)題 / 90

第5章 數(shù)組與廣義表 / 92
5.1 數(shù)組 / 92
5.2 矩陣存儲(chǔ) / 93
5.2.1 特殊矩陣 / 93
5.2.2 稀疏矩陣 / 94
5.3 廣義表 / 100
5.3.1 廣義表的定義 / 100
5.3.2 廣義表的存儲(chǔ)結(jié)構(gòu) / 101
5.3.3 廣義表的遞歸運(yùn)算 / 102
5.4 本章習(xí)題 / 105

第6章 基于線性表的查找算法 / 107
6.1 查找概述 / 107
6.2 順序表查找法 / 108
6.3 折半查找法 / 108
6.4 索引順序查找法 / 111
6.5 本章實(shí)驗(yàn)：折半查找 / 113
6.6 本章習(xí)題 / 113

第7章 基于線性表的排序算法 / 115
7.1 排序的概念及分類 / 115
7.2 插入排序 / 116
7.2.1 直接插入排序 / 116
7.2.2 折半插入排序 / 119
7.2.3 希爾排序 / 119
7.3 交換排序 / 120
7.3.1 冒泡排序 / 121
7.3.2 快速排序 / 123
7.4 歸并排序 / 124
7.5 本章實(shí)驗(yàn)：冒泡排序改動(dòng)算法 / 126
7.6 本章習(xí)題 / 127

第8章 樹(shù) / 129
8.1 樹(shù) / 129
8.1.1 什么是樹(shù) / 129
8.1.2 樹(shù)的基本概念及常用術(shù)語(yǔ) / 130
8.2 樹(shù)的存儲(chǔ)結(jié)構(gòu) / 131
8.2.1 雙親表示法 / 131
8.2.2 孩子表示法 / 132
8.2.3 孩子兄弟表示法 / 132
8.3 二叉樹(shù) / 134
8.3.1 什么是二叉樹(shù) / 134
8.3.2 二叉樹(shù)的分類 / 134
8.3.3 二叉樹(shù)的性質(zhì) / 135
8.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) / 137
8.4.1 二叉樹(shù)的順序存儲(chǔ) / 137
8.4.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ) / 138
8.5 樹(shù)的遍歷與應(yīng)用 / 139
8.5.1 二叉樹(shù)的遍歷 / 139
8.5.2 二叉樹(shù)的應(yīng)用 / 143
8.5.3 樹(shù)的遍歷 / 147
8.6 樹(shù)的轉(zhuǎn)換、構(gòu)建與線索化 / 147
8.6.1 二叉樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換 / 147
8.6.2 二叉樹(shù)的構(gòu)建 / 150
8.6.3 線索化二叉樹(shù) / 153
8.7 哈夫曼樹(shù) / 155
8.7.1 什么是哈夫曼樹(shù) / 155
8.7.2 哈夫曼樹(shù)的構(gòu)造 / 155
8.7.3 哈夫曼編碼 / 156
8.7.4 哈夫曼樹(shù)的實(shí)現(xiàn) / 157
8.8 討論課：如何學(xué)習(xí)樹(shù) / 158
8.9 本章實(shí)驗(yàn)一：二叉樹(shù)的創(chuàng)建與遍歷 / 159
8.10 本章實(shí)驗(yàn)二：二叉樹(shù)的查找 / 159
8.11 綜合實(shí)驗(yàn)：校友通訊錄—樹(shù)的應(yīng)用 / 160
8.12 本章習(xí)題 / 161

第9章 基于樹(shù)的查找算法 / 164
9.1 二叉排序樹(shù) / 164
9.1.1 二叉排序樹(shù)的插入 / 164
9.1.2 二叉排序樹(shù)的刪除 / 168
9.1.3 二叉排序樹(shù)的查找 / 170
9.2 平衡二叉樹(shù) / 172
9.2.1 平衡二叉樹(shù)的定義 / 172
9.2.2 平衡二叉樹(shù)的平衡化旋轉(zhuǎn) / 173
9.3 B樹(shù) / 177
9.3.1 B樹(shù)的查找 / 178
9.3.2 B樹(shù)的插入 / 178
9.3.3 B+樹(shù)和B*樹(shù) / 179
9.4 本章習(xí)題 / 180

第10章 基于樹(shù)的排序算法 / 182
10.1 選擇排序 / 182
10.1.1 簡(jiǎn)單選擇排序 / 182
10.1.2 樹(shù)形選擇排序 / 183
10.2 堆排序 / 184
10.2.1 堆的定義 / 184
10.2.2 堆的存儲(chǔ) / 185
10.2.3 堆排序的思想 / 189
10.3 綜合比較 / 193
10.4 本章習(xí)題 / 194

第11章 圖 / 196
11.1 圖的基本概念 / 196
11.1.1 什么是圖 / 196
11.1.2 圖的基本術(shù)語(yǔ) / 196
11.2 圖的存儲(chǔ)結(jié)構(gòu) / 199
11.2.1 鄰接矩陣 / 200
11.2.2 鄰接表 / 202
11.2.3 十字鏈表 / 205
11.2.4 鄰接多重表 / 207
11.3 圖的遍歷 / 207
11.3.1 深度優(yōu)先遍歷 / 208
11.3.2 廣度優(yōu)先遍歷 / 212
11.4 圖的應(yīng)用 / 216
11.4.1 最小生成樹(shù) / 216
11.4.2 最短路徑 / 224
11.4.3 拓?fù)湫蛄?/ 235
11.4.4 關(guān)鍵路徑 / 239
11.5 討論課：圖是什么 / 245
11.6 本章實(shí)驗(yàn)一：圖的鄰接矩陣定義與創(chuàng)建 / 246
11.7 本章實(shí)驗(yàn)二：圖的鄰接表定義與創(chuàng)建 / 246
11.8 綜合實(shí)驗(yàn)：校友通訊錄—圖的應(yīng)用 / 247
11.9 本章習(xí)題 / 248

第12章 計(jì)算式查找法 / 251
12.1 什么是哈希表 / 251
12.2 哈希函數(shù)的構(gòu)造方法 / 252
12.3 處理沖突的方法 / 253
12.3.1 開(kāi)放定址法（再散列法） / 253
12.3.2 鏈地址法 / 255
12.3.3 再哈希法 / 256
12.3.4 建立公共溢出區(qū) / 256
12.4 哈希查找法 / 257
12.5 討論課：如何選擇合適的算法，達(dá)到性能的最優(yōu) / 259
12.6 綜合實(shí)驗(yàn)：校友通訊錄—算法的應(yīng)用 / 259
12.7 本章習(xí)題 / 260