數據結構圖解

馬爾切洛·拉·羅卡（Marcello La Rocca），一名研究科學家和全棧工程師，為Twitter、Microsoft和Apple創建大規模Web應用程序和機器學習基礎設施做出了貢獻，詳見https://www.linkedin.com/in/marcellolarocca/。

第1 章 數據結構簡介：為什麼要學

數據結構 ............................................. 1

1.1 歡迎閱讀本書 ........................................... 1

1.1.1 數據結構無處不在 ........................ 2

1.1.2 人人可學數據結構 ........................ 2

1.2 什麼是數據結構 ....................................... 2

1.3 為什麼應該關註數據結構 ........................ 4

1.3.1 什麼時候需要數據結構 ................ 5

1.3.2 我將來需要編寫代碼來實現這

些數據結構嗎 ............................... 7

1.3.3 到底應該怎樣選擇數據結構 ......... 7

1.4 在實際項目中應該如何使用數據結構 ..... 8

1.4.1 以心智模型教你用數據結構 ......... 8

1.4.2 數據結構的應用實例 ................... 10

1.5 要點回顧 .................................................. 13

第2 章 靜態數組：創建你的第一個

數據結構 ............................................ 14

2.1 什麼是數組 .............................................. 14

2.1.1 什麼時候需要使用數組 ............... 15

2.1.2 定義：尺寸固定型與尺寸可變

型 ................................................. 16

2.1.3 值及其索引 .................................. 18

2.1.4 初始化 .......................................... 18

2.2 Python 中的數組 ...................................... 19

2.2.1 Python 中的list 類與

array.array 類 ......................... 20

2.2.2 索引設定 ...................................... 21

2.3 數組中的操作 ...................................... 21

2.3.1 無序數組類 .................................. 22

2.3.2 添加新元素 .................................. 23

2.3.3 刪除某個元素 .............................. 24

2.3.4 查找某個值 .................................. 25

2.3.5 遍歷.............................................. 25

2.4 數組的實際應用 ...................................... 26

2.4.1 數據統計 ...................................... 26

2.4.2 （藏品）集合 .............................. 28

2.4.3 多維數組 ...................................... 29

2.5 要點回顧 .................................................. 29

第3 章 有序數組：查找更快，但需

付出代價 ............................................ 30

3.1 有序數組的意義何在 .............................. 30

3.2 實現有序數組 .......................................... 31

3.2.1 插入.............................................. 32

3.2.2 刪除.............................................. 34

3.2.3 線性查找 ...................................... 35

3.2.4 二分查找 ...................................... 36

3.3 要點回顧 .................................................. 38

第4 章 大O 記號：衡量算法性能的

準則體系 ............................................ 39

4.1 如何選擇最佳方案 .................................. 39

4.1.1 剖面分析 ...................................... 40

4.1.2 漸近分析 ...................................... 41

4.1.3 應該選擇哪種方案 ....................... 41

4.2 大O 記號 ................................................. 41

4.2.1 隨機存取機（RAM）模型 .......... 41

4.2.2 增長速率 ...................................... 42

4.2.3 常見的函數量級 .......................... 44

4.2.4 真實世界裏的增長速率 ............... 45

4.2.5 大O 算術 ..................................... 47

4.2.6 最壞情況分析、平均情況分析

及分攤分析 .................................. 49

4.2.7 資源衡量 ...................................... 50

4.3 漸近分析實例 .......................................... 51

4.3.1 線性查找 ...................................... 51

4.3.2 二分查找 ...................................... 52

4.4 要點回顧 ................................................. 54

第5 章 動態數組：處理尺寸可變的

數據集合 ............................................ 55

5.1 靜態數組的局限性 .................................. 55

5.1.1 尺寸固定 ...................................... 56

5.1.2 權衡利弊 ...................................... 57

5.2 如何增加數組長度 .................................. 58

5.3 獲獎作品展示櫃 ...................................... 58

5.3.1 策略1：每次增加1 個單元 ........ 59

5.3.2 策略2：按固定量增加單元數 .... 60

5.3.3 策略3：容量加倍 ....................... 60

5.3.4 策略對比 ...................................... 61

5.3.5 將各種增加策略用於數組 ........... 62

5.4 數組需要進行縮減嗎 .............................. 63

5.4.1 刪除後減半 .................................. 64

5.4.2 更明智的縮減 .............................. 65

5.5 實現動態數組 .......................................... 65

