type
status
date
slug
summary
tags
category
icon
password
绪论
术语
- 基本结构
- 集合
- 线性结构
- 树形结构
- 图状结构
- 存储结构
- 顺序
- 链式
- 数据类型
- 原子类型（不可分解）
- 结构类型（可分解）
- 抽象数据类型（ADT），数学特性
- 原子类型
- 固定聚合类型
- 可变聚合类型
字符串流
线性表
线性表（Linearlist）Dictation链表
链表(Linklist)串
KMP算法
栈
动态数组栈树
二叉树Huffman树排序二叉树
图
存储
邻接表
- 记录以该节点为起点的边的终点。
- 每个item相当于记录一条边，可以自己加东西
邻接矩阵
- 直观呈现点与点的关系
- 缺点：非空间，尤其是稀疏图
搜索
深度优先搜索（DFS）
- 邻接矩阵
- 邻接表
广度优先搜索（BFS）
- 邻接矩阵
- 邻接表
连通分量
一直搜索，每搜一次加一次分量，直到所有顶点都被访问过。
最小生成树
Prim算法
- 基本思想：贪心算法
- 将点分为的两类，已在生成树中和未在树中
- 开始时树中只有起点一个
- 每次循环从生成树中的点与未在树中的点所构成的所有边（所有跨越两类点边界的边）中选取权值最小的边，将边的终点纳入树中，直到遍历完所有点。
- 以点为单位，点少优势
Kruskal算法
- 基本思想：贪心算法
- 将所有边列出来，挑权值小的边加入生成树
- 选边时运用并查集检查边的两点是否连通（即它们的根节点是否一致），如果连通则不选
- 遍历完所有边即可
- 以边为单位，边少优势
最短路径
Dijkstra算法
- 动态规划思路，基于之前算得各点的最短距离，在添加一个点后再次更新各个点的最短距离，直到到达终点。
- 只能计算正权边，负权边需要用Bellman-Ford算法
邻接矩阵
邻接表
Floyd算法
- 基本思想：动态规划
- 每次更新两点之间插入第三点是否会成为更短路径
- 三层循环
- 可以直接求得所有顶点的最短路径问题
邻接矩阵
有向无环图（DAG）
- 有向性：表示一种依赖关系或顺序关系
- 无环性：图中没有回路，适合表示具有明确顺序关系的场景
判断
DFS，拓扑排序，tarjan缩点
- DFS：判断是否存在环（遍历到终点为搜索根节点的边）
AOV网
- 用有向图的顶点表示活动，用弧表示活动间的优先关系，则称该有向图为顶点表示活动的AOV网(Activity On Vertex Network)
- 无权值，仅用于表示活动之间的依赖关系（拓扑排序）
AOE网
- 用有向图的顶点表示事件，用弧表示活动，则称该有向图为边表示活动的AOE网(Activity On Edge)
- 有权值，可以进行项目时间的分析（分析关键路径）
拓扑排序
AOV网中的三种关系
- 严格偏序
- 反自反性：元素不能与自己相关
- 反对称性：关系是单向的
- 传递性
- 详见离散数学中的描述
- 简单来说就是抽象化的大于或者小于，反映在实际可能就是项目完成的先后顺序。
- 不是所有元素都有可比性
- 全序
- 一种特殊的严格偏序
- 还需满足完全性：所有元素都可比
- 拓扑有序
- 对DAG的一种排序描述
- 所有节点有序
- 不唯一
- 全序是严格偏序的一种特殊情况。
- 全序是唯一的，因为它要求所有元素之间都有明确的顺序。
- 全序是一种特殊的拓扑有序
- 拓扑有序是严格偏序关系的一种线性扩展。
- 拓扑有序不一定是唯一的，它取决于 DAG 的结构：
- 如果 DAG 是一条链，则拓扑排序唯一。
- 如果 DAG 中存在分支，则可能有多个拓扑排序。
- 全序是拓扑有序的一种特殊情况，当拓扑排序唯一时，它就是一个全序。
- 拓扑排序就是由严格偏序定义得到的拓扑有序的操作
形象算法
- 在有向图中选一个没有前驱的顶点且输出之
- 从图中删除该顶点和所有以它为尾的弧
- 重复以上两步，直到所有顶点输出为止或跳出循环
例
代码算法
给出有向图邻接矩阵
- 逐列扫描矩阵，找出入度为0且编号最小的顶点v
- 输出v，并标识v已访问
- 把矩阵第v行全清0
重复上述步骤，直到所有顶点输出为止
如果拓扑排序能将AOV网所有顶点都排入一个拓扑有序的序列，即不剩下顶点，则该网络无环。
关键路径
- 工程问题的AOE网中，关键路径是从工程开始(顶点)到工程结束(顶点)之间路径长度最长的路径
- 反映工程的工期，评估单个活动对总体工期的影响
- 提前完成关键路径上的活动，工程进度会加快
- 提前完成非关键路径上的活动，对工程无帮助
- 关键活动：关键路径下的所有活动
- 即会影响工期的活动
- 目标就是找到所有关键路径
求解：
- 小题可以用最长路径下的Dijkstra算法，直接找到工期时长和关键路径
- 严格证明需要计算各个点的最早开始时间和最迟开始时间是否相等
求关键活动的严格步骤
1. 建立任务的有向无环图（DAG）
- 将项目中的每个任务表示为图中的一个节点。
- 用有向边表示任务之间的依赖关系。
- 边的权重代表每个任务所需的时间。
2. 进行拓扑排序
- 对 DAG 进行拓扑排序，找到一个满足依赖关系的节点顺序。
- 拓扑排序的顺序帮助我们从起点到终点逐步计算任务的最早开始时间。
3. 计算每个活动的最早开始时间和最早结束时间
- 按照拓扑排序的顺序，计算每个节点的最早开始时间（ES）和最早完成时间（EF）。
- 对于每个节点
v： - 若
u是v的前驱节点（即u -> v），则v的最早开始时间ES(v) = max(EF(u))。 EF(v) = ES(v) + duration(v)。
4. 计算每个活动的最晚开始时间和最晚结束时间
- 从终点倒序遍历，计算每个节点的最晚开始时间（LS）和最晚完成时间（LF）。
- 对于每个节点
v： - 若
w是v的后继节点（即v -> w），则v的最晚完成时间LF(v) = min(LS(w))。 LS(v) = LF(v) - duration(v)。
5. 计算活动的浮动时间
- 浮动时间（Float）表示活动的时间冗余，即任务可以延迟多少时间而不影响项目整体完工时间。
- 计算公式：
Float = LS - ES或Float = LF - EF。
- 浮动时间为零的活动即为关键活动。
6. 确定关键活动
- 遍历所有活动，选择浮动时间为零的活动，即这些活动位于关键路径上。
- 这些活动必须按计划完成，否则会延迟整个项目的完工时间。
关键活动示例
假设项目有以下活动及其依赖关系：
- 活动 A：4 天，无前置活动。
- 活动 B：3 天，依赖于 A。
- 活动 C：2 天，依赖于 A。
- 活动 D：5 天，依赖于 B 和 C。
- 拓扑排序：A → B, C → D。
- 计算最早时间和最晚时间：
- 活动 A:
ES = 0,EF = 4 - 活动 B:
ES = 4,EF = 7 - 活动 C:
ES = 4,EF = 6 - 活动 D:
ES = 7,EF = 12
- 浮动时间计算：
- 活动 B 和 D 的浮动时间为零，因此它们是关键活动。
例
查找
二分法
- 一般做法
- STL做法
lower_bound是 C++ 标准库中用于在有序范围内查找第一个不小于给定值的函数。
- 通过
lower_bound可以轻松实现二分查找，判断目标值是否存在于有序数组中。
排序二叉树
平衡二叉树（AVL）
左旋右旋左右旋右左旋
跟树的走向一致
Hash表
- 用键值对实现查找
构造散列函数
- 一般用除留余数法
散列函数的构造方法要求计算简单且分布均匀。除留余数法的基本思想是选择一个适当的除数p（通常为质数），将关键字除以p取余数作为散列地址。
- ，
其中p通常选择小于等于表长的最大质数
- 这种方法的优点是计算简单，且当p选择得当时，能够得到比较均匀的散列地址分布
处理冲突
- 线性探测法
- 往后找位置
- 二次探测法
- 反复横跳找空位
- 链地址法
- 将冲突的内容用链表记录下来
- 不存在冲突的说法，但查找时需要考虑遍历链表的性能损耗
排序
冒泡
选择排序
- 从左往右维护有序性
- 从右子数组找出最小的跟目标交换
插入排序
- 需要腾出一个空间暂存数据
- 从左往右维护数组有序性
希尔排序
堆排序
归并排序
快速排序
- Partition函数：将比pivot小的移到前面，比pivot大的移到后面，返回pivot位置
- 用lr双指针操作，如果则swap
- 交换操作之间只能移动一个指针
- 以pivot为分界，将前后的子数组继续进行Partition操作
时间复杂度汇总
1. 数组（Array）
- 访问元素：O(1)
- 插入/删除元素：
- 在末尾：O(1)
- 在中间或开头：O(n)（需要移动元素）
- 查找元素：
- 无序数组：O(n)
- 有序数组（二分查找）：O(logn)
2. 链表（Linked List）
- 访问元素：O(n)
- 插入/删除元素：
- 在头部或尾部：O(1)
- 在中间：O(n)（需要遍历到指定位置）
- 查找元素：O(n)
3. 栈（Stack）和队列（Queue）
- 栈：
- 入栈（push）：O(1)
- 出栈（pop）：O(1)
- 查看栈顶元素（peek）：O(1)
- 队列：
- 入队（enqueue）：O(1)
- 出队（dequeue）：O(1)
- 查看队首元素（peek）：O(1)
4. 哈希表（Hash Table）
- 插入：平均 O(1)，最坏 O(n)（哈希冲突时）
- 删除：平均 O(1)，最坏 O(n)
- 查找：平均 O(1)，最坏 O(n)
5. 二叉树（Binary Tree）
- 遍历：
- 前序、中序、后序遍历：O(n)
- 层序遍历：O(n)
- 查找：
- 普通二叉树：O(n)
- 二叉搜索树（BST）：平均 O(logn)，最坏 O(n)（树退化为链表）
6. 平衡二叉搜索树（Balanced BST，如 AVL 树、红黑树）
- 插入：O(logn)
- 删除：O(logn)
- 查找：O(logn)
7. 堆（Heap）
- 插入：O(logn)
- 删除堆顶元素：O(logn)
- 查找堆顶元素：O(1)
- 堆排序：O(nlogn)
8. 图（Graph）
- 表示方式：
- 邻接矩阵：空间复杂度 O(V2)
- 邻接表：空间复杂度 O(V+E)
- 遍历：
- 深度优先搜索（DFS）：O(V+E)
- 广度优先搜索（BFS）：O(V+E)
- 最短路径：
- Dijkstra 算法（无负权边）
- 堆优化：O((V+E)logV)
- 无优化：O(V3)
- Bellman-Ford 算法（允许负权边）：O(V⋅E)
- Floyd-Warshall 算法（多源最短路径）：O(V3)
- 最小生成树：
- Kruskal 算法：O(ElogE)
- Prim 算法：
- 邻接表+优先队列：O(ElogV)
- 邻接矩阵+普通数组：O(V^2)
9. 排序算法
- 简单排序：
- 冒泡排序：O(n2)
- 选择排序：O(n2)
- 插入排序：O(n2)
- 高效排序：
- 快速排序：平均 O(nlogn)，最坏 O(n2)
- 归并排序：O(nlogn)
- 堆排序：O(nlogn)
- 线性排序：
- 计数排序：O(n+k)（k是数据范围）
- 基数排序：O(n⋅k)（k是数字位数）
- 桶排序：O(n+k)（k是桶的数量）
10. 查找算法
- 线性查找：O(n)
- 二分查找：O(logn)
- 哈希查找：平均 O(1)，最坏 O(n)
- Author:Richard Liu
- URL:http://richardliuda.top/article/DataStructure
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
