作者：胡凡 日期：2016-07-03 20:30:23
这是一本零基础就能读懂的算法书籍，读者不需要因为自己没有语言基础而畏惧。书籍的第2章便是一个C语言的入门教程，内容非常易懂，并且十分实用，阅读完这章就可以对本书需要的C语言基础有一个较好的掌握。本书已经覆盖了大部分基础经典算法，不仅可以作为考研机试和PAT的学习教材，对其他的一些算法考试（例如CCF的CSP考试）或者考研初试的数据结构科目的学习和理解也很有帮助，甚至仅仅想学习经典算法的读者也能从本书中学到许多知识，本书还有配套的《算法笔记上机训练实战指南》本书的作者是同样经历过考研机试和各类算法考试的专家型学长，知晓这类考试中的痛点，以及考生在学习算法时容易产生困惑的地方，因此可以把本书看作是学长为你奉献的满满的经验干货，这是*有价值的东西。本书的*个试印版本献给了浙大考研学子，并令当年的浙大考研机试平均分增加了十多分，收获了考生的大量好评。但作者并没有止步于此，经过了半年多时间的内容完善和补充之后，新的版本在新一年的考研机试中再次获得了考生的一致赞美。*后，在经过精心整理之后，书籍终于定稿，并编撰成书。我们知道，纸质书籍的一个弱点就在于不能像软件一样随时更新内容，但本书采用了与二维码相结合的方式，使得本书变为能够随时更新内容的书籍，读者也可以随时从二维码中找到勘误。这种作者和读者能够相互沟通的方式让书籍变“活”了，也能够帮助提升读者对知识的理解。 本书内容包括：C/C快速入门、入门模拟、算法初步、数学问题、C标准模板库（STL）、数据结构专题（二章）、搜索专题、图算法专题、动态规划专题、字符串专题、专题扩展。本书印有二维码，用来实时更新、补充内容及发布勘误的。本书可作为计算机专业研究生入学考试复试上机、各类算法等级考试（如PAT、CSP等）的辅导书，也可作为“数据结构”科目的考研教材及辅导书内容的补充。本书还是学习C语言、数据结构与算法的入门辅导书，非常适合零基础的学习者对经典算法进行学习。
目录：
前言第1章如何使用本书 11.1本书的基本内容 11.2如何选择编程语言和编译器 11.3在线评测系统 21.4常见的评测结果 31.5如何高效地做题 4第2章C/C快速入前言第1章 如何使用本书11.1 本书的基本内容11.2 如何选择编程语言和编译器11.3 在线评测系统21.4 常见的评测结果31.5 如何高效地做题4第2章 C/C快速入门52.1 基本数据类型72.1.1 变量的定义72.1.2 变量类型72.1.3 强制类型转换112.1.4 符号常量和const常量122.1.5 运算符142.2 顺序结构172.2.1 赋值表达式172.2.2 使用scanf和printf输入/输出182.2.3 使用getchar和putchar输入/输出字符232.2.4 注释242.2.5 typedef242.2.6 常用math函数252.3 选择结构282.3.1 if语句282.3.2 if语句的嵌套312.3.3 switch语句322.4 循环结构342.4.1 while语句342.4.2 dowhile语句352.4.3 for语句362.4.4 break和continue语句382.5 数组392.5.1 一维数组392.5.2 冒泡排序412.5.3 二维数组432.5.4 memset——对数组中每一个元素赋相同的值462.5.5 字符数组472.5.6 string.h头文件502.5.7 sscanf与sprintf532.6 函数552.6.1 函数的定义552.6.2 再谈main函数582.6.3 以数组作为函数参数582.6.4 函数的嵌套调用592.6.5 函数的递归调用602.7 指针612.7.1 什么是指针612.7.2 指针变量622.7.3 指针与数组632.7.4 使用指针变量作为函数参数652.7.5 引用682.8 结构体（struct）的使用702.8.1 结构体的定义702.8.2 访问结构体内的元素712.8.3 结构体的初始化722.9 补充742.9.1 cin与cout742.9.2 浮点数的比较752.9.3 复杂度782.10 黑盒测试802.10.1 单点测试802.10.2 多点测试80第3章 入门篇（1）——入门模拟853.1 简单模拟853.2 查找元素873.3 图形输出893.4 日期处理913.5 进制转换933.6 字符串处理95第4章 入门篇（2）——算法初步994.1 排序994.1.1 选择排序994.1.2 插入排序1004.1.3 排序题与sort函数的应用1014.2 散列1064.2.1 散列的定义与整数散列1064.2.2 字符串hash初步1094.3 递归1114.3.1 分治1114.3.2 递归1124.4 贪心1184.4.1 简单贪心1184.4.2 区间贪心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 随机选择算法149第5章 入门篇（3）——数学问题1525.1 简单数学1525.2 最大公约数与最小公倍数1545.2.1 最大公约数1545.2.2 最小公倍数1565.3 分数的四则运算1565.3.1 分数的表示和化简1575.3.2 分数的四则运算1575.3.3 分数的输出1595.4 素数1595.4.1 素数的判断1605.4.2 素数表的获取1605.5 质因子分解1655.6 大整数运算1705.6.1 大整数的存储1705.6.2 大整数的四则运算1715.7 扩展欧几里得算法1765.8 组合数1815.8.1 关于n!的一个问题1815.8.2 组合数的计算183第6章 C标准模板库（STL）介绍1916.1 vector的常见用法详解1916.2 set的常见用法详解1976.3 string的常见用法详解2026.4 map的常用用法详解2136.5 queue的常见用法详解2186.6 priority_queue的常见用法详解2216.7 stack的常见用法详解2276.8 pair的常见用法详解2306.9 algorithm头文件下的常用函数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）——数据结构专题（1）2457.1 栈的应用2457.2 队列的应用2517.3 链表处理2537.3.1 链表的概念2537.3.2 使用malloc函数或new运算符为链表结点分配内存空间2547.3.3 链表的基本操作2567.3.4 静态链表260第8章 提高篇（2）——搜索专题2698.1 深度优先搜索（DFS）2698.2 广度优先搜索（BFS）274第9章 提高篇（3）——数据结构专题（2）2839.1 树与二叉树2839.1.1 树的定义与性质2839.1.2 二叉树的递归定义2849.1.3 二叉树的存储结构与基本操作2859.2 二叉树的遍历2899.2.1 先序遍历2899.2.2 中序遍历2909.2.3 后序遍历2919.2.4 层序遍历2929.2.5 二叉树的静态实现2989.3 树的遍历3029.3.1 树的静态写法3029.3.2 树的先根遍历3039.3.3 树的层序遍历3039.3.4 从树的遍历看DFS与BFS3049.4 二叉查找树（BST）3109.4.1 二叉查找树的定义3109.4.2 二叉查找树的基本操作3109.4.3 二叉查找树的性质3149.5 平衡二叉树（AVL树）3199.5.1 平衡二叉树的定义3199.5.2 平衡二叉树的基本操作3209.6 并查集3289.6.1 并查集的定义3289.6.2 并查集的基本操作3289.6.3 路径压缩3309.7 堆3359.7.1 堆的定义与基本操作3359.7.2 堆排序3399.8 哈夫曼树3429.8.1 哈夫曼树3429.8.2 哈弗曼编码345第10章 提高篇（4）——图算法专题34710.1 图的定义和相关术语34710.2 图的存储34810.2.1 邻接矩阵34810.2.2 邻接表34810.3 图的遍历35010.3.1 采用深度优先搜索（DFS）法遍历图35010.3.2 采用广度优先搜索（BFS）法遍历图35910.4 最短路径36710.4.1 Dijkstra算法36710.4.2 Bellman-Ford算法和SPFA算法39110.4.3 Floyd算法39810.5 最小生成树40010.5.1 最小生成树及其性质40010.5.2 prim算法40110.5.3 kruskal算法40910.6 拓扑排序41410.6.1 有向无环图41410.6.2 拓扑排序41510.7 关键路径41710.7.1 AOV网和AOE网41710.7.2 最长路径41910.7.3 关键路径419第11章 提高篇（5）——动态规划专题42511.1 动态规划的递归写法和递推写法42511.1.1 什么是动态规划42511.1.2 动态规划的递归写法42511.1.3 动态规划的递推写法42611.2 最大连续子序列和42911.3 最长不下降子序列（LIS）43211.4 最长公共子序列（LCS）43411.5 最长回文子串43611.6 DAG最长路43911.7 背包问题44211.7.1 多阶段动态规划问题44211.7.2 01背包问题44311.7.3 完全背包问题44611.8 总结447第12章 提高篇（6）——字符串专题44912.1 字符串hash进阶44912.2 KMP算法45512.2.1 next数组45612.2.2 KMP算法45812.2.3 从有限状态自动机的角度看待KMP算法463第13章 专题扩展46513.1 分块思想46513.2 树状数组（BIT）47013.2.1 lowbit运算47013.2.2 树状数组及其应用470参考文献481前言最初打算写这本书是在自己刚考完研之后。那段时间，我每天都在浙江大学天勤考研群里给学弟学妹们答疑，在感受着他们的努力与进步的同时，自己仿佛又经历了一次考研，感最初打算写这本书是在自己刚考完研之后。那段时间，我每天都在浙江大学天勤考研群里给学弟学妹们答疑，在感受着他们的努力与进步的同时，自己仿佛又经历了一次考研，感慨颇多。渐渐地，出于兴趣，我感觉自己还能为他们做些什么，于是便萌生了写一些东西的想法。由于浙江大学机试就是PAT考试，因此一开始只是打算把PAT考试题目的题解都写一遍，但是在写作过程中慢慢发现，题解本身并不能给人带来太多的提高，而算法思想的理解和学习才是最为重要的。考虑到当时的算法入门书籍要么偏重于竞赛风格，要么偏重于面试风格，因此我便打算写一本适用于考研机试与PAT的算法书籍，以供考研的学弟学妹们学习。因为浙江机试的考试范围已经能覆盖大部分学校的机试范围，所以对于报考其他学校的同学也同样适用。第一次试印的版本给当年浙江大学机试的平均分提高了十多分，反响不错。但我深知书中仍有许多不足，也有许多想要添加的内容没来得及加进去，因此便又花费了半年时间增加了许多内容。至此，本书已经覆盖了大部分基础经典算法，不仅可以作为考研机试和PAT的学习教材，对其他的一些算法考试（例如CCF的CSP考试）或者考研初试的数据结构科目的学习和理解也很有帮助，甚至仅仅想学习经典算法的读者也能从本书中学到许多知识。由于书中很多内容都来源于自己对算法的理解，因此最终把书名定为《算法笔记》。本书希望让一个C语言零基础的读者能很好地进入本书的学习，因此在第2章设置了C语言的入门详解，使读者不必因自己不会C语言而有所担心，并且在对C语言的讲解中融入了部分C的特性内容，这样读者会更容易书写顺手的代码。第3~5章是入门部分，其中介绍了一些算法思想和数学问题，读者可从中学习到一些基础但非常重要的算法思想，并培养基本的思维能力和代码能力。第6章介绍了C标准模板库（STL）的常用内容和algorithm头文件下的常用函数，以帮助读者节省写代码的时间。第7~12章是进阶部分，其中介绍了各类经典数据结构、图算法以及较为进阶的重要算法，以使读者对经典算法和数据结构有较为深入的学习。第13章补充了一些上面没有介绍的内容，以帮助读者拓宽视野。另外，书中印的二维码，是用来更新或补充书籍内容及发布本书勘误的。通过扫描本书的勘误和内容更新日志二维码，读者可以得到实时更新的相应内容。最后，由于编者水平有限，尽管对本书进行了多次校对，书中可能仍有一些待改进的地方，敬请广大读者提出宝贵建议！本书的适用范围• 研究生复试上机考试• PAT甲级、乙级考试• CCF的CSP认证（或其他算法）• 求职面试时的基础算法考试• 考研初试数据结构科目• 经典算法的入门学习