算法訓練營：入門篇（全彩版）

第1章 C++基礎知識 1
1.1 開啟算法之旅 1
1.2 常用的數據類型 2
1.3 玩轉輸入和輸出 2
1.4 常用的運算符 3
1.5 選擇結構語句 5
1.5.1 if條件語句 5
1.5.2 switch條件語句 9
1.6 循環結構語句 10
1.6.1 for語句 10
1.6.2 while語句 13
1.6.3 do while語句 14
1.7 巧用數組 15
1.7.1 一維數組 15
1.7.2 二維數組 17
1.8 玩轉字符串 18
1.8.1 C風格的字符串 19
1.8.2 C++ string類型的
字符串 20
1.9 結構體的應用 21
1.10 指針的應用 22

第2章 算法之美 24
2.1 算法復雜度 24
2.1.1 時間復雜度 27
2.1.2 空間復雜度 27
2.2 函數 30
2.2.1 標準函數 30
2.2.2 傳值參數 31
2.2.3 引用參數 31
2.2.4 數組參數 32
2.3 遞歸 33
2.3.1 遞歸函數 33
2.3.2 遞歸的原理 33

第3章 線性表的應用 37
3.1 順序表 37
3.1.1 插入 38
3.1.2 刪除 39
3.2 鏈表 40
3.2.1 單鏈表 40
3.2.2 雙向鏈表 43
3.2.3 循環鏈表 45
3.2.4 靜態鏈表 46
3.3 棧 49
3.3.1 入棧 49
3.3.2 出棧 49
3.3.3 取棧頂元素 50
3.4 隊列 50
3.4.1 順序隊列 51
3.4.2 循環隊列 53
3.5 STL中的常用函數和容器 56
3.5.1 sort() 57
3.5.2 vector（向量） 58
訓練 角谷猜想 59
3.5.3 stack（棧） 60
訓練 數字游戲 60
3.5.4 queue（隊列） 61
訓練 騎士移動 61
3.5.5 list（雙向鏈表） 63
訓練 新兵隊列訓練 64

第4章 樹的應用 66
4.1 樹 66
4.1.1 樹的存儲 68
4.1.2 樹、森林與二叉樹的
轉換 71
4.2 二叉樹 73
4.2.1 二叉樹的性質 74
4.2.2 滿二叉樹和完全二
叉樹 75
4.2.3 二叉樹的存儲結構 78
4.3 二叉樹遍歷 80
4.3.1 先序遍歷 80
4.3.2 中序遍歷 83
4.3.3 後序遍歷 86
4.3.4 層次遍歷 90
訓練1 新二叉樹 92
訓練2 二叉樹遍歷 93
4.4 哈夫曼樹 95
4.4.1 哈夫曼編碼 95
4.4.2 哈夫曼編碼的長度
計算方法 108
訓練1 圍欄修復 109
訓練2 信息熵 110
4.5 二叉搜索樹 112
4.5.1 二叉搜索樹原理詳解 112
4.5.2 查找 112
4.5.3 插入 115
4.5.4 創建 116
4.5.5 刪除 117
訓練1 落葉 122
訓練2 完全二叉搜索樹 124

第5章 圖論基礎 127
5.1 圖的存儲 128
5.1.1 鄰接矩陣 128
5.1.2 邊集數組 129
5.1.3 鄰接表 130
5.1.4 鏈式前向星 133
5.1.5 圖的存儲技巧 136
5.2 圖的遍歷 136
5.2.1 廣度優先遍歷 136
5.2.2 深度優先遍歷 140
訓練1 最大的節點 144
訓練2 油田 145

第6章 算法入門 149
6.1 貪心算法 149
6.1.1 貪心算法秘籍 149
6.1.2 最優裝載問題 150
訓練1 部分背包問題 152
訓練2 排隊接水 153
訓練3 線段覆蓋 154
6.2 分治算法 156
6.2.1 分治算法秘籍 156
6.2.2 合並排序 156
6.2.3 快速排序 161
訓練1 排序（模板） 168
訓練2 求第k小的數 169

第7章 高精度計算 171
7.1 高精度加法 171
7.1.1 接收和存儲數據 171
7.1.2 處理進位 171
訓練 A+B Problem 174
7.2 高精度減法 175
7.2.1 比較大小 175
7.2.2 接收和存儲數據 175
7.2.3 處理借位 175
訓練 A-B Problem 177
7.3 高精度乘法 178
7.3.1 接收和存儲數據 178
7.3.2 處理進位 178
訓練 A*B Problem 179
7.4 高精度除法 180
7.4.1 接收和存儲數據 180
7.4.2 按位相除 181
訓練 A/B Problem 181

第8章 搜索算法入門 183
8.1 二分算法 183
8.1.1 二分查找 183
8.1.2 二分答案 186
訓練1 查找 187
訓練2 跳石頭游戲 189
訓練3 花環 193
8.2 深度優先搜索 195
8.2.1 回溯法的原理 195
8.2.2 回溯法模板 197
訓練1 01背包問題 198
訓練2 圖的m著色問題 205
訓練3 n皇後問題 213
8.3 廣度優先搜索 227
8.3.1 分支限界法的原理 227
8.3.2 分支限界法秘籍 227
訓練1 迷宮問題 228
訓練2 01背包問題 229

第9章 動態規劃入門 235
9.1 動態規劃秘籍 235
9.1.1 動態規劃的三個要素 236
9.1.2 動態規劃的設計方法 236
9.2 背包問題 237
9.2.1 01背包問題 238
9.2.2 完全背包問題 246
訓練1 骨頭收藏家 246
訓練2 存錢罐 248
9.3 線性動態規劃 250
訓練1 超級樓梯 250
訓練2 數字三角形 251
訓練3 最長上升子序列 253
訓練4 最長公共子序列 256
訓練5 最大連續子段和 257
9.4 區間動態規劃 259
訓練1 迴文 259
訓練2 括號匹配 261
訓練3 乘法難題 263
訓練4 猴子派對 265