Logo

Menu

青云博客 记录、分享

Archives

2024 / 04

排序 - 冒泡排序

2024-04-24

数据结构 #数据结构和算法
冒泡排序是一种简单的排序算法，其基本思想是通过多次遍历数组，每次比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们的位置。这样，每一次遍历都会将当前未排序部分的最大元素“冒泡”到数组的末尾，重复执行直到整个数组排好序。 冒泡排序的时间复杂度为O(n^2)，效率相对较低，但它的实现简单，易于
图 - 拓扑排序

2024-04-24

数据结构 #数据结构和算法
拓扑排序是一种对有向无环图进行排序的算法。在拓扑排序中，图中的节点表示任务或事件，有向边表示任务间的依赖关系。拓扑排序可以确定任务的执行顺序，使得所有依赖关系得到满足，并且没有循环依赖。 拓扑排序的基本思想是，首先找到没有前驱节点的节点，将其加入结果序列中，然后移除该节点及其出边，再继续找到没有前驱
图 - 最小生成树

2024-04-24

数据结构 #数据结构和算法
最小生成树是图论中的一个重要概念，指的是一个连通图的一棵生成树，使得该生成树上所有边的权重之和最小。 普里姆算法和克鲁斯卡尔算法是求解最小生成树的经典方法。 普里姆算法从任意一个节点开始，逐步扩展生成树，每次选择与当前生成树连接的权重最小且未被选择过的边。通过不断添加边并将相关节点加入生成树中，最终
图 - 遍历

2024-04-24

数据结构 #数据结构和算法
在计算机科学中，图是由一些点（节点或顶点）和连接这些点的线（边或权重）组成的数据结构。遍历是对图进行搜索的过程，它可以访问所有节点，并按照一定顺序处理它们。 图遍历分为深度优先搜索和广度优先搜索两种方法。 深度优先搜索先访问一个节点及其相邻未访问过的节点，直到无法继续访问为止，然后回溯到上一个节点并
树 - 前缀树

2024-04-24

数据结构 #数据结构和算法
前缀树也被称为字典树，是一种用于高效存储和检索字符串的数据结构。 前缀树的基本思想是将每个字符串拆分成字符序列，然后使用树形结构进行存储。树的根节点为空，每个字符都对应着一个节点。从根节点到叶子节点的路径表示一个完整的字符串。
树 - 平衡二叉树

2024-04-24

数据结构 #数据结构和算法
平衡二叉树是一种特殊的二叉搜索树，旨在解决普通二叉搜索树的性能问题。它通过限制左右子树的高度差不超过一个常数来保持树的平衡性。平衡二叉树的设计使得插入、删除和查找等操作的时间复杂度维持在较小的范围内。 其中，AVL树和红黑树是两种常见的平衡二叉树。 AVL树通过维护每个节点的平衡因子（左子树高度减去
树 - 二叉搜索树

2024-04-24

数据结构 #数据结构和算法
二叉搜索树是一种常见的二叉树结构，它具有以下特点： 每个节点最多只有两个子节点，分别称为左子节点和右子节点； 对于任意节点，其左子树中的所有节点均小于该节点，其右子树中的所有节点均大于该节点； 对于每个节点，其左子树和右子树也都是二叉搜索树。 因此，二叉搜索树具有以下特性： 高效的查找功能。由于所有
树 - 红黑树

2024-04-24

数据结构 #数据结构和算法
红黑树是一种自平衡的二叉搜索树，它在普通二叉搜索树的基础上通过引入颜色属性和一些特定规则来维持树的平衡性。 红黑树的特性包括 以下几点： 每个节点都被标记为红色或黑色。 根节点始终为黑色，这是确保整个树的平衡的起点。 叶子节点是特殊的空节点，标记为黑色。 没有两个相邻的红色节点，这样确保了没有连续的
树 - 哈夫曼树

2024-04-24

数据结构 #数据结构和算法
哈夫曼树是一种用于数据压缩的树形结构，通过构建最优二叉树来实现高效的编码和解码。 在构建哈夫曼树的过程中，首先需要统计待编码数据中每个字符的出现频率。然后，将每个字符及其频率创建为一个叶子节点，并将它们组成一个节点集合。 接着，从节点集
线性表 - 链表的理解

2024-04-24

数据结构 #数据结构和算法
链表是一种常见的线性表数据结构，与数组不同，链表中的元素在内存中不是连续存储的。 链表由节点（Node）组成，每个节点包含数据元素和一个指向下一个节点的指针。 链表具有动态大小和灵活插入、删除的特点，因为节点间通过指针连接，无需移动其他元素。 常见的链表类型有单向链表、双向链表
Previous Next