《算法之美——隱匿在數據結構背後的原理（C++版）》是2016年3月電子工業出版社出版的圖書，作者是左飛。
基本介紹
- 書名：算法之美——隱匿在數據結構背後的原理（C++版）
- 作者：左飛 著
- ISBN：978-7-121-27718-4
- 頁數：428
- 定價：79.00元
- 出版社：電子工業出版社
- 出版時間：2016年3月出版
- 開本：16開
內容簡介,目錄,
內容簡介
《算法之美——隱匿在數據結構背後的原理（C++版）》圍繞算法與數據結構這個話題，循序漸進、深入淺出地介紹了現代計算機技術中常用的40 余個經典算法，以及回溯法、分治法、貪婪法和動態規劃等算法設計思想。在此過程中，《算法之美——隱匿在數據結構背後的原理（C++版）》也系統地講解了鍊表（包括單向鍊表、單向循環鍊表和雙向循環鍊表）、棧、佇列（包括普通佇列和優先權佇列）、樹（包括二叉樹、哈夫曼樹、堆、紅黑樹、AVL 樹和字典樹）、圖、集合（包括不相交集）與字典等常用數據結構。同時，通過對22 個經典問題（包括約瑟夫環問題、漢諾塔問題、八皇后問題和騎士週遊問題等）的講解，逐步揭開隱匿在數據結構背後的算法原理，力圖幫助讀者夯實知識儲備，激活思維技巧，並最終衝破阻礙編程能力提升的重重藩籬。
《算法之美——隱匿在數據結構背後的原理（C++版）》適合作為大專院校相關專業學生研習算法與數據結構知識的課外參考書。對有意參加信息學競賽的讀者，本書亦有很強的參考價值。此外，鑒於算法與數據結構在求職過程中常常被視為考察重點，所以就臨近畢業的學生或其他欲從事IT 行業的求職者而言，閱讀《算法之美——隱匿在數據結構背後的原理（C++版）》也將對面試備考大有裨益。
目錄
第1 章 從數據到算法 .................................................................. 1
1.1 數據與數據結構 ..................................................................................... 1
1.1.1 數據及其類型 ................................................................................................. 1
1.1.2 數據結構簡介 ................................................................................................. 3
1.2 算法 ......................................................................................................... 5
1.2.1 算法的概念 ..................................................................................................... 5
1.2.2 算法的分析 ..................................................................................................... 8
1.2.3 算法的設計 ................................................................................................... 12
1.3 C++中的STL ........................................................................................ 18
1.3.1 STL 簡介 ...................................................................................................... 19
1.3.2 STL 構成 ...................................................................................................... 20
1.3.3 STL 的不同版本 ........................................................................................... 22
本章參考文獻 ................................................................................................ 23
第2 章 指針與數組——也談中國古代兵制 ................................ 24
2.1 指針 ....................................................................................................... 24
2.1.1 記憶體與地址 ................................................................................................... 24
2.1.2 指針的語法 ................................................................................................... 27
2.1.3 使用指針變數 ............................................................................................... 29
2.1.4 函式與參數傳遞 ........................................................................................... 31
2.2 數組 ....................................................................................................... 36
2.2.1 結構型數據類型 ........................................................................................... 37
2.2.2 數組定義與初始化 ....................................................................................... 37
2.2.3 數組與指針 ................................................................................................... 41
2.2.4 數組的抽象數據類型 ................................................................................... 45
2.3 數組套用舉例 ....................................................................................... 48
2.3.1 Z 字形編排問題 ........................................................................................... 48
2.3.2 大整數乘法問題 ........................................................................................... 51
2.3.3 九宮格問題 ................................................................................................... 52
2.4 動態記憶體管理 ....................................................................................... 53
2.4.1 關鍵字new 和delete .................................................................................... 53
2.4.2 避免記憶體錯誤 ............................................................................................... 56
本章參考文獻 ................................................................................................ 61
第3 章 字元串與模式匹配——夢裡尋她千百度 ......................... 62
3.1 基本概念與定義 ................................................................................... 62
3.1.1 C++中的字元串 ............................................................................................ 62
3.1.2 字元串抽象數據類型 ................................................................................... 65
3.2 文本的精確匹配 ................................................................................... 66
3.2.1 BF 算法 ......................................................................................................... 66
3.2.2 MP 算法 ........................................................................................................ 67
3.2.3 KMP 算法 ..................................................................................................... 72
3.2.4 BM 算法 ....................................................................................................... 75
3.2.5 BMH 算法 ..................................................................................................... 81
3.3 文本的模糊匹配 ................................................................................... 83
3.3.1 全局編輯距離 ............................................................................................... 83
3.3.2 局部最佳對準 ............................................................................................... 86
3.3.3 N 元距離模型 ............................................................................................... 87
3.3.4 語音編碼模型 ............................................................................................... 88
本章參考文獻 ................................................................................................ 89
第4 章 鍊表——老鷹捉小雞 ..................................................... 91
4.1 鍊表的概念 ........................................................................................... 91
4.2 單向鍊表 ............................................................................................... 92
4.2.1 單向鍊表的結構 ........................................................................................... 92
4.2.2 單向鍊表的操作算法 ................................................................................... 94
4.2.3 有序鍊表的合併算法 ................................................................................. 101
4.3 單向循環鍊表 ..................................................................................... 102
4.3.1 單向循環鍊表的結構 ................................................................................. 102
4.3.2 單向循環鍊表的實現 ................................................................................. 103
4.3.3 約瑟夫環的問題 ......................................................................................... 107
4.3.4 魔術師發牌問題 ......................................................................................... 108
4.3.5 拉丁方陣的問題 ......................................................................................... 109
4.4 雙向循環鍊表 ...................................................................................... 110
4.4.1 雙向循環鍊表的結構 ................................................................................. 110
4.4.2 雙向循環鍊表的實現 .................................................................................. 111
4.4.3 維吉尼亞加密法問題 ................................................................................. 115
4.5 游標類的設計與實現 .......................................................................... 117
4.5.1 游標類的結構 ............................................................................................. 117
4.5.2 游標類的實現 ............................................................................................. 118
4.6 STL 與鍊表 ......................................................................................... 122
4.6.1 STL 中鍊表類的接口 ................................................................................. 122
4.6.2 遍歷 ............................................................................................................. 124
4.6.3 元素的插入與刪除 ..................................................................................... 125
本章參考文獻 .............................................................................................. 126
第5 章 先進先出與後進先出——簡單而深刻 .......................... 127
5.1 摞盤子的策略 ..................................................................................... 127
5.1.1 棧的結構 ..................................................................................................... 127
5.1.2 棧的操作及實現 ......................................................................................... 129
5.1.3 括弧匹配問題 ............................................................................................. 132
5.1.4 停車場模擬問題 ......................................................................................... 133
5.2 排隊的智慧 ......................................................................................... 136
5.2.1 佇列的結構 ................................................................................................. 136
5.2.2 佇列的操作及實現 ..................................................................................... 138
5.2.3 舞伴問題 ..................................................................................................... 142
5.2.4 楊輝三角問題 ............................................................................................. 143
5.2.5 遊程編碼問題 ............................................................................................. 145
5.3 優先權佇列——兼談頁面置換算法 .................................................. 146
5.3.1 優先權佇列的結構 ..................................................................................... 146
5.3.2 優先權佇列的實現 ..................................................................................... 149
5.4 STL 中的棧與佇列 ............................................................................. 150
5.4.1 STL 中的stack ........................................................................................... 151
5.4.2 STL 中的queue .......................................................................................... 153
5.4.3 STL 中的priority_queue ............................................................................ 155
本章參考文獻 .............................................................................................. 158
第6 章 遞歸——老和尚講故事 ................................................ 159
6.1 遞歸的概念 ......................................................................................... 159
6.1.1 定義 ............................................................................................................ 159
6.1.2 套用遞歸的原則 ......................................................................................... 162
6.1.3 遞歸和非遞歸的轉化 ................................................................................. 168
6.2 分治法 ................................................................................................. 170
6.2.1 分治法簡述 ................................................................................................. 171
6.2.2 漢諾塔問題 ................................................................................................. 172
6.2.3 傳染病問題 ................................................................................................. 174
6.3 回溯法 ................................................................................................. 176
6.3.1 回溯法簡述 ................................................................................................. 176
6.3.2 迷宮問題 ..................................................................................................... 176
6.3.3 八皇后問題 ................................................................................................. 180
本章參考文獻 .............................................................................................. 183
第7 章 樹——從紅樓夢說起 ................................................... 184
7.1 認識樹這種結構 ................................................................................. 184
7.1.1 基本定義 ..................................................................................................... 184
7.1.2 一些術語 ..................................................................................................... 186
7.1.3 樹的抽象 ..................................................................................................... 187
7.2 花開二枝分外香——二叉樹及相關算法 .......................................... 188
7.2.1 二叉樹的定義 ............................................................................................. 188
7.2.2 二叉樹的性質 ............................................................................................. 190
7.2.3 二叉樹的實現 ............................................................................................. 191
7.2.4 二叉樹的遍歷算法 ..................................................................................... 196
7.2.5 二叉樹線索化算法 ..................................................................................... 200
7.3 合抱之木，生於毫末——從樹到森林 .............................................. 203
7.3.1 樹的存儲表示 ............................................................................................. 203
7.3.2 樹的實現 ..................................................................................................... 206
7.3.3 樹與森林的遍歷算法 ................................................................................. 209
7.3.4 森林與二叉樹的轉換 .................................................................................. 211
7.4 哈夫曼樹——最優二叉樹編碼算法 .................................................. 213
7.4.1 哈夫曼編碼 ................................................................................................. 213
7.4.2 構造哈夫曼樹 ............................................................................................. 215
7.4.3 哈夫曼編碼的實現 ..................................................................................... 216
7.5 堆 ......................................................................................................... 220
7.5.1 堆的概念 ..................................................................................................... 220
7.5.2 堆的建立 ..................................................................................................... 221
7.5.3 堆的操作 ..................................................................................................... 223
7.6 基於STL 實現樹結構 ........................................................................ 224
7.6.1 STL 中的vector .......................................................................................... 224
7.6.2 STL 中的map ............................................................................................. 228
本章參考文獻 .............................................................................................. 230
第8 章 圖——始於哥尼斯堡的七橋問題 .................................. 231
8.1 圖的基本概念 ..................................................................................... 231
8.1.1 圖的定義 ..................................................................................................... 231
8.1.2 圖的術語 ..................................................................................................... 232
8.1.3 圖的運算 ..................................................................................................... 236
8.1.4 圖的抽象數據類型 ..................................................................................... 237
8.2 圖的存儲與表示 ................................................................................. 239
8.2.1 圖的鄰接矩陣表示 ..................................................................................... 239
8.2.2 圖的鄰接表表示 ......................................................................................... 241
8.2.3 兩種表示法的比較 ..................................................................................... 243
8.3 圖的遍歷 ............................................................................................. 244
8.3.1 歐拉路徑與歐拉迴路 ................................................................................. 244
8.3.2 哈密爾頓路徑與哈密爾頓迴路 ................................................................. 248
8.3.3 廣度優先遍歷算法 ..................................................................................... 252
8.3.4 深度優先遍歷算法 ..................................................................................... 254
8.4 最短路徑問題 ..................................................................................... 258
8.4.1 固定起點最短路徑問題 ............................................................................. 258
8.4.2 非固定起點最短路徑問題 ......................................................................... 264
8.4.3 最短路徑的動態規劃解法 ......................................................................... 266
8.5 最小生成樹 ......................................................................................... 273
8.5.1 最小生成樹的定義 ..................................................................................... 273
8.5.2 克魯斯卡爾算法 ......................................................................................... 275
8.5.3 普里姆算法 ................................................................................................. 279
本章參考文獻 .............................................................................................. 283
第9 章 樹形搜尋結構——做一名出色的園藝師 ....................... 284
9.1 二叉搜尋樹 ......................................................................................... 284
9.1.1 二叉搜尋樹的概念 ..................................................................................... 284
9.1.2 二叉搜尋樹的操作 ..................................................................................... 285
9.1.3 二叉搜尋樹的實現 ..................................................................................... 288
9.1.4 二叉搜尋樹的分析 ..................................................................................... 291
9.2 自平衡的二叉搜尋樹——AVL 樹 .................................................... 294
9.2.1 AVL 樹的概念 ............................................................................................ 294
9.2.2 AVL 樹的旋轉 ............................................................................................ 295
9.2.3 AVL 樹的實現 ............................................................................................ 299
9.3 樹中亦有“紅與黑” ......................................................................... 303
9.3.1 紅黑樹的概念 ............................................................................................. 303
9.3.2 紅黑樹的操作 ............................................................................................. 306
9.3.3 紅黑樹的實現 ............................................................................................. 314
9.4 基於Trie 樹的單詞檢索 ..................................................................... 314
9.4.1 Trie 樹的概念 ............................................................................................. 315
9.4.2 Trie 樹的表示 ............................................................................................. 316
9.4.3 Trie 樹的實現 ............................................................................................. 317
本章參考文獻 .............................................................................................. 320
第10 章 集合與字典——再言搜尋之話題 ............................... 321
10.1 集合論基礎 ....................................................................................... 321
10.1.1 集合的概念 ............................................................................................... 321
10.1.2 集合的運算 ............................................................................................... 323
10.2 集合的實現 ....................................................................................... 325
10.2.1 位向量集合 ............................................................................................... 325
10.2.2 單鍊表集合 ............................................................................................... 330
10.3 字典 ................................................................................................... 337
10.3.1 字典的概念 ............................................................................................... 338
10.3.2 搜尋運算 ................................................................................................... 342
10.4 散列 ................................................................................................... 346
10.4.1 散列的概念 ............................................................................................... 347
10.4.2 散列函式 ................................................................................................... 348
10.4.3 字元串散列 ............................................................................................... 351
10.4.4 處理散列衝突 ........................................................................................... 353
10.5 拼寫檢查問題 ................................................................................... 358
10.6 不相交集 ........................................................................................... 363
10.6.1 不相交集的概念 ....................................................................................... 363
10.6.2 不相交集的實現 ....................................................................................... 366
10.6.3 犯罪團伙的問題 ....................................................................................... 369
10.6.4 路徑壓縮的實現 ....................................................................................... 370
10.7 STL 中的set ...................................................................................... 371
本章參考文獻 .............................................................................................. 374
第11 章 排序——有序讓世界更美好 ....................................... 375
11.1 排序問題概述 ................................................................................... 375
11.1.1 基本概念和定義 ....................................................................................... 375
11.1.2 排序算法的分類 ....................................................................................... 376
11.1.3 排序算法的分析 ....................................................................................... 377
11.2 插入排序 ........................................................................................... 378
11.2.1 直接插入排序 ........................................................................................... 378
11.2.2 二分插入排序 ........................................................................................... 380
11.2.3 希爾排序 ................................................................................................... 382
11.3 選擇排序 ........................................................................................... 384
11.3.1 直接選擇排序 ........................................................................................... 384
11.3.2 堆排序 ....................................................................................................... 386
11.4 交換排序 ........................................................................................... 390
11.4.1 冒泡排序 ................................................................................................... 390
11.4.2 雞尾酒排序 ............................................................................................... 392
11.4.3 快速排序 ................................................................................................... 395
11.5 歸併排序 ........................................................................................... 399
11.6 計數排序 ........................................................................................... 403
本章參考文獻 .............................................................................................. 407
附錄 經典求職面試題目 .......................................................... 408
