本書是備受廣大讀者推崇的數(shù)據(jù)結(jié)構(gòu)與算法入門教程,已在GitHub獲得超60k的 Star,并多次登頂GitHub Trending。書中系統(tǒng)介紹了數(shù)據(jù)結(jié)構(gòu)與算法基礎、復雜度分析、數(shù)組與鏈表、棧與隊列、哈希表、樹、堆、圖、搜索、排序、分治、回溯、動態(tài)規(guī)劃和貪心算法等核心知識,通過清晰易懂的解釋和豐富的代碼示例,以及生動形象的全彩插圖和在線動畫圖解,揭示算法工作原理和數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn),教授讀者如何選擇和設計算法來解決不同類型的問題,切實提升編程技能,構(gòu)建完整的數(shù)據(jù)結(jié)構(gòu)與算法知識體系。
動畫圖解:重點和難點知識通過動畫以圖解形式展示,內(nèi)容清晰易懂、學習曲線平滑,引導初學者探索數(shù)據(jù)結(jié)構(gòu)與算法的知識地圖。
一鍵運行:源代碼可一鍵運行,幫助讀者在練習中提升編程技能,了解算法工作原理和數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn)。
配套齊全:附贈源代碼、思維導圖和書簽。
靳宇棟(@krahets) 前華為高級算法工程師,上海交通大學碩士,西安交通大學本科,專注于3D重建與渲染、3D生成算法的研究。曾在VEX機器人世界錦標賽拔得頭籌、全球人工智能創(chuàng)新大賽一等獎。喜歡在開源社區(qū)分享知識,作品的GitHub Star超60,000,訂閱人數(shù)超460,000。
序
前言
第 1章 初識算法 1
1.1 算法無處不在 1
1.2 算法是什么 5
1.2.1 算法定義 5
1.2.2 數(shù)據(jù)結(jié)構(gòu)定義 5
1.2.3 數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系 5
1.3 小結(jié) 7
第 2章 復雜度分析 9
2.1 算法效率評估 9
2.1.1 實際測試 9
2.1.2 理論估算 10
2.2 迭代與遞歸 10
2.2.1 迭代 11
2.2.2 遞歸 13
2.2.3 兩者對比 18
2.3 時間復雜度 19
2.3.1 統(tǒng)計時間增長趨勢 20
2.3.2 函數(shù)漸近上界 21
2.3.3 推算方法 22
2.3.4 常見類型 23
2.3.5 最差、最佳、平均時間復雜度 30
2.4 空間復雜度 32
2.4.1 算法相關(guān)空間 32
2.4.2 推算方法 33
2.4.3 常見類型 34
2.4.4 權(quán)衡時間與空間 38
2.5 小結(jié) 39
第3章 數(shù)據(jù)結(jié)構(gòu) 42
3.1 數(shù)據(jù)結(jié)構(gòu)分類 42
3.1.1 邏輯結(jié)構(gòu):線性與非線性 42
3.1.2 物理結(jié)構(gòu):連續(xù)與分散 43
3.2 基本數(shù)據(jù)類型 45
3.3 數(shù)字編碼* 46
3.3.1 原碼、反碼和補碼 46
3.3.2 浮點數(shù)編碼 49
3.4 字符編碼* 50
3.4.1 ASCII字符集 50
3.4.2 GBK字符集 51
3.4.3 Unicode字符集 51
3.4.4 UTF-8編碼 53
3.4.5 編程語言的字符編碼 54
3.5 小結(jié) 55
第4章 數(shù)組與鏈表 58
4.1 數(shù)組 58
4.1.1 數(shù)組常用操作 58
4.1.2 數(shù)組的優(yōu)點與局限性 62
4.1.3 數(shù)組典型應用 63
4.2 鏈表 63
4.2.1 鏈表常用操作 64
4.2.2 數(shù)組與鏈表對比 67
4.2.3 常見鏈表類型 67
4.2.4 鏈表典型應用 68
4.3 列表 69
4.3.1 列表常用操作 69
4.3.2 列表實現(xiàn) 71
4.4 內(nèi)存與緩存* 73
4.4.1 計算機存儲設備 73
4.4.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)存效率 75
4.4.3 數(shù)據(jù)結(jié)構(gòu)的緩存效率 75
4.5 小結(jié) 76
第5章 棧與隊列 81
5.1 棧 81
5.1.1 棧的常用操作 81
5.1.2 棧的實現(xiàn) 82
5.1.3 兩種實現(xiàn)對比 86
5.1.4 棧的典型應用 87
5.2 隊列 87
5.2.1 隊列常用操作 88
5.2.2 隊列實現(xiàn) 89
5.2.3 隊列典型應用 94
5.3 雙向隊列 95
5.3.1 雙向隊列常用操作 95
5.3.2 雙向隊列實現(xiàn)* 96
5.3.3 雙向隊列應用 104
5.4 小結(jié) 104
第6章 哈希表 107
6.1 哈希表 107
6.1.1 哈希表常用操作 108
6.1.2 哈希表簡單實現(xiàn) 109
6.1.3 哈希沖突與擴容 111
6.2 哈希沖突 113
6.2.1 鏈式地址 113
6.2.2 開放尋址 116
6.2.3 編程語言的選擇 120
6.3 哈希算法 120
6.3.1 哈希算法的目標 121
6.3.2 哈希算法的設計 122
6.3.3 常見哈希算法 124
6.3.4 數(shù)據(jù)結(jié)構(gòu)的哈希值 124
6.4 小結(jié) 125
第7章 樹 129
7.1 二叉樹 129
7.1.1 二叉樹常見術(shù)語 129
7.1.2 二叉樹基本操作 131
7.1.3 常見二叉樹類型 132
7.1.4 二叉樹的退化 134
7.2 二叉樹遍歷 135
7.2.1 層序遍歷 135
7.2.2 前序、中序、后序遍歷 136
7.3 二叉樹數(shù)組表示 138
7.3.1 表示完美二叉樹 138
7.3.2 表示任意二叉樹 139
7.3.3 優(yōu)點與局限性 142
7.4 二叉搜索樹 142
7.4.1 二叉搜索樹的操作 143
7.4.2 二叉搜索樹的效率 151
7.4.3 二叉搜索樹常見應用 151
7.5 AVL樹* 152
7.5.1 AVL樹常見術(shù)語 153
7.5.2 AVL樹旋轉(zhuǎn) 154
7.5.3 AVL樹常用操作 160
7.5.4 AVL樹典型應用 161
7.6 小結(jié) 162
第8章 堆 165
8.1 堆 165
8.1.1 堆的常用操作 166
8.1.2 堆的實現(xiàn) 167
8.1.3 堆的常見應用 177
8.2 建堆操作 177
8.2.1 借助入堆操作實現(xiàn) 177
8.2.2 通過遍歷堆化實現(xiàn) 178
8.2.3 復雜度分析 178
8.3 Top-k問題 180
8.3.1 方法一:遍歷選擇 180
8.3.2 方法二:排序 180
8.3.3 方法三:堆 181
8.4 小結(jié) 182
第9章 圖 184
9.1 圖 184
9.1.1 圖的常見類型與術(shù)語 185
9.1.2 圖的表示 186
9.1.3 圖的常見應用 188
9.2 圖的基礎操作 188
9.2.1 基于鄰接矩陣的實現(xiàn) 188
9.2.2 基于鄰接表的實現(xiàn) 192
9.2.3 效率對比 196
9.3 圖的遍歷 196
9.3.1 廣度優(yōu)先遍歷 196
9.3.2 深度優(yōu)先遍歷 198
9.4 小結(jié) 200
第 10章 搜索 203
10.1 二分查找 203
10.1.1 區(qū)間表示方法 207
10.1.2 優(yōu)點與局限性 208
10.2 二分查找插入點 209
10.2.1 無重復元素的情況 209
10.2.2 存在重復元素的情況 210
10.3 二分查找邊界 212
10.3.1 查找左邊界 212
10.3.2 查找右邊界 212
10.4 哈希優(yōu)化策略 214
10.4.1 線性查找:以時間換空間 214
10.4.2 哈希查找:以空間換時間 215
10.5 重識搜索算法 217
10.5.1 暴力搜索 217
10.5.2 自適應搜索 218
10.5.3 搜索方法選取 218
10.6 小結(jié) 220
第 11章 排序 222
11.1 排序算法 222
11.1.1 評價維度 222
11.1.2 理想排序算法 223
11.2 選擇排序 224
11.3 冒泡排序 229
11.3.1 算法流程 231
11.3.2 效率優(yōu)化 232
11.3.3 算法特性 233
11.4 插入排序 233
11.4.1 算法流程 234
11.4.2 算法特性 235
11.4.3 插入排序的優(yōu)勢 235
11.5 快速排序 235
11.5.1 算法流程 239
11.5.2 算法特性 240
11.5.3 快速排序為什么快 240
11.5.4 基準數(shù)優(yōu)化 241
11.5.5 尾遞歸優(yōu)化 242
11.6 歸并排序 242
11.6.1 算法流程 243
11.6.2 算法特性 248
11.6.3 鏈表排序 248
11.7 堆排序 249
11.7.1 算法流程 249
11.7.2 算法特性 250
11.8 桶排序 250
11.8.1 算法流程 251
11.8.2 算法特性 252
11.8.3 如何實現(xiàn)平均分配 252
11.9 計數(shù)排序 253
11.9.1 簡單實現(xiàn) 254
11.9.2 完整實現(xiàn) 255
11.9.3 算法特性 256
11.9.4 局限性 256
11.10 基數(shù)排序 257
11.10.1 算法流程 257
11.10.2 算法特性 259
11.11 小結(jié) 259
第 12章 分治 263
12.1 分治算法 263
12.1.1 如何判斷分治問題 264
12.1.2 通過分治提升效率 264
12.1.3 分治常見應用 266
12.2 分治搜索策略 267
12.3 構(gòu)建二叉樹問題 269
12.4 漢諾塔問題 273
12.5 小結(jié) 280
第 13章 回溯 282
13.1 回溯算法 282
13.1.1 嘗試與回退 283
13.1.2 剪枝 288
13.1.3 框架代碼 289
13.1.4 常用術(shù)語 291
13.1.5 優(yōu)點與局限性 291
13.1.6 回溯典型例題 292
13.2 全排列問題 292
13.2.1 無相等元素的情況 293
13.2.2 考慮相等元素的情況 295
13.3 子集和問題 298
13.3.1 無重復元素的情況 298
13.3.2 考慮重復元素的情況 302
13.4 n 皇后問題 304
13.5 小結(jié) 308
第 14章 動態(tài)規(guī)劃 310
14.1 初探動態(tài)規(guī)劃 310
14.1.1 方法一:暴力搜索 311
14.1.2 方法二:記憶化搜索 313
14.1.3 方法三:動態(tài)規(guī)劃 314
14.1.4 空間優(yōu)化 316
14.2 動態(tài)規(guī)劃問題特性 316
14.2.1 最優(yōu)子結(jié)構(gòu) 316
14.2.2 無后效性 319
14.3 動態(tài)規(guī)劃解題思路 321
14.3.1 問題判斷 321
14.3.2 問題求解步驟 322
14.4 0-1 背包問題 332
14.5 完全背包問題 343
14.5.1 完全背包問題 344
14.5.2 零錢兌換問題 I348
14.5.3 零錢兌換問題II 350
14.6 編輯距離問題 352
14.7 小結(jié) 356
第 15章 貪心 359
15.1 貪心算法 359
15.1.1 貪心算法的優(yōu)點與局限性 360
15.1.2 貪心算法特性 361
15.1.3 貪心算法解題步驟 362
15.1.4 貪心算法典型例題 363
15.2 分數(shù)背包問題 363
15.3 最大容量問題 366
15.4 最大切分乘積問題 373
15.5 小結(jié) 377
附錄A 術(shù)語表 379