第1章　緒論 1 1.1　為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1 1.2　數(shù)據(jù)結(jié)構(gòu)概述 5 1.3　算法和算法分析 8 1.3.1　算法 8 1.3.2　算法分析 8 本章小結(jié) 11 本章習(xí)題 11 第2章　線性表 14 2.1　線性表的定義和基本操作 14 2.1.1　線性表的定義 15 2.1.2　線性表的基本操作 15 2.2　線性表的順序存儲(chǔ)、實(shí)現(xiàn)和應(yīng)用 17 2.2.1　線性表的順序存儲(chǔ) 17 2.2.2　順序表的操作實(shí)現(xiàn) 18 2.2.3　用順序表實(shí)現(xiàn)糧食收購(gòu)入庫管理問題 22 2.3　線性表的鏈?zhǔn)酱鎯?chǔ)、實(shí)現(xiàn)和應(yīng)用 30 2.3.1　單鏈表 31 2.3.2　用單鏈表實(shí)現(xiàn)病患信息管理問題 39 2.3.3　單循環(huán)鏈表 44 2.3.4　雙鏈表 46 2.4　順序表和鏈表的比較 49 本章小結(jié) 49 本章習(xí)題 50 第3章　棧與隊(duì)列 52 3.1　棧 52 3.1.1　棧的定義 52 3.1.2　棧的基本操作 53 3.1.3　棧的順序存儲(chǔ)和實(shí)現(xiàn) 53 3.1.4　用棧實(shí)現(xiàn)地鐵網(wǎng)絡(luò)兩站點(diǎn)間最佳換乘問題 56 3.2　隊(duì)列 67 3.2.1　隊(duì)列的概念 68 3.2.2　隊(duì)列的基本操作 68 3.2.3　隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn) 68 3.2.4　隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 73 3.2.5　用隊(duì)列實(shí)現(xiàn)醫(yī)院排隊(duì)叫號(hào)問題 77 本章小結(jié) 83 本章習(xí)題 83 第4章　串 86 4.1　串的類型與基本運(yùn)算 86 4.1.1　串的類型定義 86 4.1.2　串的基本運(yùn)算 86 4.2　串的存儲(chǔ) 89 4.2.1　串的順序存儲(chǔ) 89 4.2.2　串的鏈?zhǔn)酱鎯?chǔ) 90 4.3　串的模式匹配 91 4.3.1　模式匹配的簡(jiǎn)單算法 91 4.3.2　KMP算法 94 4.3.3　KMP改進(jìn)算法 98 4.4　用串實(shí)現(xiàn)手機(jī)通信錄管理系統(tǒng) 99 本章小結(jié) 108 本章習(xí)題 109 第5章　多維數(shù)組 111 5.1　數(shù)組 111 5.1.1　數(shù)組的概念 111 5.1.2　數(shù)組的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn) 112 5.1.3　用二維數(shù)組解決用戶喜好相似度商品推薦的問題 114 5.2　矩陣的壓縮存儲(chǔ) 121 5.2.1　特殊矩陣的邏輯結(jié)構(gòu) 122 5.2.2　用特殊矩陣解決查詢城市 之間距離的問題 123 5.3　稀疏矩陣 125 5.3.1　稀疏矩陣的邏輯結(jié)構(gòu) 125 5.3.2　稀疏矩陣的壓縮存儲(chǔ) 125 本章小結(jié) 127 本章習(xí)題 127 第6章　樹 130 6.1　概述 130 6.2　二叉樹 133 6.2.1　二叉樹的定義和基本操作 133 6.2.2　二叉樹的性質(zhì) 134 6.2.3　二叉樹的存儲(chǔ) 136 6.3　二叉樹的遍歷和線索化 139 6.3.1　二叉樹的遍歷 139 6.3.2　二叉樹的線索化 144 6.3.3　用二叉樹解決快速搜索人口普查中的數(shù)據(jù)問題 149 6.4　樹和森林 152 6.4.1　樹的存儲(chǔ) 153 6.4.2　樹、森林與二叉樹的轉(zhuǎn)換 156 6.4.3　樹和森林的遍歷 157 6.5　哈夫曼樹及其應(yīng)用 158 6.5.1　基本概念 158 6.5.2　哈夫曼樹的構(gòu)造 159 6.5.3　哈夫曼樹的應(yīng)用 163 6.5.4　用哈夫曼樹解決文件傳輸編碼問題 164 本章小結(jié) 173 本章習(xí)題 173 第7章　圖 177 7.1　圖的定義和術(shù)語 177 7.1.1　各種圖定義 178 7.1.2　圖的頂點(diǎn)與邊間關(guān)系 180 7.1.3　連通圖的相關(guān)術(shù)語 182 7.2　圖的存儲(chǔ)結(jié)構(gòu) 184 7.2.1　鄰接矩陣存儲(chǔ)結(jié)構(gòu) 184 7.2.2　鄰接表存儲(chǔ)結(jié)構(gòu) 186 7.3　圖的遍歷 189 7.3.1　深度優(yōu)先搜索遍歷 190 7.3.2　廣度優(yōu)先搜索遍歷 192 7.4　圖的生成樹 194 7.4.1　生成樹的基本概念 194 7.4.2　最小生成樹的構(gòu)造 196 7.5　最短路徑 202 7.5.1　單源最短路徑 202 7.5.2　所有頂點(diǎn)對(duì)之間的最短路徑 207 7.6　村村通公路規(guī)劃系統(tǒng)的實(shí)現(xiàn) 211 本章小結(jié) 227 本章習(xí)題 227 第8章　排序 231 8.1　概述 231 8.2　插入排序 232 8.2.1　直接插入排序 232 8.2.2　希爾排序 235 8.3　交換排序 237 8.3.1　冒泡排序 237 8.3.2　快速排序 239 8.4　選擇排序 241 8.4.1　直接選擇排序 242 8.4.2　堆排序 243 8.5　編程實(shí)現(xiàn)奧運(yùn)會(huì)奧運(yùn)獎(jiǎng)牌排名系統(tǒng) 247 本章小結(jié) 258 本章習(xí)題 258 第9章　查找 261 9.1　概述 261 9.2　線性表查找 262 9.2.1　順序查找 262 9.2.2　二分查找 264 9.2.3　分塊查找 266 9.3　哈希表查找 268 9.3.1　哈希表的概念 269 9.3.2　哈希表的構(gòu)造 270 9.3.3　解決沖突的方法 272 9.3.4　哈希表查找實(shí)現(xiàn) 276 9.4　編程實(shí)現(xiàn)鐵路售票查詢系統(tǒng) 277 本章小結(jié) 281 本章習(xí)題 282 參考文獻(xiàn) 285