408考研-数据结构 (Ultra Mode)

数据、数据元素、数据项、数据对象的关系

**数据**：信息的载体，能被计算机识别和处理的符号集合 **数据元素**：数据的基本单位，作为一个整体处理（如学生记录） **数据项**：构成数据元素的**不可分割的最小单位**（如学号、姓名） **数据对象**：具有相同性质的数据元素的**集合**（子集）

什么是抽象数据类型(ADT)？

ADT是指一个数学模型以及定义在该模型上的一组操作。 特点：定义仅取决于逻辑特性，与计算机内部如何表示和实现**无关**。 格式： ADT 抽象数据类型名 { 数据对象：<定义> 数据关系：<定义> 基本操作：<定义> } ADT 抽象数据类型名

数据结构的三个要素

1. **逻辑结构**：数据元素之间的逻辑关系（独立于计算机） • 线性结构：一对一（线性表、栈、队列） • 非线性结构：一对多（树）、多对多（图） 2. **存储结构（物理结构）**：逻辑结构在计算机中的表示 • 顺序存储：相邻=相邻（随机存取，有碎片） • 链式存储：指针表示关系（无碎片，额外空间） • 索引存储：附加索引表 • 散列存储：关键字直接计算地址 3. **数据的运算**：定义（针对逻辑）+ 实现（针对存储）

算法的五个重要特性

1. **有穷性**：执行有穷步后结束，每步在有穷时间内完成 2. **确定性**：每条指令含义确切，无二义性 3. **可行性**：描述的操作可通过已实现的基本运算执行有限次实现 4. **输入**：零个或多个输入 5. **输出**：一个或多个输出

【填空】若算法执行时所需辅助空间相对于输入数据量是个常数，则称此算法为___

原地工作

常见时间复杂度排名（从小到大）

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ) ⚠️ log₂n < n^k （k>0），即对数阶比任何多项式都小！ **特殊情况**：最好/最坏/平均情况；均摊复杂度（连续多次均摊到每次）

【易错】时间复杂度和空间复杂度的区别

❌ 常见错误：时间复杂度看代码行数；空间复杂度只看变量个数 ✅ 正确答案：时间复杂度=算法执行时间随问题规模的增长趋势（基本运算频度）；空间复杂度=算法所需辅助空间随问题规模的增长趋势 💡 注意：输入数据本身占用的空间不属于算法的空间复杂度！

线性表的定义和特点

**定义**：具有相同数据类型的n(n≥0)个数据元素的**有限序列** L = (a₁, a₂, ..., aᵢ, aᵢ₊₁, ..., aₙ) **特点**： • 元素个数有限 • 有逻辑上的顺序性（先后次序） • 每个元素都是单个数据元素 • 所有元素数据类型相同（占用相同大小空间） • 具有抽象性（仅讨论逻辑关系）

顺序表的插入操作及时间复杂度分析

**操作**：在第i个位置插入元素e • 将第i个及之后的元素全部右移一位 • 在位置i处放入e • 表长++ **时间复杂度**： • 最好O(1)：在表尾插入 • 最坏O(n)：在表头插入 • 平均O(n)：∑(n-i+1)/(n+1) = n/2

顺序表的删除操作及时间复杂度分析

**操作**：删除第i个位置的元素 • 保存被删元素的值 • 将第i+1个及之后的元素全部左移一位 • 表长-- **时间复杂度**： • 最好O(1)：删除表尾 • 最坏O(n)：删除表头 • 平均O(n)：∑(n-i)/n = (n-1)/2

单链表 vs 双链表 vs 循环链表 vs 静态链表对比

| 类型 | 特点 | 判空条件 | 适用场景 | |------|------|----------|----------| | **单链表** | 每个结点含data+next | L==NULL或L->next==NULL | 基本操作 | | **双链表** | 增加prior前驱指针 | 同单链表 | 需要双向遍历 | | **循环单链表** | 尾结点next指向头 | L->next==L | 环形结构 | | **循环双链表** | prior和next成环 | L->prior==L且L->next==L | 双向环形 | | **静态链表** | 用数组+游标模拟链表 | next[0]==0 | 无指针语言 |

带头结点 vs 不带头结点的单链表

