算法筆記（簡體書）

本書內容包括：C/C++快速入門、入門類比、演算法初步、數學問題、C++標準範本庫(STL)、資料結構專題（兩章）、搜索專題、圖演算法專題、動態規劃專題、字串專題、專題擴展。書中每小節的末尾均印有二維碼，用以即時更新或補充書籍的內容及發佈本書的勘誤。

可作為計算機專業研究生入學考試複試上機、各類算法等級考試（如PAT、CSP等）的輔導書，也可作為“數據結構”科目的考研教材及輔導書內容的補充。《算法筆記》還是學習C語言、數據結構與算法的入門輔導書，非常適合零基礎的學習者對經典算法進行學習。

這是一本零基礎就能讀懂的算法書籍，讀者不需要因為自己沒有語言基礎而畏懼。書籍的第2章便是一個C語言的入門教程，內容非常易懂，並且十分實用，閱讀完這章就可以對本書需要的C語言基礎有一個較好的掌握。
本書已經覆蓋了大部分基礎經典算法，不僅可以作為考研機試和PAT的學習教材，對其他的一些算法考試（例如CCF的CSP考試）或者考研初試的數據結構科目的學習和理解也很有幫助，甚至僅僅想學習經典算法的讀者也能從本書中學到許多知識，本書還有配套的《算法筆記上機訓練實戰指南》
本書的作者是同樣經歷過考研機試和各類算法考試的專家型學長，知曉這類考試中的痛點，以及考生在學習算法時容易產生困惑的地方，因此可以把本書看作是學長為你奉獻的滿滿的經驗乾貨，這是有價值的東西。
本書的試印版本獻給了浙大考研學子，並令當年的浙大考研機試平均分增加了十多分，收穫了考生的大量好評。但作者並沒有止步於此，經過了半年多時間的內容完善和補充之後，新的版本在新一年的考研機試中再次獲得了考生的一致讚美。最後，在經過精心整理之後，書籍終於定稿，並編撰成書。
我們知道，紙質書籍的一個弱點就在於不能像軟件一樣隨時更新內容，但本書採用了與二維碼相結合的方式，使得本書變為能夠隨時更新內容的書籍，讀者也可以隨時從二維碼中找到勘誤。這種作者和讀者能夠相互溝通的方式讓書籍變“活”了，也能夠幫助提升讀者對知識的理解。

最初打算寫這本書是在自己剛考完研之後。那段時間，我每天都在浙江大學天勤考研群裡給學弟學妹們答疑，在感受著他們的努力與進步的同時，自己彷彿又經歷了一次考研，感慨頗多。漸漸地，出於興趣，我感覺自己還能為他們做些什麼，於是便萌生了寫一些東西的想法。由於浙江大學機試就是PAT考試，因此一開始只是打算把PAT考試題目的題解都寫一遍，但是在寫作過程中慢慢發現，題解本身並不能給人帶來太多的提高，而算法思想的理解和學習才是最為重要的。考慮到當時的算法入門書籍要么偏重於競賽風格，要么偏重於面試風格，因此我便打算寫一本適用於考研機試與PAT的算法書籍，以供考研的學弟學妹們學習。因為浙江機試的考試範圍已經能覆蓋大部分學校的機試範圍，所以對於報考其他學校的同學也同樣適用。
第一次試印的版本給當年浙江大學機試的平均分提高了十多分，反響不錯。但我深知書中仍有許多不足，也有許多想要添加的內容沒來得及加進去，因此便又花費了半年時間增加了許多內容。至此，本書已經覆蓋了大部分基礎經典算法，不僅可以作為考研機試和PAT的學習教材，對其他的一些算法考試（例如CCF的CSP考試）或者考研初試的數據結構科目的學習和理解也很有幫助，甚至僅僅想學習經典算法的讀者也能從本書中學到許多知識。由於書中很多內容都來源於自己對算法的理解，因此最終把書名定為《算法筆記》。
本書希望讓一個C語言零基礎的讀者能很好地進入本書的學習，因此在第2章設置了C語言的入門詳解，使讀者不必因自己不會C語言而有所擔心，並且在對C語言的講解中融入了部分C++的特性內容，這樣讀者會更容易書寫順手的代碼。第3~5章是入門部分，其中介紹了一些算法思想和數學問題，讀者可從中學習到一些基礎但非常重要的算法思想，並培養基本的思維能力和代碼能力。第6章介紹了C++標準模板庫（STL）的常用內容和algorithm頭文件下的常用函數，以幫助讀者節省寫代碼的時間。第7~12章是進階部分，其中介紹了各類經典數據結構、圖算法以及較為進階的重要算法，以使讀者對經典算法和數據結構有較為深入的學習。第13章補充了一些上面沒有介紹的內容，以幫助讀者拓寬視野。
另外，書中印的二維碼，是用來更新或補充書籍內容及發布本書勘誤的。通過掃描本書的勘誤和內容更新日誌二維碼，讀者可以得到實時更新的相應內容。
最後，由於編者水平有限，儘管對本書進行了多次校對，書中可能仍有一些待改進的地方，敬請廣大讀者提出寶貴建議！
本書的適用範圍
研究生復試上機考試
PAT甲級、乙級考試
CCF的CSP認證（或其他算法）
求職面試時的基礎算法考試
考研初試數據結構科目
經典算法的入門學習

