本書系統(tǒng)介紹了最常用的數(shù)據(jù)結(jié)構(gòu)，包括線性表、棧、隊列、數(shù)組、矩陣的壓縮存儲、樹與二叉樹、圖以及查找和排序的算法等。闡述各種數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系，分析討論各種數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)的存儲表示，以及在這些數(shù)據(jù)結(jié)構(gòu)下的算法實現(xiàn)，并對各種算法的時間和空間性能作簡要分析。 本書既注重原理又注重實踐，對基本的算法均給出相應(yīng)的C語言程序的描述，并加以較詳細的注釋。全書配有圖表，每章后都附有習(xí)題，內(nèi)容豐富，概念講解清楚，邏輯性強。在本書的最后給出實驗內(nèi)容的附錄。 本書可作為高等院校計算機相關(guān)專業(yè)的教材，亦適合于計算機愛好者自學(xué)，還可供廣大從事計算機應(yīng)用和開發(fā)的技術(shù)人員參考。第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ù)語 5
1.1.3 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容和任務(wù) 7
1.2 數(shù)據(jù)類型、抽象數(shù)據(jù)類型和參數(shù)傳遞 7
1.2.1 數(shù)據(jù)類型 8
1.2.2 抽象數(shù)據(jù)類型 8
1.2.3 參數(shù)傳遞 9
1.3 算法和算法分析 10
1.3.1 算法特性 10
1.3.2 算法描述 11
1.3.3 算法性能分析與度量 11
1.4 習(xí)題 13
第2章 線性表 15
2.1 線性表的邏輯結(jié)構(gòu) 15
2.1.1 線性表的類型定義 15
2.1.2 線性表的基本操作 16
2.2 線性表的順序存儲表示和實現(xiàn) 17
2.2.1 順序表 17
2.2.2 順序表的基本運算 18
2.2.3 順序表的應(yīng)用舉例 22
2.3 線性表的鏈?zhǔn)酱鎯瓦\算實現(xiàn) 24
2.3.1 單鏈表 24
2.3.2 單鏈表的基本運算 26
2.3.3 循環(huán)鏈表 32
2.3.4 雙向鏈表 33
2.3.5 單鏈表應(yīng)用舉例 34
2.4 順序表和鏈表的比較 36
2.5 習(xí)題 37
第3章 棧 39
3.1 棧的定義和基本運算 39
3.1.1 棧的定義 39
3.1.2 棧的基本運算 40
3.2 棧的存儲實現(xiàn)和運算實現(xiàn) 40
3.2.1 棧的順序存儲結(jié)構(gòu) 40
3.2.2 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 43
3.3 棧的應(yīng)用舉例 44
3.3.1 數(shù)制轉(zhuǎn)換 44
3.3.2 算術(shù)運算式的轉(zhuǎn)換 45
3.3.3 子程序調(diào)用 49
3.3.4 編譯錯誤處理 49
3.3.5 迷宮問題 49
3.4 習(xí)題 53
第4章 隊列 55
4.1 隊列的定義及基本運算 55
4.1.1 隊列的定義 55
4.1.2 隊列的基本運算 56
4.2 隊列的存儲結(jié)構(gòu)及運算實現(xiàn) 56
4.2.1 順序隊列 56
4.2.2 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) 60
4.3 隊列應(yīng)用舉例 62
4.4 習(xí)題 65
第5章 串 66
5.1 串及串的基本運算 66
5.1.1 串的基本概念 66
5.1.2 串的基本運算 67
5.2 串的定長順序存儲結(jié)構(gòu)及基本運算 68
5.2.1 串的定長順序存儲結(jié)構(gòu) 68
5.2.2 定長順序串的基本運算 69
5.3 堆分配存儲結(jié)構(gòu)及基本運算的實現(xiàn) 71
5.3.1 串的堆分配的存儲結(jié)構(gòu) 71
5.3.2 基于堆結(jié)構(gòu)串的基本運算 71
5.4 串的塊鏈存儲結(jié)構(gòu)簡介 73
5.5 串的模式匹配 74
5.5.1 簡單的模式匹配算法 74
5.5.2 改進后的模式匹配算法 76
5.6 串操作應(yīng)用舉例 81
5.7 習(xí)題 82
第6章 數(shù)組、特殊矩陣和廣義表 84
6.1 數(shù)組的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu) 84
6.1.1 數(shù)組的定義及邏輯結(jié)構(gòu) 84
6.1.2 數(shù)組的內(nèi)存映像 85
6.2 矩陣的壓縮存儲 87
6.2.1 對稱矩陣的壓縮存儲 87
6.2.2 三角矩陣 88
6.2.3 帶狀矩陣 89
6.3 稀疏矩陣 90
6．3．1 稀疏矩陣的轉(zhuǎn)置 91
6.3.2 稀疏矩陣的乘積 92
6.4 廣義表 95
6.4.1 廣義表的概念和特性 95
6.4.2 廣義表的存儲結(jié)構(gòu) 95
6.4.3 廣義表的基本運算和實現(xiàn) 98
6.5 習(xí)題 101
第7章 樹和二叉樹 103
7.1 樹的定義及表示 103
7.1.1 樹的定義及相關(guān)術(shù)語 103
7.1.2 樹的表示 105
7.2 二叉樹 107
7.2.1 二叉樹的定義 107
7.2.2 二叉樹的性質(zhì) 108
7.2.3 二叉樹的存儲結(jié)構(gòu) 109
7.2.4 二叉樹的基本操作及運算實現(xiàn) 112
7.3 二叉樹的遍歷 115
7.3.1 二叉樹的遍歷方法及遞歸實現(xiàn) 115
7.3.2 由遍歷序列恢復(fù)二叉樹 118
7.4 線索二叉樹 120
7.4.1 線索二叉樹的定義及結(jié)構(gòu) 120
7.4.2 線索二叉樹的基本運算 122
7.5 樹和森林 125
7.5.1 樹的存儲結(jié)構(gòu) 125
7.5.2 二叉樹與樹和森林的相互轉(zhuǎn)換 126
7.5.3 樹和森林的遍歷 128
7.5.4 樹的應(yīng)用 128
7.6 哈夫曼樹及應(yīng)用 131
7.6.1 最優(yōu)二叉樹(哈夫曼樹) 131
7.6.2 哈夫曼編碼 135
7.7 習(xí)題 138
第8章 圖 140
8.1 圖的基本概念和基本術(shù)語 140
8.1.1 圖的基本定義 140
8.1.2 圖的基本與術(shù)語 141
8.1.3 圖的基本操作 143
8.2 圖的存儲結(jié)構(gòu) 144
8.2.1 鄰接矩陣 144
8.2.2 鄰接表 145
8.2.3 十字鏈表 147
8.2.4 鄰接多重表 149
8.3 圖的遍歷 150
8.3.1 深度優(yōu)先搜索 150
8.3.2 廣度優(yōu)先搜索 152
8.4 圖的連通性問題 153
8.4.1 無向圖的連通分量和生成樹 153
8.4.2 應(yīng)用圖的遍歷判定圖的 連通性問題 155
8.4.3 最小生成樹 155
8.4.4 構(gòu)造最小生成樹的Prim算法 156
8.4.5 構(gòu)造最小生成樹的Kruskal算法 158
8.5 最短路徑 160
8.5.1 從一個源點到其他各頂點的
最短路徑 160
8.5.2 每一對頂點之間的最短路徑 163
8.6 有向無環(huán)圖及其應(yīng)用 165
8.6.1 有向無環(huán)圖的定義 165
8.6.2 AOV網(wǎng)與拓?fù)渑判?165
8.6.3 AOE網(wǎng)與關(guān)鍵路徑 167
8.7 習(xí)題 171
第9章 查找 173
9.1 基本概念 173
9.2 靜態(tài)查找表 174
9.2.1 順序表的查找 174
9.2.2 有序表的查找 175
9.2.3 索引順序表的查找 178
9.3 動態(tài)查找表 178
9.3.1 二叉排序樹 178
9.3.2 平衡二叉樹 183
9.3.3 B-樹和B+樹 188
9.4 哈希表查找(雜湊法) 194
9.4.1 什么是哈希表 194
9.4.2 哈希函數(shù)的構(gòu)造方法 194
9.4.3 處理沖突的方法 197
9.4.4 哈希表的查找及其分析 199
9.5 習(xí)題 200
第10章 排序 201
10.1 概述 201
10.2 插入排序 202
10.2.1 直接插入排序 202
10.2.2 折半插入排序 203
10.2.3 希爾排序(又稱縮小增量排序) 204
10.3 交換排序 206
10.3.1 冒泡排序 206
10.3.2 快速排序 206
10.4 選擇排序 209
10.4.1 簡單選擇排序 209
10.4.2 樹形選擇排序 210
10.4.3 堆排序 211
10.5 歸并排序 213
10.6 基數(shù)排序 215
10.6.1 多關(guān)鍵字的排序 215
10.6.2 鏈?zhǔn)交鶖?shù)排序 215
10.7 外部排序 218
10.8 習(xí)題 222
附錄A 實驗內(nèi)容 224