**带头结点**： • 头结点数据域可不存信息（或存长度） • 头结点指针域指向首元结点 • ✅ 第一个结点和后续结点操作**统一**，代码简洁 **不带头结点**： • 第一个结点需要单独处理 • ❌ 对空表和非空表需不同代码逻辑 💡 **推荐使用带头结点的链表！**

双链表插入操作的四个步骤（顺序很重要！）

在p结点之后插入s结点： ① s->next = p->next; // s的next指向p的后继 ② p->next->prior = s; // p的后继的prior指向s ③ s->prior = p; // s的prior指向p ④ p->next = s; // p的next指向s ⚠️ **①必须在②之前**，否则p的后继信息就丢了！

【易错】双链表插入操作的步骤顺序有什么要求？

❌ 常见错误：可以任意顺序；只需要①④在②③前面 ✅ 正确答案：①必须在②之前执行（否则丢失p的后继信息）；④可以在②③之后 💡 关键：先保存p->next的信息，再修改p->next

顺序表 vs 链表的选择依据

| 考虑因素 | 选顺序表 | 选链表 | |----------|----------|--------| | 存储规模难以估计/波动大 | — | ✅ | | 频繁按位存取（查找为主） | ✅ | — | | 频繁插入/删除 | — | ✅ | | 语言支持指针 | — | ✅ C/C++ | | Java等面向对象语言 | ✅ 引用也可 | — |

栈(Stack)的基本概念

**定义**：只允许在一端进行插入或删除操作的**限定性线性表** **特点**：**后进先出(LIFO)** **术语**： • 栈顶(Top)：允许插入/删除的一端 • 栈底(Bottom)：固定端 • 空栈：不含任何元素 **基本操作**：InitStack/Push/Pop/GetTop/StackEmpty/ClearStack

共享栈的设计思想

**思想**：利用栈底位置相对不变的特性，让两个顺序栈**共享同一个一维数组** **实现**： • 两个栈的栈底设在数组两端 • 栈顶向中间延伸 • 只有两个栈顶相遇时才上溢 **优点**：比两个独立顺序栈更节省空间

循环队列的三种判满方法

**方法1：牺牲一个单元** • 队满：(rear + 1) % MaxSize == front • 队空：rear == front **方法2：增设size变量** • 队空：size == 0 • 队满：size == MaxSize **方法3：增设tag变量** • 入队成功：tag = 1 • 出队成功：tag = 0 • 队空：front == rear && tag == 0 • 队满：front == rear && tag == 1

【填空】循环队列中，队尾指针的更新公式：Q.rear = (___) % ___

Q.rear + 1；MaxSize

栈的应用场景

1. **括号匹配**：左括号入栈，右括号与栈顶匹配 2. **表达式求值**：中缀→后缀转换（逆波兰表达式） 3. **递归调用**：系统栈保存局部变量、返回地址 4. **深度优先搜索(DFS)**：保存待访问节点路径 5. **浏览器后退功能**：访问历史栈

队列的应用场景

1. **层次遍历(BFS)**：树的层序遍历、图的BFS 2. **缓冲区**：解决主机与外设速度不匹配 3. **CPU任务调度**：进程调度队列 4. **打印机任务管理**：打印队列 5. **网络请求处理**：请求队列

双端队列(Deque)的概念

**定义**：允许**两端**都可以进行入队和出队操作的队列 **变体**： • **输出受限Deque**：一端可插入+删除，另一端只能插入 • **输入受限Deque**：一端可插入+删除，另一端只能删除 ⚠️ 验证某个输出序列是否合法→用**模拟法**逐一检验

树的基本术语（结点相关）

**结点的度**：拥有的子树个数 **树的度**：各结点度的最大值 **叶子(终端结点)**：度为0的结点 **分支结点(非终端结点)**：度>0的结点 **内部结点**：度≠0且不为根的结点 **父结点(双亲)**：直接上层结点 **子结点(孩子)**：直接下层结点 **兄弟**：同一父结点的子结点 **堂兄弟**：双亲在同一层的结点 **祖先**：从根到该结点路径上的所有结点 **子孙**：以该结点为根的子树中的任一结点

树的四条重要性质

性质1：树中结点数 = 所有结点的度数之和 + 1 性质2：度为m的树第i层至多有 m^(i-1) 个结点（i≥1） 性质3：高度为h的m叉树至多有 (m^h-1)/(m-1) 个结点 性质4：n个结点的m叉树最小高度 = ⌈logₘ[n(m-1)+1]⌉

