目錄 第 1章 緒論 1 1.1 程序設(shè)計的問題背景 1 1.2 程序設(shè)計的一般過程 2 1.3 數(shù)據(jù)結(jié)構(gòu)概述 3 1.4 數(shù)據(jù)結(jié)構(gòu)基本概念 6 1.5 算法設(shè)計的一般步驟 9 1.5.1 算法定義及性質(zhì) 9 1.5.2 算法設(shè)計步驟 12 1.6 算法復(fù)雜度分析 12 1.6.1 算法時間復(fù)雜度分析 12 1.6.2 算法空間復(fù)雜度分析 15 1.7 算法分析實例 17 1.8 本章小結(jié) 22 計算機領(lǐng)域名人堂 23 本章習題 23 第 2章 線性表 27 2.1 線性表的基本概念 27 2.1.1 線性表定義 28 2.2.2 抽象數(shù)據(jù)類型定義 29 2.2 線性表順序存儲結(jié)構(gòu)定義及實現(xiàn) 32 2.2.1 順序表存儲結(jié)構(gòu)定義 32 2.2.2 順序表的基本操作實現(xiàn) 35 2.3 線性表鏈式存儲結(jié)構(gòu)定義及實現(xiàn) 39 2.3.1 單鏈表存儲結(jié)構(gòu)定義 40 2.3.2 單鏈表的實現(xiàn) 40 2.3.3 循環(huán)單鏈表 44 2.3.4 雙向鏈表 46 2.4 順序表與鏈表的比較 48 2.5 線性表應(yīng)用實例 49 2.5.1 遞增有序單鏈表生成算法 49 2.5.2 單鏈表插入刪除算法 53 2.5.3 單鏈表合并算法 55 2.5.4 單鏈表的逆置 57 2.6 本章小結(jié) 60 計算機領(lǐng)域名人堂 61 本章習題 62 第3章 棧與隊列 66 3.1 棧 67 3.1.1 棧的基本概念 67 3.1.2 棧的抽象數(shù)據(jù)類型 68 3.1.3 棧的操作特性 68 3.1.4 棧的順序存儲結(jié)構(gòu) 70 3.1.5 棧的鏈式存儲結(jié)構(gòu) 76 3.1.6 棧的應(yīng)用 78 3.2 隊列 86 3.2.1 隊列的基本概念 87 3.2.2 隊列的抽象數(shù)據(jù)類型 87 3.2.3 鏈式隊列的基本運算及實現(xiàn) 88 3.2.4 順序隊列的基本運算及實現(xiàn) 91 3.3 應(yīng)用實例 96 3.3.1 棧的應(yīng)用實例 96 3.3.2 隊列的應(yīng)用實例 99 3.4 本章小結(jié) 102 計算機領(lǐng)域名人堂 103 本章習題 103 第4章 字符串、多維數(shù)組與廣義表 108 4.1 字符串 108 4.1.1 字符串的定義 109 4.1.2 字符串的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 111 4.1.3 字符串的模式匹配算法 116 4.2 多維數(shù)組 122 4.2.1 多維數(shù)組概念的引入 122 4.2.2 多維數(shù)組的順序存儲 124 4.2.3 矩陣的壓縮存儲 128 4.3 廣義表 137 4.3.1 廣義表的定義 137 4.3.2 廣義表的存儲 139 4.4 應(yīng)用實例 143 4.4.1最大匹配分詞算法 143 4.4.2正數(shù)值三角形的最優(yōu)路徑 147 4.5 本章小結(jié) 149 計算機領(lǐng)域名人堂 149 本章習題 150 第5章 樹與二叉樹 153 5.1 實際應(yīng)用中的樹 153 5.2樹的邏輯結(jié)構(gòu) 155 5.2.1 樹的定義與基本術(shù)語 155 5.2.2 樹的抽象數(shù)據(jù)類型定義 157 5.3 樹的存儲結(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 二叉樹的存儲結(jié)構(gòu) 168 5.5.1 二叉樹的順序存儲結(jié)構(gòu) 168 5.5.2 二叉樹的鏈式存儲結(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)用實例：表達式二叉樹 193 5.8.1 表達式二叉樹的概念 194 5.8.2 表達式二叉樹的實現(xiàn) 194 5.9本章小結(jié) 197 計算機領(lǐng)域名人堂 197 本章習題 198 第6章 圖 203 6.1 實際應(yīng)用中的圖 203 6.2 圖的基本概念 204 6.2.1 圖的定義和基本術(shù)語 204 6.2.2 圖的操作定義 207 6.3 圖的存儲結(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 各頂點間最短路徑Floyd算法 230 6.7 有向無環(huán)圖的應(yīng)用 233 6.7.1 拓撲排序 233 6.7.2 關(guān)鍵路徑 236 6.8 應(yīng)用實例 241 6.8.1 并查集 241 6.8.2 地鐵換乘問題 245 6.9 本章小結(jié) 258 計算機領(lǐng)域名人堂 258 本章習題 259 第7章 排序 263 7.1 實際應(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 簡單選擇排序 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 計算機領(lǐng)域名人堂 301 本章習題 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è)計 351 8.4.3 處理沖突的方法 352 8.4.4 散列查找性能分析 355 8.5 本章小結(jié) 357 計算機領(lǐng)域名人堂 358 本章習題 359 第9章 大數(shù)據(jù)存儲與檢索 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ā)展趨勢 367 9.2 大數(shù)據(jù)存儲 367 9.2.1 數(shù)據(jù)存儲管理 368 9.2.2 分布式文件系統(tǒng) 368 9.2.3 NoSQL數(shù)據(jù)庫 371 9.2.4 HBase數(shù)據(jù)庫 372 9.3 大數(shù)據(jù)檢索 375 9.3.1 大數(shù)據(jù)索引 375 9.3.2 大數(shù)據(jù)高效檢索 377 9.4 應(yīng)用實例 378 9.5 本章小結(jié) 382 計算機領(lǐng)域名人堂 383 本章習題 383