前言
第1章如何使用本書1
1.1 本書的基本內容1
1.2 如何選擇編程語言和編譯器1
1.3 在線評測系統2
1.4 常見的評測結果3
1.5 如何高效地做題4
第2章C/C++快速入門5
2.1 基本數據類型7
2.1.1 變量的定義7
2.1.2 變量類型7
2.1.3 強制類型轉換11
2.1.4 符號常量和const常量12
2.1.5 運算符14
2.2 順序結構17
2.2.1 賦值表達式17
2.2.2 使用scanf和printf輸入/輸出18
2.2.3 使用getchar和putchar輸入/輸出字符23
2.2.4 註釋24
2.2.5 typedef 24
2.2.6 常用math函數25
2.3 選擇結構28
2.3.1 if語句28
2.3.2 if語句的嵌套31
2.3.3 switch語句32
2.4 循環結構34
2.4.1 while語句34
2.4.2 do while語句35
2.4.3 for語句36
2.4.4 break和continue語句38
2.5 數組39
2.5.1 一維數組39
2.5.2 冒泡排序41
2.5.3 二維數組43
2.5.4 memset——對數組中每一個元素賦相同的值46
2.5.5 字符數組47
2.5.6 string.h頭文件50
2.5.7 sscanf與sprintf 53
2.6 函數55
2.6.1 函數的定義55
2.6.2 再談main函數58
2.6.3 以數組作為函數參數58
2.6.4 函數的嵌套調用59
2.6.5 函數的遞歸調用60
2.7 指針61
2.7.1 什麼是指針61
2.7.2 指針變量62
2.7.3 指針與數組63
2.7.4 使用指針變量作為函數參數65
2.7.5 引用68
2.8 結構體（struct）的使用70
2.8.1 結構體的定義70
2.8.2 訪問結構體內的元素71
2.8.3 結構體的初始化72
2.9 補充74
2.9.1 cin與cout 74
2.9.2 浮點數的比較75
2.9.3 複雜度78
2.10 黑盒測試80
2.10.1 單點測試80
2.10.2 多點測試80
第3章入門篇（1）——入門模擬85
3.1 簡單模擬85
3.2 查找元素87
3.3 圖形輸出89
3.4 日期處理91
3.5 進制轉換93
3.6 字符串處理95
第4章入門篇（2）——算法初步99
4.1 排序99
4.1.1 選擇排序99
4.1.2 插入排序100
4.1.3 排序題與sort函數的應用101
4.2 散列106
4.2.1 散列的定義與整數散列106
4.2.2 字符串hash初步109
4.3 遞歸111
4.3.1 分治111
4.3.2 遞歸112
4.4 貪心118
4.4.1 簡單貪心118
4.4.2 區間貪心122
4.5 二分124
4.5.1 二分查找124
4.5.2 二分法拓展131
4.5.3 快速冪134
4.6 two pointers 137
4.6.1 什麼是two pointers 137
4.6.2 歸併排序139
4.6.3 快速排序142
4.7 其他高效技巧與算法146
4.7.1 打表146
4.7.2 活用遞推147
4.7.3 隨機選擇算法149
第5章入門篇（3）——數學問題152
5.1 簡單數學152
5.2 最大公約數與最小公倍數154
5.2.1 最大公約數154
5.2.2 最小公倍數156
5.3 分數的四則運算156
5.3.1 分數的表示和化簡157
5.3.2 分數的四則運算157
5.3.3 分數的輸出159
5.4 素數159
5.4.1 素數的判斷160
5.4.2 素數表的獲取160
5.5 質因子分解165
5.6 大整數運算170
5.6.1 大整數的存儲170
5.6.2 大整數的四則運算171
5.7 擴展歐幾里得算法176
5.8 組合數181
5.8.1 關於n!的一個問題181
5.8.2 組合數的計算183
第6章C++標準模板庫（STL）介紹191
6.1 vector的常見用法詳解191
6.2 set的常見用法詳解197
6.3 string的常見用法詳解202
6.4 map的常用用法詳解213
6.5 queue的常見用法詳解218
6.6 priority_queue的常見用法詳解221
6.7 stack的常見用法詳解227
6.8 pair的常見用法詳解230
6.9 algorithm頭文件下的常用函數232
6.9.1 max()、min()和abs() 232
6.9.2 swap() 233
6.9.3 reverse() 233
6.9.4 next_permutation() 234
6.9.5 fill() 235
6.9.6 sort() 235
6.9.7 lower_bound()和upper_bound() 242
第7章提高篇（1）——數據結構專題（1） 245
7.1 棧的應用245
7.2 隊列的應用251
7.3 鍊錶處理253
7.3.1 鍊錶的概念253
7.3.2 使用malloc函數或new運算符為鍊錶結點分配內存空間254
7.3.3 鍊錶的基本操作256
7.3.4 靜態鍊錶260
第8章提高篇（2）——搜索專題269
8.1 深度優先搜索（DFS） 269
8.2 廣度優先搜索（BFS） 274
第9章提高篇（3）——數據結構專題（2） 283
9.1 樹與二叉樹283
9.1.1 樹的定義與性質283
9.1.2 二叉樹的遞歸定義284
9.1.3 二叉樹的存儲結構與基本操作285
9.2 二叉樹的遍歷289
9.2.1 先序遍歷289
9.2.2 中序遍歷290
9.2.3 後序遍歷291
9.2.4 層序遍歷292
9.2.5 二叉樹的靜態實現298
9.3 樹的遍歷302
9.3.1 樹的靜態寫法302
9.3.2 樹的先根遍歷303
9.3.3 樹的層序遍歷303
9.3.4 從樹的遍歷看DFS與BFS 304
9.4 二叉查找樹（BST） 310
9.4.1 二叉查找樹的定義310
9.4.2 二叉查找樹的基本操作310
9.4.3 二叉查找樹的性質314
9.5 平衡二叉樹（AVL樹） 319
9.5.1 平衡二叉樹的定義319
9.5.2 平衡二叉樹的基本操作320
9.6 並查集328
9.6.1 並查集的定義328
9.6.2 並查集的基本操作328
9.6.3 路徑壓縮330
9.7 堆335
9.7.1 堆的定義與基本操作335
9.7.2 堆排序339
9.8 哈夫曼樹342
9.8.1 哈夫曼樹342
9.8.2 哈弗曼編碼345
第10章提高篇（4）——圖算法專題347
10.1 圖的定義和相關術語347
10.2 圖的存儲348
10.2.1 鄰接矩陣348
10.2.2 鄰接表348
10.3 圖的遍歷350
10.3.1 採用深度優先搜索（DFS）法遍歷圖350
10.3.2 採用廣度優先搜索（BFS）法遍歷圖359
10.4 最短路徑367
10.4.1 Dijkstra算法367
10.4.2 Bellman-Ford算法和SPFA算法391
10.4.3 Floyd算法398
10.5 最小生成樹400
10.5.1 最小生成樹及其性質400
10.5.2 prim算法401
10.5.3 kruskal算法409
10.6 拓撲排序414
10.6.1 有向無環圖414
10.6.2 拓撲排序415
10.7 關鍵路徑417
10.7.1 AOV網和AOE網417
10.7.2 最長路徑419
10.7.3 關鍵路徑419
第11章提高篇（5）——動態規劃專題425
11.1 動態規劃的遞歸寫法和遞推寫法425
11.1.1 什麼是動態規劃425
11.1.2 動態規劃的遞歸寫法425
11.1.3 動態規劃的遞推寫法426
11.2 最大連續子序列和429
11.3 最長不下降子序列（LIS） 432
11.4 最長公共子序列（LCS） 434
11.5 最長回文子串436
11.6 DAG最長路439
11.7 背包問題442
11.7.1 多階段動態規劃問題442
11.7.2 01背包問題443
11.7.3 完全背包問題446
11.8 總結447
第12章提高篇（6）——字符串專題449
12.1 字符串hash進階449
12.2 KMP算法455
12.2.1 next數組456
12.2.2 KMP算法458
12.2.3 從有限狀態自動機的角度看待KMP算法463
第13章專題擴展465
13.1 分塊思想465
13.2 樹狀數組（BIT） 470
13.2.1 lowbit運算470
13.2.2 樹狀數組及其應用470
參考文獻481