二叉树的五种基本形态

1. 空二叉树 2. 只有根结点 3. 根只有左子树 4. 根只有右子树 5. 根既有左子树又有右子树 ⚠️ 二叉树的子树有**左右之分**，次序不能颠倒！

满二叉树 vs 完全二叉树 vs 二叉排序树 vs 平衡二叉树

| 类型 | 定义 | 关键特征 | |------|------|----------| | **满二叉树** | 高度h，含2^h-1个结点 | 每层都是最大结点数 | | **完全二叉树** | 与满二叉树前n个结点对应 | 叶子只在最后两层；最多一个度为1的结点(只有左孩子) | | **二叉排序树(BST)** | 左<根<右 | 查找性能取决于形态 | | **平衡二叉树(AVL)** | 任一结点左右子树高度差≤1 | 查找O(log₂n) |

二叉树的五大性质

性质1：**n₀ = n₂ + 1**（叶子数 = 度为2的结点数 + 1） 证明：n=n₀+n₁+n₂ 且 n=n₁+2n₂+1 → 联立得证 性质2：完全二叉树按层序编号，结点i： • 父结点：⌊i/2⌋（i=1时无双亲） • 左孩子：2i（2i≤n则有） • 右孩子：2i+1（2i+1≤n则有） 性质3：n个结点的完全二叉树高度 h = ⌈log₂(n+1)⌉ = ⌊log₂n⌋ + 1 性质4：完全二叉树：2^(h-1)-1 < n ≤ 2^h-1 性质5：n个结点的二叉链表有 **n+1个空链域**（可用于线索化）

【易错】由哪些遍历序列可以唯一确定一棵二叉树？

❌ 常见错误：先序+后序；先序+层序；后序+层序 ✅ 正确答案：先序+中序 或 后序+中序 可以唯一确定 💡 先序+后序不能唯一确定（无法区分左右子树）！

四种遍历方式对比

| 遍历方式 | 顺序 | 辅助结构 | 应用 | |----------|------|----------|------| | **先序(DLR)** | 根→左→右 | 栈/递归 | 复制树、路径打印 | | **中序(LDR)** | 左→根→右 | 栈/递归 | BST排序输出 | | **后序(LRD)** | 左→右→根 | 栈/递归 | 后缀表达式求值、删除树 | | **层序** | 自上而下自左而右 | **队列** | BFS、层次统计 |

线索二叉树的概念与作用

**动机**：利用n个结点二叉链表中**n+1个空链域**存放前驱/后继信息 **线索规定**： • lchild为空 → lchild指向前驱（ltag=1） • rchild为空 → rchild指向后继（rtag=1） **中序线索二叉树找后继**： • rtag==1 → rchild直接是后继 • rtag==0 → 后继=右子树中最左下的结点 **找前驱**： • ltag==1 → lchild直接是前驱 • ltag==0 → 前驱=左子树中最右下的结点

树转换为二叉树的规则

**规则：左孩子右兄弟** 三步转换： 1. **加线**：所有兄弟结点之间加连线 2. **抹线**：对每个结点，除左孩子外去掉与其他孩子的连线 3. **旋转**：以根为轴顺时针旋转45° **结果**： • 二叉树左孩子 ↔ 树的第一个孩子 • 二叉树右兄弟 ↔ 树的下一个兄弟 **森林→二叉树**：第一棵不动，后续各棵的根作为前一棵根的右孩子

树/森林遍历与二叉树遍历的对应关系

| 树/森林遍历 | 对应二叉树遍历 | |-------------|---------------| | 树的先根遍历 | 二叉树的先序遍历 | | 树的后根遍历 | 二叉树的中序遍历 | | 森林的先序遍历 | 二叉树的先序遍历 | | 森林的中序遍历 | 二叉树的中序遍历 |

二叉排序树(BST)的查找效率分析

**最好情况**：形态均匀（接近完全二叉树），ASL = O(log₂n) **最坏情况**：退化为**单支树**（有序序列依次插入），ASL = O(n) **删除操作三种情况**： 1. 叶结点：直接删除 2. 只有一棵子树：子树替代其位置 3. 有两棵子树：用**直接后继（或前驱）替代**，再删后继/前驱

AVL树的四种平衡调整（旋转）方式

