408 系统知识手册

链表结点的构造

链表结点由数据域和链接域组成。声明指针只得到保存地址的变量；malloc 申请结点空间后，指针才可以指向这片空间。分配失败时返回空指针，不能继续访问成员。释放结点前应保存后继地址，释放后不能再通过原指针读写结点。

typedef struct Node {
    int data;
    struct Node *next;
} Node;
Node *p = (Node *)malloc(sizeof(Node));
if (p != NULL) {
    p->data = 0;
    p->next = NULL;
}

从基本操作次数估计增长阶

时间复杂度由基本操作执行次数 T(n) 的增长阶刻画。保留最高阶项并忽略常数因子，例如 3n²+10n+8 属于 Θ(n²)，也常记为 O(n²)。必须说明讨论的是最坏、平均还是最好情况，不能把这三种情况混为一谈。

顺序执行的两段取增长更快的一段；嵌套执行则累计内层次数。只有各层次数独立时，才可直接相乘；若内层上界随外层变化，应求和。例如内层执行 1、2、…、n 次，总量为 n(n+1)/2。

循环变量倍增或缩减通常产生对数层数；递归需同时考虑分支数、子问题规模与合并工作。空间复杂度通常统计额外辅助空间，递归调用栈也应计入。

连续地址与长度管理

顺序表包含连续数组和有效长度 length。按位序访问第 i 个元素时，数组下标为 i−1，地址可由起始地址加固定偏移直接算出，所以按位访问为 O(1)。顺序存储本身不保证按值查找快，未排序时仍需顺序扫描。

静态分配的容量通常固定；动态分配允许扩容，但重新分配和搬移数据可能花费 O(n)。初始化 length=0 不代表分配的每个单元都成为有效元素。

查找与插删的边界

• 按位查找从首个数据结点开始累计位序，按值查找逐个比较 data；一般均为 O(n)。查找失败返回 NULL，不能继续解引用。
• 在已知结点 p 之后插入 s：先 s->next=p->next，再 p->next=s。若颠倒顺序，可能丢失原后继或形成自环。
• 删除 p 的后继 q：先确认 q 存在，保存 q=p->next，令 p->next=q->next，最后 free(q)。已知前驱时改链 O(1)，但按位删除仍包含查找前驱的 O(n)。

链式实现

链栈通常把单链表表头作为栈顶，插入与删除栈顶为 O(1)。带头结点与不带头结点的空栈判断不同；出栈时先保存数据和后继，再释放原栈顶。动态链栈没有数组固定容量的“满”，但仍可能内存分配失败。

链队同时设 front 和 rear，分别定位队头入口与队尾。带头结点时，空队通常 front==rear，且头结点 next 为空；不带头结点时，空队通常 front==rear==NULL。入队接到 rear 后并更新 rear；删除最后一个数据结点后，还必须同步调整 rear，防止悬空。

top 指向当前栈顶元素

容量为 M、数组下标 0…M−1、top 指向当前栈顶时：空栈 top=−1，满栈 top=M−1，元素数 top+1。入栈先检查未满，再执行 data[++top]=x；出栈先检查非空，再执行 x=data[top--]。逻辑出栈不要求清除原数组字节。

若 top 指向下一空位，空栈可为 top=0，入栈可写 data[top++]=x，出栈可读 data[--top]。指针型 base、top 的差表示元素数时，也要确认 top 是否指向下一空位。前置、后置自增表达不同取值时机，不能据此断言其中一种在所有编译环境下效率都更高。

队头指向首元素、队尾指向下一空位

数组容量为 M，采用牺牲一个存储单元的约定：空队 front==rear；满队 (rear+1)%M==front；元素数 (rear−front+M)%M，最多保存 M−1 个元素。入队先写 data[rear] 再推进 rear，出队先读 data[front] 再推进 front。

也可以规定指针指向首元素之前或末元素本身，相应读写顺序和公式会改变。不能把“先移后存”的代码直接套入“rear 指向下一空位”的定义。

二维数组的行优先与列优先

设 A 的行下界为 r₀、列下界为 c₀，共 R 行 C 列，每元素占 w 个存储单元，首地址为 base。行优先先存较小行号，同一行再存较小列号；列优先则交换行列角色。

计算偏移前先把实际下标减去对应下界，再乘前面完整行或列的元素数。多维数组同理：某维下标的权重是其后各维长度的乘积（行优先）。

行优先；括号中是从首元素起经过的元素个数。

列优先；行数 R 是相邻两列首元素的间隔。

