顺序表
含AI生成内容
顺序表
线性表的定义
线性表（Linear List）是具有相同数据类型的 n（n ≥ 0）个数据元素的有限序列。记为：
L = (a₁, a₂, ..., aᵢ, ..., aₙ)其中：
- n 为表长，n = 0 时称为空表
- aᵢ₋₁ 是 aᵢ 的直接前驱，aᵢ₊₁ 是 aᵢ 的直接后继
- 元素之间存在一对一的线性关系
辨析：线性表是逻辑结构概念，不是存储结构。“顺序表”和”链表”才是存储结构。不能说”线性表是用数组实现的”——线性表既可以用顺序存储也可以用链式存储。
顺序表的核心特点
顺序表（Sequential List）是线性表的顺序存储实现，用一组地址连续的存储单元依次存储线性表的数据元素。
关键特性
| 特性 | 说明 |
|---|---|
| 逻辑相邻 = 物理相邻 | 第 i 个元素存储在地址为 LOC(a₁) + (i-1)×d 的单元中，d 为元素大小 |
| 随机访问（Random Access） | 通过起始地址 + 偏移量即可直接访问任意元素，时间复杂度 O(1) |
| 存储密度高 | 只存储数据本身，无需额外指针域，密度 = 1 |
静态分配 vs 动态分配
| 对比项 | 静态分配 | 动态分配 |
|---|---|---|
| 数组声明 | ElemType data[MaxSize] | ElemType *data = (ElemType *)malloc(sizeof(ElemType)*initSize) |
| 空间来源 | 栈区（函数调用时分配） | 堆区（运行时手动分配） |
| 大小是否可变 | 固定，不可变 | 可通过 realloc 扩容 |
| 空间溢出 | 无法扩展，程序可能崩溃 | 可扩容，但需要复制数据 |
| 适用场景 | 最大表长可预先确定 | 表长变化范围不确定 |
考点提醒：动态扩容（如 C 的 realloc、Java ArrayList 的 grow）的均摊时间复杂度是 O(1)，但单次扩容的时间复杂度是 O(n)（需要复制全部元素到新空间）。408 选择题可能问”顺序表插入的最坏时间复杂度”，如果考虑扩容则是 O(n)。
基本操作及复杂度
按位查找
通过数组下标直接访问，时间复杂度 O(1)。
ElemType GetElem(SqList L, int i) { return L.data[i - 1]; // 数组下标从 0 开始，第 i 个元素在 i-1 位置}按值查找
从第一个元素开始逐个比较，直到找到目标值或遍历完整个表，时间复杂度 O(n)。
int LocateElem(SqList L, ElemType e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) return i + 1; // 返回位序 } return 0; // 未找到}易错：顺序表的按值查找是 O(n)，即使表是有序的也是 O(n)——除非使用折半查找。不要混淆”顺序表上的顺序查找”和”有序顺序表上的折半查找”。
插入操作
在位置 i 插入新元素时，需要将第 i 个及之后的所有元素依次后移一位，腾出位置给新元素。
关键步骤：
- 判断插入位置是否合法（1 ≤ i ≤ n+1）
- 判断存储空间是否已满
- 从最后一个元素开始，依次后移到第 i 个元素
- 将新元素放入位置 i
- 表长加 1
平均移动次数：在位置 1~n+1 等概率插入，平均移动 n/2 个元素。
时间复杂度：O(n)。
删除操作
删除位置 i 的元素时，需要将第 i+1 个及之后的所有元素依次前移一位，填补空位。
关键步骤：
- 判断删除位置是否合法（1 ≤ i ≤ n）
- 取出被删除的元素
- 从第 i+1 个元素开始，依次前移
- 表长减 1
平均移动次数：在位置 1~n 等概率删除，平均移动 (n-1)/2 个元素。
时间复杂度：O(n)。
复杂度汇总
| 操作 | 时间复杂度 | 平均移动元素数 | 说明 |
|---|---|---|---|
| 按位查找 | O(1) | — | 随机访问，直接计算地址 |
| 按值查找 | O(n) | — | 最坏需遍历整个表 |
| 插入 | O(n) | n/2 | 插入位置 i 后所有元素后移 |
| 删除 | O(n) | (n-1)/2 | 删除位置 i 后所有元素前移 |
空间复杂度：所有操作均为 O(1)，只需常数级辅助空间。
动态扩容的均摊分析
当动态顺序表容量不足时，通常将容量翻倍（如 Java 的 ArrayList 扩容为 1.5 倍，C++ vector 为 2 倍）。
- 单次扩容：复制 n 个元素，时间 O(n)
- 均摊到每次插入：假设从空表开始，经过 m 次扩容，总复制次数为 O(1) + O(2) + O(4) + … + O(m) = O(m)，均摊到每次插入为 O(1)
因此，动态顺序表的插入在均摊意义下仍然是 O(1)（不考虑元素移动的前提下）。
顺序表 vs 链表
| 比较维度 | 顺序表 | 链表 |
|---|---|---|
| 存取方式 | 随机访问 O(1) | 顺序访问 O(n) |
| 插入/删除 | 需要移动元素 O(n) | 修改指针 O(1)（已知位置时） |
| 空间分配 | 静态分配或动态扩容 | 动态分配，按需申请 |
| 存储密度 | 高（无额外指针开销）= 1 | 低（每个结点需要额外指针域）< 1 |
| 缓存性能 | 好（连续存储空间） | 差（离散存储，局部性差） |
| 适用场景 | 表长可预估，频繁按位访问 | 频繁插入/删除，表长变化大 |
适用场景
顺序表最适合以下场景：
- 频繁按位查找：O(1) 的随机访问是顺序表相对于链表的核心优势
- 表长可预先确定：避免频繁动态扩容的开销
- 插入/删除操作集中在表尾：在表尾插入/删除不需要移动元素（O(1)）
- 对缓存性能敏感：连续存储具有良好的空间局部性
判断依据：如果应用需求中”查找”操作远多于”插入/删除”，优先选择顺序表；反之优先选择链表。这是 408 简答题和选择题的经典分析框架。
考研高频考点
- ⭐ 插入和删除的平均移动次数计算（选择题/填空题高频，n/2 和 (n-1)/2 是常考数值）
- ⭐ 顺序表 vs 链表的优缺点对比（简答题必考）
- ⭐ 随机访问特性及其原因（概念题）
- ⭐ 按值查找的时间复杂度（选择题，注意区分顺序表和有序顺序表）
- 动态扩容的时间开销分析（均摊 O(1) vs 单次 O(n)）
- 顺序表的存储密度（= 1，对比链表 < 1）
- 静态分配与动态分配的区别
关联页面
- 算法分析 — 复杂度分析方法，顺序表的复杂度推导基础
- 链表（Linked List） — 链式存储实现，与顺序表进行对比
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
评论区