| 类型 | 触发条件 | 操作 | |------|----------|------| | **LL调整(右单旋)** | A的左孩子的左子树上插入 | A的左孩子B右上旋代替A | | **RR调整(左单旋)** | A的右孩子的右子树上插入 | A的右孩子B左上旋代替A | | **LR调整(先左后右双旋)** | A的左孩子的右子树上插入 | 先左旋B的右孩子C，再右旋C | | **RL调整(先右后左双旋)** | A的右孩子的左子树上插入 | 先右旋B的左孩子C，再左旋C |

哈夫曼树(Huffman Tree)的构造与特点

**构造算法**： 1. n个结点作为n棵仅含一个结点的树，构成森林F 2. 从F中选两棵权值最小的作为新结点的左右孩子 3. 新结点权值=左右孩子权值之和 4. 删除选出的两棵，将新树加入F 5. 重复直到F只剩一棵树 **特点**： • 权值大的叶离根近，小的离根远 • 共新建n-1个分支结点，总共**2n-1个结点** • **不存在度为1的结点** • 不唯一但WPL一定相同且最小

哈夫曼编码的特点

**前缀编码**：没有一个编码是另一个编码的前缀 **构造过程**： 1. 统计字符出现频率 2. 以频率为权构造哈夫曼树 3. 左分支标0，右分支标1 4. 路径标记序列即为编码 **特点**： ✅ 是前缀编码（译码唯一） ✅ 高频字符编码短，低频字符编码长 ✅ 电文总长度最短

图的基本概念——分类体系

**有向图 vs 无向图**：边是否有方向（弧<vs边()） **简单图 vs 多重图**：是否允许重复边/自环 **完全图**： • 无向完全图：n个顶点，n(n-1)/2条边 • 有向完全图：n个顶点，n(n-1)条弧 **连通性**： • 连通图（无向）：任意两点都有路径 • 强连通图（有向）：任意两点互相可达 • 连通分量/强连通分量：极大连通子图 **生成树**：包含全部n个顶点、n-1条边的极小连通子图

图的度、入度、出度及其性质

**无向图**：度TD(v)=与v相连的边数 性质：所有顶点度之和 = **2×边数** **有向图**： • 入度ID(v)=以v为终点的边数 • 出度OD(v)=以v为起点的边数 • TD(v) = ID(v) + OD(v) 性质：所有顶点入度之和 = 出度之和 = **边数**

邻接矩阵法 vs 邻接表法

| 维度 | 邻接矩阵 | 邻接表 | |------|----------|--------| | **空间** | O(|V|²) | O(|V|+|E|)无向 / O(|V|+|E|)有向 | | **无向图** | 对称矩阵 | 每条边存两次 | | **求度** | 第i行非零元素个数=度 | 链表结点数=度（无向）/出度（有向）| | **判断邻接** | O(1) 直接查 | O(度) 需搜索链表 | | **适用** | 稠密图 | 稀疏图 | | **边的数量** | O(|V|²)扫描 | 直接统计 | ⚠️ 有向图中求入度需遍历整个邻接表！

DFS和BFS遍历对比

| | DFS深度优先 | BFS广度优先 | |--|-------------|-------------| | **策略** | 一条路走到头再回溯 | 层层扩展 | | **辅助结构** | **栈**(或递归) | **队列** | | **邻接矩阵时间** | O(|V|²) | O(|V|²) | | **邻接表时间** | O(|V|+|E|) | O(|V|+|E|) | | **空间复杂度** | O(|V|) | O(|V|) | | **特殊能力** | 可用于拓扑排序、求连通分量 | 可求**无权图单源最短路径** | | **调用次数** | =连通分量/强连通分量数 | =连通分量数 |

最小生成树(MST)的两个经典算法

**Prim算法（普里姆）**： • 思想：从某顶点开始，每次加入与当前树连接的最小权边 • 适合：**稠密图**（邻接矩阵O(|V|²)） • 类似Dijkstra **Kruskal算法（克鲁斯卡尔）**： • 思想：按权值从小到大选边，不形成环就加入 • 适合：**稀疏图**（排序O(|E|log|E|)） • 用**并查集**判断是否形成环 ⚠️ 两者都适用于**无向连通带权图**！

迪杰斯特拉(Dijkstra)算法求单源最短路径

