数据结构思维导图
数据结构
树
- 存储结构、遍历算法
- 树、森林、二叉树转换相关
- 二叉树
- 遍历
- 线索化
- 应用
- 哈夫曼树
- 计算WPL 【注意 WPL 需要路径长度*权重,不乘是错的!】
- 哈夫曼树
图
- 应用
- 最小生成树
- 第一性:无环、总权最小、包含所有节点
- 实现
- 克鲁斯卡尔:加边
- prim:加点
- 最短路径
- 迪杰斯特拉,思想是贪心,找新加入节点到已知节点的最短路径【求 dist 数组】
- 拓扑排序
- 实现
- 时间复杂度 O(V+E)
- 关键路径
- 问题:活动余量、关键路径、最早开始、最晚结束时间,以及关键路径概念
- 增加、减少关键活动对工期的影响
- 求解
- 从左往写最早开始时间
- 从右往左写每每个节点的最晚开始时间
- 活动的余量 = 该活动的结束节点的最晚开始时间 - 开始节点的最早开始时间 - 该活动的持续时长
- 余量为 0 的活动为关键路径【或者直接找图里最长的路径】
- 问题:活动余量、关键路径、最早开始、最晚结束时间,以及关键路径概念
- 用 DAG 表示表达式,求节点个数 #2018
- 最小生成树
- 定义相关
- 数据结构
- 邻接表、邻接矩阵、邻接多重表、十字链表
- 算法
- DFS
- BFS
- 数据结构
查找
排序
- 内部排序
顺序表
- 数组压缩,求元素下标