算法训练营：海量图解+竞赛刷题（入门篇）

目前，信息技术已被广泛应用于互联网、金融、航空、军事、医疗等各个领域，在未来的应用将更加广泛和深入。现在，很多中小学都已开设计算机语言课程，并且越来越多的中小学生对编程、算法感兴趣，甚至在NOIP、NOI等算法竞赛中大显身手。大学生通常参加ACM-ICPC、CCPC等算法竞赛，其获奖者更是被各大名企所青睐。

学习数据结构与算法，不仅可以使我们具备较强的思维能力及解决问题的能力，还可以使我们快速学习各种新技术，拥有超强的学习能力。

写作背景

很多读者都觉得数据结构与算法太难，市面上晦涩难懂的各种教材更是“吓退”了一大批读者。实际上，数据结构与算法并没有我们想象中那么难，反而相当有趣。每当有学生说看不懂某个算法的时候，笔者就会让其画图。笔者认为，画图是学习数据结构与算法好的方法，它可以把抽象难懂的数据结构、算法展现得生动形象、简单易懂。在出版《趣学数据结构》《趣学算法》两本书之后，很多读者建议笔者写一本算法竞赛的书，延续前两本书的图解风格，再加上竞赛刷题的内容。经过近两年的筹备，《算法训练营：海量图解 竞赛刷题（入门篇）》和《算法训练营：海量图解 竞赛刷题（进阶篇）》两本书终于和大家见面了！这两本书以海量图解的形式，结合大量竞赛实例进行讲解。全书图文并茂，可帮助读者全面、系统地搭建数据结构与算法知识体系，以模块化方式逐一拆解算法问题。以通俗易懂的方式讲解算法，让更多的读者爱上算法，这也是笔者写作这两本书的初衷。

本书详细讲解常用的数据结构和算法，还增加了语言基础和STL函数的内容。如果读者已经熟悉C  ，则可跳过这些基础章节。本书不是知识点的堆砌，也不是粘贴代码的简单题解，而是将知识点讲解和对应的竞赛刷题融会贯通，可使读者在轻松阅读的同时进行实战，在实战中体会算法的妙处，感受算法之美。

本书特色

本书具有以下特色。

（1）完美图解，通俗易懂。本书对每个算法的基本操作都有图解演示。通过图解，许多问题都变得简单，可迎刃而解。

（2）实例丰富，简单有趣。本书结合大量竞赛实例，讲解如何利用数据结构与算法解决实际问题，使复杂难懂的问题变得简单有趣，帮助读者轻松掌握算法知识，体会其中的妙处。

（3）深入浅出，透析本质。本书透过问题看本质，重点讲解如何分析和解决问题。本书采用了简洁易懂的代码，对数据结构设计和算法的描述全面细致，而且有算法复杂性分析及优化过程。

（4）实战演练，循序渐进。本书在对每个数据结构与算法讲解清楚后，都进行了实战演练，使读者在实战中体会数据结构与算法的设计和操作，从而提高了独立思考、动手实践的能力。书中有丰富的练习题和竞赛题，可帮助读者及时检验对知识的掌握情况，为从小问题出发、逐步解决大型复杂性工程问题奠定基础。

（5）网络资源，技术支持。本书为读者提供书中所有范例程序的源代码、竞赛题及答案解析，读者可以对这些源代码自由修改编译，以符合自己的需要。本书提供博客、微信群、QQ群技术支持，可随时为读者答疑解惑。

建议和反馈

写书是极其琐碎、繁重的工作，尽管笔者已经竭力使本书和网络支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，因为对本书的评论和建议有利于我们改进和提高，以帮助更多的读者。如果对本书有什么评论和建议，或者有问题需要帮助，可以加入QQ群1029262418，也可以致信rainchxy@126.com与笔者交流，笔者将不胜感激。

读者资源请参照本书封底提示。

致谢

感谢笔者的家人和朋友在本书写作过程中提供的大力支持。感谢电子工业出版社工作严谨、高效的张国霞编辑，她的认真负责促成本书的早日出版。感谢提供宝贵意见的同事们，感谢提供技术支持的同学们。感恩遇到这么多良师益友！

本书以海量图解的形式，详细讲解常用的数据结构与算法，又融入大量的竞赛实例和解题技巧。通过对本书的学习，读者可掌握12种初级数据结构、15种常用STL函数、10种二叉树和图的应用，以及8种搜索技术，并领悟不同的数据结构和算法的精髓，熟练应用各种算法解决实际问题。

