文章作者: Meta Xiao
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 浮生若梦！
相关推荐
2025-04-02
数据结构笔记--导论
系列文章目录： 数据结构—导论 数据结构—算法基础 数据结构—线性表 数据结构—树 数据结构—并查集、哈希表、堆 数据结构—图 数据结构的基本知识和导论 数据结构是计算机存储、组织数据的方式，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 Nikolaus Wirth 在其著作《Algorithms + Data Structures =...
2025-04-28
数据结构笔记--算法基础
系列文章目录： 数据结构—导论 数据结构—算法基础 数据结构—线性表 数据结构—树 数据结构—并查集、哈希表、堆 数据结构—图 算法分析算法满足的五个基本特性： 输入：算法有零个或多个输入。 输出：算法有一个或多个输出。 确定性：算法的每一步骤都有确定的含义，不会出现二义性。 可行性：算法的每一步骤都是可行的，也就是说，每一步都能够通过执行有限次数完成。 有穷性：算法在执行有限步骤后，会自动结束而不会出现无限循环。 评价算法优劣的四个标准： 正确性：算法能够正确地解决实际问题。 可读性：算法应具有良好的可读性，以便于理解和维护。 健壮性：算法应能够对输入的非法数据进行检查，并作出相应的处理，而不是产生错误的结果。 效率与低存储量需求：算法应尽量减少计算时间和占用存储空间。 时间复杂度 Donald Ervin Knuth said: “Programs must be written for people to read, and only incidentally for machines to...
2025-04-28
数据结构笔记--线性表
系列文章目录： 数据结构—导论 数据结构—算法基础 数据结构—线性表 数据结构—树 数据结构—并查集、哈希表、堆 数据结构—图 线性表线性表就是一种线性结构，它是由 $n$ 个具有相同类型的数据元素组成的有限序列。 线性表的特点： 有序性：线性表中的数据元素存在一对一的线性关系，即除了第一个元素外，每个元素都有唯一的前驱元素；除了最后一个元素外，每个元素都有唯一的后继元素。 有限性：线性表中包含的数据元素个数是有限的，即线性表的长度是有限的。 线性表可以采用顺序存储结构或链式存储结构来表示。 顺序表顺序表是一种线性表的顺序存储结构，它使用一组连续的存储单元来存储线性表中的数据元素。 特点 顺序表中的数据元素在内存中是连续存储的，即每个元素都存储在相邻的存储单元中。 顺序表中的数据元素可以通过下标直接访问，即可以通过下标快速定位到指定的数据元素。 if (window.eChartecharts4121ResizeHandler) { window.removeEventListener("resize",...
2025-05-27
数据结构笔记--树
系列文章目录： 数据结构—导论 数据结构—算法基础 数据结构—线性表 数据结构—树 数据结构—并查集、哈希表、堆 数据结构—图 树树就是一种特殊的图，是一个无向图，是一种连通且无环的无向图。 含有以下内容： 树与二叉树的定义 二叉树的实现与遍历 树与森林 哈夫曼树与哈夫曼编码 树的定义：树是一个或者多个结点的有限集合，存在一个称为根的特定结点，其余结点分为若干个互不相交的集合，每个集合本身又是一棵树，这些树称为根的子树。如下图： F / \ D J / \ / \ B E G K / \ \ A C L / \ \ / / \ I H M N O P 一些重要名词 结点： 树中的每一个独立单元。 结点的度： 结点拥有的子树个数。 树的度： 树中所有结点度的最大值。 叶子： 度为0的结点或者终端结点。 分支结点：...
2025-08-31
数据结构笔记--并查集 哈希表 堆
系列文章目录： 数据结构—导论 数据结构—算法基础 数据结构—线性表 数据结构—树 数据结构—并查集、哈希表、堆 数据结构—图 本博文仍在施工中，如果作者有时间的话。 并查集并查集（Disjoint Set Union, Union-Find）是一种高效维护多个不相交集合的数据结构。它用一个森林（Forest）实现：每个集合（集合间不相交）对应一棵树，树的根（root）作为该集合的“代表”或“标识”。 主要操作有两类： 查找Find(x)：查找元素所在的集合，即找到它的根。 合并Union(x, y)：将两个集合合并为一个集合，即找到两个根，将一个根的父节点指向另一个根。 用途包括判断两个元素是否属于同一个集合、合并集合、判环（比如在 Kruskal 算法里避免生成环），等等。 基本实现由于是基于森林的写法，我们这里用父节点表示法来表示树，以及再开一个root[]来记录根节点的位置。 初始化我们把每个节点都看作一个集合，初始化时每个节点的父节点都指向自己，表示每个节点都是根节点。 1parent[i] =...
评论