前言
第1章 如何使用本書(shū) 1
1.1 本書(shū)的基本內(nèi)容 1
1.2 如何選擇編程語(yǔ)言和編譯器 1
1.3 在線評(píng)測(cè)系統(tǒng) 2
1.4 常見(jiàn)的評(píng)測(cè)結(jié)果 3
1.5 如何高效地做題 4
第2章 C/C++快速入門(mén) 5
2.1 基本數(shù)據(jù)類(lèi)型 7
2.1.1 變量的定義 7
2.1.2 變量類(lèi)型 7
2.1.3 強(qiáng)制類(lèi)型轉(zhuǎn)換 11
2.1.4 符號(hào)常量和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語(yǔ)句 28
2.3.2 if語(yǔ)句的嵌套 31
2.3.3 switch語(yǔ)句 32
2.4 循環(huán)結(jié)構(gòu) 34
2.4.1 while語(yǔ)句 34
2.4.2 do while語(yǔ)句 35
2.4.3 for語(yǔ)句 36
2.4.4 break和continue語(yǔ)句 38
2.5 數(shù)組 39
2.5.1 一維數(shù)組 39
2.5.2 冒泡排序 41
2.5.3 二維數(shù)組 43
2.5.4 memset——對(duì)數(shù)組中每一個(gè)元素賦相同的值 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 訪問(wèn)結(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 浮點(diǎn)數(shù)的比較 75
2.9.3 復(fù)雜度 78
2.10 黑盒測(cè)試 80
2.10.1 單點(diǎn)測(cè)試 80
2.10.2 多點(diǎn)測(cè)試 80
第3章 入門(mén)篇（1）——入門(mén)模擬 85
3.1 簡(jiǎn)單模擬 85
3.2 查找元素 87
3.3 圖形輸出 89
3.4 日期處理 91
3.5 進(jìn)制轉(zhuǎn)換 93
3.6 字符串處理 95
第4章 入門(mén)篇（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 簡(jiǎn)單貪心 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章 入門(mén)篇（3）——數(shù)學(xué)問(wèn)題 152
5.1 簡(jiǎn)單數(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ù)的表示和化簡(jiǎn) 157
5.3.2 分?jǐn)?shù)的四則運(yùn)算 157
5.3.3 分?jǐn)?shù)的輸出 159
5.4 素?cái)?shù) 159
5.4.1 素?cái)?shù)的判斷 160
5.4.2 素?cái)?shù)表的獲取 160
5.5 質(zhì)因子分解 165
5.6 大整數(shù)運(yùn)算 170
5.6.1 大整數(shù)的存儲(chǔ) 170
5.6.2 大整數(shù)的四則運(yùn)算 171
5.7 擴(kuò)展歐幾里得算法 176
5.8 組合數(shù) 181
5.8.1 關(guān)于n!的一個(gè)問(wèn)題 181
5.8.2 組合數(shù)的計(jì)算 183
第6章 C++標(biāo)準(zhǔn)模板庫(kù)（STL）介紹 191
6.1 vector的常見(jiàn)用法詳解 191
6.2 set的常見(jiàn)用法詳解 197
6.3 string的常見(jiàn)用法詳解 202
6.4 map的常用用法詳解 213
6.5 queue的常見(jiàn)用法詳解 218
6.6 priority_queue的常見(jiàn)用法詳解 221
6.7 stack的常見(jiàn)用法詳解 227
6.8 pair的常見(jiàn)用法詳解 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)專(zhuān)題（1） 245
7.1 棧的應(yīng)用 245
7.2 隊(duì)列的應(yīng)用 251
7.3 鏈表處理 253
7.3.1 鏈表的概念 253
7.3.2 使用malloc函數(shù)或new運(yùn)算符為鏈表結(jié)點(diǎn)分配內(nèi)存空間 254
7.3.3 鏈表的基本操作 256
7.3.4 靜態(tài)鏈表 260
第8章 提高篇（2）——搜索專(zhuān)題 269
8.1 深度優(yōu)先搜索（DFS） 269
8.2 廣度優(yōu)先搜索（BFS） 274
第9章 提高篇（3）——數(shù)據(jù)結(jié)構(gòu)專(zhuān)題（2） 283
9.1 樹(shù)與二叉樹(shù) 283
9.1.1 樹(shù)的定義與性質(zhì) 283
9.1.2 二叉樹(shù)的遞歸定義 284
9.1.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與基本操作 285
9.2 二叉樹(shù)的遍歷 289
9.2.1 先序遍歷 289
9.2.2 中序遍歷 290
9.2.3 后序遍歷 291
9.2.4 層序遍歷 292
9.2.5 二叉樹(shù)的靜態(tài)實(shí)現(xiàn) 298
9.3 樹(shù)的遍歷 302
9.3.1 樹(shù)的靜態(tài)寫(xiě)法 302
9.3.2 樹(shù)的先根遍歷 303
9.3.3 樹(shù)的層序遍歷 303
9.3.4 從樹(shù)的遍歷看DFS與BFS 304
9.4 二叉查找樹(shù)（BST） 310
9.4.1 二叉查找樹(shù)的定義 310
9.4.2 二叉查找樹(shù)的基本操作 310
9.4.3 二叉查找樹(shù)的性質(zhì) 314
9.5 平衡二叉樹(shù)（AVL樹(shù)） 319
9.5.1 平衡二叉樹(shù)的定義 319
9.5.2 平衡二叉樹(shù)的基本操作 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 哈夫曼樹(shù) 342
9.8.1 哈夫曼樹(shù) 342
9.8.2 哈弗曼編碼 345
第10章 提高篇（4）——圖算法專(zhuān)題 347
10.1 圖的定義和相關(guān)術(shù)語(yǔ) 347
10.2 圖的存儲(chǔ) 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 最小生成樹(shù) 400
10.5.1 最小生成樹(shù)及其性質(zhì) 400
10.5.2 prim算法 401
10.5.3 kruskal算法 409
10.6 拓?fù)渑判?414
10.6.1 有向無(wú)環(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 最長(zhǎng)路徑 419
10.7.3 關(guān)鍵路徑 419
第11章 提高篇（5）——?jiǎng)討B(tài)規(guī)劃專(zhuān)題 425
11.1 動(dòng)態(tài)規(guī)劃的遞歸寫(xiě)法和遞推寫(xiě)法 425
11.1.1 什么是動(dòng)態(tài)規(guī)劃 425
11.1.2 動(dòng)態(tài)規(guī)劃的遞歸寫(xiě)法 425
11.1.3 動(dòng)態(tài)規(guī)劃的遞推寫(xiě)法 426
11.2 最大連續(xù)子序列和 429
11.3 最長(zhǎng)不下降子序列（LIS） 432
11.4 最長(zhǎng)公共子序列（LCS） 434
11.5 最長(zhǎng)回文子串 436
11.6 DAG最長(zhǎng)路 439
11.7 背包問(wèn)題 442
11.7.1 多階段動(dòng)態(tài)規(guī)劃問(wèn)題 442
11.7.2 01背包問(wèn)題 443
11.7.3 完全背包問(wèn)題 446
11.8 總結(jié) 447
第12章 提高篇（6）——字符串專(zhuān)題 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)自動(dòng)機(jī)的角度看待KMP算法 463
第13章 專(zhuān)題擴(kuò)展 465
13.1 分塊思想 465
13.2 樹(shù)狀數(shù)組（BIT） 470
13.2.1 lowbit運(yùn)算 470
13.2.2 樹(shù)狀數(shù)組及其應(yīng)用 470
參考文獻(xiàn) 481