2k words 2 mins.

# 定义 寻找一个带权有向图中某一点到另一个点的最短路径 / 权最小的路径 当然以下算法也适用于无向图 # Floyd (弗洛伊德) 算法 可以算出所有点之间的最短距离 c++//dist 初始化为邻接矩阵，若 i 没有指向 j 的边，则应有 dist [i][j]=MAX_INT (表示无穷大的数)void floyd(){ for(int k = 0; k < n; k ++){ // 作为循环中间点的 k 必须放在最外一层循环 for(int i = 0; i < n; i ++){ for(int j...
1.1k words 1 mins.

# 图的存储结构： AM: Adjacent Matrix 邻接矩阵 AL: Adjacent List 邻接表 RAL: Reverse Adjacent List 逆邻接表 TL: Triple List 三元组顺序表 (往往是行逻辑链接的，性能更好) CL: Cross List 十字链表 # 图按存储结构分为： AMGraph: Adjacent Matrix Graph ALGraph: Adjacent List Graph TLGraph: Triple List Graph RALGraph: Reverse Adjacent List Graph CLGraph:...
3.1k words 3 mins.

# AOV: Activity On Vertex 略（不考） # AOE: Activity On Edge 与 AOV 网相对应的是 AOE (Activity On Edge) ，是边表示活动的有向无环图，如图所示。图中顶点表示事件 (Event)，每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用 与 AOE 有关的研究问题 完成整个工程至少需要多少时间？ 哪些活动是影响工程进度 (费用) 的关键？ 工程完成最短时间：从起点到终点的最长路径长度...
12k words 11 mins.

# Scala # import 在 Scala 中，import 语句用于引入其他类、对象或特质，以便在当前作用域中可以直接访问它们的成员。下面是一些关于 Scala 中 import 的常见用法： 基本用法 a// 导入单个类import scala.collection.mutable.ListBuffer// 导入整个包import scala.collection.mutable._// 重命名导入的类 / 对象 / 特质import java.util.{ArrayList => JArrayList, HashMap =>...
1k words 1 mins.

# Multiway Tree 多叉树任意节点的所有子树也都是有顺序的 多叉树可以按固定的方法向二叉树转化： 对所有节点只保留与最左侧子节点的连接，删除其他连接 从左到右依次连接同一层的兄弟节点 (siblings) # B-Tree Banlanced Multiway Tree, 顾名思义，B - 树是一种平衡的多路查找树，是平衡二叉树的外延概念。 B-Tree 是为外部查找（如磁盘）设计的一种平衡查找树。 系统从磁盘读取数据到内存时是以存储块 （block） 为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。B-Tree...
9.5k words 9 mins.

# 二叉树的一些规范 (考研) 节点的度数：节点出发指向下一层节点的边的数量 (出度) N0,N1,N2N_0,N_1,N_2N0​,N1​,N2​：分别表示度数为 1，2，3 的顶点数量 # 结论 任意二叉树满足： n=N0+N1+N2n=N_0+N_1+N_2n=N0​+N1​+N2​ n−1=0×N0+1×N1+2×N2=N1+2N2n-1=0\times N_0+1\times N_1+2\times...
5.4k words 5 mins.

# 哈希表 / 散列表 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表 # 哈希查找 / 散列查找 利用哈希函数进行查找的过程叫哈希查找 # 哈希映射函数 / 散列函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数 # 原始 hash 函数 简单一点的 hash 算法就是直接取模 (除留余数法)。 高级一点的 hash 算法会模乘以一个大素数来将源数据的分布规律变得不那么显著，也就是说，不管输入的是一串分布很紧凑的数字序列还是很稀疏的数字序列，生成的结果都是非常分散的数字序列。 linux 内核代码里面的这个 hash...
1.5k words 1 mins.

基排序 / 桶排序 / 数字排序 # 原理 需要频繁进行分组重排，（类似于归并）适用于链表 可分为两种： MSD，最高位优先 (Most Significant Digit first) LSD，最低位优先 (Least Significant Digit first) # 代码 c++//Definition for singly-linked list.struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {}...
3.8k words 3 mins.

区分：堆排序的堆不是堆栈的堆 # 原理 堆排序可以视为一种聪明的选择排序。 堆排序适合数组这样的数据结构。 选择排序需要不断在未排序部分找最大 / 小值然后放在已排序部分后面，堆排序只是将 “找最值” 的部分用 “调整堆” 代替，调整好的堆的堆顶就是我们想要的最值。 堆排序基于二叉树结构，堆是一种按一定规律存储数据的二叉树。利用堆最值位于堆顶的特点，不断将堆顶的最值和堆最后一个元素交换（堆最后一个元素后面都是已排序部分），然后重新调整未排序部分使其再变回一个堆。 # 最大堆 / 小根堆 / 小顶堆 最大值在根节点 / 堆顶 结点的键值都小于等于其父结点的键值 排降序建最大堆 # 最小堆...