本书总计9章。第1章讲解C  语言基础，包括语法、函数、递归和数组；第2章讲解算法入门知识，包括算法复杂度计算、贪心算法、分治算法和STL应用；第3章讲解线性表的应用，包括顺序表、单链表、双向链表、循环链表和静态链表；第4章讲解栈和队列的应用，包括顺序栈、链栈、顺序队列和链队列；第5章讲解树的应用，包括树的存储、二叉树遍历与还原、哈夫曼编码；第6章讲解图论基础，包括图的存储、图的遍历和图的连通性；第7章讲解图的应用，包括短路径、小生成树、拓扑排序和关键路径；第8章讲解查找算法，包括哈希表、字符串模式匹配、二叉查找树和平衡二叉树；第9章讲解搜索技术，包括二分搜索、深度优先搜索、广度优先搜索和启发式搜索。

本书面向对算法感兴趣的读者，无论是想扎实内功或参加算法竞赛的学生，还是想进入名企的学生、求职者，抑或是想提升技术的在职人员，都可以参考本书。若读者想学习数据结构与算法方面的进阶知识，则可参考《算法训练营：海量图解 竞赛刷题（进阶篇）》。

陈小玉 副教授，高级程序员，主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营：海量图解 竞赛刷题（入门篇）》《算法训练营：海量图解 竞赛刷题（进阶篇）》，所教学生多次获得ACM、蓝桥杯等算法竞赛奖项。

第1章  语言基础... 1

1.1  开启算法之旅：hello world! 1

1.2  常见数据类型及其表达范围... 2

1.3  玩转输入输出... 2

1.4  人生就是不断地选择：if…else. 9

1.5  每天都有很多次重复：for/while. 13

1.6  如何轻松写一个函数... 20

1.7  从前有座山，山里有座庙：递归之法... 25

1.8  信息携带者：定义一个结构体... 29

1.9  巧用数组——好玩贪吃蛇... 31

1.10  玩转字符串——不一样的风格... 37

第2章  算法入门... 42

2.1  算法之美... 42

2.1.1  如何评价一个算法的优劣... 42

2.1.2  算法复杂度的计算方法... 45

2.2  贪心算法... 48

2.2.1  贪心本质... 48

2.2.2  装载问题... 49

2.3  分治算法... 51

2.3.1  分治算法秘籍... 51

2.3.2  合并排序... 51

2.3.3  快速排序... 57

2.4  STL应用... 65

2.4.1  vector 65

训练  间谍... 67

2.4.2  栈... 68

训练  Web导航... 69

2.4.3  queue. 75

训练  骑士移动... 75

2.4.4  list 77

训练  士兵队列训练... 78

2.4.5  deque. 79

训练  度度熊学队列... 80

2.4.6  priority_queue. 82

训练  黑盒子... 83

2.4.7  bitset 85

训练  集合运算... 88

2.4.8  set/multiset 90

训练1  集合合并... 91

训练2  并行处理... 92

2.4.9  map/multimap. 94

训练1  硬木种类... 96

训练2  双重队列... 97

训练3  水果... 99

2.4.10  STL的常用函数... 100

训练1  差的中位数... 106

训练2  中位数... 108

训练3  订单管理... 109

训练4  字谜... 110

第3章  线性表的应用... 112

3.1  顺序表... 112

3.2  单链表... 116

3.3  双向链表... 119

3.4  循环链表... 122

3.5  静态链表... 123

训练1  区块世界... 126

训练2  悲剧文本... 132

训练3  移动盒子... 133

第4章  栈和队列的应用... 140

4.1  顺序栈... 140

4.2  链栈... 143

4.3  顺序队列... 146

4.4  链队列... 155

训练1  括号匹配... 158

训练2  铁轨... 160

训练3  矩阵连乘... 164

训练4  打印队列... 168

训练5  并发模拟器... 171

第5章  树的应用... 187

5.1  树... 187

5.1.1  树的存储... 190

5.1.2  树、森林与二叉树的转换... 193

5.2  二叉树... 194

5.2.1  二叉树的性质... 195

5.2.2  二叉树的存储结构... 200

5.2.3  二叉树的创建... 202

5.3  二叉树遍历... 210

5.3.1  先序遍历... 210

5.3.2  中序遍历... 214

5.3.3  后序遍历... 217

5.3.4  层次遍历... 221

5.3.5  遍历序列还原树... 224

训练1  新二叉树... 228

训练2  还原树... 229

训练3  树... 230

5.4  哈夫曼树... 232

原理  哈夫曼编码... 232

训练1  围栏修复... 245

训练2  信息熵... 246

训练3  转换哈夫曼编码... 248

训练4  可变基哈夫曼编码... 251

