Learning Path
浏览 数据结构 相关教程与章节。
主流编程语言、数据结构、设计模式、正则与基础算法。
教程
45
数据结构与算法 数据结构（英语：data structure）是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。 不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。 为什么要学习数据结构和算法？ 随着应用程序变得越来越复..
双路快速排序 双路快速排序算法是随机化快速排序的改进版本，partition 过程使用两个索引值（i、j）用来遍历数组，将 <v 的元素放在索引i所指向位置的左边，而将 >v 的元素放在索引j所指向位置的右边，v 代表标定值。 适用说明 时间和空间复杂度同随机化快速排序。 对于有大量重复元素的数组，如果使用上一节随机化快速排序效率是非常低的，导致 partition 后大于基点或者小于基点数据的子数组长度会..
三路排序算法 三路排序算法（Three-Way Partitioning）是一种特殊的快速排序变体，专门为处理包含大量重复元素的数组而优化。它的核心思想是在一次分区过程中，将数组划分为三个部分，而不是传统的两个部分。 三路快速排序是双路快速排序的进一步改进版本，三路排序算法把排序的数据分为三部分，分别为小于 v，等于 v，大于 v，v 为标定值，这样三部分的数据中，等于 v 的数据在下次递归中不再需要排序，小于 v 和大于 v 的数据也..
二分搜索树的特性 一、顺序性 二分搜索树可以当做查找表的一种实现。我们使用二分搜索树的目的是通过查找 key 马上得到 value。minimum、maximum、successor（后继）、predecessor（前驱）、floor（地板）、ceil（天花板、rank（排名第几的元素）、select（排名第n的元素是谁）这些都是二分搜索树顺序性的表现。 二、局限性 二分搜索树在时间性能上是具有局限性的。 如下图所示，元素节点一样，组成..
二分搜索树层序遍历 二分搜索树的层序遍历，即逐层进行遍历，即将每层的节点存在队列当中，然后进行出队（取出节点）和入队（存入下一层的节点）的操作，以此达到遍历的目的。 通过引入一个队列来支撑层序遍历： 如果根节点为空，无可遍历； 如果根节点不为空： 先将根节点入队； 只要队列不为空： 出队队首节点，并遍历；如果队首节点有左孩子，将左孩子入队；如果队首节点有右孩子，将右孩子入队； 下面依次演示如下步骤： （1）先取出..
二分搜索树节点删除 本小节介绍二分搜索树节点的删除之前，先介绍如何查找最小值和最大值，以及删除最小值和最大值。 以最小值为例（最大值同理）： 查找最小 key 值代码逻辑，往左子节点递归查找下去： [mycode4 type='java'] ... // 返回以node为根的二分搜索树的最小键值所在的节点 private Node minimum(Node node){ if( node.left == nu..
二分搜索树深度优先遍历 二分搜索树遍历分为两大类，深度优先遍历和层序遍历。 深度优先遍历分为三种：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后序遍历（postorder tree walk），分别为： 1、前序遍历：先访问当前节点，再依次递归访问左右子树。 2、中序遍历：先递归访问左子树，再访问自身，再递归访问右子树。 3、后序遍历：先递归访问左右子树，再访问自身节点。 前序遍..
二分搜索树节点的插入 首先定义一个二分搜索树，Java 代码表示如下: [mycode4 type='java'] public class BST { // 树中的节点为私有的类, 外界不需要了解二分搜索树节点的具体实现 private class Node { private Key key; private Value value; privat..
二分搜索树节点的查找 二分搜索树没有下标, 所以针对二分搜索树的查找操作, 这里定义一个 contain 方法, 判断二分搜索树是否包含某个元素, 返回一个布尔型变量, 这个查找的操作一样是一个递归的过程, 具体代码实现如下: [mycode4 type='java'] ... // 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法 private boolean contain(Node..
二分搜索树 一、概念及其介绍 二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件： 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。 若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。 它的左、右子树也都是二分搜索树。 如下图所示： 二、适用说明 二分搜索树有着高效的插入、删除、查询操作。平均时间的时间复杂度为 O(log n)..
高级图算法 在前面的基础教程中，我们已经学习了图的基本概念、表示方法以及广度优先搜索（BFS）和深度优先搜索（DFS）等基础算法，这些算法帮助我们解决了诸如两点之间是否连通、图的遍历等问题。 然而，现实世界中的许多复杂问题，比如社交网络中的好友推荐、地图导航中的最短路径规划、物流配送中的最优路线安排，甚至是互联网网页的排名，都需要更强大、更高效的算法。这些就是高级图算法要解决的挑战。 高级图算法就像是为解决特定复杂问题设计的专业工..
高级树结构 在掌握了二叉树、二叉搜索树等基础树结构后，我们即将踏入一个更广阔、更高效的领域——高级树结构。如果说基础树是数据结构世界中的普通公路，那么高级树结构就是精心设计的高速公路”和立交桥，它们通过巧妙的平衡规则和存储策略，确保了在数据量巨大或操作频繁时，依然能保持卓越的性能。 本章节将介绍 AVL树、红黑树、B树 和 B+树 这四种经典高级树结构。 为什么需要高级树结构？ 在深入学习之前，我们先问一个问题：有了高效的二叉搜索树（..
算法基础与分析方法 在计算机科学的世界里，算法 就是计算机的菜谱，它是一个明确的、有限的、可执行的指令序列，用于解决一个特定的问题或完成一项具体的计算任务。无论是手机上的导航软件为你规划最短路径，还是搜索引擎在毫秒间从海量数据中找出最相关的网页，背后都依赖于精心设计的算法。 理解算法的基础和分析方法，是每一位程序员从代码实现者迈向问题解决者的关键一步。本文将带你系统地认识算法的核心概念，并学习如何科学地评价一个算法的优劣。 算法的核心..
分治算法 分治法（英语：Divide and conquer）是建基于多项分支递归的一种很重要的算法范型，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 简单来说，分治就是三个步骤：分解 -> 解决 -> 合并。 想象一下，你面前有一大堆积木需要按颜色分类。如果直接动手，可能会眼花缭乱。一个更聪明的办法是..
动态规划 动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 想象一下，你正在爬一个 n 级的楼梯。每次你可以爬 1 级或 2 级台阶。那么，爬到楼顶总共有多少种不同的方法呢？ 如果你从最顶层的目标（第 n 级）开始想，可能会觉得复杂。但如果我们换个思路：要到达第 n 级台阶，你只能从第 n-..
图论结构 在计算机科学中，图被广泛用于模拟社交网络（用户是点，好友关系是线）、网页链接（网页是点，超链接是线）、通信网络乃至路径规划等问题。 图就像是一张社交网络关系图： 节点（顶点）：社交网络中的每个人 边：人与人之间的关系（好友、关注等） 权重：关系的强度（亲密度、互动频率等） 想象一下你所在城市的交通网络：各个地点（如家、学校、商场）是点，连接这些地点的道路是线。图（Graph）就是这种点和线关系..
贪心算法 贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。 贪心算法 就像我们常说的只顾眼前利益，并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优解。 想象一下，你面前有一堆不同面额的硬币（比如 1 元、5 角、1 角），你需要用最少数量的硬币凑出 1.8 元。一个很自然的想法是：每次都先拿..
哈希表 哈希表（Hash Table），也叫散列表，是一种极其高效的数据结构。哈希表能在平均情况下，以接近 O(1) 的时间复杂度进行数据的插入、删除和查找，这比数组的遍历（O(n)）和二叉搜索树的搜索（O(log n)）要快得多。 操作 数组/链表 哈希表 ..
线性数据结构 本章节，我们将介绍最基础、最常用的一类数据结构——线性数据结构。 线性数据结构就像是一排排队的人： 每个人（元素）都有明确的前后关系 除了第一个和最后一个，每个人都有一个前驱和一个后继 数据元素之间是一对一的线性关系 想象一下你正在排队买咖啡，或者整理书架上的书。这些场景都有一个共同点：元素一个接一个地排列，形成一条线。在计算机科学中，这种按顺序排列的数据集合，就是线性数据结构。线性数据结..
排序算法 排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式排列的算法，排序后的资料即可放在有序数组。 排序 是指将一组数据（例如一个数组或列表）按照某种特定的顺序（升序或降序）重新排列的过程。排序的依据通常是数据元素的某个关键码，比如数字的大小、字符串的字典序等。 排序是计算机科学中最基础、最核心的算法问题之一。无论是整理通讯录、分析考试成绩，还是数据库查询优化，排序算法都无处不在。理解不同的排序算..
树形结构 树（Tree）是一种非线性的数据结构，它模拟了自然界中树的分支层次，与数组、链表这种一个接一个的线性结构不同，树中的数据元素（称为节点）之间存在明确的一对多的层次关系。 树形结构就像是一棵真实的树： 根节点：树的根部，唯一没有父节点的节点 子节点：从某个节点分支出去的节点 叶节点：没有子节点的节点，像树叶 路径：从一个节点到另一个节点的路线 深度：从根节点到该节点的路径长度 ..
数据结构与算法简介 在计算机科学中，数据结构和算法是构建高效、可靠软件的核心基础，它们是程序员解决复杂问题的工具箱，决定了程序的运行速度和资源消耗。 想象一下，你正在整理一个杂乱无章的书架。如果只是把书随意堆放，找一本特定的书会非常困难。但如果你按照书名首字母排序，或者按照类别（如小说、历史、科学）分类，查找效率就会大大提高。数据结构就像是整理书架的方法，它定义了数据应该如何组织和存储。而算法则是查找、插入或删除一本书的具体步骤。..
深度优先遍历与连通分量 深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。 下图示例的图从 0 开始遍历顺序如右图所示： 无向图 G 的一个极大连通子图称为 G 的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。连通分..