**适用**：非负权图的单源最短路径 **思想**：贪心，每次选择未确定的最短距离顶点 **步骤**： 1. 初始化：源点距离=0，其余=∞ 2. 重复n-1次：选未访问的最小距离顶点u 3. 松弛：通过u更新邻居距离 4. 标记u已访问 **时间复杂度**： • 朴素实现：O(|V|²) • 优先队列优化：O((|V|+|E|)log|V|) ⚠️ **不适用于负权边！**

弗洛伊德(Floyd)算法求各顶点间最短路径

**适用**：求**所有顶点对**之间的最短路径 **核心思想**：动态规划，允许经过中间顶点k **状态转移**：dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]) **时间复杂度**：O(|V|³) **空间复杂度**：O(|V|²) ⚠️ 也**不适用于负权回路**（但可检测负权回路）

【易错】Dijkstra和Floyd算法的区别

❌ 常见错误：两者完全一样；Dijkstra更高效所以总用它 ✅ 正确答案：Dijkstra=单源最短路径（非负权）；Floyd=全源最短路径（可处理负权但不能有负权回路） 💡 Dijkstra是贪心策略；Floyd是DP策略。Dijkstra一次O(V²)；Floyd一次O(V³)

AOV网与拓扑排序

**AOV网**：用顶点表示活动，弧表示优先关系的有向无环图(DAG) **拓扑排序**：将DAG中所有顶点排成一个线性序列 • 若存在Vi→Vj，则序列中Vi在Vj之前 **算法**： 1. 选择入度为0的顶点并输出 2. 删除该顶点及所有以它为尾的弧 3. 重复直到无入度为0的顶点 **应用**：判断工程能否顺利进行、确定执行顺序

AOE网与关键路径

**AOE网**：用边表示活动，权表示活动持续时间的有向无环图 **关键概念**： • **事件(ve/vl)**：最早发生时间ve / 最晚发生时间vl • **活动(ee/el)**：最早开始时间ee / 最晚开始时间el • **关键活动**：ee == el 的活动（无时间余量） • **关键路径**：从源点到汇点的最长路径（=关键活动组成的路径） **求法**： 1. 正向求ve（取max） 2. 反向求vl（取min） 3. 计算每个活动的ee和el 4. ee==el的活动构成关键路径

直接插入排序详解

**思想**：每次将待排序元素插入到已排序序列的正确位置 **过程**： • 第1趟：a[1]与a[0]比较，必要时交换 • 第i趟：将a[i]插入到a[0..i-1]的合适位置 **时间复杂度**： • 最好O(n)（有序） • 最坏/平均O(n²) **空间复杂度**：O(1) **稳定性**：**稳定**（相等元素不交换）

希尔排序(Shell Sort)详解

**思想**：分组插入排序，增量d逐渐缩小 **过程**： 1. 取初始增量d₁ = ⌊n/2⌋ 2. 将相隔d的元素分为一组，组内直接插入排序 3. d逐渐减小：d₂=⌊d₁/2⌋, ... 4. 最后d=1时就是直接插入排序 **时间复杂度**：与增量序列有关，约O(n^1.3) **稳定性**：**不稳定**（相同元素可能分在不同组） ⚠️ 希尔排序是**第一个突破O(n²)的简单排序**！

冒泡排序详解

**思想**：每趟将最大元素"冒泡"到末尾 **优化**：设置flag，某趟无交换则提前结束 **时间复杂度**： • 最好O(n)（优化后，已有序） • 最坏/平均O(n²) **空间复杂度**：O(1) **稳定性**：**稳定**

快速排序(Quick Sort)详解

**思想**：分治，选pivot，小于pivot的在左边，大于的在右边 **Partition过程**： 1. 取pivot（通常第一个/最后一个/随机） 2. i从左找>pivot的，j从右找<pivot的 3. 交换a[i]和a[j] 4. i和j相遇时，pivot归位 **时间复杂度**： • 最好O(nlogn)（均匀划分） • 最坏O(n²)（已有序/逆序） • 平均O(nlogn) **空间复杂度**：O(logn)（递归栈） **稳定性**：**不稳定**

简单选择排序详解

**思想**：每趟从未排序部分选出最小元素放到已排序末尾 **时间复杂度**：始终O(n²)（比较次数固定） **空间复杂度**：O(1) **稳定性**：**不稳定**（如5 5 3 → 交换后两个5的相对顺序改变）

堆排序(Heap Sort)详解