对称矩阵与三角矩阵

n 阶对称矩阵满足 aᵢⱼ=aⱼᵢ，只需保存主对角线及一个三角区域，共 n(n+1)/2 个元素。以原矩阵下标从 1 开始、下三角按行存入 B[0…] 为例：i≥j 时 k=i(i−1)/2+j−1；i<j 时交换 i、j 后使用公式。

上、下三角矩阵的一侧严格三角区域为同一个常量 c 时，保存另一侧连同主对角线，再保存一个 c，共 n(n+1)/2+1 个位置；若题目规定零常量无需单独保存，应按题设处理。上三角按行存储时，先累计前面各行的 n、n−1、… 个元素，再加本行偏移。

原矩阵下标从 1 开始、B 从 0 开始时，上三角按行存储的非恒定项（i≤j）映射 k=(i−1)(2n−i+2)/2+(j−i)，严格下三角常量统一映射到 B[n(n+1)/2]。下三角对应 i≥j 用 k=i(i−1)/2+j−1，严格上三角常量同样映射到最后一个位置；这与对称矩阵把另一侧交换下标的办法不同。

括号匹配的完整条件

扫描表达式：遇左括号入栈；遇右括号，先判栈是否非空，再检查栈顶是否为相同类型的左括号，匹配才弹出。右括号到来时栈空、括号类型不一致，或扫描结束后栈仍非空，都属于不匹配。

KMP 利用相同前后缀

模式串某一前缀的最长相等真前缀与真后缀长度表示已匹配信息可以保留多少。KMP 失配后主串指针 i 不回退，只让模式指针按预处理表跳转，避免重新比较已知相同的片段。

使用 1 起始 next 数组时，next[1]=0；j≥2 时，next[j] 等于模式串前 j−1 个字符的最长相等真前后缀长度加 1。失配令 j=next[j]；当 j=0 时，统一推进 i、j，相当于主串移到下一字符并重新从模式开头开始。预处理 O(m)，完整匹配 O(n)，总计 O(n+m)。

递归跳过无效比较

在 1 起始约定下，若模式字符 P[j] 与 P[next[j]] 不同，可令 nextval[j]=next[j]；若相同，则令 nextval[j]=nextval[next[j]]，跳到更前的位置。nextval[1]=0。优化只是减少必然失败的重复比较，不改变匹配结果与 O(n+m) 的渐近复杂度。

结点数、分支数与 m 叉树界限

n 个结点的非空树有 n−1 条边，也等于所有结点孩子数之和，所以 n=1+Σd(v)。注意这里求和的是出度／孩子数；若按无向图的度计数，则度和为 2(n−1)。

m 叉树指每个结点最多 m 个孩子；“度恰为 m 的树”还要求至少有一个结点具有 m 个孩子，因此二者不是同一限制。m≥2、根为第 1 层时，第 i 层最多 mⁱ⁻¹ 个结点，高度 h 的最大结点数为 (mʰ−1)/(m−1)。

m≥2、n≥1，求含 n 个结点的 m 叉树最小高度；来自 n≤(mʰ−1)/(m−1)。

完全二叉树的结构限制

完全二叉树中度为 1 的结点至多一个，且只有左孩子；编号大于 ⌊n/2⌋ 的结点均为叶子。遇到第一个不完整的分支结点后，后续层序位置都不能再有孩子。奇数 n 时无度为 1 的结点，偶数 n 时恰有一个。

通用二叉树计数

设度为 0、1、2 的结点数分别为 n₀、n₁、n₂。由 n=n₀+n₁+n₂ 和 n−1=n₁+2n₂ 相减，得到 n₀=n₂+1，不要求完全或平衡。

根为第 1 层时，第 i 层至多 2ⁱ⁻¹ 个结点，高度 h 的二叉树至多 2ʰ−1 个结点；含 n 个结点的最小高度为 ⌈log₂(n+1)⌉，最大高度为 n。

三种深度优先次序

先序与中序的显式栈

先序可先把根压栈，循环弹出并访问，再依次压右孩子、左孩子；由于栈后进先出，左孩子会先访问。中序则反复把当前结点及其左链压栈，遇空后弹栈访问，再转向弹出结点的右子树。

例如根 A、左孩子 B、右孩子 C，B 的左右孩子为 D、E：先序 A B D E C，中序 D B E A C，后序 D E B C A。必须按同一棵树检查三种序列。

互不相同关键字条件下的重建

