C\C++算法从菜鸟到达人

◆各章自成体系，可以作为独立的学习单元（算法基础→经典算法思想→重要数据结构→常用算法），满足从 “菜鸟”向 “达人”进阶的的需求 零基础也能轻松掌握，自学算法的好搭档 ◆200多个示意图，生动介绍算法执行过程 ◆全书包含40道经典算法真题，每道题目均一题多解，深入剖析不同算法在性能方面的优劣 ◆免费提供立体化学习资源，包括16个章节核心知识点讲解视频，各类算法实现源代码、实例数据及运行结果

《C/C++算法从菜鸟到达人》用言简意赅的语言介绍了算法的基本概念、五种经典的算法思想、重要的数据结构以及实践中常用的几种算法。本书中每章内容都包括了基本概念、实现方式、具体应用以及近年相关的面试真题。每一种算法思想中的面试真题都提供了相应的源代码，可供读者运行，从而达到理论与实践并重的目的。《C/C++算法从菜鸟到达人》从算法基本分析到算法基本思想，再到具体应用及大量面试真题，内容全面，条理清楚，语言通俗。本书对计算机及相关专业本科生及研究生的面试、笔试将有所帮助；此外，计算机科学相关领域的工程师以及爱好者也可以将本书当作技术参考书籍，在需要时找到所需算法的相关内容直接应用或得到启示；当然，对计算机科学感兴趣的高中生以及项目经理也可以阅读本书，从而开启算法世界的大门。

郭晶晶，西安电子科技大学计算机科学与技术博士，2014年至2015年于丹麦科技大学（DTU）应用数学与计算机科学系从事博士研究工作，现任职于西安电子科技大学网络与信息安全学院，主持国家自然科学基金、航空科学基金，参与科技部重点研发计划项目等多项科研项目，研究方向包括信任管理、车载网络安全、人工智能系统安全等，目前在IEEE Internet of Things Journal, IEEE Transaction of Vehicle Technology 等国内外知名学术期刊发表论文十余篇，对算法有着深刻的理解，精通C、C++等多种高级程序设计语言。

前言 第一部分 算法基础/1 第1章 算法综述/2 1.1 算法在计算机系统中的作用/2 1.1.1 算法的定义/2 1.1.2 算法的地位/2 1.1.3 一个简单的算法/3 1.2 伪代码的约定/4 第2章 算法分析/6 2.1 准确效率分析/6 2.2 渐进效率分析/8 2.2.1 渐进记号/9 2.2.2 渐进记号的应用/10 2.3 递归式求解/15 第二部分 经典算法思想/17 第3章 递归与分治/18 3.1 递归的概念/18 3.2 分治法/22 3.3 分治法的应用/24 3.4 达人修炼/26 第4章 动态规划算法/55 4.1 动态规划基础/55 4.1.1 动态规划基本思想/55 4.1.2 动态规划算法举例——最长公共子序列/55 4.2 动态规划算法分析/59 4.2.1 很优子结构/59 4.2.2 重叠子问题/60 4.3 动态规划算法的应用/60 4.3.1 0-1背包问题/60 4.3.2 石子归并/62 4.3.3 常用动态规划类问题/65 4.4 达人修炼真题/66 第5章 贪心算法/90 5.1 贪心算法基础/90 5.1.1 贪心算法基本思想/90 5.1.2 贪心算法举例——装载问题/90 5.2 贪心算法的分析/91 5.3 贪心算法的应用/92 5.3.1 普通背包问题/92 5.3.2 活动安排问题/94 5.3.3 纪念品分组/96 5.4 达人修炼真题/99 第6章 回溯法/103 6.1 回溯法基本概念与算法框架/103 6.1.1 基本思路/103 6.1.2 回溯法的实现/105 6.2 回溯法的应用/106 6.2.1 0-1背包问题/106 6.2.2 八皇后问题/108 6.2.3 一摞烙饼的排序/110 6.3 达人修炼真题/113 第7章 分支界限法/116 7.1 分支界限法概念与算法框架/116 7.1.1 分支界限法基本思想/116 7.1.2 算法框架与分析/117 7.1.3 一个简单的例子（0-1背包问题）/119 7.2 分支界限法的应用/121 7.2.1 TSP问题/121 7.2.2 多段图的最短路径问题/125 7.2.3 任务分配问题/127 7.3 达人修炼真题/129 第三部分 重要数据结构/136 第8章 栈与队列/137 8.1 栈/137 8.2 队列/140 8.3 达人修炼真题/143 第9章 链表/164 9.1 链表概述/164 9.2 链表的操作/165 9.3 达人修炼真题/168 第10章 树与二叉树/176 10.1 树的概念与定义/176 10.1.1 基本概念/176 10.1.2 树的表示/177 10.2 二叉树/178 10.2.1 基本概念/178 10.2.2 二叉树的存储结构/179 10.2.3 遍历二叉树和线索二叉树/180 10.3 树、二叉树和森林/184 10.4 达人修炼真题/189 第11章 散列表/197 11.1 散列表概述/197 11.2 散列表的应用/200 11.3 达人修炼真题/202 第12章 并查集/219 12.1 并查集基本思想/219 12.1.1 并查集概念/220 12.1.2 并查集的实现/220 12.1.3 带权并查集/224 12.2 并查集的应用/226 12.2.1 食物链/226 12.2.2 Kruskal最小生成树算法/228 12.3 达人修炼真题/230 第13章 位图/233 13.1 位图基本概念/233 13.2 位图法的应用/238 13.2.1 位运算常见应用/238 13.2.2 位图法在大数据处理中的应用/244 13.3 达人修炼真题/245 第四部分 常用算法/251 第14章 排序算法/252 14.1 插入排序/252 14.2 选择排序/257 14.3 交换排序/261 14.4 归并排序/266 14.5 桶排序/基数排序/267 14.6 达人修炼真题/270 第15章 查找算法/275 15.1 基本概念/275 15.2 静态查找/276 15.3 动态查找/279 15.4 散列查找/286 15.5 达人修炼真题/286 第16章 字符串匹配算法/292 16.1 简单字符串匹配/292 16.2 KMP算法/293 16.3 BM算法/296 16.4 SUNDAY算法/297 16.5 达人修炼真题/298 结束语/313 算法相关书籍推荐/313