算法筆記

前言
第1章如何使用本書
1.1本書的基本內容
1.2如何選擇編程語言和編譯器
1.3在線評測系統
1.4常見的評測結果
1.5如何高效地做題
第2章C／C++快速入門
2.1基本數據類型
2.1.1變量的定義
2.1.2變量類型
2.1.3強制類型轉換
2.1.4符號常量和const常量
2.1.5運算符
2.2順序結構
2.2.1賦值表達式
2.2.2使用scanf和printf輸入／輸出
2.2.3使用getchar和putchar輸入／輸出字符
2.2.4注釋
2.2.5typedef
2.2.6常用math函數
2.3選擇結構
2.3.1if語句
2.3.2if語句的嵌套
2.3.3switch語句
2.4循環結構
2.4.1while語句
2.4.2do…while語句
2.4.3for語句
2.4.4break和continue語句
2.5數組
2.5.1一維數組
2.5.2冒泡排序
2.5.3二維數組
2.5.4memset——對數組中每一個元素賦相同的值
2.5.5字符數組
2.5.6string.h頭文件
2.5.7sscanf與sprintf
2.6函數
2.6.1函數的定義
2.6.2再談mam函數
2.6.3以數組作為函數參數
2.6.4函數的嵌套調用
2.6.5函數的遞歸調用
2.7指針
2.7.1什麼是指針
2.7.2指針變量
2.7.3指針與數組
2.7.4使用指針變量作為函數參數
2.7.5引用
2.8結構體（struct）的使用
2.8.1結構體的定義
2.8.2訪問結構體內的元素
2.8.3結構體的初始化
2.9補充
2.9.1cin與cout
2.9.2浮點數的比較
2.9.3復雜度
2.10黑盒測試
2.10.1單點測試
2.10.2多點測試

第3章入門篇 ---------------------（1）——入門模擬
3.1簡單模擬
3.2查找元素
3.3圖形輸出
3.4日期處理
3.5進制轉換
3.6字符串處理
第4章入門篇 ---------------------（2）——算法初步
4.1排序
4.1.1選擇排序
4.1.2插入排序
4.1.3排序題與sort函數的應用
4.2散列
4.2.1散列的定義與整數散列
4.2.2字符串hash初步
4.3遞歸
4.3.1分治
4.3.2遞歸
4.4貪心
4.4.1簡單貪心
4.4.2區間貪心
4.5二分
4.5.1二分查找
4.5.2二分法拓展
4.5.3快速冪
4.6twopointers
4.6.1什麼是Mopointers
4.6.2歸並排序
4.6.3快速排序
4.7其他高效技巧與算法
4.7.1打表
4.7.2活用遞推
4.7.3隨機選擇算法

第5章入門篇 ---------------------（3）——數學問題
5.1簡單數學
5.2最大公約數與最小公倍數
5.2.1最大公約數
5.2.2最小公倍數
5.3分數的四則運算
5.3.1分數的表示和化簡
5.3.2分數的四則運算
5.3.3分數的輸出
5.4素數
5.4.1素數的判斷
5.4.2素數表的獲取
5.5質因子分解
5.6大整數運算
5.6.1大整數的存儲
5.6.2大整數的四則運算
5.7擴展歐幾里得算法
5.8組合數
5.8.1關於n！的一個問題
5.8.2組合數的計算
第6章C++標准模板庫（STL）介紹
6.1vector的常見用法詳解
6.2set的常見用法詳解
6.3string的常見用法詳解
6.4map的常用用法詳解
6.5queue的常見用法詳解
6.6priority_queue的常見用法詳解
6.7stack的常見用法詳解
6.8pair的常見用法詳解
6.9algorithm頭文件下的常用函數
6.9.1max（）、min（）和abs（）
6.9.2swap（）
6.9.3reverse（）
6.9.4next_permutation（）
6.9.5fill（）
6.9.6sort（）
6.9.7lower_bound（）和upper_bound（）

第7章提高篇 ---------------------（1）——數據結構專題（1）
7.1棧的應用
7.2隊列的應用
7.3鏈表處理
7.3.1鏈表的概念
7.3.2使用malloc函數或new運算符為鏈表結點分配內存空間
7.3.3鏈表的基本操作
7.3.4靜態鏈表

第8章提高篇 ---------------------（2）——搜索專題
8.1深度優先搜索（DFS）
8.2廣度優先搜索（BFS）

第9章提高篇 ---------------------（3）——數據結構專題（2）
9.1樹與二叉樹
9.1.1樹的定義與性質
9.1.2二叉樹的遞歸定義
9.1.3二叉樹的存儲結構與基本操作
9.2二叉樹的遍歷
9.2.1先序遍歷
9.2.2中序遍歷
9.2.3后序遍歷
9.2.4層序遍歷
9.2.5二叉樹的靜態實現
9.3樹的遍歷
9.3.1樹的靜態寫法
9.3.2樹的先根遍歷
9.3.3樹的層序遍歷
9.3.4從樹的遍歷看DFS與BFS
9.4二叉查找樹（BST）
9.4.1二叉查找樹的定義
9.4.2二叉查找樹的基本操作
9.4.3二叉查找樹的性質
9.5平衡二叉樹（AVL樹）
9.5.1平衡二叉樹的定義
9.5.2平衡二叉樹的基本操作
9.6並查集
9.6.1並查集的定義
9.6.2並查集的基本操作
9.6.3路徑壓縮
9.7堆
9.7.1堆的定義與基本操作
9.7.2堆排序
9.8哈夫曼樹
9.8.1哈夫曼樹
9.8.2哈弗曼編碼

第10章提高篇 ---------------------（4）——圖算法專題
10.1圖的定義和相關術語
10.2圖的存儲
10.2.1鄰接矩陣
10.2.2鄰接表
10.3圖的遍歷
10.3.1采用深度優先搜索（DFS）法遍歷圖
10.3.2采用廣度優先搜索（BFS）法遍歷圖
10.4最短路徑
10.4.1Dijkstra算法
10.4.2Bellman—Ford算法和SPFA算法
10.4.3Floyd算法
10.5最小生成樹
10.5.1最小生成樹及其性質
10.5.2prim算法
10.5.3kruskal算法
10.6拓撲排序
10.6.1有向無環圖
10.6.2拓撲排序
10.7關鍵路徑
10.7.1AOV網和AOE網
10.7.2最長路徑
10.7.3關鍵路徑

第11章提高篇 ---------------------（5）——動態規划專題
11.1動態規划的遞歸寫法和遞推寫法
11.1.1什麼是動態規划
11.1.2動態規划的遞歸寫法
11.1.3動態規划的遞推寫法
11.2最大連續子序列和
11.3最長不下降子序列（LIS）
11.4最長公共子序列（LCS）
11.5最長回文子串
11.6DAG最長路
11.7背包問題
11.7.1多階段動態規划問題
11.7.201背包問題
11.7.3完全背包問題
11.8總結

第12章提高篇 ---------------------（6）—字符串專題
12.1字符串hash進階
12.2KMP算法
12.2.1next數組
12.2.2KMP算法
12.2.3從有限狀態自動機的角度看待KMP算法
第13章專題擴展
13.1分塊思想
13.2樹狀數組（BIT）
13.2.1lowbit運算
13.2.2樹狀數組及其應用
參考文獻