5.5.1 DynamicArray 類 ......................... 66

5.5.2 插入 ............................................. 66

5.5.3 查找 ............................................. 68

5.5.4 刪除 ............................................. 69

5.6 要點回顧 ................................................. 70

第6 章 鏈表：易於變通的動態集合 .......... 71

6.1 鏈表與數組 .............................................. 71

6.1.1 鏈表的底層機制 .......................... 72

6.1.2 對比數組與鏈表 .......................... 72

6.2 單鏈表 ..................................................... 73

6.2.1 訂單管理 ...................................... 74

6.2.2 實現單鏈表 .................................. 75

6.2.3 插入 ............................................. 76

6.2.4 查找 ............................................. 78

6.2.5 刪除 ............................................. 80

6.2.6 從表首刪除元素 .......................... 81

6.3 有序鏈表 ................................................. 82

6.3.1 在鏈表裏面插入 .......................... 82

6.3.2 能否改進查找操作的性能 ........... 83

6.4 雙鏈表 ..................................................... 83

6.4.1 鏈接雙倍，樂趣翻倍 ................... 84

6.4.2 折返的重要性 .............................. 85

6.4.3 插入 ............................................. 86

6.4.4 查找與遍歷 .................................. 88

6.4.5 刪除 ............................................. 88

6.4.6 拼接兩個鏈表 .............................. 89

6.5 循環鏈表 ................................................. 90

6.5.1 循環鏈表實例 .............................. 90

6.5.2 實現技巧 ...................................... 92

6.6 要點回顧 ................................................. 93

第7 章 抽象數據類型：設計最簡單的

容器——袋 ....................................... 94

7.1 抽象數據類型與數據結構 ....................... 94

7.1.1 定義 ............................................. 95

7.1.2 數組與鏈表：抽象數據類型

還是數據結構 .............................. 96

7.1.3 又一個實例：照明開關 ............... 97

7.2 容器 ......................................................... 99

7.2.1 什麼是容器 .................................. 99

7.2.2 什麼不是容器 ............................ 100

7.2.3 容器的主要特征 ........................ 100

7.3 最簡單的容器：袋 ................................ 101

7.3.1 袋的定義 .................................... 101

7.3.2 袋的應用實例 ............................ 102

7.3.3 袋的實現 .................................... 104

7.4 要點回顧 ................................................ 106

第8 章 棧：處理數據之前先將其

疊放起來 .......................................... 108

8.1 棧作為抽象數據類型 ............................. 108

8.1.1 棧與後進先出策略 ..................... 109

8.1.2 棧的操作 .................................... 109

8.1.3 棧的應用實例 ............................ 110

8.2 棧作為數據結構 .................................... 111

8.2.1 以靜態數組存儲棧的數據 ......... 112

8.2.2 以動態數組存儲棧的數據 ......... 112

8.2.3 鏈表與棧 .................................... 113

8.3 棧的鏈表實現 ........................................ 114

8.3.1 入棧 ............................................ 115

8.3.2 出棧 ............................................ 115

8.3.3 查看 ............................................ 116

8.4 理論與現實 ............................................ 117

8.5 棧的更多應用 ........................................ 119

8.5.1 調用棧 ........................................ 120

8.5.2 表達式求值 ................................ 121

8.5.3 撤銷/重做 ................................... 122

8.5.4 折返 ............................................ 122

8.6 要點回顧 ................................................ 123

第9 章 隊列：按抵達次序留存信息 ........ 124

9.1 隊列作為抽象數據類型 ......................... 124

9.1.1 先進先出策略 ............................ 124

9.1.2 隊列的操作 ................................ 125

9.1.3 隊列的應用實例 ......................... 126

9.2 隊列作為數據結構 ................................ 128

9.2.1 以鏈表實現隊列 ......................... 129

9.2.2 以靜態數組實現隊列 ................. 130

9.2.3 實現方案對比 ............................ 133

9.3 隊列的實現 ............................................ 133

9.3.1 底層靜態數組 ............................ 134

9.3.2 入隊............................................ 136

9.3.3 出隊............................................ 138

9.4 用動態數組會如何 ............................. 140

9.5 隊列的更多應用 .................................... 141

9.5.1 消息傳送系統 ............................ 142

9.5.2 Web 服務器 ................................ 142

9.5.3 操作系統 .................................... 142

9.6 要點回顧 ................................................ 143

