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

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

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

◆各章自成体系，可以作为独立的学习单元（算法基础→经典算法思想→重要数据结构→常用算法），满足从 “菜鸟”向 “达人”进阶的的需求

零基础也能轻松掌握，自学算法的好搭档

◆200多个示意图，生动介绍算法执行过程

◆全书包含40道经典算法真题，每道题目均一题多解，深入剖析不同算法在性能方面的优劣

◆免费提供立体化学习资源，包括16个章节核心知识点讲解视频，各类算法实现源代码、实例数据及运行结果

前言

为什么要写这本书

随着大数据处理、人工智能等领域飞速的发展和计算机性能飞跃性的提升，无论在学术界还是产业界，计算机领域的前沿概念与技术都逐步深入到思维层面，数学在这其中发挥的作用越来越重要，越来越多的高深数学理论被用到实际中来，有效地解决了许多实际问题，例如分析几何、小波分析、数值计算等。这一切让人们逐步意识到计算机程序设计依赖的就是数学知识和算法思想。在软件工程师动手编程完成某一任务之前，先要通过一系列的过程来确定解决该任务的方法。首先，分析待求解任务/问题，将其抽象为某种数学模型；然后确定求解该问题时的资源限制（包括时间资源、电力资源、存储资源、计算资源、容错成本等）；最后在已知信息的基础上，选择已有的算法或提出新的算法，在满足资源限制的情况下解决问题。因此，可以说一个不懂算法的“菜鸟”程序员是无法独立、自主地解决具体工程问题的，也很难写出逻辑严密、简化的高质量代码。

一名优秀的计算机科学领域的工程师或科学家一定对经典算法思想有深入的理解并能够将这些算法灵活应用于解决实际问题的过程中。目前，很多顶尖IT公司都会考察应聘者的算法功底和逻辑思维能力，因为算法功底深厚的应聘者，往往可以使项目的设计模式格外优化，程序逻辑也非常严密清晰。IT公司的顶尖专家和“达人”都对算法有很深的造诣，而项目经理也必须具备超强的逻辑思维能力。

对于所有即将迈入职场的计算机科学相关领域的学生而言，应该都希望以后在职场中逐渐成长为自身所在细分领域的优秀人才，具备出色完成各类任务、解决各类问题的能力，算法可以说是解决这些问题的关键，而程序只是一件外衣。算法的功底与一个计算机科学工程师的水平上限关系密切。所以，如果你想从事计算机科学相关工作，那么就认真地培养自己的逻辑思维，从而提高算法功底吧！

本书的所有相关作者以及团队均在计算机科学领域有着多年的算法学习经历和IT领域工作经验，对算法有着较为深入的开发与实践。本书是在所有作者（包括未出现在作者名单中的幕后奉献者）钻研算法的基础上，加之长期的应用总结而完成的，并用言简意赅的语言将这些算法问题的答案展现出来。

本书特色

当前，市面上的算法书籍不计其数，从经典的《算法导论》到针对具体的细分领域（例如文本处理、神经网络等）相关算法的书籍，每一本都有自己的侧重点与特色。本书的特色主要体现在以下几方面：

1）强调算法基础，理论与应用并重。

2）包含大量实际应用中的算法真题。

3）本书以C/C++语言实现。

读者对象

1）计算机领域程序员及工程师。

2）计算机科学相关领域本科生及硕士研究生。

3）其他算法爱好者（对算法感兴趣的高中生、产品经理等）。

我们的目标是将本书作为广大IT从业者和程序开发人员学习和提升算法能力的高效学习材料，同时可以作为科研院所及企业的工程师参考的一本技术性书籍，不论你是“菜鸟”还是“达人”，阅读本书都将受益匪浅，提升解决实际编程问题的能力。

本书内容

本书共16章内容，总体可以分为以下四大部分。

第一部分（算法基础，第1、2章）

这一部分将引导读者理清算法在计算机系统中的作用以及伪代码的约定等，不仅给出了算法的定义，简单地介绍了算法的表达方式，同时引导读者思考算法的设计和分析问题，本书后面的内容都是建立在这些基础之上的。

第1章 算法综述：阐述了算法在计算机领域的定义、地位及作用，让读者对算法有一个简单、初步的认识。此外，还给出了本书中伪代码写法的约定。

第2章 算法分析：详细讨论了如何分析一个算法的时间与空间复杂度，令读者清楚衡量一个算法好坏的标准。

第二部分（经典算法思想，第3～7章）

