本书是一本深入浅出，通俗易懂，原理性、趣味性和实用性相结合的算法设计教材。本书在介绍常见数据结构基本知识的基础上，着重从“易读、易学、易用”和培养“问题解决能力”两方面对常见算法进行了有效组织与阐述。 本书是衔接本科生“算法与数据结构”与研究生“算法分析与设计”两门课程的、面向高年级本科生的算法设计教材。本书内容设计合理，既包括常见的算法介绍，又包括流算法、图算法等流行算法的介绍；讲解清晰、透彻，能够帮助初学者建立信心，快速入手。本书采用“问题导引”的方式依次介绍数据结构基础知识，分治、枚举、贪心、递归等基础算法，排序、查找、字符串匹配、图论、动态规划等常见算法，计算几何基础以及流算法、图算法等高级算法。 本书适合作为高等院校各专业本科生的算法设计教材，也可以作为广大计算机爱好者及各类自学人员的参考资料。

近年来，随着ACM国际大学生程序设计竞赛(ACM ICPC)在国内深入推广和中国大学生程序设计竞赛(CCPC)以及蓝桥杯程序设计竞赛的兴起，参加程序设计竞赛的学生越来越多。程序设计竞赛主要考察大学生分析问题和运用计算机解决实际问题的综合能力，而算法设计是程序设计中的重要环节，算法实现能力对于参加程序设计竞赛的同学来说尤为重要。尤其是ACM ICPC对大学生的算法设计能力要求更高，更强调算法在有限存储空间下运行的高效性。该竞赛涉及的知识也相当广泛，包括程序设计、数据结构、离散数学、算法分析与设计、数论、图论、操作系统、概率论、计算几何等。 中国人民解放军陆军工程大学从2012年正式参加程序设计竞赛并开展了正式集中训练，2013年夏天在南京理工大学余立功老师的帮助下搭建了学校的OnlineJudge实践平台，从此程序设计课程和竞赛的实践教学都依托此平台开展，吸引了大批热衷于程序设计和算法竞赛的同学。学校程序设计竞赛团队的整体水平逐年提高，多次在ACM ICPC区域赛中摘得奖牌。本书以历年培训内容和OnlineJudge实践平台资源为基础，精选数据结构基础，分治、递归、枚举、贪心等基础算法，排序、查找、字符串匹配和高精度运算、图论、动态规划等常见算法，计算几何基础以及流算法、图算法、信息匹配等高级算法等内容，精心剖析各知识点，通过大量实例讲解常见问题的解决方案和算法设计方法。在编写过程中，力求将复杂的知识通过浅显易懂的语言来表述，从而提高读者的阅读兴趣。 本书通过对实例的分析和对数据结构、算法的讨论，着重培养学生解决问题的思维方式、解决问题的能力以及面对问题时的应变能力。 本书由雷小宇主编，第1章由郑雨编写，第2章和第4章由蒋园园编写，第3章、第8章和第5.2节由雷小宇编写，第5.1节和第6章由张赛男编写，第7章和第9章由胡琨编写。雷小宇对整个书稿进行了校对。书中的所有案例和代码由胡哲、孙毅、徐有为、王楠、李明倩和杨义鑫等同学调试通过，在此对他们的辛勤付出表示衷心的感谢。在本书编写过程中还得到了许多国内前辈、同行及CSDN论坛许多版主的指导，因篇幅有限不一一列出，一并表示诚挚的谢意！ 在此，衷心感谢所有为此书出版做出贡献的人！ 因编者水平有限，书中疏漏之处在所难免，欢迎读者提出意见和建议，以便我们及时更正。 编 者 2023年2月

