Appearance
顺序表（数组）
核心思想
顺序表的核心特点：
- 逻辑顺序与物理顺序一致：第 i 个元素存储在第 i 个物理位置
- 随机访问：通过起始地址 + 偏移量，O(1) 时间访问任意元素
- 静态分配 vs 动态分配：静态数组大小固定，动态数组可扩容（但需要复制数据）
⚠️ 易错：动态扩容（如 C 的 realloc、Java ArrayList 的 grow）的均摊时间复杂度是 O(1)，但单次扩容的时间复杂度是 O(n)（需要复制全部元素到新空间）。408 选择题可能问'顺序表插入的最坏时间复杂度'，如果考虑扩容则是 O(n)。
数据元素在内存中的存储方式：
地址: LOC(a₁) LOC(a₁)+d LOC(a₁)+2d ... LOC(a₁)+(n-1)d
元素: a₁ a₂ a₃ ... aₙ其中 d 是每个元素占用的存储空间大小。
插入操作流程图
交互可视化
通过下方的交互动画，你可以逐步观察顺序表各操作的执行过程：
操作详解
插入操作
在位置 i 插入新元素时，需要将第 i 个及之后的所有元素依次后移一位，腾出位置。
关键步骤：
- 判断插入位置是否合法（1 ≤ i ≤ n+1）
- 判断存储空间是否已满
- 从最后一个元素开始，依次后移到第 i 个元素
- 将新元素放入位置 i
- 表长加 1
删除操作
删除位置 i 的元素时，需要将第 i+1 个及之后的所有元素依次前移一位，填补空位。
关键步骤：
- 判断删除位置是否合法（1 ≤ i ≤ n）
- 取出被删除的元素（可能需要返回）
- 从第 i+1 个元素开始，依次前移
- 表长减 1
按值查找
从第一个元素开始，逐个比较，直到找到目标值或遍历完整个表。
⚠️ 易错：顺序表的按值查找是 O(n)，即使表是有序的也是 O(n)——除非你用折半查找。很多同学会混淆'顺序表上的顺序查找'和'有序顺序表上的折半查找'。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按位查找 | O(1) | 随机访问，直接计算地址 |
| 按值查找 | O(n) | 最坏需遍历整个表 |
| 插入 | O(n) | 平均移动 n/2 个元素 |
| 删除 | O(n) | 平均移动 (n-1)/2 个元素 |
⚠️ 易错：顺序表插入的平均移动次数是 n/2，不是 n。推导过程：假设在位置 1~n+1 等概率插入，在位置 i 插入需移动 n-i+1 个元素，平均移动 = Σ(n-i+1)/(n+1) = n/2。408 填空题常直接考这个结果。
空间复杂度：O(1)，插入和删除操作只需常数级辅助空间。
考研高频考点
- ⭐ 插入和删除的平均移动次数计算（选择题/填空题高频）
- ⭐ 顺序表 vs 链表的优缺点对比（简答题必考）
- ⭐ 随机访问特性及其原因（概念题）
- 动态扩容的时间开销分析（偶尔考）
- 顺序表的存储密度（= 1，对比链表）
相关知识
- 顺序表 vs 链表的对比贯穿整个线性表章节：顺序表胜在随机访问 O(1)，单链表胜在插入删除 O(1)（已知位置时）
- 顺序表的有序版本支持折半查找，这是查找章节的核心算法
- 栈和队列的顺序存储本质上就是对顺序表的受限操作——栈只允许在一端插入删除，队列只允许一端插入另一端删除
- 排序算法（如快速排序、堆排序）的前提就是数据存储在顺序表中，因为需要随机访问