算法设计有很多思想，但是归纳起来，算法设计中有五种思想使用最为广泛，它们分别是分治法、动态规划算法、贪心算法、回溯法与分支界限法。这一部分逐一介绍了这些经典算法思想的具体思路以及利用这些算法思想可以解决的具体问题。

第3章 递归与分治：详细介绍了递归与分治的思想以及它们的应用，此外还给出了近年来的算法真题。

第4章 动态规划算法：动态规划（Dynamic Programming，DP）是求解决策过程（Decision Process）最优化的数学方法。本章详细介绍了动态规划的思想以及可以应用这种思想解决的一些经典问题，此外还给出了近年来的算法真题。

第5章 贪心算法：这一章介绍了另一种解最优化问题的思路——贪心算法。主要介绍了贪心算法的基本思想以及可以应用这种思想解决的一些经典问题，此外还给出了近年来与此相关的算法真题。

第6章 回溯法：这一章介绍了一种适用于面对大规模处理对象时的选优搜索思想——回溯法。主要内容包括了回溯法的具体思想、实现框架和具体的应用，以及近年来的算法真题。

第7章 分支界限法：这一章介绍了回溯法之外的另一种通过搜索问题的解空间树来寻找问题解的算法——分支界限法，详细介绍了分支界限法的基本概念与算法框架，同时通过几个典型的问题来给出利用分支界限法解具体问题的方法，以及近年来的算法真题。

第三部分（重要数据结构，第8～13章）

谈到算法的时候，数据结构这个词大概率也不会缺席。数据结构也是所有计算机专业学生必修的一门课程。这一部分主要讲解了一些重要数据结构的相关知识以及应用范围。如果数据结构基础足够好的读者，可以跳过本部分，并不会影响阅读本书其余章节。

第8章 栈与队列：这一章主要介绍了栈和队列这两种线性数据结构的具体结构以及主要操作，同时通过例题阐述它们在解决实际问题时的应用，并给出近年来的算法真题。

第9章 链表：这一章介绍了另外一种线性数据结构——链表。详细介绍了链表的具体实现方式以及主要操作，同时也通过例题阐述其在解决实际问题时的应用，并给出近年来的算法真题。

第10章 树与二叉树：这一章详细介绍了树的结构及相关术语，重点介绍了常用的树结构：二叉树以及森林。

第11章 散列表：这一章主要介绍了一种基于散列函数使得记录的存储地址和它的关键码之间建立一个确定的对应关系的数据结构——散列表。主要阐述散列表的基本概念及构造思路。

第12章 并查集：这一章介绍了一种分离集合操作的抽象数据类型——并查集。它是一种常被考察的抽象数据结构。这一章重点介绍了并查集的基本概念、具体实现方法以及实际应用。

第13章 位图：这一章介绍了一种逻辑上很巧妙的描述集合的方法——位图。用位图对集合进行描述后，可以很方便地进行集合的运算，如交、并、差和补集，适用于涉及大规模数据（海量数据），但数据状态又不是很多的问题的求解。这一章将介绍位图的概念、运算方法以及具体的应用。

第四部分（常用算法，第14～16章）

这一部分重点介绍了日常学习或工作中最常用的一些算法，包括常用的排序算法、查找算法以及字符串匹配算法。这些算法并不复杂，但是都有着非常高的使用频率，掌握它们将快速提升读者算法应用和实践能力。

第14章 排序算法：排序问题一直是计算机技术研究的重要问题，有关排序算法的种类非常多也非常巧妙，其中快速排序算法很早就被列为20世纪十大算法之一，可见排序算法的重要性。本章详细分析了常见的各种排序算法，并从时间复杂度、空间复杂度、适用情况等多个方面对它们进行综合比较，并给出近年来的算法真题。仔细研读这些排序算法，也可以体会到算法设计的某些重要原则和技巧。

第15章 查找算法：在计算机应用中，查找是最常用的运算之一。典型的查找算法有顺序查找、折半查找、分块查找、二叉排序树查找、散列表查找等。这一章逐一介绍了这些算法的具体思路。

第16章 字符串匹配算法：这一章介绍了常见的字符串匹配算法，包括简单字符串匹配、KMP算法、BM算法以及SUNDAY算法，并给出近年来的算法真题。

反馈沟通

欢迎读者朋友在阅读本书过程中给予反馈意见，以利于本书的进一步完善与提升。反馈意见请发送至[email protected]，我们将尽力解决问题。

本书全体作者

目录

前言

第一部分 算法基础/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