先序+中序：先序首项是根，在中序中找根，左侧是左子树、右侧是右子树；按左右结点数切分先序后递归。后序+中序同理，只是根取后序末项。层序+中序也可唯一确定：层序中在当前结点集合里最先出现的结点是当前根，再按中序左右范围分别筛出子树层序。

单独先序、单独后序或先序+后序一般不能唯一确定二叉树，例如一个孩子时无法判断是左孩子还是右孩子。若关键字重复，还需额外标识或条件，不能直接套用唯一性结论。

中序找后继

若 rtag=1，右链接就是中序后继；若 rtag=0，则转入右子树，沿着“有真实左孩子”的链接走到最左结点。中序前驱对称处理：有左线索直接取，无则到左子树最右结点。

左孩子、右兄弟的语义

孩子兄弟表示中，左链接不是“普通树唯一的左孩子”，而是第一个孩子；右链接是同一层的下一个兄弟。单棵树根没有兄弟，转换后的二叉树根因此无右孩子。必须保留原树兄弟次序，否则转换结果会改变。

遍历次序的对应

贪心构造

把每个叶子看成独立树，反复取根权最小的两棵树作为新根的左右子树，新根权为两者之和，再放回候选集合，直到只剩一棵。n 个叶子（n≥2）产生 n−1 个内部结点，总结点数 2n−1，没有度为 1 的结点。

同权时选择不同或交换左右可能产生不同形态和编码，但最优 WPL 相同。把“较小权放左边”等作为画图约定即可，不是哈夫曼最优性的必要条件。

前缀编码

沿根到叶路径分别以 0、1 标记左右边，叶子路径串就是其编码。由于叶子不会成为其他叶子的祖先，一个完整编码不会是另一编码的前缀，因此可即时识别边界。哈夫曼编码在给定权重和二元前缀码条件下使加权平均码长最小，码字本身通常不唯一。

定长编码每个符号使用相同位数；变长编码可让高频符号码字更短。不能把“不同长度”与“可唯一译码”直接画等号，前缀性是便于唯一译码的重要结构条件。

合并的前置条件

合并前先分别查根，仅当两个根不同才连接，否则不应再改变结构。把一个集合根接到另一个集合根是常见实现；按规模或按秩合并，可避免无谓增加高度。不能直接把任意非根元素的 parent 改向另一集合，否则可能只移动了原集合的一部分。

路径、回路和连通分量

路径长度按边数计；带权路径长度按经过边的权值之和计。简单路径不重复顶点；简单回路只允许起点与终点相同，其余顶点不重复。

无向图任意两点有路径则连通；连通分量为极大连通子图，不能再添加同图中的顶点仍保持为同一连通块。有向图强连通要求每对顶点双向可达，强连通分量是极大强连通子图。一次从某点可达全部顶点，不足以说明有向图强连通。

矩阵元素表达什么

邻接矩阵用一维表保存顶点信息，用 |V|×|V| 矩阵保存邻接关系。无权简单图可用 1 表示有边、0 表示无边；带权图可用边权表示有边、∞ 表示无边，对角线通常另设为 0。若允许权为 0 的边，就不能把所有 0 都当作无边。

无向图矩阵对称，可以压缩保存一侧；有向图第 i 行反映出边、第 i 列反映入边。对无权图数 1 可求度，对带权图应按“边是否存在”计数而非简单数非零项，且按题设排除对角线。

访问与回溯

从未访问顶点 v 开始，先访问并置 visited[v]，再逐个检查邻接顶点，对每个未访问邻居递归 DFS。当前结点所有邻居都已处理时返回上一层。visited 避免在环中重复访问。

只调用一次 DFS，覆盖从起点可达的部分。遍历全部无向图应外层扫描所有顶点，遇未访问者重新启动 DFS；启动次数等于连通分量数。遍历中首次发现顶点的边形成深度优先生成树，各分量合起来是生成森林。

队列控制层次

访问起点并置 visited 后入队；循环取队头，依次发现未访问邻居，立即标记并入队。若延迟到出队才标记，同一个顶点可能由不同前驱多次入队。遍历全部非连通图同样需要外层扫描未访问起点。

BFS 首次发现 v 时可记录 dist[v]=dist[u]+1、parent[v]=u。在无权图或所有边权相同的图中，得到从起点到 v 的最少边数；不可达顶点距离保持 ∞。对任意非等权图，BFS 不能代替带权最短路算法。

Prim 维护已选顶点集合

