本書圖文并茂、通俗易懂,詳細講解常用的算法知識,又融入了大量的競賽實例和解題技巧,可幫助讀者熟練應用各種算法解決實際問題。 本書總計9章。第1章講解C++基礎(chǔ)知識,涉及語法、數(shù)組、字符串、結(jié)構(gòu)體和指針;第2章帶讀者感受算法之美,涉及算法復雜度、函數(shù)和遞歸;第3章講解線性表的應用,涉及順序表、鏈表、棧和隊列,以及STL中的常用函數(shù)和容器;第4章講解樹的應用,涉及樹、二叉樹、二叉樹遍歷、哈夫曼樹和二叉搜索樹;第5章講解圖論基礎(chǔ),涉及圖的存儲和圖的遍歷;第6章帶讀者進行算法入門,涉及貪心算法和分治算法;第7章講解高精度計算,涉及高精度加法、高精度減法、高精度乘法和高精度除法;第8章帶讀者進行搜索算法入門,涉及二分算法、深度優(yōu)先搜索和廣度優(yōu)先搜索;第9章帶讀者進行動態(tài)規(guī)劃入門,涉及動態(tài)規(guī)劃秘籍、背包問題、線性動態(tài)規(guī)劃和區(qū)間動態(tài)規(guī)劃。 本書面向?qū)λ惴ǜ信d趣的讀者,無論是想扎實內(nèi)功或參加算法競賽的學生,還是想進入名企的學生、求職者,抑或是想提升核心競爭力的在職人員,都可以參考本書。若讀者想進一步學習數(shù)據(jù)結(jié)構(gòu)與算法,則可參考《算法訓練營:提高篇(全彩版)》和《算法訓練營:進階篇(全彩版)》。
陳小玉南陽理工學院副教授,高級程序員,主要研究方向為算法優(yōu)化和機器學習。出版著作有《趣學算法》《趣學數(shù)據(jù)結(jié)構(gòu)》《算法訓練營》,所教學生多次獲得ACM-ICPC、藍橋杯等算法競賽獎項。
第1章 C++基礎(chǔ)知識 1
1.1 開啟算法之旅 1
1.2 常用的數(shù)據(jù)類型 2
1.3 玩轉(zhuǎn)輸入和輸出 2
1.4 常用的運算符 3
1.5 選擇結(jié)構(gòu)語句 5
1.5.1 if條件語句 5
1.5.2 switch條件語句 9
1.6 循環(huán)結(jié)構(gòu)語句 10
1.6.1 for語句 10
1.6.2 while語句 13
1.6.3 do while語句 14
1.7 巧用數(shù)組 15
1.7.1 一維數(shù)組 15
1.7.2 二維數(shù)組 17
1.8 玩轉(zhuǎn)字符串 18
1.8.1 C風格的字符串 19
1.8.2 C++ string類型的
字符串 20
1.9 結(jié)構(gòu)體的應用 21
1.10 指針的應用 22
第2章 算法之美 24
2.1 算法復雜度 24
2.1.1 時間復雜度 27
2.1.2 空間復雜度 27
2.2 函數(shù) 30
2.2.1 標準函數(shù) 30
2.2.2 傳值參數(shù) 31
2.2.3 引用參數(shù) 31
2.2.4 數(shù)組參數(shù) 32
2.3 遞歸 33
2.3.1 遞歸函數(shù) 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 循環(huán)鏈表 45
3.2.4 靜態(tài)鏈表 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 循環(huán)隊列 53
3.5 STL中的常用函數(shù)和容器 56
3.5.1 sort() 57
3.5.2 vector(向量) 58
訓練 角谷猜想 59
3.5.3 stack(棧) 60
訓練 數(shù)字游戲 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 樹、森林與二叉樹的
轉(zhuǎn)換 71
4.2 二叉樹 73
4.2.1 二叉樹的性質(zhì) 74
4.2.2 滿二叉樹和完全二
叉樹 75
4.2.3 二叉樹的存儲結(jié)構(gòu) 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 創(chuàng)建 116
4.5.5 刪除 117
訓練1 落葉 122
訓練2 完全二叉搜索樹 124
第5章 圖論基礎(chǔ) 127
5.1 圖的存儲 128
5.1.1 鄰接矩陣 128
5.1.2 邊集數(shù)組 129
5.1.3 鄰接表 130
5.1.4 鏈式前向星 133
5.1.5 圖的存儲技巧 136
5.2 圖的遍歷 136
5.2.1 廣度優(yōu)先遍歷 136
5.2.2 深度優(yōu)先遍歷 140
訓練1 最大的節(jié)點 144
訓練2 油田 145
第6章 算法入門 149
6.1 貪心算法 149
6.1.1 貪心算法秘籍 149
6.1.2 最優(yōu)裝載問題 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小的數(shù) 169
第7章 高精度計算 171
7.1 高精度加法 171
7.1.1 接收和存儲數(shù)據(jù) 171
7.1.2 處理進位 171
訓練 A+B Problem 174
7.2 高精度減法 175
7.2.1 比較大小 175
7.2.2 接收和存儲數(shù)據(jù) 175
7.2.3 處理借位 175
訓練 A-B Problem 177
7.3 高精度乘法 178
7.3.1 接收和存儲數(shù)據(jù) 178
7.3.2 處理進位 178
訓練 A*B Problem 179
7.4 高精度除法 180
7.4.1 接收和存儲數(shù)據(jù) 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 花環(huán) 193
8.2 深度優(yōu)先搜索 195
8.2.1 回溯法的原理 195
8.2.2 回溯法模板 197
訓練1 01背包問題 198
訓練2 圖的m著色問題 205
訓練3 n皇后問題 213
8.3 廣度優(yōu)先搜索 227
8.3.1 分支限界法的原理 227
8.3.2 分支限界法秘籍 227
訓練1 迷宮問題 228
訓練2 01背包問題 229
第9章 動態(tài)規(guī)劃入門 235
9.1 動態(tài)規(guī)劃秘籍 235
9.1.1 動態(tài)規(guī)劃的三個要素 236
9.1.2 動態(tài)規(guī)劃的設(shè)計方法 236
9.2 背包問題 237
9.2.1 01背包問題 238
9.2.2 完全背包問題 246
訓練1 骨頭收藏家 246
訓練2 存錢罐 248
9.3 線性動態(tài)規(guī)劃 250
訓練1 超級樓梯 250
訓練2 數(shù)字三角形 251
訓練3 最長上升子序列 253
訓練4 最長公共子序列 256
訓練5 最大連續(xù)子段和 257
9.4 區(qū)間動態(tài)規(guī)劃 259
訓練1 回文 259
訓練2 括號匹配 261
訓練3 乘法難題 263
訓練4 猴子派對 265