**大根堆**：任一结点≥其左右孩子（根是最大值） **小根堆**：任一结点≤其左右孩子（根是最小值） **建堆**：从最后一个非叶结点(⌊n/2⌋)开始向下调整 **排序过程**： 1. 建大根堆 2. 交换堆顶(最大)与末尾元素 3. 对剩余n-1个元素重新调整为堆 4. 重复 **时间复杂度**：O(nlogn)（建堆O(n)，n-1次调整O(logn)每次） **空间复杂度**：O(1) **稳定性**：**不稳定**

归并排序(Merge Sort)详解

**思想**：分治，将序列分成两半分别排序，然后合并 **合并(Merge)**：两个有序序列合并为一个有序序列 **时间复杂度**：始终O(nlogn) **空间复杂度**：O(n)（辅助数组） **稳定性**：**稳定** 💡 归并排序的**最好/最坏/平均都是O(nlogn)**！

基数排序(Radix Sort)详解

**思想**：按各位数字依次分配收集（LSD/MSD） **过程**（以LSD为例）： 1. 按个位数分配到0~9号桶 2. 依次收集 3. 按十位数分配... 4. 直到最高位 **时间复杂度**：O(d(n+r)) • d=最大位数 • n=元素个数 • r=基数（10进制r=10） **空间复杂度**：O(r) **稳定性**：**稳定**

各种内部排序算法总结对比

| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | |------|------|------|------|------|------| | 插入排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ | | 希尔排序 | — | O(n^1.3) | O(n²) | O(1) | ❌ | | 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ | | 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | ❌ | | 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ❌ | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ✅ | | 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | ✅ |

【易错】哪种排序算法的时间复杂度在最好/最坏/平均情况下都是O(nlogn)？

❌ 常见错误：快速排序；堆排序；归并排序和堆排序 ✅ 正确答案：归并排序（三者都是O(nlogn)）；堆排序也是O(nlogn) 💡 注意：快速排序最坏O(n²)，归并排序需要O(n)辅助空间

顺序查找(Sequential Search)

**思想**：从头到尾逐个比较 **ASL成功**：(n+1)/2 **ASL失败**：n+1 **时间复杂度**：O(n) **优化**：哨兵技术（减少边界判断次数）

折半查找(Binary Search) —— 要求有序表

**思想**：每次与中间元素比较，缩小一半范围 **判定树**：是一棵**平衡二叉排序树** • 查找成功的比较次数 ≤ 树的高度 • 查找失败的比较次数 = 树的高度 **ASL计算**：根据判定树各层结点数加权平均 **时间复杂度**：O(log₂n) **前提**：**必须是有序的顺序表**！（链表无法折半查找）

B树和B+树的区别（数据库索引重点）

| | B树 | B+树 | |--|-----|------| | **关键字分布** | 各结点都有关键字 | 只有叶子结点有完整的关键字 | | **查找方式** | 可在非叶结点结束 | 必须到叶子结点 | | **叶子链接** | 无 | 所有叶子用指针链成有序链表 | | **范围查询** | 效率低 | ✅ 高效（沿叶子链表遍历）| | **实际应用** | 文件系统 | **数据库索引** |

散列(Hash)查找——散列函数构造方法

**除留余数法**：H(key) = key % p（p≤表长且为素数最佳） **直接定址法**：H(key = a*key + b（已知关键字分布均匀） **数字分析法**：选取分布均匀的若干位 **平方取中法**：取key²的中间几位 ⚠️ **除留余数法最常用**！

散列表冲突解决方法

**开放定址法**： • 线性探测：Hᵢ=(H(key)+di)%m, di=1,2,3,... 容易产生**堆积（聚集）**现象 • 二次探测：di=1²,-1²,2²,-2²,... • 双散列法：用第二个散列函数做步长 **拉链法(链地址法)**： • 同义词用链表链接 • ✅ 不会产生堆积，删除方便 • 适合规模不确定的情况

散列表的装填因子α

**α = 表中记录数n / 散列表长度m** **意义**： • α标志散列表的装满程度 • α越大，冲突可能性越大 • α越小，空间浪费越多 **ASL依赖α**： • 开放定址法：ASL ≈ (1+1/(1-α))/2（查找成功） • 拉链法：ASL ≈ 1 + α/2（查找成功） ⚠️ 散列表的ASL**基于α而非n**！这是和其他查找的本质区别