从任一顶点加入集合 S 开始，每轮在一端在 S、另一端不在 S的边中选最小边，加入该边及新顶点。随后更新每个未选顶点连接 S 的最小边权及其前驱。直到所有顶点加入；若无法找到跨集合的有限边，则原图不连通。

普通数组实现每轮扫描未选顶点并更新连接代价，共 O(|V|²)，适合稠密图；此代价对应具体实现。稀疏图用邻接表和优先队列可有不同复杂度，不能把 O(|V|²) 当作所有实现必然相同。

排序、判环、合并

开始时每个顶点是独立分量，将所有边按权值非降序排序。依次检查边 (u,v)：Find(u)≠Find(v) 时选入并合并集合；若根相同，加入会形成环，跳过。已选 |V|−1 条边后可结束。

边排序通常 O(|E|log|E|)，并查集操作在优化后相对较小，因此总体常记为 O(|E|log|E|)。适合边较少的稀疏图。若遍历完仍不足 |V|−1 条边，则只得到最小生成森林。

维护距离而非直接边权

令 dist[s]=0，其余为 ∞，重复选出未确定顶点中 dist 最小者 u，把它固定，再对其出边 (u,v) 松弛：若 dist[u]+w(u,v)<dist[v]，更新 dist[v] 和前驱。已确定的距离在非负权条件下不会再被更短路径推翻。

数组扫描选最小值的普通实现时间 O(|V|²)；在此实现下，即便用邻接表，选点步骤仍可能主导。优先队列实现可改善稀疏图时间，需与具体数据结构对应。负边可能使已固定距离后来变小，标准 Dijkstra 不适用。

递推关系与循环次序

初始化 dist[i][i]=0，有边取对应权值，无边为 ∞。第 k 轮允许顶点 k 作为中间点，更新 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])。k 必须处于最外层，表示本轮扩展的中间顶点集合。

同时维护中转点或前驱／后继矩阵，可以恢复具体路径。三重循环时间 O(|V|³)，距离和路径矩阵空间 O(|V|²)。相加前应检查两段是否可达，避免用有限整数模拟 ∞ 时溢出。

入度法

先计算所有顶点入度，把入度为 0 的顶点放入队列或栈。每取出一个顶点就输出，并对其所有出边终点入度减 1，减为 0 后加入候选集合。输出数不足 |V| 时，图中存在环。邻接表实现时间 O(|V|+|E|)。

同时有多个零入度顶点时，选择不同通常产生不同拓扑序。对当前 DAG 若每一步都只有一个可选零入度顶点，则拓扑序唯一。不要将拓扑序列中的相邻项都理解成原图存在直接边。

正向取最大、逆向取最小

ve 表示事件最早发生时间；vl 表示不延长总工期的最迟发生时间。活动最早开始取弧尾 ve，最迟开始取弧头 vl 再减自身持续时间。

源点 ve=0，按拓扑序向前计算。

汇点 vl=ve(汇点)，按逆拓扑序向后计算。

d=0 的活动为关键活动；事件时间与活动开始时间不要混用。

ASL 的定义

成功与失败的平均查找长度分别计算。判定树中成功查找的比较次数通常等于目标结点层次；失败结点是空区间或空链接，不应自动额外计作一次关键字比较，须按题目约定计数。

pᵢ 为查找第 i 项的概率，cᵢ 为相应关键字比较次数；概率和为 1。

普通扫描与哨兵

顺序查找从表一端依次比较关键字，匹配即成功，到达边界仍未匹配则失败。顺序表用下标推进，链表用 next 推进，两种存储均适用。

哨兵实现可把待查关键字临时存入保留单元，例如下标 0，从表尾向前比较，直到相等；返回 0 表示未在有效元素中找到。哨兵减少循环中的边界判断，并不减少渐近阶，且保留单元不能与有效记录冲突。

查找区间逐步收缩

每次比较中间元素后，排除中间元素及不可能包含目标的一半；low>high 表示区间为空。若 mid 取下整或上整不同，判定树形态可能改变，但最坏时间仍 O(log n)。避免 low+high 溢出可用 low+(high−low)/2。