第10 章 優先級隊列和堆：根據優先級

處理數據 ........................................ 144

10.1 引入優先級來拓展隊列 ....................... 144

10.1.1 處理漏洞（以改進方式） ..... 145

10.1.2 優先級隊列的抽象數據

類型 ........................................ 146

10.2 優先級隊列作為數據結構 ................... 147

10.2.1 有序鏈表和有序數組 ............. 147

10.2.2 無序鏈表和無序數組 ............. 148

10.2.3 性能概覽 ................................ 148

10.2.4 偏序 ........................................ 149

10.3 堆 ......................................................... 149

10.3.1 特殊的樹結構 ........................ 150

10.3.2 堆的其他性質 ........................ 151

10.3.3 堆的性能 ................................ 152

10.3.4 最大堆和最小堆 ..................... 152

10.4 實現堆 ................................................. 153

10.4.1 如何存儲堆 ............................ 153

10.4.2 構造函數、優先級及輔助

方法 ........................................ 154

10.4.3 插入 ........................................ 155

10.4.4 取頂 ........................................ 158

10.4.5 堆化 ........................................ 161

10.5 優先級隊列的應用實例 ....................... 163

10.6 要點回顧 .............................................. 165

第11 章 二叉查找樹：尋求平衡的

容器 ................................................ 166

11.1 樹的構成要素 ...................................... 166

11.1.1 樹的定義 ................................ 167

11.1.2 從鏈表到樹 ............................ 168

11.1.3 二叉樹 .................................... 169

11.1.4 樹的若幹應用 ........................ 169

11.2 二叉查找樹 .......................................... 170

11.2.1 次序很重要 ............................ 170

11.2.2 類定義和構造函數 ................. 171

11.2.3 查找 ........................................ 171

11.2.4 尋找最大值和最小值 ............. 173

11.2.5 插入 ........................................ 174

11.2.6 刪除 ........................................ 176

11.2.7 所有情況的整合 ..................... 179

11.2.8 遍歷 ........................................ 180

11.2.9 前鄰與後鄰 ............................ 180

11.3 平衡樹 ................................................. 182

11.3.1 二叉查找樹的應用實例 ......... 182

11.3.2 敵手型插入序列 ..................... 183

11.3.3 刪除操作會使樹失衡 ............. 184

11.3.4 調整樹的平衡 ........................ 184

11.4 要點回顧 .............................................. 185

第12 章 字典與散列表：如何構建和

使用關聯式數組 ........................... 186

12.1 字典問題 .............................................. 186

12.1.1 刪除重復項 ............................ 187

12.1.2 字典抽象數據類型 ................. 188

12.2 實現字典的數據結構 .......................... 189

12.2.1 數組 ........................................ 189

12.2.2 鏈表 ........................................ 189

12.2.3 平衡二叉查找樹 ..................... 190

12.2.4 對比總結 ................................ 190

12.3 散列表 ................................................. 190

12.3.1 新的索引方案 ........................ 191

12.3.2 索引操作的開銷 .................... 192

12.3.3 理想模型的問題 .................... 192

12.4 散列 ..................................................... 193

12.4.1 散列函數 ................................ 194

12.4.2 除余法 .................................... 195

12.4.3 乘截法 .................................... 195

12.5 解決沖突 ............................................. 196

12.5.1 結鏈 ....................................... 197

12.5.2 開放式定址 ............................ 199

12.5.3 開放式定址存在的問題 ......... 200

12.5.4 使用散列會帶來的風險 ......... 201

12.6 要點回顧 ............................................. 202

第13 章 圖：學會如何對數據中的

復雜關系進行建模....................... 204

13.1 什麼是圖 ............................................. 204

13.1.1 圖的定義 ................................ 205

13.1.2 好友圖 .................................... 206

13.1.3 有向圖與無向圖 .................... 206

13.1.4 有環圖與無環圖 .................... 207

13.1.5 連通圖和連通分量 ................ 208

13.1.6 作為圖的樹 ............................ 210

13.2 圖的實現 ............................................. 210

13.2.1 鄰接表 .................................... 210

13.2.2 鄰接矩陣 ................................ 213

13.3 圖搜索 ................................................. 214

13.3.1 尋找好友 ................................ 214

13.3.2 廣度優先搜索 ........................ 215

13.3.3 深度優先搜索 ........................ 218

13.4 未來可期 ............................................. 220

13.5 要點回顧 ............................................. 221