第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介 1
1.2 基本術(shù)語(yǔ) 4
1.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 8
1.4 算法及算法分析 10
1.4.1 算法 10
1.4.2 算法分析 15
1.5 數(shù)據(jù)結(jié)構(gòu)課程的地位 16
單元測(cè)試 17
習(xí)題 18
第2章 線性表 20
2.1 線性表的邏輯結(jié)構(gòu) 20
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 24
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 30
2.3.1 線性單鏈表 30
2.3.2 靜態(tài)單鏈表 38
2.3.3 循環(huán)鏈表 41
2.3.4 雙向鏈表 42
2.4 線性表的應(yīng)用 47
單元測(cè)試 56
習(xí)題 57
實(shí)驗(yàn) 58
第3章 棧和隊(duì)列 66
3.1 棧 66
3.1.1 棧的意義及抽象數(shù)據(jù)類型 66
3.1.2 棧操作的實(shí)現(xiàn) 67
3.2 隊(duì)列 72
3.2.1 隊(duì)列及其抽象數(shù)據(jù)類型 72
3.2.2 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 73
3.2.3 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)循環(huán)
隊(duì)列 74
3.3 棧和隊(duì)列的應(yīng)用 77
單元測(cè)試 99
習(xí)題 100
實(shí)驗(yàn) 101
第4章 串 107
4.1 串的基本概念和存儲(chǔ)結(jié)構(gòu) 107
4.1.1 串的基本概念 107
4.1.2 串的存儲(chǔ)結(jié)構(gòu) 109
4.2 串基本操作的實(shí)現(xiàn) 111
4.3 模式匹配 115
4.3.1 子串定位函數(shù) 115
4.3.2 模式匹配的一種改進(jìn)算法 116
4.4 串操作應(yīng)用 121
單元測(cè)試 125
習(xí)題 126
實(shí)驗(yàn) 127
第5章 數(shù)組 130
5.1 數(shù)組的定義和運(yùn)算 130
5.2 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 132
5.3 矩陣的壓縮存儲(chǔ) 134
5.3.1 特殊矩陣 134
5.3.2 稀疏矩陣 136
5.3.3 稀疏矩陣操作實(shí)例 139
單元測(cè)試 144
習(xí)題 144
實(shí)驗(yàn) 145
第6章 樹(shù)與二叉樹(shù) 149
6.1 樹(shù)的邏輯結(jié)構(gòu)和基本操作 149
6.2 二叉樹(shù) 152
6.2.1 二叉樹(shù)的定義及邏輯結(jié)構(gòu) 152
6.2.2 二叉樹(shù)的性質(zhì) 153
6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 155
6.3 遍歷二叉樹(shù)和線索二叉樹(shù) 157
6.3.1 遍歷二叉樹(shù) 157
6.3.2 線索二叉樹(shù) 166
6.4 樹(shù)和森林 168
6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) 168
6.4.2 森林與二叉樹(shù)的轉(zhuǎn)換 170
6.4.3 樹(shù)的遍歷 172
6.5 哈夫曼樹(shù)及其應(yīng)用 172
6.5.1 二叉樹(shù)(哈夫曼樹(shù)) 172
6.5.2 哈夫曼編碼 175
單元測(cè)試 179
習(xí)題 179
實(shí)驗(yàn) 181
第7章 圖 189
7.1 圖的定義與基本術(shù)語(yǔ) 189
7.1.1 圖的定義 189
7.1.2 圖的基本術(shù)語(yǔ) 190
7.2 圖的存儲(chǔ) 193
7.2.1 鄰接矩陣 193
7.2.2 鄰接表 196
7.2.3 十字鏈表 199
7.2.4 鄰接多重表 200
7.3 圖的遍歷 203
7.3.1 深度優(yōu)先搜索 203
7.3.2 廣度優(yōu)先搜索 206
7.4 圖的連通性 208
7.4.1 無(wú)向圖的連通分量
與生成樹(shù) 208
7.4.2 小生成樹(shù) 210
7.5 有向無(wú)環(huán)圖及應(yīng)用 221
7.5.1 拓?fù)渑判?topological sort) 221
7.5.2 關(guān)鍵路徑 224
7.6 短路徑 230
單元測(cè)試 236
習(xí)題 237
實(shí)驗(yàn) 238
第8章 查找 243
8.1 查找的基本概念 243
8.2 基于線性表查找 244
8.2.1 順序查找 244
8.2.2 折半查找 246
8.2.3 分塊查找 249
8.3 基于樹(shù)的查找 253
8.3.1 二叉排序樹(shù) 253
8.3.2 平衡二叉排序樹(shù) 261
8.3.3 B樹(shù) 268
8.3.4 靜態(tài)樹(shù)表的查找 277
8.4 哈希表 281
8.4.1 哈希表的概念 281
8.4.2 哈希函數(shù)的構(gòu)造方法 282
8.4.3 處理沖突的方法 286
8.4.4 哈希表的實(shí)現(xiàn) 288
8.4.5 哈希表的查找分析 291
單元測(cè)試 292
習(xí)題 293
實(shí)驗(yàn) 294
第9章 排序 301
9.1 概述 301
9.2 插入排序 303
9.2.1 直接插入排序 303
9.2.2 折半插入排序 307
9.2.3 二路插入排序 307
9.2.4 表插入排序 309
9.2.5 希爾排序 311
9.3 交換排序 314
9.3.1 冒泡排序 315
9.3.2 快速排序 316
9.4 選擇排序 319
9.4.1 簡(jiǎn)單選擇排序 319
9.4.2 堆排序 320
9.5 歸并排序 325
9.6 基數(shù)排序 329
9.6.1 多關(guān)鍵字排序 329
9.6.2 基數(shù)排序 330
9.7 外部排序 333
9.7.1 二路歸并排序 333
9.7.2 多路歸并排序 334
9.7.3 初始順串的生成 338
單元測(cè)試 339
習(xí)題 340
實(shí)驗(yàn) 342
參考文獻(xiàn) 348