第1章 数据结构基础 1 1.1 常见的数据结构 1 1.1.1 数组 1 1.1.2 链表 3 1.1.3 堆栈和队列 6 1.1.4 树和图 9 1.1.5 散列表 15 1.2 算法 16 1.2.1 算法及性质 16 1.2.2 算法性能评价 18 1.3 本章小结 20 第2章 基础算法 21 2.1 分治法 21 2.1.1 分治法的基本概念 21 2.1.2 分治法应用举例1：循环赛日程表 22 2.1.3 分治法应用举例2：大整数乘法 24 2.2 递归法 28 2.2.1 递归法的基本概念 28 2.2.2 递归应用举例1：斐波那契数列 30 2.2.3 递归优化—斐波那契数列的优化求解 32 2.2.4 递归应用举例2：饮料换购 35 2.2.5 递归应用举例3：输出全排列 36 2.3 枚举法 38 2.3.1 枚举法的基本概念 38 2.3.2 枚举法应用举例1：百鸡百钱 38 2.3.3 枚举法应用举例2：鸡兔同笼问题 39 2.3.4 枚举法应用举例3：水仙花数 41 2.3.5 枚举法应用举例4：孪生素数 42 2.3.6 枚举法应用举例5：最大公约数 43 2.4 贪心法 45 2.4.1 贪心法的基本概念 45 2.4.2 贪心法应用举例1：找零钱 46 2.4.3 贪心法应用举例2：删除k位数字 47 2.5 本章小结 48 第3章 排序算法 50 3.1 排序的相关概念 50 3.2 冒泡排序 50 3.2.1 冒泡排序算法描述 51 3.2.2 冒泡排序程序实现举例 52 3.2.3 冒泡排序算法分析 55 3.3 选择排序 55 3.3.1 选择排序算法描述 56 3.3.2 选择排序算法实现举例 57 3.3.3 选择排序算法分析 59 3.4 插入排序 60 3.4.1 插入排序算法描述 60 3.4.2 插入排序算法实现举例 61 3.4.3 插入排序算法分析 62 3.5 归并排序 62 3.5.1 归并排序算法描述 63 3.5.2 归并排序算法实现举例 63 3.5.3 归并排序算法分析 66 3.6 快速排序 66 3.6.1 快速排序算法描述 66 3.6.2 快速排序算法实现举例 68 3.6.3 快速排序算法分析 70 3.7 排序算法的性能比较 70 3.8 本章小结 70 第4章 查找 72 4.1 顺序查找 72 4.1.1 顺序查找的基本概念 72 4.1.2 顺序查找的应用举例1：找最大值 72 4.1.3 顺序查找的应用举例2：字母统计 73 4.2 二分查找 75 4.2.1 二分查找的基本概念 75 4.2.2 二分查找的应用举例1：查找元素x 75 4.2.3 二分查找的应用举例2：统计数字在有序数组中出现的次数 77 4.3 图的搜索 79 4.3.1 DFS的基本概念 79 4.3.2 BFS的基本概念 81 4.3.3 DFS与BFS的应用举例1：最小高度树 82 4.3.4 DFS与BFS的应用举例2：水壶问题 86 4.4 本章小结 89 第5章 字符串匹配和高精度运算 91 5.1 字符串匹配 91 5.1.1 朴素模式匹配 91 5.1.2 KMP模式匹配 93 5.2 高精度运算 96 5.2.1 简单计算方法—“列竖式” 96 5.2.2 大数求和的程序实现 97 5.2.3 阶乘的精确计算 100 5.3 本章小结 102 第6章 图论算法 104 6.1 最小生成树 104 6.2 最短路径 110 6.2.1 Dijkstra算法 111 6.2.2 使用优先队列的Dijkstra算法 116 6.2.3 Bellman-Ford算法 117 6.2.4 Floyd算法 120 6.3 最大匹配—匈牙利算法 124 6.4 本章小结 127 第7章 动态规划算法 128 7.1 基本思想和概念 128 7.2 算法原理和步骤 129 7.3 0-1背包问题 132 7.3.1 0-1背包问题的多阶段决策 132 7.3.2 规划方向 133 7.3.3 滚动数组 135 7.4 动态规划应用举例1：仓库的警犬 136 7.5 动态规划应用举例2：火力打击 137 7.6 本章小结 138 第8章 计算几何基础* 140 8.1 几何基础概念 140 8.1.1 点、直线、线段和向量 140 8.1.2 向量的运算 141 8.1.3 常见几何问题计算 143 8.2 包含关系 147 8.2.1 判断图形是否在矩形中 147 8.2.2 判断图形是否在多边形内部 147 8.3 凸包 148 8.3.1 凸包的定义 148 8.3.2 求解凸包的算法 148 8.4 本章小结 154 第9章 高级算法 155 9.1 流算法 155 9.1.1 数据流的基本概念 155 9.1.2 数据流的基本问题—确定频繁元素 156 9.1.3 Lossy Counting和Sticky Sampling算法 158 9.2 图算法 159 9.2.1 中心性算法 160 9.2.2 社群发现算法 164 9.3 信息匹配 166 9.3.1 穷举法 168 9.3.2 自动机 169 9.4 本章小结 170 参考文献 172