刘志全，男，博士，暨南大学网络空间安全学院副研究员、硕士生导师，研究方向包括车联网安全、无人机安全、Web安全、信任与隐私、人工智能、区块链等；近年来共在IEEE TITS、IEEE TDSC、IEEE IOTJ、IEEE TVT等国内外期刊/会议发表SCI/EI论文40余篇，申请/授权/公告国家发明专利/国外发明专利/PCT专利40余项；主持国家自然科学基金、广东省自然科学基金、广州市自然科学基金等纵向项目；指导学生获得港澳台侨创业大赛一等奖、吴渔夫学术科技创新竞赛一等奖等。

本书以Java语言为实现平台，全书分四个部分，用言简意赅的语言介绍了算法的基本概念、五种经典的算法思想、重要的数据结构以及实践中常用的几种算法。除第1章和第2章外，书中每章内容都包括了基本概念、实现方式、具体应用以及达人修炼真题。每一种算法思想中的真题都提供了相应的源代码，可供读者运行，从而达到理论与实践并重的目的。 本书涉及算法基本分析、算法基本思想、具体应用及大量真题等实用知识，内容全面、条理清楚、语言通俗。本书对计算机及相关专业本科生及研究生的算法能力提升和就业将有所帮助；此外，计算机科学相关领域的工程师以及爱好者也可以将本书作为技术参考书籍，查找所需算法的相关内容并从中得到启示；当然，对计算机科学感兴趣的读者以及IT领域项目经理也可以阅读本书，从而开启算法世界的大门。

前言

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

第二部分 经典算法思想
第3章 递归与分治法/18
3.1 递归的概念/18
3.2 分治法/22
3.3 分治法的应用/24
3.4 达人修炼真题/26

第4章 动态规划算法/52
4.1 动态规划基础/52
4.1.1 动态规划基本思想/52
4.1.2 动态规划算法举例—最长公共子序列/52
4.2 动态规划算法分析/56
4.2.1 最优子结构/56
4.2.2 重叠子问题/57
4.3 动态规划算法的应用/57
4.3.1 0-1背包问题/57
4.3.2 石子归并/59
4.3.3 常用动态规划类问题/61
4.4 达人修炼真题/63

第5章 贪心算法/83
5.1 贪心算法基础/83
5.1.1 贪心算法基本思想/83
5.1.2 贪心算法举例—装载问题/83
5.2 贪心算法的分析/84
5.3 贪心算法的应用/85
5.3.1 普通背包问题/85
5.3.2 活动安排问题/87
5.3.3 纪念品分组/89
5.4 达人修炼真题/92

第6章 回溯法/96
6.1 回溯法基本概念与算法框架/96
6.1.1 基本思路/96
6.1.2 回溯法的实现/98
6.2 回溯法的应用/99
6.2.1 0-1背包问题/99
6.2.2 八皇后问题/101
6.2.3 一摞烙饼的排序/102
6.3 达人修炼真题/105

第7章 分支界限法/109
7.1 分支界限法概念与算法框架/109
7.1.1 分支界限法基本思想/109
7.1.2 算法框架与分析/110
7.1.3 一个简单的例子（0-1背包问题）/112
7.2 分支界限法的应用/114
7.2.1 TSP问题/114
7.2.2 多段图的最短路径问题/117
7.2.3 任务分配问题/119
7.3 达人修炼真题/121

第三部分 重要数据结构
第8章 栈与队列/131
8.1 栈/131
8.2 队列/134
8.3 达人修炼真题/137

第9章 链表/153
9.1 链表概述/153
9.2 链表的操作/154
9.3 达人修炼真题/157

第10章 树与二叉树/165
10.1 树的概念与定义/165
10.1.1 基本概念/165
10.1.2 树的表示/166
10.2 二叉树/167
10.2.1 基本概念/167
10.2.2 二叉树的存储结构/168
10.2.3 遍历二叉树和线索二叉树/169
10.3 树、二叉树和森林之间的关系/173
10.4 达人修炼真题/178

第11章 哈希表/184
11.1 哈希表概述/184
11.2 哈希表的应用/187
11.3 达人修炼真题/189

第12章 并查集/202
12.1 并查集基本思想/202
12.1.1 并查集概念/203
12.1.2 并查集的实现/203
12.1.3 带权并查集/206
12.2 并查集的应用/209
12.2.1 食物链/209
12.2.2 Kruskal最小生成树算法/211
12.3 达人修炼真题/212

第13章 位图/218
13.1 位图基本概念/218
13.2 位图法的应用/223
13.2.1 位运算常见应用/223
13.2.2 位图法在大数据处理中的应用/228
13.3 达人修炼真题/229

第四部分 常用算法
第14章 排序算法/235
14.1 插入排序/235
14.2 选择排序/240
14.3 交换排序/243
14.4 归并排序/248
14.5 桶排序/基数排序/249
14.6 达人修炼真题/252

第15章 查找算法/257
15.1 基本概念/257
15.2 静态查找/258
15.3 动态查找/261
15.4 哈希查找/266
15.5 达人修炼真题/267

第16章 字符串匹配算法/273
16.1 简单字符串匹配/273
16.2 KMP算法/274
16.3 BM算法/277
16.4 SUNDAY算法/278
16.5 达人修炼真题/278

附 录/287