数据结构

堆¶

建堆时，要记住元素按照层次遍历顺序放入数组，并且从后往前调整。

建堆后弹出堆顶元素后，将数组最后一个元素放置在堆顶，自顶向下调整。直到堆中不存在元素时，得到了一个序列，这叫做堆排序。

最早开始时间与最晚开始时间¶

对于这类题，最早开始时间可以取最大值，最迟开始时间可以求出关键路径（最长路径）后逆推。避免进行一遍完整计算浪费时间。

对于快排¶

408考试中，对于一趟的定义，常常为对尚未确定最终位置的所有元素进行一遍处理称为一“趟”

第一趟： 对整个大数组进行处理。选出一个枢轴，确定了 1 个 元素的最终位置。此时数组被切分成了左（\(L\)）和右（\(R\)）两部分。

第二趟： 必须对剩下的所有元素处理一遍。这意味着，如果 \(L\) 和 \(R\) 都有元素，你必须在 \(L\) 里挑一个枢轴划分一次，同时在 \(R\) 里也挑一个枢轴划分一次！

情况一（枢轴在两端）： 如果第一趟选的枢轴恰好是最大或最小值，那么它只有一边有数据（比如只有 \(L\) 没有 \(R\)）。第二趟就只能处理 \(L\)，确定 1 个 新枢轴。两趟下来共确定 \(1+1=2\) 个。
情况二（枢轴在中间）： 如果第一趟选的枢轴在中间，它把数组劈成了非空的 \(L\) 和 \(R\) 两半。第二趟必须同时处理 \(L\) 和 \(R\)，于是 \(L\) 确定一个新枢轴，\(R\) 也确定一个新枢轴。两趟下来共确定了 \(1+2=3\) 个元素！

快排第一次肯定只能确定一个元素的位置，第二次才能最多两个，也就是说两趟后最多确定三个元素的最终位置。如果只确定两个，这两个必须至少有一个在边界。

注意！！！此处的确定，是根据算法确定下来的，而非挪动元素时偶然放在了他的最终位置。

m路归并排序¶

这里假设对于120个初始归并段，进行12路归并，不难发现每次选12个进行合并，生成一个，因此相当于每次消耗11个初始归并段，而我们的目标是合并到只剩最后一个段，所以一共要消耗120 - 1个段，因此119 % 11 = 9，还要再补充两个虚段凑够11个。

所以一般公式是设初始段数为 \(N\)，归并路数为 \(k\)。

计算 \((N - 1) \bmod (k - 1) = R\)

如果 \(R = 0\)：说明刚好能合并完，不需要补虚段（补 0 个）。
如果 \(R \neq 0\)：需要补充的虚段数 = \((k - 1) - R\)。

循环链表¶

看强化/数据结构-2

直接插入排序和简单选择排序¶

在大部分元素已有序的情况下，前者比较次数比后者比较次数少，后者移动元素次数比前者移动元素次数少（因为后者是直接交换，前者要一个一个挪），二者的空间复杂度都是O(1)。

B树与B+树的插入删除¶

无论插入还是删除都是看是否超过边界

无论B树还是B+的插入原则都规定：所有新插入的外来关键字，必须且只能插入到最底层的终端节点中。

而刚创建B树时只有一个节点，它既是根节点又是终端节点。

B树插入就是看插入后的序列第ceil(m - 1)个上升至父亲节点，其余的成为新节点

B树的删除：

删除关键字不在终端节点，用他的前驱或后继代替他，然后当作这个前驱或后继进行删除
删除关键字在终端节点
删完没出边界，直接删
删完出边界
- 兄弟够借就父下子上
- 兄弟不够借就父下与子合并
若删除后导致叶结点不在同一层了，就可以认为，原父节点下来了，所以导致原来位置空闲，相当于删除了，所以再看兄弟是否够借，如：

B+树的插入：（不是重点）

B+树的删除：

删完没超边界，直接删
删完超边界
兄弟够借，抢兄弟一个，同时会引发上层关键字的变动（因为B+树关键字是所指子树最大值）
兄弟不够，和兄弟合并了，也会导致上层关键字的变动

哈夫曼树¶

哈夫曼树中两个权值最小的结点不一定是兄弟结点，因为可能存在两个以上的最小权值。
权值可以是0，用来凑数

败者树¶

败者树结点上是败者的段号

二路归并的主要功能¶

“二路归并”这个操作本身的核心功能就是：把两个已经有序的序列，合并成一个新的有序序列。

三元组¶

数据结构里说的“三元组”，一般指的是稀疏矩阵的三元组表示法。

对于矩阵中的一个非零元素，用：\[[ (i,j,a_{ij}) ]\]

所以你考试时直接记： \[\boxed{\text{三元组}=(\text{行号},\text{列号},\text{元素值})}\]

加权平均长度¶

\[\boxed{\text{加权平均长度}=\frac{\text{权值}\times\text{长度的总和}}{\text{权值总和}}}\]

置换选择排序¶

当文件中n个记录时按照升序进行排序时，置换选择排序指挥生产一个归并段。

置换选择排序就是每次从当前工作区选一个比已选出最小值大的最小值。

中缀表达式¶

在转化为前缀或后缀表达式时，同级别的运算符要按照从左向右的顺序进行转换，不能随机选择顺序。

AOE图¶

第四问需要在求出事件（结点）、活动（边）的最早最晚发生时间比较好。b在6时刻开始会影响到终点事件2，而2的最晚开始时间应该是10，因此b的持续时间应该是10 - 6 = 4。若b时间不能变，2最早开始时间是6 + 5 = 11，影响到5的最晚开始时间，5的最晚开始时间是12，因此可以压缩k = 12 - 11 = 1。

第一种：允许缩短活动本身

活动开始时间 + 活动持续时间 ≤ 终点事件的最晚发生时间

第二种：不允许缩短活动本身，只能缩短后续活动

先计算延迟活动的实际结束时间，再利用后续事件的最晚发生时间，确定后续活动最多能持续多久。

二叉查找树¶

以左右取左为例

AVL¶

AVL默认左小右大，也可以规定左大右小。这点不是绝对的。

中缀表达式转后缀表达式¶

核心规则¶

从左向右扫描中缀表达式，借助运算符栈完成转换。

扫描到的元素	处理规则
操作数	直接输出到后缀表达式
左括号 `(`	直接入栈
右括号 `)`	依次弹出并输出运算符，直到遇到 `(`，丢弃这对括号
普通运算符	若栈顶运算符优先级 ≥ 当前运算符，则不断弹出并输出，最后将当前运算符入栈
扫描结束	将栈中剩余运算符依次弹出并输出

注意： 比较运算符优先级时，遇到左括号就停止弹栈。

运算符优先级¶

*、/ 高于 +、-。
优先级相同时，先弹出栈顶运算符，再将当前运算符入栈（四则运算符均为左结合）。
左括号作为分界，不参与普通运算符的优先级比较。

408 易错点¶

栈中只保存运算符和括号，操作数直接输出。