第6章  图论基础... 256

6.1  图的存储... 257

6.1.1  邻接矩阵... 257

6.1.2  边集数组... 263

6.1.3  邻接表... 263

6.1.4  链式前向星... 271

训练1  的节点... 274

训练2  有向图D和E. 276

训练3  奶牛排序... 278

6.2  图的遍历... 279

6.2.1  广度优先遍历... 279

6.2.2  深度优先遍历... 283

训练1  油田... 287

训练2  理想路径... 290

训练3  骑士的旅程... 293

训练4  抓住那头牛... 295

6.3  图的连通性... 298

6.3.1  连通性的相关知识... 298

6.3.2  Tarjan算法... 302

训练1  电话网络... 306

训练2  道路建设... 308

训练3  图的底部... 311

训练4  校园网络... 313

第7章  图的应用... 316

7.1  短路径... 316

7.1.1  Dijkstra算法... 316

7.1.2  Floyd算法... 322

7.1.3  Bellman-Ford算法... 326

7.1.4  SPFA算法... 328

训练1  重型运输... 329

训练2  货币兑换... 331

训练3  虫洞... 332

训练4  短路径... 335

7.2  小生成树... 336

7.2.1  Prim算法... 337

7.2.2  Kruskal算法... 346

训练1  丛林之路... 351

训练2  联网... 352

训练3  空间站... 354

训练4  道路建设... 356

7.3  拓扑排序... 358

原理  拓扑排序... 358

训练1  家族树... 362

训练2  全排序... 364

训练3  标签球... 366

训练4  秩序... 369

7.4  关键路径... 371

原理  关键路径... 371

训练1  关键路径... 380

训练2  指令安排... 382

训练3  家务琐事... 384

训练4  免费DIY之旅... 385

训练5  游戏玩家... 388

第8章  查找算法... 391

8.1  哈希表... 391

8.1.1  散列函数... 392

8.1.2  处理冲突的方法... 394

8.1.3  散列查找及性能分析... 404

训练1  雪花... 406

训练2  公式... 407

训练3  正方形... 409

8.2  字符串模式匹配... 411

8.2.1  BF算法... 412

8.2.2  KMP算法... 415

训练1  统计单词数... 421

训练2  KMP字符串匹配... 423

8.3  二叉查找树... 424

原理  二叉查找树详解... 424

训练1  落叶... 436

训练2  完全二叉搜索树... 439

训练3  硬木种类... 441

训练4  二叉搜索树... 442

8.4  平衡二叉树... 444

原理  AVL树详解... 445

训练1  平衡二叉树... 458

训练2  双重队列... 461

训练3  黑盒子... 464

训练4  硬木种类... 465

第9章  搜索技术... 466

9.1  二分搜索... 466

原理  二分搜索技术... 466

训练1  跳房子游戏... 471

训练2  烘干衣服... 475

训练3  花环... 477

训练4  电缆切割... 479

9.2  深度优先搜索... 480

9.2.1  回溯法... 480

9.2.2  子集树... 483

9.2.3  m叉树... 491

9.2.4  排列树... 499

训练1  魅力手镯... 515

训练2  图的m着色问题... 516

训练3  N皇后问题... 517

9.2.5  DFS 剪枝优化... 517

训练1  数独游戏... 518

训练2  生日蛋糕... 521

训练3  木棒... 522

9.3  广度优先搜索... 524

9.3.1  分支限界法... 525

9.3.2  队列式广度优先搜索.... 525

9.3.3  优先队列式广度优先搜索... 535

训练1  迷宫问题... 541

训练2  加满油箱... 542

9.3.4  嵌套广度优先搜索... 545

训练  推箱子... 545

9.3.5  双向广度优先搜索... 549

训练  魔鬼Ⅱ... 549

9.4  启发式搜索... 551

9.4.1  A*算法... 552

9.4.2  IDA*算法... 552

训练1  八数码... 552

训练2  八数码II 562

训练3  第K短路... 565

训练4  幂运算... 567

本书以海量图解的形式，详细讲解常用的数据结构与算法，又融入大量的竞赛实例和解题技巧。通过对本书的学习，读者可掌握12种初级数据结构、15种常用STL函数、10种二叉树和图的应用，以及8种搜索技术，并领悟不同的数据结构和算法的精髓，熟练应用各种算法解决实际问题。

本书总计9章。第1章讲解C  语言基础，包括语法、函数、递归和数组；第2章讲解算法入门知识，包括算法复杂度计算、贪心算法、分治算法和STL应用；第3章讲解线性表的应用，包括顺序表、单链表、双向链表、循环