算法笔记

本书内容包括：C/C++快速入门、入门模拟、算法初步、数学问题、C++标准模板库(STL)、数据结构专题（两章）、搜索专题、图算法专题、动态规划专题、字符串专题、专题扩展。书中每小节的末尾均印有二维码，用以实时更新或补充书籍的内容及发布本书的勘误。

前言
第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树状数组及其应用
参考文献

最初打算写这本书是在自己刚考完研之后。那段时间，我每天都在浙江大学天勤考研群里给学弟学妹们答疑，在感受着他们的努力与进步的同时，自己仿佛又经历了一次考研，感慨颇多。渐渐地，出于兴趣，我感觉自己还能为他们做些什么，于是便萌生了写一些东西的想法。由于浙江大学机试就是PAT考试，因此一开始只是打算把PAT考试题目的题解都写一遍，但是在写作过程中慢慢发现，题解本身并不能给人带来太多的提高，而算法思想的理解和学习才是最为重要的。考虑到当时的算法入门书籍要么偏重于竞赛风格，要么偏重于面试风格，因此我便打算写一本适用于考研机试与PAT的算法书籍，以供考研的学弟学妹们学习。
    因为浙江机试的考试范围已经能覆盖大部分学校的机试范围，所以对于报考其他学校的同学也同样适用。
    第一次试印的版本给当年浙江大学机试的平均分提高了十多分，反响不错。但我深知书中仍有许多不足，也有许多想要添加的内容没来得及加进去，因此便又花费了半年时间增加了许多内容。至此，本书已经覆盖了大部分基础经典算法，不仅可以作为考研机试和PAT的学习教材，对其他的一些算法考试（例如CCF的CSP考试）或者考研初试的数据结构科目的学习和理解也很有帮助，甚至仅仅想学习经典算法的读者也能从本书中学到许多知识。由于书中很多内容都来源于自己对算法的理解，因此最终把书名定为《算法笔记》。
    本书希望让一个C语言零基础的读者能很好地进入本书的学习，因此在第2章设置了C语言的入门详解，使读者不必因自己不会C语言而有所担心，并且在对C语言的讲解中融入了部分C++的特性内容，这样读者会更容易书写顺手的代码。第3～5章是入门部分，其中介绍了一些算法思想和数学问题，读者可从中学习到一些基础但非常重要的算法思想，并培养基本的思维能力和代码能力。第6章介绍了C++标准模板库(STL)的常用内容和algorithm头文件下的常用函数，以帮助读者节省写代码的时间。第7～12章是进阶部分，其中介绍了各类经典数据结构、图算法以及较为进阶的重要算法，以使读者对经典算法和数据结构有较为深入的学习。第13章补充了一些上面没有介绍的内容，以帮助读者拓宽视野。
    另外，书中印的二维码，是用来更新或补充书籍内容及发布本书勘误的。通过扫描本书的勘误和内容更新日志二维码，读者可以得到实时更新的相应内容。致谢求职面试时的基础算法考试考研初试数据结构科目经典算法的入门学习在本书写作过程中，得到了许多朋友给予的帮助，他们是鲁蕴铖、徐涵、王改革和周伟，他们在本书的内容、细节等方面给出了很多建设性的意见，在此表示衷心的感谢。
    参加本书编写的人员还有：曾磊、唐晓瑜、庞志飞、冯杰、刘伟、王改革、柯扬斌、何世伟、朱逸晨、林炀平、杨晓海、庞博、张也、刘阳、吴联坤、于志超、朱清华、陈鸿翔、柴一平、李幸超、李邦鹏、范旭民、李疆、胡学军、厉月艳、朱华、鲁蕴铖、徐涵、王巨峰、金明健、刘欧、田唐昊。
    感谢维护PAT的浙江大学陈越老师、维护Codeup的浙江传媒学院张浩斌老师，他们耐心回复了我关于PAT和Codeup的使用问题，使我能够更好地使用上面的题目作为例题和练习题。
    感谢本书最初试印版本的读者，他们发现了书中的许多错误，并就本书的内容提了许多建议，使得本书更为完善。还有很多朋友对本书的写作十分关心，在他们的鼓励下，我才能在巨大的学业压力中最终完成本书，在此一并表示感谢。
    感谢书链团队为本书提供的二维码与资源管理系统，它让本书成为一本可以动态添加内容的书籍，增强了本书的可扩展性。
    最后，还要特别感谢机械工业出版社的吉玲编辑，在她的鼓励和帮助下，我顺利完成了本书的编写，并把更好的内容展现给读者。
    胡凡