出版社:清華大學出版社 ISBN:9787302459897 商品編碼:25773239273 品牌:鳳凰新華(PHOENIX 包裝:平裝-膠訂 開本:16 出版時間:2017-04-01 頁數:404 字數:638000 代碼:49 作者:殷人昆
" 內容介紹 本書是根據教育部《高等學校計算機科學與技術專業公共核心知識體繫與課程》編寫的數據結構主教材。全書共8章。D1章介紹數據結構的地位和主要知識點,數據結構和算法的基本概念和算法分析的簡單方法,以及C語言編程的要點。D2~8章分別介紹了線性表、棧和隊列及其應用、多維數組、特殊矩陣、稀疏矩陣、字符串和廣義表、樹與二叉樹、圖、查找、排序,並做了適D延伸。作者在討論每一個時,結合30多年教學的經驗和考試輔導的體會,合理安排教材內容,力求透徹、全面,對學生讀書容易忽略的地方和隱藏在書中所討論問題後面的東西都有適D的提示。 本書的編寫得到清華大學2015年精品教材建設項目的資助。本書既可作為高等學校計算機科學與技術專業和軟件工程專業本科生學習數據結構與算法課程的教材,也可以作為計算機專業考研的輔導教材或其他計算機或軟件考試的復習教材,還可作為計算機或軟件繫統開發人員的參考資料。 關聯推薦 (1)根據教育部頒發的《高等學校計算機科學與技術專業公共核心知識體繫與課程》規範編寫。(2)內容涵蓋數據結構與算法的基本概念和算法分析的簡單方法,以及C語言編程的要點。(3)作者在討論每一個時,結合30多年教學的經驗和考試輔導的體會,合理安排了教材內容,力求透徹、全面。對學生讀書容易忽略的地方和隱藏在書中所討論問題後面的東西,都有適D的提示。(4)是學習數據結構與算法課程的教材,也可以作為計算機專業考研的輔導教材或其他計算機或軟件考試的復習教材。 目錄 目錄 D1章 緒論 1 1.1 數據結構的概念及分類 1 1.1.1 為什麼要學習數據結構 1 1.1.2 與數據結構相關的基本術語 2 1.1.3 數據結構的分類 5 1.1.4 數據結構的存儲結構 6 1.1.5 定義在數據結構上的操作 7 1.1.6 “好”數據結構 7 1.2 使用C語言描述數據結構 7 1.2.1 C語言的數據類型 8 1.2.2 算法的控制結構 9 1.2.3 算法的函數結構 10 1.2.4 動態存儲分配 12 目錄 D1章 緒論 1 1.1 數據結構的概念及分類 1 1.1.1 為什麼要學習數據結構 1 1.1.2 與數據結構相關的基本術語 2 1.1.3 數據結構的分類 5 1.1.4 數據結構的存儲結構 6 1.1.5 定義在數據結構上的操作 7 1.1.6 “好”數據結構 7 1.2 使用C語言描述數據結構 7 1.2.1 C語言的數據類型 8 1.2.2 算法的控制結構 9 1.2.3 算法的函數結構 10 1.2.4 動態存儲分配 12 1.2.5 邏輯和關繫運算的約定 12 1.2.6 輸入與輸出 13 1.3 算法和算法設計 13 1.3.1 算法的定義和特性 13 1.3.2 算法的設計步驟 14 1.3.3 算法設計的基本方法 15 1.4 算法分析與度量 18 1.4.1 算法的評價標準 18 1.4.2 算法的時間和空間復雜度度量 18 1.4.3 算法的漸近分析 21 小結 24 習題 24 D2章 線性表 27 2.1 線性表 27 2.1.1 線性表的定義和特點 27 2.1.2 線性表的主要操作 28 2.2 順序表 29 2.2.1 順序表的定義和特點 29 2.2.2 順序表的結構定義 30 2.2.3 順序表查找操作的實現 31 2.2.4 順序表插入和刪除操作的實現 32 2.2.5 順序表的應用:集合運算 34 2.3 單鏈表 35 2.3.1 單鏈表的定義和特點 35 2.3.2 單鏈表的結構定義 36 2.3.3 單鏈表中的插入與刪除 36 2.3.4 帶頭結點的單鏈表 40 2.3.5 單鏈表的遍歷與創建 42 2.3.6 單鏈表的應用:集合運算 44 2.3.7 循環鏈表 46 2.3.8 雙向鏈表 50 2.3.9 靜態鏈表 53 2.4 順序表與線性鏈表的比較 54 2.5 線性表的應多項式及其運算 56 2.5.1 多項式的表示 56 2.5.2 多項式的結構定義 57 2.5.3 多項式的加法 59 2.5.4 擴展閱讀:多項式的乘法 60 小結 62 習題 63 D3章 棧和隊列 66 3.1 棧 66 3.1.1 棧的概念 66 3.1.2 順序棧 67 3.1.3 擴展閱讀:多棧處理 70 3.1.4 鏈式棧 73 3.1.5 擴展閱讀:棧的混洗 74 3.2 隊列 76 3.2.1 隊列的概念 76 3.2.2 循環隊列 76 3.2.3 鏈式隊列 80 3.3 棧的應用 82 3.3.1 數制轉換 82 3.3.2 括號匹配 83 3.3.3 表達式的計算與優先級處理 84 3.3.4 棧與遞歸的實現 88 3.4 隊列的應用 91 3.5 在算法設計中使用遞歸 92 3.5.1 漢諾塔問題與分治法 92 3.5.2 直接把遞歸過程改為非遞歸過程 94 3.5.3 擴展閱讀:遞歸過程的非遞歸模擬算法 95 3.5.4 迷宮問題與回溯法 98 3.5.5 計算組合數與動態規劃 101 3.6 擴展閱讀:雙端隊列 102 3.6.1 雙端隊列的概念 102 3.6.2 輸入受限的雙端隊列 103 3.6.3 輸出受限的雙端隊列 104 3.6.4 雙端隊列的存儲表示 104 3.7 擴展閱讀:優先隊列 106 3.7.1 優先隊列的概念 106 3.7.2 優先隊列的實現 107 小結 108 習題 108 D4章 數組、串和廣義表 112 4.1 數組 112 4.1.1 一維數組 112 4.1.2 多維數組 114 4.2 特殊矩陣的壓縮存儲 116 4.2.1 對稱矩陣的壓縮存儲 117 4.2.2 三對角矩陣的壓縮存儲 118 4.2.3 擴展閱讀:w對角矩陣的壓縮存儲 119 4.3 稀疏矩陣 120 4.3.1 稀疏矩陣的概念 120 4.3.2 稀疏矩陣的順序存儲表示 121 4.3.3 稀疏矩陣的鏈表表示 124 4.4 字符串 125 4.4.1 字符串的概念 126 4.4.2 字符串的初始化和賦值 126 4.4.3 自定義字符串的存儲表示 128 4.4.4 串的模式匹配 132 4.5 廣義表 140 4.5.1 廣義表的概念 140 4.5.2 廣義表的性質 141 4.5.3 廣義表的鏈接表示 141 4.5.4 擴展閱多項式的表示 147 小結 148 習題 149 D5章 樹與二叉樹 152 5.1 樹的基本概念 152 5.1.1 樹的定義和術語 152 5.1.2 樹的基本操作 154 5.2 二叉樹及其存儲表示 155 5.2.1 二叉樹的概念 155 5.2.2 二叉樹的性質 156 5.2.3 二叉樹的主要操作 158 5.2.4 二叉樹的順序存儲表示 159 5.2.5 二叉樹的鏈表存儲表示 160 5.3 二叉樹的遍歷 161 5.3.1 二叉樹遍歷的遞歸算法 162 5.3.2 遞歸遍歷算法的應用舉例 163 5.3.3 二叉樹遍歷的非遞歸算法 166 5.3.4 利用隊列實現二叉樹的層次序遍歷 169 5.3.5 非遞歸遍歷算法的應用舉例 170 5.3.6 二叉樹的計數 171 5.4 線索二叉樹 174 5.4.1 線索二叉樹的概念 174 5.4.2 線索二叉樹的種類 175 5.4.3 中序線索二叉樹的建立和遍歷 176 5.4.4 先序與後序線索二叉樹 178 5.5 樹與森林 180 5.5.1 樹的存儲表示 180 5.5.2 森林與二叉樹的轉換 184 5.5.3 樹與森林的深度優先遍歷 185 5.5.4 樹與森林的廣度優先遍歷 187 5.5.5 樹遍歷算法的應用舉例 188 5.6 Huffman樹 190 5.6.1 帶權路徑長度的概念 190 5.6.2 Huffman樹的概念 191 5.6.3 擴展閱讀:Z優判定樹 194 5.6.4 Huffman編碼 196 5.7 堆 198 5.7.1 小根堆和大根堆 198 5.7.2 堆的建立 199 5.7.3 堆的插入 201 5.7.4 堆的刪除 202 5.8 等價類與並查集 202 5.8.1 等價關繫與等價類 202 5.8.2 確定等價類的方法 203 5.8.3 並查集的定義及其實現 203 5.8.4 並查集操作的分析和改進 205 5.9 擴展閱讀:八皇後問題與樹的剪枝 207 5.9.1 八皇後問題的提出 207 5.9.2 八皇後問題的狀態樹 208 5.9.3 八皇後問題算法 210 小結 211 習題 212 D6章 圖 216 6.1 圖的基本概念 216 6.1.1 與圖有關的若干概念 216 6.1.2 圖的基本操作 219 6.2 圖的存儲結構 221 6.2.1 圖的鄰接矩陣表示 221 6.2.2 圖的鄰接表表示 225 6.2.3 鄰接矩陣表示與鄰接表表示的比較 229 6.2.4 圖的鄰接多重表和十字鏈表表示 230 6.3 圖的遍歷 231 6.3.1 深度優先搜索 232 6.3.2 廣度優先搜索 234 6.3.3 連通分量 235 6.3.4 雙連通圖 237 6.3.5 有向圖的強連通分量 238 6.4 Z小生成樹 240 6.4.1 Z小生成樹求解和貪心法 240 6.4.2 Kruskal算法 242 6.4.3 Prim算法 244 6.4.4 擴展閱讀:其他建立Z小生成樹的方法 246 6.5 Z短路徑 248 6.5.1 非負權值的單源Z短路徑 248 6.5.2 擴展閱讀:邊上權值為任意值的單源Z短路徑問題 252 6.5.3 所有1;CY=CY點之間的Z短路徑 254 6.5.4 無權值的Z短路徑 257 6.6 活動網絡 259 6.6.1 AOV網絡與拓撲排序 259 6.6.2 AOE網絡與關鍵路徑法 262 小結 267 習題 268 D7章 查找 273 7.1 查找的概念及簡單查找方法 273 7.1.1 查找的基本概念 273 7.1.2 順序查找法 274 7.1.3 折半查找法 276 7.1.4 擴展閱讀:次優查找樹 279 7.1.5 擴展閱讀:斐波那契查找和插值查找 282 7.1.6 擴展閱讀:跳表 283 7.2 二叉查找樹 284 7.2.1 二叉查找樹的概念 285 7.2.2 二叉查找樹的查找 285 7.2.3 二叉查找樹的插入 286 7.2.4 二叉查找樹的刪除 288 7.2.5 二叉查找樹的性能分析 289 7.3 AVL樹 292 7.3.1 AVL樹的概念 292 7.3.2 平衡化旋轉 293 7.3.3 AVL樹的插入 295 7.3.4 AVL樹的刪除 296 7.3.5 AVL樹的性能分析 299 7.4 B樹 300 7.4.1 索引順序表與分塊查找 300 7.4.2 多級索引結構與m叉查找樹 301 7.4.3 B樹的概念 302 7.4.4 B樹上的查找 304 7.4.5 B樹上的插入 305 7.4.6 B樹上的刪除 306 7.4.7 B 樹 308 7.5 擴展閱讀:其他查找樹 311 7.5.1 紅黑樹 311 7.5.2 伸展樹 313 7.5.3 字典樹 315 7.6 散列表及其查找 317 7.6.1 散列的概念 318 7.6.2 常見的散列函數 318 7.6.3 解決衝突的開地址法 321 7.6.4 解決衝突的鏈地址法 327 7.6.5 散列法分析 329 小結 330 習題 330 D8章 排序 335 8.1 排序的概念 335 8.1.1 排序的相關概念 335 8.1.2 排序算法的性能分析 336 8.1.3 數據表的結構定義 337 8.2 插入排序 338 8.2.1 直接插入排序 338 8.2.2 基於靜態鏈表的直接插入排序 339 8.2.3 折半插入排序 341 8.2.4 希爾排序 342 8.3 交換排序 343 8.3.1 起泡排序 344 8.3.2 快速排序 345 8.3.3 快速排序的改進算法 348 8.4 選擇排序 350 8.4.1 簡單選擇排序 350 8.4.2 錦標賽排序 351 8.4.3 堆排序 352 8.5 歸並排序 356 8.5.1 二路歸並排序的設計思路 356 8.5.2 二路歸並排序的遞歸算法 356 8.5.3 擴展閱讀:基於鏈表的歸並排序算法 358 8.5.4 擴展閱讀:迭代的歸並排序算法 359 8.6 基數排序 361 8.6.1 基數排序 362 8.6.2 MSD基數排序 362 8.6.3 LSD基數排序 364 8.7 內排序算法的分析和比較 367 8.7.1 排序方法的下界 367 8.7.2 各種內排序方法的比較 368 8.8 外排序 371 8.8.1 常用的外存儲器與緩衝區 371 8.8.2 基於磁盤的外排序過程 372 8.8.3 m路平衡歸並的過程 374 8.8.4 初始歸並段的生成 378 8.8.5 ZJ歸並樹 381 8.8.6 磁帶歸並排序 382 小結 385 習題 386 附錄A 實訓作業要求與樣例 391 A.1 實訓作業要求 391 A.2 實訓作業樣例 392 附錄B 詞彙索引 397 參考文獻 405 顯示全部信息
" |