這是一本零基礎(chǔ)就能讀懂的算法書籍，讀者不需要因?yàn)樽约簺](méi)有語(yǔ)言基礎(chǔ)而畏懼。書籍的第2章便是一個(gè)C語(yǔ)言的入門教程，內(nèi)容非常易懂，并且十分實(shí)用，閱讀完這章就可以對(duì)本書需要的C語(yǔ)言基礎(chǔ)有一個(gè)較好的掌握。本書已經(jīng)覆蓋了大部分基礎(chǔ)經(jīng)典算法，不僅可以作為考研機(jī)試和PAT的學(xué)習(xí)教材，對(duì)其他的一些算法考試（例如CCF的CSP考試）或者考研初試的數(shù)據(jù)結(jié)構(gòu)科目的學(xué)習(xí)和理解也很有幫助，甚至僅僅想學(xué)習(xí)經(jīng)典算法的讀者也能從本書中學(xué)到許多知識(shí)，本書還有配套的《算法筆記上機(jī)訓(xùn)練實(shí)戰(zhàn)指南》本書的作者是同樣經(jīng)歷過(guò)考研機(jī)試和各類算法考試的專家型學(xué)長(zhǎng)，知曉這類考試中的痛點(diǎn)，以及考生在學(xué)習(xí)算法時(shí)容易產(chǎn)生困惑的地方，因此可以把本書看作是學(xué)長(zhǎng)為你奉獻(xiàn)的滿滿的經(jīng)驗(yàn)干貨，這是*有價(jià)值的東西。本書的*個(gè)試印版本獻(xiàn)給了浙大考研學(xué)子，并令當(dāng)年的浙大考研機(jī)試平均分增加了十多分，收獲了考生的大量好評(píng)。但作者并沒(méi)有止步于此，經(jīng)過(guò)了半年多時(shí)間的內(nèi)容完善和補(bǔ)充之后，新的版本在新一年的考研機(jī)試中再次獲得了考生的一致贊美。*后，在經(jīng)過(guò)精心整理之后，書籍終于定稿，并編撰成書。我們知道，紙質(zhì)書籍的一個(gè)弱點(diǎn)就在于不能像軟件一樣隨時(shí)更新內(nèi)容，但本書采用了與二維碼相結(jié)合的方式，使得本書變?yōu)槟軌螂S時(shí)更新內(nèi)容的書籍，讀者也可以隨時(shí)從二維碼中找到勘誤。這種作者和讀者能夠相互溝通的方式讓書籍變“活”了，也能夠幫助提升讀者對(duì)知識(shí)的理解。 本書內(nèi)容包括：C/C快速入門、入門模擬、算法初步、數(shù)學(xué)問(wèn)題、C標(biāo)準(zhǔn)模板庫(kù)（STL）、數(shù)據(jù)結(jié)構(gòu)專題（二章）、搜索專題、圖算法專題、動(dòng)態(tài)規(guī)劃專題、字符串專題、專題擴(kuò)展。本書印有二維碼，用來(lái)實(shí)時(shí)更新、補(bǔ)充內(nèi)容及發(fā)布勘誤的。本書可作為計(jì)算機(jī)專業(yè)研究生入學(xué)考試復(fù)試上機(jī)、各類算法等級(jí)考試（如PAT、CSP等）的輔導(dǎo)書，也可作為“數(shù)據(jù)結(jié)構(gòu)”科目的考研教材及輔導(dǎo)書內(nèi)容的補(bǔ)充。本書還是學(xué)習(xí)C語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)與算法的入門輔導(dǎo)書，非常適合零基礎(chǔ)的學(xué)習(xí)者對(duì)經(jīng)典算法進(jìn)行學(xué)習(xí)。
目錄：
前言第1章如何使用本書 11.1本書的基本內(nèi)容 11.2如何選擇編程語(yǔ)言和編譯器 11.3在線評(píng)測(cè)系統(tǒng) 21.4常見(jiàn)的評(píng)測(cè)結(jié)果 31.5如何高效地做題 4第2章C/C快速入前言第1章 如何使用本書11.1 本書的基本內(nèi)容11.2 如何選擇編程語(yǔ)言和編譯器11.3 在線評(píng)測(cè)系統(tǒng)21.4 常見(jiàn)的評(píng)測(cè)結(jié)果31.5 如何高效地做題4第2章 C/C快速入門52.1 基本數(shù)據(jù)類型72.1.1 變量的定義72.1.2 變量類型72.1.3 強(qiáng)制類型轉(zhuǎn)換112.1.4 符號(hào)常量和const常量122.1.5 運(yùn)算符142.2 順序結(jié)構(gòu)172.2.1 賦值表達(dá)式172.2.2 使用scanf和printf輸入/輸出182.2.3 使用getchar和putchar輸入/輸出字符232.2.4 注釋242.2.5 typedef242.2.6 常用math函數(shù)252.3 選擇結(jié)構(gòu)282.3.1 if語(yǔ)句282.3.2 if語(yǔ)句的嵌套312.3.3 switch語(yǔ)句322.4 循環(huán)結(jié)構(gòu)342.4.1 while語(yǔ)句342.4.2 dowhile語(yǔ)句352.4.3 for語(yǔ)句362.4.4 break和continue語(yǔ)句382.5 數(shù)組392.5.1 一維數(shù)組392.5.2 冒泡排序412.5.3 二維數(shù)組432.5.4 memset——對(duì)數(shù)組中每一個(gè)元素賦相同的值462.5.5 字符數(shù)組472.5.6 string.h頭文件502.5.7 sscanf與sprintf532.6 函數(shù)552.6.1 函數(shù)的定義552.6.2 再談main函數(shù)582.6.3 以數(shù)組作為函數(shù)參數(shù)582.6.4 函數(shù)的嵌套調(diào)用592.6.5 函數(shù)的遞歸調(diào)用602.7 指針612.7.1 什么是指針612.7.2 指針變量622.7.3 指針與數(shù)組632.7.4 使用指針變量作為函數(shù)參數(shù)652.7.5 引用682.8 結(jié)構(gòu)體（struct）的使用702.8.1 結(jié)構(gòu)體的定義702.8.2 訪問(wèn)結(jié)構(gòu)體內(nèi)的元素712.8.3 結(jié)構(gòu)體的初始化722.9 補(bǔ)充742.9.1 cin與cout742.9.2 浮點(diǎn)數(shù)的比較752.9.3 復(fù)雜度782.10 黑盒測(cè)試802.10.1 單點(diǎn)測(cè)試802.10.2 多點(diǎn)測(cè)試80第3章 入門篇（1）——入門模擬853.1 簡(jiǎn)單模擬853.2 查找元素873.3 圖形輸出893.4 日期處理913.5 進(jìn)制轉(zhuǎn)換933.6 字符串處理95第4章 入門篇（2）——算法初步994.1 排序994.1.1 選擇排序994.1.2 插入排序1004.1.3 排序題與sort函數(shù)的應(yīng)用1014.2 散列1064.2.1 散列的定義與整數(shù)散列1064.2.2 字符串hash初步1094.3 遞歸1114.3.1 分治1114.3.2 遞歸1124.4 貪心1184.4.1 簡(jiǎn)單貪心1184.4.2 區(qū)間貪心1224.5 二分1244.5.1 二分查找1244.5.2 二分法拓展1314.5.3 快速冪1344.6 twopointers1374.6.1 什么是twopointers1374.6.2 歸并排序1394.6.3 快速排序1424.7 其他高效技巧與算法1464.7.1 打表1464.7.2 活用遞推1474.7.3 隨機(jī)選擇算法149第5章 入門篇（3）——數(shù)學(xué)問(wèn)題1525.1 簡(jiǎn)單數(shù)學(xué)1525.2 最大公約數(shù)與最小公倍數(shù)1545.2.1 最大公約數(shù)1545.2.2 最小公倍數(shù)1565.3 分?jǐn)?shù)的四則運(yùn)算1565.3.1 分?jǐn)?shù)的表示和化簡(jiǎn)1575.3.2 分?jǐn)?shù)的四則運(yùn)算1575.3.3 分?jǐn)?shù)的輸出1595.4 素?cái)?shù)1595.4.1 素?cái)?shù)的判斷1605.4.2 素?cái)?shù)表的獲取1605.5 質(zhì)因子分解1655.6 大整數(shù)運(yùn)算1705.6.1 大整數(shù)的存儲(chǔ)1705.6.2 大整數(shù)的四則運(yùn)算1715.7 擴(kuò)展歐幾里得算法1765.8 組合數(shù)1815.8.1 關(guān)于n!的一個(gè)問(wèn)題1815.8.2 組合數(shù)的計(jì)算183第6章 C標(biāo)準(zhǔn)模板庫(kù)（STL）介紹1916.1 vector的常見(jiàn)用法詳解1916.2 set的常見(jiàn)用法詳解1976.3 string的常見(jiàn)用法詳解2026.4 map的常用用法詳解2136.5 queue的常見(jiàn)用法詳解2186.6 priority_queue的常見(jiàn)用法詳解2216.7 stack的常見(jiàn)用法詳解2276.8 pair的常見(jiàn)用法詳解2306.9 algorithm頭文件下的常用函數(shù)2326.9.1 max()、min()和abs()2326.9.2 swap()2336.9.3 reverse()2336.9.4 next_permutation()2346.9.5 fill()2356.9.6 sort()2356.9.7 lower_bound()和upper_bound()242第7章 提高篇（1）——數(shù)據(jù)結(jié)構(gòu)專題（1）2457.1 棧的應(yīng)用2457.2 隊(duì)列的應(yīng)用2517.3 鏈表處理2537.3.1 鏈表的概念2537.3.2 使用malloc函數(shù)或new運(yùn)算符為鏈表結(jié)點(diǎn)分配內(nèi)存空間2547.3.3 鏈表的基本操作2567.3.4 靜態(tài)鏈表260第8章 提高篇（2）——搜索專題2698.1 深度優(yōu)先搜索（DFS）2698.2 廣度優(yōu)先搜索（BFS）274第9章 提高篇（3）——數(shù)據(jù)結(jié)構(gòu)專題（2）2839.1 樹(shù)與二叉樹(shù)2839.1.1 樹(shù)的定義與性質(zhì)2839.1.2 二叉樹(shù)的遞歸定義2849.1.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與基本操作2859.2 二叉樹(shù)的遍歷2899.2.1 先序遍歷2899.2.2 中序遍歷2909.2.3 后序遍歷2919.2.4 層序遍歷2929.2.5 二叉樹(shù)的靜態(tài)實(shí)現(xiàn)2989.3 樹(shù)的遍歷3029.3.1 樹(shù)的靜態(tài)寫法3029.3.2 樹(shù)的先根遍歷3039.3.3 樹(shù)的層序遍歷3039.3.4 從樹(shù)的遍歷看DFS與BFS3049.4 二叉查找樹(shù)（BST）3109.4.1 二叉查找樹(shù)的定義3109.4.2 二叉查找樹(shù)的基本操作3109.4.3 二叉查找樹(shù)的性質(zhì)3149.5 平衡二叉樹(shù)（AVL樹(shù)）3199.5.1 平衡二叉樹(shù)的定義3199.5.2 平衡二叉樹(shù)的基本操作3209.6 并查集3289.6.1 并查集的定義3289.6.2 并查集的基本操作3289.6.3 路徑壓縮3309.7 堆3359.7.1 堆的定義與基本操作3359.7.2 堆排序3399.8 哈夫曼樹(shù)3429.8.1 哈夫曼樹(shù)3429.8.2 哈弗曼編碼345第10章 提高篇（4）——圖算法專題34710.1 圖的定義和相關(guān)術(shù)語(yǔ)34710.2 圖的存儲(chǔ)34810.2.1 鄰接矩陣34810.2.2 鄰接表34810.3 圖的遍歷35010.3.1 采用深度優(yōu)先搜索（DFS）法遍歷圖35010.3.2 采用廣度優(yōu)先搜索（BFS）法遍歷圖35910.4 最短路徑36710.4.1 Dijkstra算法36710.4.2 Bellman-Ford算法和SPFA算法39110.4.3 Floyd算法39810.5 最小生成樹(shù)40010.5.1 最小生成樹(shù)及其性質(zhì)40010.5.2 prim算法40110.5.3 kruskal算法40910.6 拓?fù)渑判?1410.6.1 有向無(wú)環(huán)圖41410.6.2 拓?fù)渑判?1510.7 關(guān)鍵路徑41710.7.1 AOV網(wǎng)和AOE網(wǎng)41710.7.2 最長(zhǎng)路徑41910.7.3 關(guān)鍵路徑419第11章 提高篇（5）——動(dòng)態(tài)規(guī)劃專題42511.1 動(dòng)態(tài)規(guī)劃的遞歸寫法和遞推寫法42511.1.1 什么是動(dòng)態(tài)規(guī)劃42511.1.2 動(dòng)態(tài)規(guī)劃的遞歸寫法42511.1.3 動(dòng)態(tài)規(guī)劃的遞推寫法42611.2 最大連續(xù)子序列和42911.3 最長(zhǎng)不下降子序列（LIS）43211.4 最長(zhǎng)公共子序列（LCS）43411.5 最長(zhǎng)回文子串43611.6 DAG最長(zhǎng)路43911.7 背包問(wèn)題44211.7.1 多階段動(dòng)態(tài)規(guī)劃問(wèn)題44211.7.2 01背包問(wèn)題44311.7.3 完全背包問(wèn)題44611.8 總結(jié)447第12章 提高篇（6）——字符串專題44912.1 字符串hash進(jìn)階44912.2 KMP算法45512.2.1 next數(shù)組45612.2.2 KMP算法45812.2.3 從有限狀態(tài)自動(dòng)機(jī)的角度看待KMP算法463第13章 專題擴(kuò)展46513.1 分塊思想46513.2 樹(shù)狀數(shù)組（BIT）47013.2.1 lowbit運(yùn)算47013.2.2 樹(shù)狀數(shù)組及其應(yīng)用470參考文獻(xiàn)481前言最初打算寫這本書是在自己剛考完研之后。那段時(shí)間，我每天都在浙江大學(xué)天勤考研群里給學(xué)弟學(xué)妹們答疑，在感受著他們的努力與進(jìn)步的同時(shí)，自己仿佛又經(jīng)歷了一次考研，感最初打算寫這本書是在自己剛考完研之后。那段時(shí)間，我每天都在浙江大學(xué)天勤考研群里給學(xué)弟學(xué)妹們答疑，在感受著他們的努力與進(jìn)步的同時(shí)，自己仿佛又經(jīng)歷了一次考研，感慨頗多。漸漸地，出于興趣，我感覺(jué)自己還能為他們做些什么，于是便萌生了寫一些東西的想法。由于浙江大學(xué)機(jī)試就是PAT考試，因此一開(kāi)始只是打算把PAT考試題目的題解都寫一遍，但是在寫作過(guò)程中慢慢發(fā)現(xiàn)，題解本身并不能給人帶來(lái)太多的提高，而算法思想的理解和學(xué)習(xí)才是最為重要的�？紤]到當(dāng)時(shí)的算法入門書籍要么偏重于競(jìng)賽風(fēng)格，要么偏重于面試風(fēng)格，因此我便打算寫一本適用于考研機(jī)試與PAT的算法書籍，以供考研的學(xué)弟學(xué)妹們學(xué)習(xí)。因?yàn)檎憬瓩C(jī)試的考試范圍已經(jīng)能覆蓋大部分學(xué)校的機(jī)試范圍，所以對(duì)于報(bào)考其他學(xué)校的同學(xué)也同樣適用。第一次試印的版本給當(dāng)年浙江大學(xué)機(jī)試的平均分提高了十多分，反響不錯(cuò)。但我深知書中仍有許多不足，也有許多想要添加的內(nèi)容沒(méi)來(lái)得及加進(jìn)去，因此便又花費(fèi)了半年時(shí)間增加了許多內(nèi)容。至此，本書已經(jīng)覆蓋了大部分基礎(chǔ)經(jīng)典算法，不僅可以作為考研機(jī)試和PAT的學(xué)習(xí)教材，對(duì)其他的一些算法考試（例如CCF的CSP考試）或者考研初試的數(shù)據(jù)結(jié)構(gòu)科目的學(xué)習(xí)和理解也很有幫助，甚至僅僅想學(xué)習(xí)經(jīng)典算法的讀者也能從本書中學(xué)到許多知識(shí)。由于書中很多內(nèi)容都來(lái)源于自己對(duì)算法的理解，因此最終把書名定為《算法筆記》。本書希望讓一個(gè)C語(yǔ)言零基礎(chǔ)的讀者能很好地進(jìn)入本書的學(xué)習(xí)，因此在第2章設(shè)置了C語(yǔ)言的入門詳解，使讀者不必因自己不會(huì)C語(yǔ)言而有所擔(dān)心，并且在對(duì)C語(yǔ)言的講解中融入了部分C的特性內(nèi)容，這樣讀者會(huì)更容易書寫順手的代碼。第3~5章是入門部分，其中介紹了一些算法思想和數(shù)學(xué)問(wèn)題，讀者可從中學(xué)習(xí)到一些基礎(chǔ)但非常重要的算法思想，并培養(yǎng)基本的思維能力和代碼能力。第6章介紹了C標(biāo)準(zhǔn)模板庫(kù)（STL）的常用內(nèi)容和algorithm頭文件下的常用函數(shù)，以幫助讀者節(jié)省寫代碼的時(shí)間。第7~12章是進(jìn)階部分，其中介紹了各類經(jīng)典數(shù)據(jù)結(jié)構(gòu)、圖算法以及較為進(jìn)階的重要算法，以使讀者對(duì)經(jīng)典算法和數(shù)據(jù)結(jié)構(gòu)有較為深入的學(xué)習(xí)。第13章補(bǔ)充了一些上面沒(méi)有介紹的內(nèi)容，以幫助讀者拓寬視野。另外，書中印的二維碼，是用來(lái)更新或補(bǔ)充書籍內(nèi)容及發(fā)布本書勘誤的。通過(guò)掃描本書的勘誤和內(nèi)容更新日志二維碼，讀者可以得到實(shí)時(shí)更新的相應(yīng)內(nèi)容。最后，由于編者水平有限，盡管對(duì)本書進(jìn)行了多次校對(duì)，書中可能仍有一些待改進(jìn)的地方，敬請(qǐng)廣大讀者提出寶貴建議！本書的適用范圍• 研究生復(fù)試上機(jī)考試• PAT甲級(jí)、乙級(jí)考試• CCF的CSP認(rèn)證（或其他算法）• 求職面試時(shí)的基礎(chǔ)算法考試• 考研初試數(shù)據(jù)結(jié)構(gòu)科目• 經(jīng)典算法的入門學(xué)習(xí)
|
