第1章 概論 1 1.1 問(wèn)題求解方法 1 1.1.1 問(wèn)題和問(wèn)題求解 1 1.1.2 問(wèn)題求解過(guò)程 2 1.1.3 計(jì)算機(jī)求解問(wèn)題的過(guò)程 2 1.1.4 算法與數(shù)據(jù)結(jié)構(gòu) 2 1.2 什么是數(shù)據(jù)結(jié)構(gòu) 3 1.2.1 基本概念 3 1.2.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 4 1.2.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 5 1.2.4 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 6 1.3 數(shù)據(jù)抽象和抽象數(shù)據(jù)類(lèi)型 7 1.3.1 抽象、數(shù)據(jù)抽象和過(guò)程抽象 7 1.3.2 封裝和信息隱蔽 7 1.3.3 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型 7 1.3.4 數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類(lèi)型 8 1.4 描述數(shù)據(jù)結(jié)構(gòu) 9 1.4.1 數(shù)據(jù)結(jié)構(gòu)的規(guī)范 9 1.4.2 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu) 9 1.5 算法和算法分析 11 1.5.1 算法及其性能標(biāo)準(zhǔn) 11 1.5.2 算法的時(shí)間復(fù)雜度 12 1.5.3 漸近時(shí)間復(fù)雜度 14 1.5.4 最壞、最好和平均情況時(shí)間 復(fù)雜度 15 1.5.5 算法的空間復(fù)雜度 15 小結(jié) 15 習(xí)題1 16 第2章 數(shù)組和鏈表 18 2.1 結(jié)構(gòu)與聯(lián)合 18 2.1.1 結(jié)構(gòu) 18 2.1.2 聯(lián)合 19 2.2 數(shù)組 20 2.2.1 一維數(shù)組 20 2.2.2 二維數(shù)組 20 2.2.3 多維數(shù)組 22 2.3 鏈表 22 2.3.1 指針 22 2.3.2 單鏈表 26 2.3.3 帶表頭結(jié)點(diǎn)的單鏈表 32 2.3.4 循環(huán)鏈表 32 2.3.5 雙向鏈表 33 2.4 采用模擬指針的鏈表 35 2.4.1 結(jié)點(diǎn)結(jié)構(gòu) 35 2.4.2 可用空間表 35 小結(jié) 37 習(xí)題2 37 第3章 堆棧和隊(duì)列 39 3.1 堆棧 39 3.1.1 堆棧ADT 39 3.1.2 堆棧的順序表示 40 3.1.3 堆棧的鏈接表示 42 3.2 隊(duì)列 43 3.2.1 隊(duì)列ADT 43 3.2.2 隊(duì)列的順序表示 44 3.2.3 隊(duì)列的鏈接表示 47 *3.3 表達(dá)式的計(jì)算 47 3.3.1 表達(dá)式 47 3.3.2 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 48 3.3.3 計(jì)算后綴表達(dá)式的值 52 *3.4 遞歸和遞歸過(guò)程 54 3.4.1 遞歸的概念 54 3.4.2 遞歸的實(shí)現(xiàn) 55 *3.5 演示和測(cè)試 57 小結(jié) 59 習(xí)題3 59 第4章 線(xiàn)性表和數(shù)組ADT 61 4.1 線(xiàn)性表 61 4.1.1 線(xiàn)性表ADT 61 4.1.2 線(xiàn)性表的順序表示 62 4.1.3 線(xiàn)性表的鏈接表示 65 4.1.4 兩種存儲(chǔ)表示的比較 69 *4.2 多項(xiàng)式的算術(shù)運(yùn)算 69 4.2.1 多項(xiàng)式ADT 69 4.2.2 多項(xiàng)式的鏈接表示 70 4.2.3 多項(xiàng)式的輸入和輸出 71 4.2.4 多項(xiàng)式相加 73 4.3 數(shù)組作為抽象數(shù)據(jù)類(lèi)型 74 4.4 特殊矩陣 75 4.4.1 對(duì)稱(chēng)矩陣 75 *4.4.2 帶狀矩陣 76 4.5 稀疏矩陣 77 4.5.1 稀疏矩陣ADT 77 4.5.2 稀疏矩陣的順序表示 78 4.5.3 稀疏矩陣轉(zhuǎn)置 79 4.5.4 稀疏矩陣的正交鏈表表示 82 小結(jié) 84 習(xí)題4 84 第5章 字符串和廣義表 86 5.1 字符串 86 5.1.1 字符串ADT 86 5.1.2 字符串的存儲(chǔ)表示 87 5.1.3 簡(jiǎn)單模式匹配算法 88 *5.1.4 模式匹配的KMP算法 91 *5.2 廣義表 95 5.2.1 廣義表的概念 95 5.2.2 廣義表ADT 96 5.2.3 廣義表的存儲(chǔ)表示 97 5.2.4 廣義表的算法 98 小結(jié) 99 習(xí)題5 99 第6章 樹(shù) 100 6.1 樹(shù)的基本概念 100 6.1.1 樹(shù)的定義 100 6.1.2 基本術(shù)語(yǔ) 101 6.2 二叉樹(shù) 102 6.2.1 二叉樹(shù)的定義和性質(zhì) 102 6.2.2 二叉樹(shù)ADT 104 6.2.3 二叉樹(shù)的存儲(chǔ)表示 105 6.2.4 二叉樹(shù)的遍歷 108 *6.2.5 二叉樹(shù)遍歷的非遞歸算法 112 *6.2.6 二叉樹(shù)遍歷的應(yīng)用實(shí)例 114 *6.2.7 線(xiàn)索二叉樹(shù) 116 6.3 樹(shù)和森林 120 6.3.1 森林與二叉樹(shù)的轉(zhuǎn)換 120 6.3.2 樹(shù)和森林的存儲(chǔ)表示 121 6.3.3 樹(shù)和森林的遍歷 123 *6.4 堆和優(yōu)先權(quán)隊(duì)列 124 6.4.1 堆 124 6.4.2 優(yōu)先權(quán)隊(duì)列 127 6.5 哈夫曼樹(shù)和哈夫曼編碼 130 6.5.1 樹(shù)的路徑長(zhǎng)度 130 6.5.2 哈夫曼樹(shù)和哈夫曼算法 131 6.5.3 哈夫曼編碼 133 *6.6 并查集和等價(jià)關(guān)系 135 6.6.1 并查集 135 6.6.2 并查集的實(shí)現(xiàn) 135 6.6.3 集合按等價(jià)關(guān)系分組 138 小結(jié) 139 習(xí)題6 139 第7章 集合和搜索 141 7.1 集合及其表示 141 7.1.1 集合和搜索 141 7.1.2 集合ADT 142 7.1.3 集合的表示 143 7.2 順序搜索 143 7.3 二分搜索 145 7.3.1 對(duì)半搜索 146 7.3.2 二叉判定樹(shù) 147 *7.3.3 斐波那契搜索 149 7.3.4 插值搜索 150 7.4 分塊搜索 151 *7.5 搜索算法的時(shí)間下界 152 小結(jié) 153 習(xí)題7 153 第8章 搜索樹(shù) 154 8.1 二叉搜索樹(shù) 154 8.1.1 二叉搜索樹(shù)的定義 154 8.1.2 二叉搜索樹(shù)的搜索 154 8.1.3 二叉搜索樹(shù)的插入 155 8.1.4 二叉搜索樹(shù)的刪除 157 *8.1.5 二叉搜索樹(shù)的高度 159 8.2 二叉平衡樹(shù) 160 8.2.1 二叉平衡樹(shù)的定義 160 8.2.2 二叉平衡樹(shù)的平衡旋轉(zhuǎn) 161 8.2.3 二叉平衡樹(shù)的插入 167 8.2.4 二叉平衡樹(shù)的刪除 170 8.2.5 二叉平衡樹(shù)的高度 173 8.3 B-樹(shù) 173 8.3.1 m叉搜索樹(shù) 173 8.3.2 B-樹(shù)的定義 175 8.3.3 B-樹(shù)的高度 175 8.3.4 B-樹(shù)的搜索 176 8.3.5 B-樹(shù)的插入 176 8.3.6 B-樹(shù)的刪除 179 *8.4 鍵樹(shù) 181 8.4.1 鍵樹(shù)的定義 181 8.4.2 雙鏈樹(shù) 182 8.4.3 Trie樹(shù) 183 8.5 伸展樹(shù) 184 8.5.1 自調(diào)節(jié)樹(shù)和伸展樹(shù) 184 8.5.2 伸展樹(shù)的伸展操作 184 8.5.3 分?jǐn)倳r(shí)間分析 187 8.6 紅黑樹(shù) 187 8.6.1 紅黑樹(shù)的定義 188 8.6.2 紅黑樹(shù)的搜索 188 8.6.3 紅黑樹(shù)的插入 188 8.6.4 紅黑樹(shù)的刪除 192 8.6.5 紅黑樹(shù)的高度 192 小結(jié) 192 習(xí)題8 193 第9章 跳表和散列表 195 9.1 字典 195 *9.2 跳表 195 9.2.1 什么是跳表 196 9.2.2 跳表的搜索 199 9.2.3 跳表的插入 200 9.2.4 跳表的刪除 201 9.3 散列表 202 9.3.1 散列技術(shù) 202 9.3.2 散列函數(shù) 203 9.3.3 解決沖突的拉鏈法 204 9.3.4 解決沖突的線(xiàn)性探查法 205 9.3.5 解決沖突的其他開(kāi)地址法 209 9.3.6 性能分析 211 小結(jié) 212 習(xí)題9 212 第10章 圖 213 10.1 圖的基本概念 213 10.1.1 圖的定義與術(shù)語(yǔ) 213 10.1.2 圖ADT 215 10.2 圖的存儲(chǔ)結(jié)構(gòu) 216 10.2.1 矩陣表示法 216 10.2.2 鄰接表表示法 220 *10.2.3 正交鏈表和多重表表示法 223 10.3 圖的遍歷 225 10.3.1 深度優(yōu)先遍歷 225 10.3.2 寬度優(yōu)先遍歷 227 10.4 拓?fù)渑判蚝完P(guān)鍵路徑 229 10.4.1 拓?fù)渑判?229 *10.4.2 關(guān)鍵路徑 233 10.5 最小代價(jià)生成樹(shù) 236 10.5.1 普里姆算法 237 *10.5.2 克魯斯卡爾算法 238 *10.6 最短路徑 240 10.6.1 單源最短路徑 241 10.6.2 所有頂點(diǎn)之間的最短路徑 244 小結(jié) 246 習(xí)題10 247 第11章 內(nèi)排序 249 11.1 排序的基本概念 249 11.2 插入排序 250 11.2.1 直接插入排序 250 *11.2.2 希爾排序 254 11.2.3 對(duì)半插入排序 255 11.3 交換排序 255 11.3.1 冒泡排序 256 11.3.2 快速排序 257 11.4 合并排序 262 11.4.1 兩路合并排序 262 11.4.2 合并排序的迭代算法 262 *11.4.3 鏈表上的合并排序 264 11.5 選擇排序 267 11.5.1 簡(jiǎn)單選擇排序 268 *11.5.2 堆排序 269 *11.6 排序算法的時(shí)間下界 270 *11.7 基數(shù)排序 271 小結(jié) 275 習(xí)題11 275 第12章 文件和外排序 277 *12.1 輔助存儲(chǔ)器簡(jiǎn)介 277 12.1.1 主存儲(chǔ)器和輔助存儲(chǔ)器 277 12.1.2 磁盤(pán)存儲(chǔ)器 277 12.2 文件 279 12.2.1 文件的基本概念 279 12.2.2 文件的組織方式 279 12.2.3 C語(yǔ)言文件 283 12.3 文件的索引結(jié)構(gòu) 284 12.3.1 靜態(tài)索引結(jié)構(gòu) 284 12.3.2 動(dòng)態(tài)索引結(jié)構(gòu) 285 *12.4 外排序 286 12.4.1 外排序的基本過(guò)程 286 12.4.2 初始游程的生成 286 12.4.3 多路合并 288 12.4.4 最佳合并樹(shù) 290 小結(jié) 291 習(xí)題12 292 第13章 實(shí)習(xí)指導(dǎo)和實(shí)習(xí)題 293 13.1 實(shí)習(xí)目的和要求 293 13.1.1 實(shí)習(xí)目的 293 13.1.2 實(shí)習(xí)要求 293 13.2 實(shí)習(xí)步驟 294 13.3 實(shí)習(xí)報(bào)告 294 13.4 實(shí)習(xí)題 295 13.5 實(shí)習(xí)報(bào)告范例 303 13.5.1 實(shí)習(xí)題：表達(dá)式計(jì)算 303 13.5.2 實(shí)習(xí)報(bào)告 303 13.6 上機(jī)考核 309 附錄A 軟件工程概述 311 附錄B 考研大綱和教材內(nèi)容 318 參考文獻(xiàn) 322