int binarySearch(const int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

平均查找长度分解

若均匀分为 b 块，每块 s 个元素、n=bs，索引和块内都采用顺序查找且成功等概率，则 ASL=(b+1)/2+(s+1)/2=(s²+2s+n)/(2s)。当 s 约为 √n、b 也约为 √n 时，该表达式最小，约为 √n+1。

索引也可折半查找，则总 ASL=索引定位平均代价+块内顺序扫描平均代价。log₂(b+1) 的上取整只是索引最坏比较层数的一种表达，不能不加条件当作准确平均值。

按实际关键字层数计算高度

最满时 n≤mʰ−1；最稀疏时根至少两个孩子，之后每层至少扩展 t 倍，可得 n≥2tʰ⁻¹−1。磁盘模型下访问结点的次数与树高相关，结点内部查键通常在已读入内存的数据块中完成。

非空 m 阶 B 树，h 不含外部失败结点层，n 为关键字总数，m≥3。

查找与插入定位

进入一个结点后，先在该结点的有序关键字中查找；相等则成功，否则选择包含目标区间的孩子指针，继续下降，到外部空位置则失败。插入时把新关键字加到查找失败所对应的终端结点中。

插入后关键字数不超过 m−1 则完成；达到 m 时，对结点分裂，取约定中间关键字上升到双亲，左、右部分形成两个孩子。双亲也超满时继续向上，根分裂则新增根，树高增加 1。

先把内部键删除转移到终端层

若删除内部结点关键字，可以用中序前驱或后继替换，再在对应终端结点删除那个替代键。随后检查实际删除位置的关键字数。不能直接把带有子树的键及其整棵子树一并删掉。

令 t=⌈m/2⌉。删除后若仍至少 t−1 个关键字，无需调整；若只剩 t−2 个，先检查相邻兄弟能否借。兄弟若至少有 t 个关键字，就通过双亲分隔键旋转：双亲键下降填空，兄弟边界键上升到双亲，相应子树指针一并转移。

两条入口与边界键

可同时保存根指针和最小叶结点指针，分别支持多路定位和从最小键开始的顺序访问。资料以内部分支的最大关键字作为索引边界；其他实现也可能使用最小键分隔，计算时必须沿用题设。

内部根至少两个孩子，其他内部结点孩子数下限通常为 ⌈m/2⌉，上限为 m；叶层的容量定义要与题目中“阶”的约定一致，不能直接照搬 B 树的 m−1 个关键字上限。

开放定址的四种步长

• 线性探查按 H、H+1、H+2…（模表长）寻找位置，容易形成连续聚集。
• 平方探查可按 H±1²、H±2²…（模表长）访问，能缓解一次聚集，但并非对任意表长都保证访问全部位置；覆盖性质依赖表长与探查公式。
• 双散列用第二个散列函数决定步长，例如 (H₁(key)+iH₂(key)) mod m；应让步长与 m 互素等，以保证探查覆盖。
• 伪随机探查使用可重复生成的伪随机步长序列；查找时必须重现相同序列。

查找与建树

在不重复键约定下，左子树所有键小于根、右子树所有键大于根，左右子树继续满足同一性质；中序遍历得到递增序列。查找时 key 小于当前键走左，大于走右，相等成功，走到空链接失败。

插入落在失败空链接位置，新增结点起初为叶子。按输入次序从空树逐个插入即可建树；插入序列不同，树形可能不同，排序输入可能形成单支树。重复键的保留与插入方向应另按题设。

四种插入失衡

红黑树的五项结构约束

• 它首先是一棵二叉排序树，每个实际结点颜色为红或黑。
• 根为黑色，外部空叶 NIL 视作黑色。
• 红结点的孩子必须为黑，因而不存在相邻红结点。
• 从任意结点到其所有后代 NIL 的路径包含相同数量黑结点，即黑高一致。

先检查父结点颜色

新结点若为根，染黑后结束；父为黑时无需修复；父为红则违反“不连续红”，需检查叔结点与祖父。以下以父是祖父左孩子为例，右侧情况完全镜像。

转成至多一个孩子的删除

待删结点有两个实际孩子时，用中序后继或前驱的键替代，实际移除该替代结点；它至多有一个实际孩子。移除红叶不会改变路径黑高。黑结点若只有一个实际孩子，该孩子必为红，提升该孩子并染黑即可；实际移除黑结点而替代位置仍为黑（可能为 NIL）时，需要补偿黑高。

算法与循环不变量

处理 a[i] 前，a[0…i−1] 已有序，后段仍待处理。先保存当前记录，向右搬移所有大于它的前缀元素，再填入空位。只移动严格大于的项，遇相等就停止，保证稳定。

void insertionSort(int a[], int n) {
    for (int i=1; i<n; ++i) {
        int x=a[i], j=i-1;
        while (j>=0 && a[j]>x) {
            a[j+1]=a[j];
            --j;
        }
        a[j+1]=x;
    }
}

在有序前缀二分定位

处理第 i 个记录时，对前 i−1 个有序记录折半查找插入位置，然后把插入位置后的记录整体后移一位，再写入新记录。为了稳定，相等时应把新记录放在已有相等记录之后。

闭区间实现可令 low=0、high=i−1；若 x<a[mid] 则 high=mid−1，否则 low=mid+1，结束时 low 是插入位置。相等归右正是保持稳定的关键。

冒泡：相邻逆序交换

从左向右比较相邻元素，前者大于后者就交换，一轮把最大值推到未排序段末尾；下一轮缩小范围。也可反向扫描把最小值向前移动，但必须沿用同一方向分析每轮结果。

设置本轮是否交换的标志，若一轮无交换则整体已有序，可提前结束。相等不交换时稳定；最好 O(n)，平均和最坏 O(n²)，空间 O(1)。无提前终止标志的实现，最好比较次数也可能仍为 O(n²)。

分组不是切成连续小段

对增量 gap，把下标相差 gap 的记录分成一组，在每组内做插入排序；再逐步缩小 gap，最后 gap=1 对全体做直接插入。前面的大步调整减少远距离逆序，最后一轮利用基本有序性。

各增量应满足最终覆盖到 1，合适增量序列影响性能；“所有增量必须互质”不是一般定义要求，不能当作判断希尔排序是否合法的必要条件。

双指针挖坑划分示例

保存枢轴后，右侧先找小值填左空位，左侧再找大值填右空位，直到两指针相遇，最后放回枢轴。每次划分 O(n)，递归只处理枢轴两侧，不再把枢轴放回子问题。不同划分方案的等号和指针推进不同，代码应成套使用。

int partition(int a[], int low, int high) {
    int pivot=a[low];
    while (low<high) {
        while (low<high && a[high]>=pivot) --high;
        a[low]=a[high];
        while (low<high && a[low]<=pivot) ++low;
        a[high]=a[low];
    }
    a[low]=pivot;
    return low;
}
void quickSort(int a[], int low, int high) {
    if (low>=high) return;
    int p=partition(a,low,high);
    quickSort(a,low,p-1);
    quickSort(a,p+1,high);
}

向下筛选与建堆

大根堆向下筛选先挑较大孩子，再与当前保存值比较；小根堆则选较小孩子。child≤n 判断有没有孩子，child<n 判断有没有右兄弟，不可混用。由最后一个非叶结点倒序建堆，保证处理父时其孩子子树已经是堆。

单次筛选最坏 O(log n)，但建堆各层需要下沉的高度不同，累计为 O(n)，不能把 n 个结点都机械乘上 log n。

void siftDown(int a[], int root, int n) {
    int x=a[root];
    for (int child=2*root; child<=n; child=2*root) {
        if (child<n && a[child]<a[child+1]) ++child;
        if (x>=a[child]) break;
        a[root]=a[child];
        root=child;
    }
    a[root]=x;
}
void buildMaxHeap(int a[], int n) {
    for (int i=n/2; i>=1; --i) siftDown(a,i,n);
}

堆排序流程

升序排序先建大根堆，把根与当前末元素交换，最大值落到最终位置；有效堆长减 1，再从根向下筛选，重复直到剩一个元素。降序可采用小根堆对应处理。

堆排序各常见情况下为 O(nlog n)，常数辅助变量使空间为 O(1)。长距离交换与筛选可能颠倒相等记录，因此不稳定；与快排不同，它有 O(nlog n) 的最坏保证。

双指针合并

将待排序列看成长度 1 的有序段，两两归并成长度 2、4、8…的有序段，直到整表有序。递归实现先排左半，再排右半，最后合并；迭代实现按段长逐轮扩大。

合并时把两段复制到辅助空间，用 i、j 分别指向两段首项，比较后取较小者写回；一段用尽后，另一段剩余项可以直接整体追加。遇相等键时先取左段记录，才保持原有相对次序。

分配与收集

使用 r 个队列或桶，扫描记录把它按当前位放入相应桶尾，然后按位值从小到大顺次收集各桶。每轮扫描 n 个记录并访问 r 个桶，时间 O(n+r)，共 d 轮，为 O(d(n+r))，与初始排列通常无关。

空间取决于表示：链式队列可利用原记录链接并配 r 组首尾指针，额外桶指针 O(r)；数组分配一般还要 O(n+r) 辅助空间。不能把 d 轮各自可复用的桶空间再乘 d，也不能忽略数组实现实际保存记录的位置。

趟数和块读写

提高 k 或减少初始段数 r 可减少趟数。k 路归并至少要给 k 个输入段准备输入缓冲，还需要输出缓冲；若只有总共 M 个缓冲块，常见单缓冲模型要求 k≤M−1。实际双缓冲会增加需求。

增大 k 会增加缓冲空间并改变内存选最小值的成本，不能只看趟数。逐次线性比较 k 个段首每输出一条需 O(k) 比较，败者树可降到 O(log k)。

r 个初始归并段做平衡 k 路归并需要的合并趟数；r=1 时无需合并。

若文件共 B 个磁盘块，每轮完整读取并写回一次；初始段生成另计约 2B。

活动集合与冻结集合

将工作区填满后，在当前可输出记录中取最小值写入当前有序段，再读入下一记录填空。新值若不小于刚输出值，可继续参与当前段；若更小，标记为下一段冻结记录。

当前活动集合耗尽时，本段结束，解除冻结开始下一段，直到输入与工作区都处理完。初始段可能长于内存可容纳记录数，且各段长度可以不同；随机输入下常见平均长度约两倍工作区大小，但具体输入并不保证这一长度。

最佳归并树

当初始段长度不同时，不同合并顺序造成记录被反复读写的次数不同。把段长作为叶权，每次选 k 个最短段合并，构造 k 叉哈夫曼式最佳归并树；必要时补 0 权虚拟叶，使叶数满足满 k 叉树条件。

每个原始段被合并的次数等于其叶深度，因此总读写量为 2×WPL（权重单位为记录或块时，结果单位也应一致）。这优化的是加权 I/O 总量，不等同于单纯让所有叶子高度相同。

按约束选择算法

• 记录少或基本有序，可优先考虑直接插入；移动昂贵且 n 较小时，简单选择交换少可能有优势。
• n 大且要求稳定、最坏 O(nlog n)，常用归并；要求 O(1) 额外空间及 O(nlog n) 最坏界，可考虑堆。
• 快排常有良好的平均实际性能，但需关注枢轴策略、递归栈和最坏情况，不能脱离实现声称它永远最快。
• 键位数少且可分解时可考虑基数；记录本体很大时，可间接排序指针或索引以减少移动。
• 若采用链式存储，要检查算法是否依赖随机访问；快排常见数组划分和堆的下标寻址不能原样照搬链表。

存储程序与五大部件

• 基本功能部件是运算器、控制器、存储器、输入设备和输出设备。
• 指令与数据以二进制形式存入存储器，按地址访问；指令由操作码与地址码等字段组成。
• 操作码说明完成什么操作，地址信息用于确定操作数或下一条指令；程序按顺序存放，控制转移指令可改变执行顺序。
• 早期结构以运算器为中心，输入输出的信息经运算器传递；现代结构以存储器为中心，使输入输出尽量直接与存储器交换信息，提高整体效率。

MAR 和 MDR

从源文件到可执行文件

主存容量的计算

主存容量等于可编址单元数×每单元位数。按字节编址时，地址数对应字节数；按字编址时，再乘每字字节数。不要把地址线条数直接当作存储容量的位数。

CPU 时间的核心关系

Ninst 为执行的指令条数，CPI 为该程序的平均每条指令时钟周期数，f 为主频。

以各类指令在动态执行指令中的比例加权，不能只把各类 CPI 直接求平均。

整数与小数分别转换

• 十进制整数转 r 进制：反复除以 r 取余，余数从后向前排列；最先得到的是最低位。
• 十进制小数转 r 进制：反复乘以 r 取整数部分，整数按产生顺序排列；最先得到的是最高小数位。
• 达到精度要求或小数部分变为 0 时停止；某一步乘积恰为 1.0 时，取出整数位 1 后剩余小数为 0，也应停止；不能要求所有转换都必须达到同一个乘积。
• 二进制与八进制按 3 位分组、与十六进制按 4 位分组；以小数点为界，整数左端和小数右端可补 0。

n 位编码的范围与零

算术移位的补位规则

串行和并行结构

串行加法器用一个全加器逐位处理，操作数由移位寄存器从低位依次送入，并用触发器保存上一步进位；器件少、成本低，但速度慢。并行加法器使用多个全加器同时处理各位，本位和仍可能等待进位，故“并行加法器”不等于“并行进位”。

串行进位链逐级传递进位；先行进位用进位产生函数 Gᵢ=AᵢBᵢ和进位传递函数 Pᵢ=Aᵢ⊕Bᵢ展开关系，使高位进位不必逐级等待。

加减运算规则

补码加法连符号位一起相加，超出固定位宽的进位舍去；减法转为加被减数的相反数补码。舍弃最高进位不等于发生有符号溢出。

固定 n 位补码按模 2ⁿ 运算；最小负数的相反数不在同位宽正数范围内，须注意边界。

四类状态位

位宽变化

• 长整数转短整数：保留低位、截去高位，结果可能改变真值。
• 无符号数扩展位宽：高位补 0；补码有符号数扩展：重复原最高符号位。
• 原码扩展不能直接照搬补码符号扩展；讨论时应明确机器实际采用的编码。
• C 语言类型位宽由实现和数据模型决定，不能无条件认定 long 总是 32 位或 64 位、char 总为有符号。混合表达式的比较应先进行整数提升和通常算术转换，再决定按何种类型比较。

IEEE 常用格式

规格化的判断

基数为 2、原码小数尾数模型中，非零规格化尾数满足 1/2≤|M|<1，即第一数值位为 1。补码小数尾数的规格化特征是符号位与第一数值位不同，负数的边界与原码不同；−1 可作为补码规格化尾数，而 −1/2 的补码不是规格化形式。IEEE 的 1.f 是另一种等价表达约定，不要混写小数点位置。

常见转换的损失

奇偶校验与海明码

一位奇偶校验使整个码字的 1 的数量满足奇数或偶数约定；能发现奇数个位翻转，不能保证发现偶数个位翻转，也不能定位错误。海明码把校验位置于 1、2、4、8…等位置，按位号二进制展开决定各校验组。

k 个信息位配 r 个校验位，要区分 k+r 个单比特错误位置及无错状态。

编码和检验

• 选定 r 次生成多项式 G(x)，其二进制表示有 r+1 位，最高项和常数项通常为 1。
• 在信息位后附 r 个 0，再用 G(x) 对应位串做模 2 除法；减法采用异或，不借位。
• 将所得余数补足 r 位放在原信息位之后，组成发送码字；前导 0 也是校验位的一部分，不能省略。
• 接收端用同一生成多项式除收到的码字：余数非 0 判为出错；余数为 0 只说明未检出错误。CRC 通常配合重传，不应一般性地由余数自行纠正某一位。

层次之间的信息交换

CPU 可访问寄存器、Cache 和主存；辅存内容通常先调入主存。Cache—主存之间以块交换，主要由硬件管理，对一般程序员透明；主存—辅存之间的调入调出由操作系统和硬件协同完成。

局部性使少量快速存储器可以保存近期常用内容，形成接近高速存储器的访问性能和接近低层存储器的容量、成本。

存取时间与存取周期

存取时间是从启动一次存储操作到该操作完成的时间；存取周期是连续两次独立存储操作启动之间必须间隔的最小时间，可能包含恢复时间，通常不小于存取时间。不能把它们当作同一个参数。

两类 RAM 对照

SSD 的组成与特点

SSD 由闪存芯片和控制器等组成，闪存转换层 FTL 把主机逻辑地址映射到闪存物理位置，承担地址映射、垃圾回收、磨损均衡等工作。无机械运动使随机访问延迟、噪声、抗震性和能耗等优于传统磁盘。

高位交叉与低位交叉

位扩展、字扩展与字位扩展

• 位扩展增加一个存储字的位数：如两片 1K×4 合成 1K×8。地址线和片选并接，各芯片分别连接不同的数据位，同一时刻共同被选中。
• 字扩展增加可寻址单元数：如两片 1K×8 合成 2K×8。低位地址和数据线共享，用额外高位地址区分芯片，同一时刻仅选相应组。
• 字位同时扩展：如八片 1K×4 合成 4K×8，先两片构成一组 1K×8，再用四组扩大字数；需 12 位地址，其中低 10 位到组内，高 2 位译码选组。

容量与访问时间

各面同样组织时，容量为盘面数×每面磁道数×每道扇区数×每扇区字节数。

平均旋转等待通常取一圈时间的一半；实际题设还可能另计控制器开销。

各级组织对照

平均时间的两种写法

命中率为命中次数占全部相关访问次数的比例。

Pmiss 定义为命中检查之外的额外失效开销时使用。

若 Tmiss,total 已包含一次失效的全部访问过程，不能再重复加命中检查时间。

映射方式对照