《數據結構與算法之美（全彩印刷）》是2022年人民郵電出版社出版的圖書。
基本介紹
- 中文名：數據結構與算法之美（全彩印刷）
- 出版時間：2022年11月
- 出版社： 人民郵電出版社
- ISBN： 9787115562050
內容簡介,圖書目錄,作者簡介,
內容簡介
本書結合實際套用場景講解數據結構和算法，涵蓋常用、常考的數據結構和算法的原理講解、代碼實現和套用場景等。
本書分為11章。第1章介紹複雜度分析方法。第2章介紹數組、鍊表、棧和佇列這些基礎的線性表數據結構。第3章介紹遞歸編程技巧、8種經典排序、二分查找及二分查找的變體問題。第4章介紹哈希表、點陣圖、哈希算法和布隆過濾器。第5章介紹樹相關的數據結構，包括二叉樹、二叉查找樹、平衡二叉查找樹、遞歸樹和B+樹。第6章介紹堆，以及堆的各種套用，包括堆排序、優先權佇列、求Top K、求中位數和求百分位數。第7章介紹跳表、並查集、線段樹和樹狀數組這些比較高級的數據結構。第8章介紹字元串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie樹和AC自動機。第9章介紹圖及相關算法，包括深度優先搜尋、廣度優先搜尋、拓撲排序、Dijkstra算法、Floyd算法、A*算法、最小生成樹算法、最大流算法和最大二分匹配等。第10章介紹4種算法思想，包括貪心、分治、回溯和動態規劃。第11章介紹4個經典項目中的數據結構和算法的套用，包括Redis、搜尋引擎、鑒許可權流和短網址服務。另外，附錄A為書中的思考題的解答。
儘管本書的大部分代碼採用Java語言編寫，但本書講解的知識與具體程式語言無關，因此，本書不但適合各種類型的研發工程師，而且可以作為高校計算機相關專業師生的學習用書和培訓學校的教材。
圖書目錄
目錄
第 1章 複雜度分析 1
1.1 複雜度分析（上）：如何分析代碼的執行效率和資源消耗 2
1.1.1 複雜度分析的意義 2
1.1.2 大O複雜度表示法 2
1.1.3 時間複雜度分析方法 4
1.1.4 幾種常見的時間複雜度量級 5
1.1.5 空間複雜度分析方法 7
1.1.6 內容小結 7
1.1.7 思考題 8
1.2 複雜度分析（下）：詳解最好、最壞、平均、均攤這4種時間複雜度 8
1.2.1 最好時間複雜度和最壞時間複雜度 8
1.2.2 平均時間複雜度 9
1.2.3 均攤時間複雜度 10
1.2.4 內容小結 11
1.2.5 思考題 12
第 2章 數組、鍊表、棧和佇列 13
2.1 數組（上）：為什麼數組的下標一般從0開始編號 14
2.1.1 數組的定義 14
2.1.2 定址公式和隨機訪問特性 15
2.1.3 低效的插入和刪除操作 15
2.1.4 警惕數組訪問越界問題 16
2.1.5 容器能否完全替代數組 17
2.1.6 解答本節開篇問題 18
2.1.7 內容小結 18
2.1.8 思考題 18
2.2 數組（下）：數據結構中的數組和程式語言中的數組的區別 19
2.2.1 C/C++中數組的實現方式 19
2.2.2 Java中數組的實現方式 20
2.2.3 JavaScript中數組的實現方式 22
2.2.4 內容小結 23
2.2.5 思考題 23
2.3 鍊表（上）：如何基於鍊表實現LRU快取淘汰算法 23
2.3.1 鍊表的底層存儲結構 24
2.3.2 鍊表的定義和操作 24
2.3.3 鍊表的變形結構 26
2.3.4 鍊表與數組的性能對比 28
2.3.5 解答本節開篇問題 29
2.3.6 內容小結 29
2.3.7 思考題 30
2.4 鍊表（下）：藉助哪些技巧可以輕鬆地編寫鍊表相關的複雜代碼 30
2.4.1 技巧1：理解指針或引用的含義 30
2.4.2 技巧2：警惕指針丟失和記憶體泄露 30
2.4.3 技巧3：利用“哨兵”簡化代碼 31
2.4.4 技巧4：留意邊界條件和特殊情況 33
2.4.5 技巧5：舉例畫圖，輔助思考 34
2.4.6 技巧6：多寫多練，沒有捷徑 34
2.4.7 內容小結 34
2.4.8 思考題 35
2.5 棧：如何實現瀏覽器的前進和後退功能 35
2.5.1 棧的定義 35
2.5.2 順序棧和鏈式棧 35
2.5.3 支持動態擴容的順序棧 36
2.5.4 棧在函式調用中的套用 37
2.5.5 棧在表達式求值中的套用 38
2.5.6 棧在括弧匹配中的套用 38
2.5.7 解答本節開篇問題 39
2.5.8 內容小結 40
2.5.9 思考題 40
2.6 佇列：如何實現執行緒池等有限資源池的請求排隊功能 40
2.6.1 佇列的定義 40
2.6.2 順序佇列和鏈式佇列 41
2.6.3 循環佇列 42
2.6.4 阻塞佇列和並發佇列 44
2.6.5 解答本節開篇問題 44
2.6.6 內容小結 45
2.6.7 思考題 45
第3章 遞歸、排序、二分查找 46
3.1 遞歸：如何用3行代碼找到“最終推薦人” 47
3.1.1 什麼是遞歸 47
3.1.2 遞歸需要滿足的3個條件 48
3.1.3 如何編寫遞歸代碼 48
3.1.4 編寫遞歸代碼的難點 49
3.1.5 警惕遞歸代碼出現堆疊溢出 49
3.1.6 警惕遞歸代碼的重複計算問題 50
3.1.7 將遞歸代碼改寫為非遞歸代碼 51
3.1.8 解答本節開篇問題 52
3.1.9 內容小結 52
3.1.10 思考題 52
3.2 尾遞歸：如何藉助尾遞歸避免遞歸過深導致的堆疊溢出 53
3.2.1 遞歸產生堆疊溢出的原因 53
3.2.2 什麼樣的遞歸代碼可以改寫為尾遞歸 54
3.2.3 尾遞歸真的可以避免堆疊溢出嗎 54
3.2.4 思考題 55
3.3 排序算法基礎：從哪幾個方面分析排序算法 55
3.3.1 排序算法的執行效率 55
3.3.2 排序算法的記憶體消耗 56
3.3.3 排序算法的穩定性 56
3.3.4 內容小結 57
3.3.5 思考題 57
3.4 O(n2)排序：為什麼插入排序比冒泡排序更受歡迎 58
3.4.1 冒泡排序 58
3.4.2 插入排序 60
3.4.3 選擇排序 62
3.4.4 解答本節開篇問題 63
3.4.5 內容小結 64
3.4.6 思考題 64
3.5 O(nlogn)排序：如何藉助快速排序思想快速查找第K大元素 64
3.5.1 歸併排序的原理和實現 64
3.5.2 歸併排序的性能分析 66
3.5.3 快速排序的原理和實現 68
3.5.4 快速排序的性能分析 70
3.5.5 解答本節開篇問題 71
3.5.6 內容小結 72
3.5.7 思考題 72
3.6 線性排序：如何根據年齡給100萬個用戶排序 72
3.6.1 桶排序 73
3.6.2 計數排序 74
3.6.3 基數排序 76
3.6.4 解答本節開篇問題 77
3.6.5 內容小結 77
3.6.6 思考題 77
3.7 排序最佳化：如何實現一個高性能的通用的排序函式 78
3.7.1 如何選擇合適的排序算法 78
3.7.2 如何最佳化快速排序 79
3.7.3 排序函式舉例分析 79
3.7.4 內容小結 80
3.7.5 思考題 80
3.8 二分查找：如何用最省記憶體的方式實現快速查找功能 80
3.8.1 無處不在的二分思想 81
3.8.2 O(logn)驚人的查找速度 82
3.8.3 二分查找的遞歸與非遞歸實現 82
3.8.4 二分查找套用場景的局限性 83
3.8.5 解答本節開篇問題 84
3.8.6 內容小結 85
3.8.7 思考題 85
3.9 二分查找的變體：如何快速定位IP位址對應的歸屬地 85
3.9.1 什麼是二分查找變體問題 86
3.9.2 變體問題1：查找第 一個值等於給定值的元素 86
3.9.3 變體問題2：查找最後一個值等於給定值的元素 88
3.9.4 變體問題3：查找第 一個值大於或等於給定值的元素 88
3.9.5 變體問題4：查找最後一個值小於或等於給定值的元素 89
3.9.6 解答本節開篇問題 89
3.9.7 內容小結 90
3.9.8 思考題 90
第4章 哈希表、點陣圖和哈希算法 91
4.1 哈希表（上）：Word軟體的單詞拼寫檢查功能是如何實現的 92
4.1.1 哈希思想 92
4.1.2 哈希函式 93
4.1.3 哈希衝突 93
4.1.4 解答本節開篇問題 95
4.1.5 內容小結 95
4.1.6 思考題 96
4.2 哈希表（中）：如何打造一個工業級的哈希表 96
4.2.1 設計哈希函式 96
4.2.2 解決裝載因子過大的問題 97
4.2.3 避免低效的擴容 98
4.2.4 選擇合適的衝突解決方法 99
4.2.5 工業級的哈希表舉例分析 100
4.2.6 解答本節開篇問題 100
4.2.7 內容小結 101
4.2.8 思考題 101
4.3 哈希表（下）：如何利用哈希表最佳化LRU快取淘汰算法 101
4.3.1 LRU快取淘汰算法 102
4.3.2 Java LinkedHashMap 104
4.3.3 內容小結 105
4.3.4 思考題 105
4.4 點陣圖：如何實現網頁“爬蟲”中的網址連結去重功能 106
4.4.1 基於哈希表的解決方案 106
4.4.2 基於點陣圖的解決方案 106
4.4.3 基於布隆過濾器的解決方案 108
4.4.4 回答本節開篇問題 110
4.4.5 內容小結 110
4.4.6 思考題 111
4.5 哈希算法：如何防止資料庫脫庫後用戶信息泄露 111
4.5.1 哈希算法介紹 111
4.5.2 套用1：安全加密 112
4.5.3 套用2：唯一標識 113
4.5.4 套用3：數據校驗 113
4.5.5 套用4：哈希函式 113
4.5.6 套用5：負載均衡 114
4.5.7 套用6：數據分片 114
4.5.8 套用7：分散式存儲 115
4.5.9 解答本節開篇問題 116
4.5.10 內容小結 116
4.5.11 思考題 116
第5章 樹 117
5.1 樹和二叉樹：什麼樣的二叉樹適合用數組存儲 118
5.1.1 樹的定義 118
5.1.2 二叉樹的定義 118
5.1.3 二叉樹的存儲 119
5.1.4 二叉樹的遍歷 120
5.1.5 解答本節開篇問題 122
5.1.6 內容小結 122
5.1.7 思考題 122
5.2 二叉查找樹：相比哈希表，二叉查找樹有何優勢 122
5.2.1 二叉查找樹的定義和操作 123
5.2.2 支持重複數據的二叉查找樹 126
5.2.3 二叉查找樹的性能分析 126
5.2.4 解答本節開篇問題 127
5.2.5 內容小結 128
5.2.6 思考題 128
5.3 平衡二叉查找樹：為什麼紅黑樹如此受歡迎 128
5.3.1 平衡二叉查找樹的定義 128
5.3.2 紅黑樹的定義 129
5.3.3 紅黑樹的性能分析 129
5.3.4 解答本節開篇問題 130
5.3.5 內容小結 130
5.3.6 思考題 131
5.4 遞歸樹：如何藉助樹求遞歸算法的時間複雜度 131
5.4.1 遞歸樹時間複雜度分析法 131
5.4.2 實戰1：快速排序的時間複雜度分析 132
5.4.3 實戰2：斐波那契數列的時間複雜度分析 133
5.4.4 實戰3：全排列的時間複雜度分析 133
5.4.5 內容小結 135
5.4.6 思考題 135
5.5 B+樹：MySQL資料庫索引是如何實現的 135
5.5.1 典型需求：按值查詢和按區間查詢 135
5.5.2 基於哈希表和二叉查找樹的解決方案 136
5.5.3 基於B+樹的解決方案 136
5.5.4 內容小結 139
5.5.5 思考題 140
第6章 堆 141
6.1 堆：如何維護動態集合的最值 142
6.1.1 堆的定義 142
6.1.2 堆的存儲 142
6.1.3 往堆中插入元素 143
6.1.4 刪除堆頂元素 144
6.1.5 刪除任意元素 145
6.1.6 堆的性能分析 145
6.1.7 解答本節開篇問題 145
6.1.8 內容小結 146
6.1.9 思考題 146
6.2 堆排序：為什麼說堆排序沒有快速排序快 147
6.2.1 堆排序之建堆 147
6.2.2 堆排序之排序 149
6.2.3 堆排序的性能分析 149
6.2.4 解答本節開篇問題 150
6.2.5 內容小結 150
6.2.6 思考題 151
6.3 堆的套用：如何快速獲取Top 10熱門搜尋關鍵字 151
6.3.1 堆的套用1：優先權佇列 151
6.3.2 堆的套用2：求Top K 152
6.3.3 堆的套用3：求中位數和百分位數 153
6.3.4 解答本節開篇問題 155
6.3.5 內容小結 155
6.3.6 思考題 156
第7章 跳表、並查集、線段樹和樹狀數組 157
7.1 跳表：Redis中的有序集合類型是如何實現的 158
7.1.1 跳表的由來 158
7.1.2 用跳表查詢到底有多快 159
7.1.3 跳表是不是很浪費記憶體 160
7.1.4 高效插入和刪除 161
7.1.5 跳表索引動態更新 162
7.1.6 解答本節開篇問題 162
7.1.7 內容小結 163
7.1.8 思考題 163
7.2 並查集：路徑壓縮和按秩合併這兩個最佳化是否衝突 163
7.2.1 並查集的由來 163
7.2.2 基於鍊表的實現思路 164
7.2.3 基於樹的實現思路 166
7.2.4 內容小結 168
7.2.5 思考題 168
7.3 線段樹：如何查找獵聘網中積分排在第K位的獵頭 168
7.3.1 區間統計問題 169
7.3.2 線段樹的其他套用 172
7.3.3 解答本節開篇問題 174
7.3.4 內容小結 174
7.3.5 思考題 174
7.4 樹狀數組：如何實現一個高性能、低延遲的實時排行榜 174
7.4.1 “前綴和”問題 175
7.4.2 樹狀數組與線段樹的對比 177
7.4.3 解答本節開篇問題 177
7.4.4 內容小結 178
7.4.5 思考題 178
第8章 字元串匹配算法 179
8.1 BF算法：程式語言中的查找、替換函式是怎樣實現的 180
8.1.1 BF算法的原理與實現 180
8.1.2 BF算法的性能分析 181
8.1.3 解答本節開篇問題 181
8.1.4 內容小結 182
8.1.5 思考題 182
8.2 RK算法：如何藉助哈希算法實現高效的字元串匹配 182
8.2.1 RK算法的原理與實現 182
8.2.2 RK算法的性能分析 183
8.2.3 內容小結 184
8.2.4 思考題 184
8.3 BM算法：如何實現文本編輯器中的查找和替換功能 185
8.3.1 BM算法的核心思想 185
8.3.2 BM算法的原理分析 186
8.3.3 BM算法的代碼實現 188
8.3.4 BM算法的性能分析 192
8.3.5 解答本節開篇問題 193
8.3.6 內容小結 193
8.3.7 思考題 193
8.4 KMP算法：如何藉助BM算法理解KMP算法 194
8.4.1 KMP算法的基本原理 194
8.4.2 失效函式的計算方法 196
8.4.3 KMP算法的性能分析 197
8.4.4 內容小結 198
8.4.5 思考題 198
8.5 Trie樹：如何實現搜尋引擎的搜尋關鍵字提示功能 198
8.5.1 Trie樹的定義 199
8.5.2 Trie樹的代碼實現 200
8.5.3 Trie樹的性能分析 201
8.5.4 Trie樹與哈希表、紅黑樹的比較 202
8.5.5 解答本節開篇問題 202
8.5.6 內容小結 203
8.5.7 思考題 204
8.6 AC自動機：如何用多模式串匹配實現敏感詞過濾 204
8.6.1 基於單模式串的敏感詞過濾 204
8.6.2 基於Trie樹的敏感詞過濾 205
8.6.3 基於AC自動機的敏感詞過濾 205
8.6.4 AC自動機的性能分析 208
8.6.5 內容小結 209
8.6.6 思考題 209
第9章 圖 210
9.1 圖的表示：如何存儲微博、微信等社交網路中的好友關係 211
9.1.1 圖的定義 211
9.1.2 鄰接矩陣的存儲方法 212
9.1.3 鄰接表的存儲方法 213
9.1.4 解答本節開篇問題 214
9.1.5 內容小結 215
9.1.6 思考題 215
9.2 深度優先搜尋和廣度優先搜尋：如何找出社交網路中的三度好友關係 216
9.2.1 什麼是搜尋算法 216
9.2.2 廣度優先搜尋 217
9.2.3 深度優先搜尋 219
9.2.4 解答本節開篇問題 220
9.2.5 內容小結 220
9.2.6 思考題 220
9.3 拓撲排序：如何確定代碼源檔案的編譯依賴關係 221
9.3.1 什麼是拓撲排序 221
9.3.2 利用Kahn算法實現拓撲排序 222
9.3.3 利用深度優先搜尋實現拓撲排序 222
9.3.4 利用拓撲排序檢測環 223
9.3.5 解答本節開篇問題 224
9.3.6 內容小結 224
9.3.7 思考題 224
9.4 單源最短路徑：地圖軟體如何“計算”最優出行路線 225
9.4.1 最短路徑算法介紹 225
9.4.2 Dijkstra算法的原理與實現 225
9.4.3 Dijkstra算法的性能分析 228
9.4.4 Dijkstra算法思想的套用 228
9.4.5 解答本節開篇問題 229
9.4.6 內容小結 230
9.4.7 思考題 230
9.5 多源最短路徑：如何利用Floyd算法解決傳遞閉包問題 231
9.5.1 Floyd算法的原理與實現 231
9.5.2 Floyd算法的性能分析 232
9.5.3 利用Floyd算法求解傳遞閉包 232
9.5.4 內容小結 233
9.5.5 思考題 233
9.6 啟發式搜尋：如何用A*算法實現遊戲中的尋路功能 233
9.6.1 什麼是次優路線 234
9.6.2 A*算法的原理與實現 234
9.6.3 A*算法與Dijkstra算法的對比 236
9.6.4 解答本節開篇問題 237
9.6.5 內容小結 237
9.6.6 思考題 238
9.7 最小生成樹：如何隨機生成遊戲中的迷宮地圖 238
9.7.1 什麼是最小生成樹 238
9.7.2 Kruskal算法的原理與實現 239
9.7.3 Prim算法的原理與實現 240
9.7.4 解答本節開篇問題 242
9.7.5 內容小結 244
9.7.6 思考題 245
9.8 最大流：如何解決單身交友聯誼中的最多匹配問題 245
9.8.1 什麼是最大流 245
9.8.2 Ford-Fulkerson方法 246
9.8.3 Edmonds-Karp算法 247
9.8.4 最大二分匹配 249
9.8.5 解答本節開篇問題 249
9.8.6 內容小結 249
9.8.7 思考題 250
第 10章 貪心、分治、回溯和動態規劃 251
10.1 貪心算法：如何利用貪心算法實現霍夫曼編碼 252
10.1.1 如何理解貪心算法 252
10.1.2 貪心算法的套用示例 253
10.1.3 解答本節開篇問題 255
10.1.4 內容小結 256
10.1.5 思考題 256
10.2 分治算法：談一談大規模計算框架MapReduce中的分治思想 256
10.2.1 如何理解分治算法 257
10.2.2 分治算法的套用示例 257
10.2.3 分治算法在大數據處理中的套用 259
10.2.4 解答本節開篇問題 259
10.2.5 內容小結 260
10.2.6 思考題 260
10.3 回溯算法：從電影《蝴蝶效應》中學習回溯算法的核心思想 260
10.3.1 如何理解回溯算法 261
10.3.2 八皇后問題 261
10.3.3 0-1背包問題 262
10.3.4 正則表達式匹配問題 263
10.3.5 內容小結 264
10.3.6 思考題 264
10.4 初識動態規劃：如何巧妙解決“雙11”購物時的湊單問題 264
10.4.1 動態規劃的學習路線 265
10.4.2 利用動態規劃解決0-1背包問題 265
10.4.3 0-1背包問題的升級版 269
10.4.4 解答本節開篇問題 270
10.4.5 內容小結 271
10.4.6 思考題 272
10.5 動態規劃理論：徹底理解最優子結構、無後效性和重複子問題 272
10.5.1 “一個模型和三個特徵”理論介紹 272
10.5.2 “一個模型和三個特徵”的套用示例 273
10.5.3 動態規劃的兩種解題方法 274
10.5.4 4種算法思想的比較分析 277
10.5.5 內容小結 277
10.5.6 思考題 278
10.6 動態規劃實戰：如何實現搜尋引擎中的拼寫糾錯功能 278
10.6.1 如何量化兩個字元串的相似度 278
10.6.2 如何通過編程計算萊文斯坦距離 279
10.6.3 如何通過編程計算最長公共子串長度 281
10.6.4 解答本節開篇問題 282
10.6.5 內容小結 283
10.6.6 思考題 283
第 11章 數據結構和算法實戰 284
11.1 實戰1：剖析Redis的常用數據類型對應的數據結構 285
11.1.1 Redis資料庫介紹 285
11.1.2 列表（list） 285
11.1.3 哈希（hash） 286
11.1.4 集合（set） 286
11.1.5 有序集合（sorted set） 287
11.1.6 數據結構的持久化問題 287
11.1.7 總結和引申 288
11.1.8 思考題 288
11.2 實戰2：剖析搜尋引擎背後的經典數據結構和算法 288
11.2.1 搜尋引擎系統的整體介紹 288
11.2.2 蒐集 289
11.2.3 分析 290
11.2.4 索引 292
11.2.5 查詢 292
11.2.6 總結和引申 293
11.2.7 思考題 293
11.3 實戰3：剖析微服務鑒權和限流背後的數據結構和算法 293
11.3.1 鑒權背景介紹 294
11.3.2 如何實現快速鑒權 294
11.3.3 限流背景介紹 297
11.3.4 如何實現精準限流 297
11.3.5 總結和引申 298
11.3.6 思考題 299
11.4 實戰4：用學過的數據結構和算法實現短網址服務 299
11.4.1 短網址服務的整體介紹 299
11.4.2 通過哈希算法生成短網址 299
11.4.3 通過ID生成器生成短網址 302
11.4.4 總結和引申 303
11.4.5 思考題 303
附錄A 思考題答案 304
作者簡介
王爭，前Google工程師，微信公眾號【小爭哥】作者，GitHub上算法教程Star數排名前列。熱衷分享，致力於通俗易懂地講解數據結構和算法，幫助廣大程式設計師攻克算法學習、算法刷題、算法面試三項難關。
