目錄 第 1章 緒論 1 1.1 程序設(shè)計(jì)的問題背景 1 1.2 程序設(shè)計(jì)的一般過程 2 1.3 數(shù)據(jù)結(jié)構(gòu)概述 3 1.4 數(shù)據(jù)結(jié)構(gòu)基本概念 6 1.5 算法設(shè)計(jì)的一般步驟 9 1.5.1 算法定義及性質(zhì) 9 1.5.2 算法設(shè)計(jì)步驟 12 1.6 算法復(fù)雜度分析 12 1.6.1 算法時(shí)間復(fù)雜度分析 12 1.6.2 算法空間復(fù)雜度分析 15 1.7 算法分析實(shí)例 17 1.8 本章小結(jié) 22 計(jì)算機(jī)領(lǐng)域名人堂 23 本章習(xí)題 23 第 2章 線性表 27 2.1 線性表的基本概念 27 2.1.1 線性表定義 28 2.2.2 抽象數(shù)據(jù)類型定義 29 2.2 線性表順序存儲(chǔ)結(jié)構(gòu)定義及實(shí)現(xiàn) 32 2.2.1 順序表存儲(chǔ)結(jié)構(gòu)定義 32 2.2.2 順序表的基本操作實(shí)現(xiàn) 35 2.3 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義及實(shí)現(xiàn) 39 2.3.1 單鏈表存儲(chǔ)結(jié)構(gòu)定義 40 2.3.2 單鏈表的實(shí)現(xiàn) 40 2.3.3 循環(huán)單鏈表 44 2.3.4 雙向鏈表 46 2.4 順序表與鏈表的比較 48 2.5 線性表應(yīng)用實(shí)例 49 2.5.1 遞增有序單鏈表生成算法 49 2.5.2 單鏈表插入刪除算法 53 2.5.3 單鏈表合并算法 55 2.5.4 單鏈表的逆置 57 2.6 本章小結(jié) 60 計(jì)算機(jī)領(lǐng)域名人堂 61 本章習(xí)題 62 第3章 棧與隊(duì)列 66 3.1 棧 67 3.1.1 棧的基本概念 67 3.1.2 棧的抽象數(shù)據(jù)類型 68 3.1.3 棧的操作特性 68 3.1.4 棧的順序存儲(chǔ)結(jié)構(gòu) 70 3.1.5 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 76 3.1.6 棧的應(yīng)用 78 3.2 隊(duì)列 86 3.2.1 隊(duì)列的基本概念 87 3.2.2 隊(duì)列的抽象數(shù)據(jù)類型 87 3.2.3 鏈?zhǔn)疥?duì)列的基本運(yùn)算及實(shí)現(xiàn) 88 3.2.4 順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn) 91 3.3 應(yīng)用實(shí)例 96 3.3.1 棧的應(yīng)用實(shí)例 96 3.3.2 隊(duì)列的應(yīng)用實(shí)例 99 3.4 本章小結(jié) 102 計(jì)算機(jī)領(lǐng)域名人堂 103 本章習(xí)題 103 第4章 字符串、多維數(shù)組與廣義表 108 4.1 字符串 108 4.1.1 字符串的定義 109 4.1.2 字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 111 4.1.3 字符串的模式匹配算法 116 4.2 多維數(shù)組 122 4.2.1 多維數(shù)組概念的引入 122 4.2.2 多維數(shù)組的順序存儲(chǔ) 124 4.2.3 矩陣的壓縮存儲(chǔ) 128 4.3 廣義表 137 4.3.1 廣義表的定義 137 4.3.2 廣義表的存儲(chǔ) 139 4.4 應(yīng)用實(shí)例 143 4.4.1最大匹配分詞算法 143 4.4.2正數(shù)值三角形的最優(yōu)路徑 147 4.5 本章小結(jié) 149 計(jì)算機(jī)領(lǐng)域名人堂 149 本章習(xí)題 150 第5章 樹與二叉樹 153 5.1 實(shí)際應(yīng)用中的樹 153 5.2樹的邏輯結(jié)構(gòu) 155 5.2.1 樹的定義與基本術(shù)語 155 5.2.2 樹的抽象數(shù)據(jù)類型定義 157 5.3 樹的存儲(chǔ)結(jié)構(gòu) 158 5.3.1 雙親表示法 159 5.3.2 孩子表示法 159 5.3.3 孩子兄弟表示法 161 5.4 二叉樹的邏輯結(jié)構(gòu) 162 5.4.1 二叉樹的定義 163 5.4.2 二叉樹的性質(zhì) 163 5.4.3 二叉樹的操作與抽象數(shù)據(jù)類型定義 166 5.5 二叉樹的存儲(chǔ)結(jié)構(gòu) 168 5.5.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 168 5.5.2 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 169 5.5.3 基于二叉鏈表的二叉樹遍歷 170 5.5.4 線索鏈表與線索二叉樹 179 5.6 樹、森林與二叉樹的轉(zhuǎn)換 185 5.6.1 樹與二叉樹的轉(zhuǎn)換 185 5.6.2 森林與二叉樹的轉(zhuǎn)換 186 5.6.3 樹與森林的遍歷 187 5.7 哈夫曼樹 189 5.7.1 哈夫曼樹與哈夫曼算法 189 5.7.2 哈夫曼編碼 192 5.8 應(yīng)用實(shí)例：表達(dá)式二叉樹 193 5.8.1 表達(dá)式二叉樹的概念 194 5.8.2 表達(dá)式二叉樹的實(shí)現(xiàn) 194 5.9本章小結(jié) 197 計(jì)算機(jī)領(lǐng)域名人堂 197 本章習(xí)題 198 第6章 圖 203 6.1 實(shí)際應(yīng)用中的圖 203 6.2 圖的基本概念 204 6.2.1 圖的定義和基本術(shù)語 204 6.2.2 圖的操作定義 207 6.3 圖的存儲(chǔ)結(jié)構(gòu) 208 6.3.1 鄰接矩陣 208 6.3.2 鄰接表 211 6.3.3 十字鏈表 213 6.3.4 鄰接多重表 214 6.4 圖的遍歷 215 6.4.1 圖的深度優(yōu)先搜索遍歷 215 6.4.2 圖的廣度優(yōu)先搜索遍歷 217 6.4.3 圖的連通性 218 6.5 圖的生成樹問題 219 6.5.1 生成樹與最小生成樹 219 6.5.2 最小生成樹Prim算法 220 6.5.3 最小生成樹Kruskal算法 223 6.6 圖的最短路徑問題 226 6.6.1 單源最短路徑Dijkstra算法 226 6.6.2 各頂點(diǎn)間最短路徑Floyd算法 230 6.7 有向無環(huán)圖的應(yīng)用 233 6.7.1 拓?fù)渑判?233 6.7.2 關(guān)鍵路徑 236 6.8 應(yīng)用實(shí)例 241 6.8.1 并查集 241 6.8.2 地鐵換乘問題 245 6.9 本章小結(jié) 258 計(jì)算機(jī)領(lǐng)域名人堂 258 本章習(xí)題 259 第7章 排序 263 7.1 實(shí)際應(yīng)用中的排序 263 7.2 排序的概述 264 7.2.1 排序算法的穩(wěn)定性 265 7.2.2 排序算法的分類 266 7.2.3 排序算法的性能 266 7.3 插入排序 266 7.3.1 直接插入排序 266 7.3.2 折半插入排序 269 7.3.3 希爾排序 271 7.4 交換排序 274 7.4.1 冒泡排序 274 7.4.2 快速排序 277 7.5 選擇排序 281 7.5.1 簡(jiǎn)單選擇排序 281 7.5.2 樹形選擇排序 284 7.6 歸并排序 291 7.7 分配排序 295 7.7.1 桶排序 295 7.7.2 基數(shù)排序 296 7.8 各種排序技術(shù)比較 299 7.9 本章小結(jié) 300 計(jì)算機(jī)領(lǐng)域名人堂 301 本章習(xí)題 302 第8章 查找 308 8.1 查找概述 308 8.1.1 查找基本概念 308 8.1.2 查找操作性能分析 309 8.2 線性表的查找技術(shù) 309 8.2.1 順序查找 309 8.2.2 折半查找 312 8.2.3 索引查找 315 8.3 樹表的查找技術(shù) 316 8.3.1 二叉排序樹 316 8.3.2 平衡二叉樹 325 8.3.3 紅黑樹 331 8.3.4 B樹 346 8.4 散列表的查找技術(shù) 350 8.4.1 散列表概述 350 8.4.2 散列函數(shù)設(shè)計(jì) 351 8.4.3 處理沖突的方法 352 8.4.4 散列查找性能分析 355 8.5 本章小結(jié) 357 計(jì)算機(jī)領(lǐng)域名人堂 358 本章習(xí)題 359 第9章 大數(shù)據(jù)存儲(chǔ)與檢索 364 9.1 大數(shù)據(jù)的定義與特征 364 9.1.1 大數(shù)據(jù)定義 365 9.1.2 大數(shù)據(jù)特征 365 9.1.3 大數(shù)據(jù)的行業(yè)發(fā)展趨勢(shì) 367 9.2 大數(shù)據(jù)存儲(chǔ) 367 9.2.1 數(shù)據(jù)存儲(chǔ)管理 368 9.2.2 分布式文件系統(tǒng) 368 9.2.3 NoSQL數(shù)據(jù)庫(kù) 371 9.2.4 HBase數(shù)據(jù)庫(kù) 372 9.3 大數(shù)據(jù)檢索 375 9.3.1 大數(shù)據(jù)索引 375 9.3.2 大數(shù)據(jù)高效檢索 377 9.4 應(yīng)用實(shí)例 378 9.5 本章小結(jié) 382 計(jì)算機(jī)領(lǐng)域名人堂 383 本章習(xí)題 383