分类 课程笔记 下的文章
比较需要记忆的公式：A + BC = (A+B)(A+C)
A + AB = A
A + A'B = A + B
A(A+B) = A【算法/数据结构】查找1_线性表的查找
查找表： 一组记录组成的表，每个记录可能有多个数据项，因此使用某个关键字来代表该记录 可理解为如下示例
map<string,pair<int,int>> mp
mp中，mp["abc"]为关键字为"abc"的记录，数据项是一个pair<int,int>
【算法/数据结构】排序算法
插入排序 1.直接插入排序 从第一个元素开始 把 $0...i-1$的区域作为有序区，第 $i$ 个元素作为待插入元素，每次在有序区中查找其插入的位置 2.折半插入排序 与直接插入排序的区别就是每次查找插入位置的时候使用的是折半查找 以上两种排序都在排序区形成全局有序 $O(n^2)$ 3.shell排序 $O(n^{1.3})$ 不稳定 将数组间隔分组，在每个组内进行直接插入排序，逐渐增大每组的元素数量，直到只剩下一组
【算法/数据结构】堆排序/优先队列
堆 每个父节点都大于其子节点称为大根堆 小于则称为小根堆
堆排序 维护$n$个元素的初始大根堆或小根堆，以大根堆为例，每次取出堆的最大元素R[1]放到堆末尾R[n]，然后对$1...n-1$进行大根堆性质的维护，即$sift$操作，重复上述操作$n-1$次 最后得到的序列即为按照递增顺序排好的序列。
【数据结构\图】最短路径
定义： 带权图中从一个顶点到另一个顶点的权值和最小的路径，无权图中路径长度最小的路径（可视为边权为1）