DSA数据结构与算法

更新: 2025/2/24 字数: 0 字 时长: 0 分钟

序

本知识库中的大部分内容都来源《Hello 算法》这本书，相关资源可以在我的网站主页的《资源目录》页面里面找到。

前言

计算机的出现给世界带来了巨大变革，它凭借高速的计算能力和出色的可编程性，成为了执行算法与处理数据的理想媒介。无论是电子游戏的逼真画面、自动驾驶的智能决策，还是 AlphaGo 的精彩棋局、ChatGPT 的自然交互，这些应用都是算法在计算机上的精妙演绎。

事实上，在计算机问世之前，算法和数据结构就已经存在于世界的各个角落。早期的算法相对简单，例如古代的计数方法和工具制作步骤等。随着文明的进步，算法逐渐变得更加精细和复杂。从巧夺天工的匠人技艺、到解放生产力的工业产品、再到宇宙运行的科学规律，几乎每一件平凡或令人惊叹的事物背后，都隐藏着精妙的算法思想。

同样，数据结构无处不在：大到社会网络，小到地铁线路，许多系统都可以建模为“图”；大到一个国家，小到一个家庭，社会的主要组织形式呈现出“树”的特征；冬天的衣服就像“栈”，最先穿上的最后才能脱下；羽毛球筒则如同“队列”，一端放入、另一端取出；字典就像一个“哈希表”，能够快速查找目标词条。

本知识库旨在通过清晰易懂的动画图解和可运行的代码示例，使读者理解算法和数据结构的核心概念，并能够通过编程来实现它们。在此基础上，本书致力于揭示算法在复杂世界中的生动体现，展现算法之美。希望本知识库能够帮助到你！

建议

数据结构与算法是独立于编程语言的，而本知识库是基于 Python 编程语言的实现。

使用方法

为了获得最佳的阅读体验，建议你了解本知识库的使用方法。

行文风格

• 重点内容和总结性语句会加粗，这类文字值得特别关注。
• 有特指含义的词句会使用“引号”标注，以避免歧义。
• 本知识库均以 Python 为准，例如使用 None 来表示“空”。
• 本知识库部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注释、内容注释、多行注释。

"""标题注释，用于标注函数、类、测试样例等"""

# 内容注释，用于详解代码

"""
多行
注释
"""

图主文辅

相较于文字，视频和图片具有更高的信息密度和结构化程度，更易于理解。在本知识库中，重点和难点知识将主要通过动画以图解形式展示，而文字则作为解释与补充。如果你在阅读本知识库时，发现某段内容提供了如图所示的动画图解，请以图为主、以文字为辅，综合两者来理解内容。

代码实践

本知识库的配套代码托管在 GitHub 仓库，如果你已经安装了 Git ，可以通过 git clone https://github.com/krahets/hello-algo.git 命令克隆本仓库。当然，你也可以在下图所示的位置，点击“Download ZIP”按钮直接下载代码压缩包，然后在本地解压即可。

在源代码中附有测试样例，可一键运行。如果时间允许，建议你参照代码自行敲一遍。如果学习时间有限，请至少通读并运行所有代码。与阅读代码相比，编写代码的过程往往能带来更多收获。动手学，才是真的学。

章节内容

本知识库的主要内容如下图所示：

• 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示例等。
• 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。
• 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤和示例问题等。

学习路线

从总体上看，我们可以将学习数据结构与算法的过程划分为三个阶段。

1. 阶段一：算法入门。我们需要熟悉各种数据结构的特点和用法，学习不同算法的原理、流程、用途和效率等方面的内容。
2. 阶段二：刷算法题。建议从热门题目开刷，先积累至少 100 道题目，熟悉主流的算法问题。初次刷题时，“知识遗忘”可能是一个挑战，但请放心，这是很正常的。我们可以按照“艾宾浩斯遗忘曲线”来复习题目，通常在进行 3～5 轮的重复后，就能将其牢记在心。推荐的题单和刷题计划请见此 GitHub 仓库。
3. 阶段三：搭建知识体系。在学习方面，我们可以阅读算法专栏文章、解题框架和算法教材，以不断丰富知识体系。在刷题方面，可以尝试采用进阶刷题策略，如按专题分类、一题多解、一解多题等，相关的刷题心得可以在各个社区找到。

如下图所示，本知识库内容主要涵盖“阶段一”，旨在帮助你更高效地展开阶段二和阶段三的学习。