本書內(nèi)容包括:C/C++快速入門、入門模擬、算法初步、數(shù)學(xué)問題、C++標(biāo)準(zhǔn)模板庫、數(shù)據(jù)結(jié)構(gòu)專題、搜索專題、圖算法專題等。
這是一本零基礎(chǔ)就能讀懂的算法書籍,讀者不需要因為自己沒有語言基礎(chǔ)而畏懼。書籍的第2章便是一個C語言的入門教程,內(nèi)容非常易懂,并且十分實用,閱讀完這章就可以對本書需要的C語言基礎(chǔ)有一個較好的掌握。
本書已經(jīng)覆蓋了大部分基礎(chǔ)經(jīng)典算法,不僅可以作為考研機(jī)試和PAT的學(xué)習(xí)教材,對其他的一些算法考試(例如CCF的CSP考試)或者考研初試的數(shù)據(jù)結(jié)構(gòu)科目的學(xué)習(xí)和理解也很有幫助,甚至僅僅想學(xué)習(xí)經(jīng)典算法的讀者也能從本書中學(xué)到許多知識,本書還有配套的《算法筆記上機(jī)訓(xùn)練實戰(zhàn)指南》
本書的作者是同樣經(jīng)歷過考研機(jī)試和各類算法考試的專家型學(xué)長,知曉這類考試中的痛點,以及考生在學(xué)習(xí)算法時容易產(chǎn)生困惑的地方,因此可以把本書看作是學(xué)長為你奉獻(xiàn)的滿滿的經(jīng)驗干貨,這是有價值的東西。
本書的試印版本獻(xiàn)給了浙大考研學(xué)子,并令當(dāng)年的浙大考研機(jī)試平均分增加了十多分,收獲了考生的大量好評。但作者并沒有止步于此,經(jīng)過了半年多時間的內(nèi)容完善和補(bǔ)充之后,新的版本在新一年的考研機(jī)試中再次獲得了考生的一致贊美。最后,在經(jīng)過精心整理之后,書籍終于定稿,并編撰成書。
我們知道,紙質(zhì)書籍的一個弱點就在于不能像軟件一樣隨時更新內(nèi)容,但本書采用了與二維碼相結(jié)合的方式,使得本書變?yōu)槟軌螂S時更新內(nèi)容的書籍,讀者也可以隨時從二維碼中找到勘誤。這種作者和讀者能夠相互溝通的方式讓書籍變“活”了,也能夠幫助提升讀者對知識的理解。
最初打算寫這本書是在自己剛考完研之后。那段時間,我每天都在浙江大學(xué)天勤考研群里給學(xué)弟學(xué)妹們答疑,在感受著他們的努力與進(jìn)步的同時,自己仿佛又經(jīng)歷了一次考研,感慨頗多。漸漸地,出于興趣,我感覺自己還能為他們做些什么,于是便萌生了寫一些東西的想法。由于浙江大學(xué)機(jī)試就是PAT考試,因此一開始只是打算把PAT考試題目的題解都寫一遍,但是在寫作過程中慢慢發(fā)現(xiàn),題解本身并不能給人帶來太多的提高,而算法思想的理解和學(xué)習(xí)才是最為重要的。考慮到當(dāng)時的算法入門書籍要么偏重于競賽風(fēng)格,要么偏重于面試風(fēng)格,因此我便打算寫一本適用于考研機(jī)試與PAT的算法書籍,以供考研的學(xué)弟學(xué)妹們學(xué)習(xí)。因為浙江機(jī)試的考試范圍已經(jīng)能覆蓋大部分學(xué)校的機(jī)試范圍,所以對于報考其他學(xué)校的同學(xué)也同樣適用。
第一次試印的版本給當(dāng)年浙江大學(xué)機(jī)試的平均分提高了十多分,反響不錯。但我深知書中仍有許多不足,也有許多想要添加的內(nèi)容沒來得及加進(jìn)去,因此便又花費(fèi)了半年時間增加了許多內(nèi)容。至此,本書已經(jīng)覆蓋了大部分基礎(chǔ)經(jīng)典算法,不僅可以作為考研機(jī)試和PAT的學(xué)習(xí)教材,對其他的一些算法考試(例如CCF的CSP考試)或者考研初試的數(shù)據(jù)結(jié)構(gòu)科目的學(xué)習(xí)和理解也很有幫助,甚至僅僅想學(xué)習(xí)經(jīng)典算法的讀者也能從本書中學(xué)到許多知識。由于書中很多內(nèi)容都來源于自己對算法的理解,因此最終把書名定為《算法筆記》。
本書希望讓一個C語言零基礎(chǔ)的讀者能很好地進(jìn)入本書的學(xué)習(xí),因此在第2章設(shè)置了C語言的入門詳解,使讀者不必因自己不會C語言而有所擔(dān)心,并且在對C語言的講解中融入了部分C++的特性內(nèi)容,這樣讀者會更容易書寫順手的代碼。第3~5章是入門部分,其中介紹了一些算法思想和數(shù)學(xué)問題,讀者可從中學(xué)習(xí)到一些基礎(chǔ)但非常重要的算法思想,并培養(yǎng)基本的思維能力和代碼能力。第6章介紹了C++標(biāo)準(zhǔn)模板庫(STL)的常用內(nèi)容和algorithm頭文件下的常用函數(shù),以幫助讀者節(jié)省寫代碼的時間。第7~12章是進(jìn)階部分,其中介紹了各類經(jīng)典數(shù)據(jù)結(jié)構(gòu)、圖算法以及較為進(jìn)階的重要算法,以使讀者對經(jīng)典算法和數(shù)據(jù)結(jié)構(gòu)有較為深入的學(xué)習(xí)。第13章補(bǔ)充了一些上面沒有介紹的內(nèi)容,以幫助讀者拓寬視野。
另外,書中印的二維碼,是用來更新或補(bǔ)充書籍內(nèi)容及發(fā)布本書勘誤的。通過掃描本書的勘誤和內(nèi)容更新日志二維碼,讀者可以得到實時更新的相應(yīng)內(nèi)容。
最后,由于編者水平有限,盡管對本書進(jìn)行了多次校對,書中可能仍有一些待改進(jìn)的地方,敬請廣大讀者提出寶貴建議!
本書的適用范圍
研究生復(fù)試上機(jī)考試
PAT甲級、乙級考試
CCF的CSP認(rèn)證(或其他算法)
求職面試時的基礎(chǔ)算法考試
考研初試數(shù)據(jù)結(jié)構(gòu)科目
經(jīng)典算法的入門學(xué)習(xí)
前言
第1章 如何使用本書 1
1.1 本書的基本內(nèi)容 1
1.2 如何選擇編程語言和編譯器 1
1.3 在線評測系統(tǒng) 2
1.4 常見的評測結(jié)果 3
1.5 如何高效地做題 4
第2章 C/C++快速入門 5
2.1 基本數(shù)據(jù)類型 7
2.1.1 變量的定義 7
2.1.2 變量類型 7
2.1.3 強(qiáng)制類型轉(zhuǎn)換 11
2.1.4 符號常量和const常量 12
2.1.5 運(yùn)算符 14
2.2 順序結(jié)構(gòu) 17
2.2.1 賦值表達(dá)式 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函數(shù) 25
2.3 選擇結(jié)構(gòu) 28
2.3.1 if語句 28
2.3.2 if語句的嵌套 31
2.3.3 switch語句 32
2.4 循環(huán)結(jié)構(gòu) 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 數(shù)組 39
2.5.1 一維數(shù)組 39
2.5.2 冒泡排序 41
2.5.3 二維數(shù)組 43
2.5.4 memset——對數(shù)組中每一個元素賦相同的值 46
2.5.5 字符數(shù)組 47
2.5.6 string.h頭文件 50
2.5.7 sscanf與sprintf 53
2.6 函數(shù) 55
2.6.1 函數(shù)的定義 55
2.6.2 再談main函數(shù) 58
2.6.3 以數(shù)組作為函數(shù)參數(shù) 58
2.6.4 函數(shù)的嵌套調(diào)用 59
2.6.5 函數(shù)的遞歸調(diào)用 60
2.7 指針 61
2.7.1 什么是指針 61
2.7.2 指針變量 62
2.7.3 指針與數(shù)組 63
2.7.4 使用指針變量作為函數(shù)參數(shù) 65
2.7.5 引用 68
2.8 結(jié)構(gòu)體(struct)的使用 70
2.8.1 結(jié)構(gòu)體的定義 70
2.8.2 訪問結(jié)構(gòu)體內(nèi)的元素 71
2.8.3 結(jié)構(gòu)體的初始化 72
2.9 補(bǔ)充 74
2.9.1 cin與cout 74
2.9.2 浮點數(shù)的比較 75
2.9.3 復(fù)雜度 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 進(jìn)制轉(zhuǎn)換 93
3.6 字符串處理 95
第4章 入門篇(2)——算法初步 99
4.1 排序 99
4.1.1 選擇排序 99
4.1.2 插入排序 100
4.1.3 排序題與sort函數(shù)的應(yīng)用 101
4.2 散列 106
4.2.1 散列的定義與整數(shù)散列 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 區(qū)間貪心 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 隨機(jī)選擇算法 149
第5章 入門篇(3)——數(shù)學(xué)問題 152
5.1 簡單數(shù)學(xué) 152
5.2 最大公約數(shù)與最小公倍數(shù) 154
5.2.1 最大公約數(shù) 154
5.2.2 最小公倍數(shù) 156
5.3 分?jǐn)?shù)的四則運(yùn)算 156
5.3.1 分?jǐn)?shù)的表示和化簡 157
5.3.2 分?jǐn)?shù)的四則運(yùn)算 157
5.3.3 分?jǐn)?shù)的輸出 159
5.4 素數(shù) 159
5.4.1 素數(shù)的判斷 160
5.4.2 素數(shù)表的獲取 160
5.5 質(zhì)因子分解 165
5.6 大整數(shù)運(yùn)算 170
5.6.1 大整數(shù)的存儲 170
5.6.2 大整數(shù)的四則運(yùn)算 171
5.7 擴(kuò)展歐幾里得算法 176
5.8 組合數(shù) 181
5.8.1 關(guān)于n!的一個問題 181
5.8.2 組合數(shù)的計算 183
第6章 C++標(biāo)準(zhǔn)模板庫(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頭文件下的常用函數(shù) 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)——數(shù)據(jù)結(jié)構(gòu)專題(1) 245
7.1 棧的應(yīng)用 245
7.2 隊列的應(yīng)用 251
7.3 鏈表處理 253
7.3.1 鏈表的概念 253
7.3.2 使用malloc函數(shù)或new運(yùn)算符為鏈表結(jié)點分配內(nèi)存空間 254
7.3.3 鏈表的基本操作 256
7.3.4 靜態(tài)鏈表 260
第8章 提高篇(2)——搜索專題 269
8.1 深度優(yōu)先搜索(DFS) 269
8.2 廣度優(yōu)先搜索(BFS) 274
第9章 提高篇(3)——數(shù)據(jù)結(jié)構(gòu)專題(2) 283
9.1 樹與二叉樹 283
9.1.1 樹的定義與性質(zhì) 283
9.1.2 二叉樹的遞歸定義 284
9.1.3 二叉樹的存儲結(jié)構(gòu)與基本操作 285
9.2 二叉樹的遍歷 289
9.2.1 先序遍歷 289
9.2.2 中序遍歷 290
9.2.3 后序遍歷 291
9.2.4 層序遍歷 292
9.2.5 二叉樹的靜態(tài)實現(xiàn) 298
9.3 樹的遍歷 302
9.3.1 樹的靜態(tài)寫法 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 二叉查找樹的性質(zhì) 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 圖的定義和相關(guān)術(shù)語 347
10.2 圖的存儲 348
10.2.1 鄰接矩陣 348
10.2.2 鄰接表 348
10.3 圖的遍歷 350
10.3.1 采用深度優(yōu)先搜索(DFS)法遍歷圖 350
10.3.2 采用廣度優(yōu)先搜索(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 最小生成樹及其性質(zhì) 400
10.5.2 prim算法 401
10.5.3 kruskal算法 409
10.6 拓?fù)渑判?414
10.6.1 有向無環(huán)圖 414
10.6.2 拓?fù)渑判?415
10.7 關(guān)鍵路徑 417
10.7.1 AOV網(wǎng)和AOE網(wǎng) 417
10.7.2 最長路徑 419
10.7.3 關(guān)鍵路徑 419
第11章 提高篇(5)——動態(tài)規(guī)劃專題 425
11.1 動態(tài)規(guī)劃的遞歸寫法和遞推寫法 425
11.1.1 什么是動態(tài)規(guī)劃 425
11.1.2 動態(tài)規(guī)劃的遞歸寫法 425
11.1.3 動態(tài)規(guī)劃的遞推寫法 426
11.2 最大連續(xù)子序列和 429
11.3 最長不下降子序列(LIS) 432
11.4 最長公共子序列(LCS) 434
11.5 最長回文子串 436
11.6 DAG最長路 439
11.7 背包問題 442
11.7.1 多階段動態(tài)規(guī)劃問題 442
11.7.2 01背包問題 443
11.7.3 完全背包問題 446
11.8 總結(jié) 447
第12章 提高篇(6)——字符串專題 449
12.1 字符串hash進(jìn)階 449
12.2 KMP算法 455
12.2.1 next數(shù)組 456
12.2.2 KMP算法 458
12.2.3 從有限狀態(tài)自動機(jī)的角度看待KMP算法 463
第13章 專題擴(kuò)展 465
13.1 分塊思想 465
13.2 樹狀數(shù)組(BIT) 470
13.2.1 lowbit運(yùn)算 470
13.2.2 樹狀數(shù)組及其應(yīng)用 470
參考文獻(xiàn) 481