数据结构与算法完全手册

本书力图以简洁明了的例子讲解笔试、面试中常涉及的数据结构与算法，包括以数组为代表的顺序存储结构及以链表为代表的链式存储结构，并依次介绍了栈、队列、树、图、Hash、几个经典的贪心算法，以及一些经典的排序及查找算法。算法的世界奇妙无穷，我们只看到了其中一丁点璀璨，万丈光芒的世界等我们一起探索和创造。 本书适用于学习数据结构和算法知识的人，希望学习如何解算法题或正在刷题的计算机行业从业者，可作为相关专业的辅导参考书。

一个让算法更简单的奋斗者。

硕士毕业，现就职于知名商业银行，负责重要核心系统的研发和管理工作。

擅长拆解算法思路，以图文并茂、通俗易懂的算法内容获得了全网读者的一致好评。

@程序员吴师兄 @帅地 @程序员cxuan @哪吒编程

百万大V高口碑力荐

“庖丁解牛”式讲解算法知识、逻辑

给你一部“活”的算法书

借助互联网，我的文章在知乎中“数据结构为什么这么难？”的提问下获得上千个赞同、上万次收藏和好评，有很多人添加 我的个人微信仅为表示感谢，这些人中有从文章中获益的考研的人，有基于这些文章深入 了解相关知识并转行到互联网相关行业的人，有在校读书的学弟、学妹，有从事互联网行 业想跳槽的人。在这些朋友和编辑老师的鼓励下，我克服重重困难终于完成了本书，希望 您可以喜欢本书，通过阅读本书有所收获。

Algorithms + Data Structures = Programs.

——Niklaus Wirth（Pascal 语言的作者，1984 年图灵奖得主）

这句话可以说是计算机编程的本质。一方面，数据结构作为计算机科学教学计划的基础科目，各种数据结构相关测试都要求熟练地掌握常用的数据结构与算法；另一方面，数据结构与算法是计算机编程的“灵魂”，学习过程充满乐趣，总能让人收获满满。

本书力图以简洁明了的例子讲解笔试、面试中常见的数据结构与算法，包括线性存储结构——数组、链式存储结构、栈、队列、树、图、Hash、贪心算法、排序及查找算法。

第 1、2 章介绍了线性存储结构（数组）和链式存储结构（链表）；第 3 章介绍了栈的相关应用；第 4 章讨论了队列的相关问题，包括普通队列、循环队列和优先级队列；第 5 章讨论了与树相关的基本数据结构，包括二叉树、堆、二叉排序树、平衡二叉树、红黑树、B 树及 B+树；第 6 章介绍了图相关的问题，包括图简介、图的存储结构、图的遍历，以及Union-Find 算法；第 7 章着重介绍了 Hash 算法及其应用；第 8 章讨论了贪心算法的基本概念，以及 Dijkstra 算法、Kruskal 算法、Prim 算法和赫夫曼编码；第 9 章介绍了一些经典的排序及查找算法。全书图文并茂，干货满满，易于自学理解及温习巩固。

本书使用 Java 语言实现数据结构与算法，代码风格遵循标准的 Java 编程规范，有清晰的注释，并针对每个算法都结合图文进行了详尽的讲解，内容清晰直观，易于理解，这让本书俨然成了一本“活着”的数据结构与算法书籍。

本书着重对算法执行过程进行介绍，对于大多数算法的时间复杂度和空间复杂度的分 析一笔带过，如需要了解详细推导过程，可参考严蔚敏老师编著的相关书籍。

本书在计算机专业数据结构课程的基础上，结合笔试和面试的考查重点，甄选了一些经典的数据结构和算法，并对其进行了讲解。

算法的世界奇妙无穷，我们只看到了其中一丁点儿璀璨，万丈光芒的世界等我们一起探索和创造。

书中代码示例基于 Java 8 编写。本书不提供书中的源代码，建议大家根据自己的理解，选择自己熟悉的编程语言，在适当的编程环境中自行编写代码，只有这样，我们对于相关内容的理解和记忆才会更加深刻。

景禹

1线性存储结构――数组
1．1 数组简介 / 2
1．2 Java中的数组 / 4
1．3 旋转数组 / 13
2 链式存储结构
2．1 单链表 / 28
2．2 双向链表 / 36
2．3 循环链表 / 43
2．4 跳表 / 48
3栈
3．1 栈的定义 / 57
3．2 栈的顺序存储结构 / 58
3．3 栈的链式存储结构 / 60
4队列
4．1 队列简介 / 65
4．2 循环队列 / 72
4．3 优先级队列 / 81
5 树
5．1 树的基本概念 / 87
5．2 树的存储结构 / 88
5．3 二叉树 / 91
5．4 树的遍历 / 100
5．5 堆 / 105
5．6 二叉排序树 / 121
5．7 平衡二叉树 / 134
5．8 红黑树 / 155
5．9 B树 / 183
5．10 B+树 / 204
6 图
6．1 图简介 / 231
6．2 图的存储结构 / 239
6．3 图的遍历 / 246
6．4 Union-Find算法 / 265
7Hash
7．1 基本概念 / 282
7．2 缓解Hash碰撞的方案 / 284
7．3 Hash算法的应用 / 303
8贪心算法
8．1 贪心算法概述 / 305
8．2 Dijkstra算法 / 307
8．3 Kruskal算法 / 316
8．4 Prim算法 / 323
8．5 赫夫曼编码 / 334
9 排序及查找算法
9．1 排序基本概念 / 348
9．2 冒泡排序 / 350
9．3 插入排序 / 356
9．4 希尔排序 / 359
9．5 选择排序 / 363
9．6 稳定选择排序 / 367
9．7 归并排序 / 370
9．8 快速排序 / 378
9．9 计数排序 / 388
9．10 基数排序 / 395
9．11 堆排序 / 400
9．12 线性搜索 / 410
9．13 二分查找 / 412