顺序表（数组）

2026 大纲 二（二）线性表的实现 · 1 顺序存储。

一条约定，推出全部性质

顺序表只有一条约定：第 $i$ 个元素存放在第 $i$ 个物理位置上。 本篇剩下的所有性质，都是这一条的推论。

先看它带来的红利。既然位置是固定的，那么第 $i$ 个元素的地址就能算出来：

$$\mathrm{LOC}(a_i)=\mathrm{LOC}(a_1)+(i-1)\times d$$

$d$ 是每个元素占用的存储单元数。这是一次乘法加一次加法，与 $i$ 的大小无关——取第 1 个和取第 100 万个一样快，这就是随机存取。

再看它的账单。插入和删除会破坏这条约定：在中间插一个元素，后面每个元素的"第 $i$ 个"身份都往后挪了一位；删一个则往前挪。要让约定继续成立，就只能把元素搬回它该在的物理位置上——这就是顺序表插删必须移动元素的全部原因。

还有一处贯穿全篇的错位要先说好：位序从 1 数，数组下标从 0 数，第 $i$ 个元素存在 data[i-1]。顺序表代码写错，多半就错在这个 1 上。

先看一眼

加载可视化中...

拖着插入和删除各走一遍，重点盯元素搬动的方向和搬了几个：在表头插入时整个表都要后移，在表尾插入则一个都不用动。这个"位置不同、代价差 $n$ 倍"的现象，就是下面平均移动次数那一节要算的东西。

存储结构

#define MaxSize 50            // 静态分配：容量上限，编译期确定

typedef struct {
    ElemType data[MaxSize];   // 定长数组，直接嵌在结构体里
    int length;               // 当前表长（元素个数），不是容量
} SqList;

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 2.2，p46。图中 last 记的是最后一个元素的下标（空表 last = -1），下文代码用 length 记元素个数（空表 length = 0）。两套等价（last = length - 1），但同一份代码里必须只用一套。

容量也可以在运行期再定，即动态分配：结构体里只存一个基地址，空间用 malloc 在堆上申请，满了就另申请一块更大的、把老数据整体搬过去。

⚠️ 动态分配不是链式存储。 这是概念上最容易滑过去的一处：动态分配只把"什么时候申请这块连续空间"从编译期推迟到了运行期，申请到手的仍然是一整块地址连续的空间，第 $i$ 个元素仍在第 $i$ 个物理位置上，地址公式照样成立，随机存取照样 $O(1)$。真正区分顺序存储与链式存储的是"逻辑相邻是不是等于物理相邻"，不是"空间什么时候申请"。

动态分配的结构定义、扩容代码与均摊分析（想弄清"均摊常数时间"怎么来的就展开）

#define InitSize 10

typedef struct {
    ElemType *data;   // 只存基地址，真正的空间用 malloc 在堆上申请
    int MaxSize;      // 当前容量，可变
    int length;       // 当前表长
} SeqList;

void InitList(SeqList &L) {
    L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
    L.MaxSize = InitSize;
    L.length = 0;
}

// 扩容：另申请一块更大的空间，把老数据整体复制过去，再释放老空间
void IncreaseSize(SeqList &L, int len) {
    ElemType *p = L.data;
    L.data = (ElemType *)malloc(sizeof(ElemType) * (L.MaxSize + len));
    for (int i = 0; i < L.length; i++)
        L.data[i] = p[i];        // 逐个搬到新空间，这一步是 O(n)
    L.MaxSize += len;
    free(p);                      // 释放老空间，否则内存泄漏
}

均摊分析：单次扩容要复制全部 $n$ 个元素，代价 $O(n)$，但扩容不是每次插入都发生。按倍增策略（容量满则翻倍）连续插入 $n$ 个元素，发生复制的时刻是容量为 $1,2,4,8,\dots$ 的那几次，总复制次数为

$$1+2+4+\cdots +2^{\lfloor {\log }_{2}n\rfloor }<2n$$

平摊到 $n$ 次插入上，每次插入分担的扩容开销小于 2 次元素复制，即均摊 $O(1)$。

⚠️ 如果扩容策略是"每次固定加 $c$ 个位置"而非倍增，则扩容发生 $n/c$ 次、每次复制 $O(n)$，总代价 $O(n^2/c)$，均摊退化为 $O(n)$。"扩容均摊 $O(1)$"这个结论依赖倍增策略，不是无条件成立的。

四个基本操作

// 按位查找：直接算地址，一步到位
bool GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;  // 位序从 1 起算
    e = L.data[i - 1];                        // 位序 i ↔ 下标 i-1
    return true;
}

// 按值查找：从头逐个比较，返回位序（不是下标）；0 是非法位序，可作失败标志
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;
    return 0;
}

// 插入：在第 i 个位置之前插入 e，第 i ~ 第 n 个元素依次后移一位
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;  // 插入的合法范围比删除多一个 n+1
    if (L.length >= MaxSize) return false;        // 表满，静态分配下无法插入
    for (int j = L.length; j >= i; j--)           // 必须从后往前，否则前面的值被覆盖
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}

// 删除：删掉第 i 个元素，第 i+1 ~ 第 n 个元素依次前移一位
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;   // 删除的合法范围没有 n+1
    e = L.data[i - 1];                          // 先取出被删元素的值
    for (int j = i; j < L.length; j++)          // 从前往后，把后面的往前挪
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

两个循环的方向相反，这不是巧合，也不用死记。判据只有一句：先动的那一格，必须是马上要被覆盖掉的那一格。 插入时空位在后面，所以从后往前搬；删除时空位在前面，所以从前往后搬。方向写反的后果很有辨识度——同一个值会被复制满整段区间。

还有两个合法范围的细节：插入是 $1\le i\le n+1$，删除是 $1\le i\le n$。插入多出来的那个 $n+1$ 对应"插在表尾之后"，此时一个元素都不用移动。

⚠️ 按值查找是 $O(n)$，表有序也仍是 $O(n)$——上面的 LocateElem 根本没利用有序性。要降到 $O({\log }_{2}n)$ 必须换算法，即折半查找，而折半查找成立的前提恰恰是顺序表的随机存取。

插入与删除四个边界的逐格自查（第一次学、或想手动模拟时展开）

插入的边界自查：

• $i=n+1$（插在表尾之后）：循环 j 从 $n$ 递减到 $n+1$，一次都不执行，直接写 data[n] = e，移动 0 个元素，正确；
• $i=1$（插在表头）：循环执行 $n$ 次，全部元素后移，移动 $n$ 个元素，代价最大；
• 空表插入 $i=1$：length = 0，循环不执行，data[0] = e，length 变 1，正确。

删除的边界自查：

• $i=n$（删表尾）：循环 j 从 $n$ 到 $n-1$，不执行，移动 0 个元素；
• $i=1$（删表头）：循环执行 $n-1$ 次，移动 $n-1$ 个元素，代价最大；
• 空表删除：length = 0，$i\ge 1>0$ 触发合法性判断，返回 false，正确。

删除后落在表外的残值不需要清除——length 已经减 1，任何合法操作都不会读到它。这是"删除即改 length"的直接体现。

一次插删要搬多少个元素

上一节的边界自查已经透出规律：搬多少，只取决于插在哪。 插在表尾之后一个不用搬，插在表头要搬 $n$ 个。把所有位置平均一下，就是两个结论：

$$E_{\text{ins}}=\frac{n}{2},E_{\text{del}}=\frac{n-1}{2}$$

🔴 两者为什么差一点，有确定的来历：插入有 $n+1$ 个合法位置、删除只有 $n$ 个；对应地，插入的移动次数取遍 $\{0,1,\dots ,n\}$，删除取遍 $\{0,1,\dots ,n-1\}$。两个式子其实在算同一件事——一个从 0 到某上界的等差数列的平均值，上界分别是 $n$ 和 $n-1$。记住这个结构比记两个式子可靠：换成问"最坏移动多少次"也能立刻答上来（分别是 $n$ 和 $n-1$）。

按值查找的平均比较次数同理，等概率下是 ${\displaystyle \frac{n+1}{2}}$ 次。

⚠️ 等概率是一个显式前提，不是恒成立的事实。 题目若改成"只在表尾插入"，平均移动次数是 0；改成"只在表头插入"，就是 $n$。看到"平均"二字，先找它的概率假设。

三个平均值的完整求和推导（想自己推一遍而不是记结论就展开）

插入：插入位置 $i$ 的合法取值是 $1,2,\dots ,n+1$，共 $n+1$ 种。在第 $i$ 个位置插入需要移动第 $i$ 至第 $n$ 个元素，共 $n-i+1$ 个。设 $p_i$ 为在第 $i$ 个位置插入的概率：

$$E_{\text{ins}}=\sum _{i=1}^{n+1}{p}_i(n-i+1)$$

在等概率假设下 $p_i={\displaystyle \frac{1}{n+1}}$，代入得

$$E_{\text{ins}}=\frac{1}{n+1}\sum _{i=1}^{n+1}(n-i+1)=\frac{1}{n+1}(n+(n-1)+\cdots +1+0)=\frac{1}{n+1}\cdot \frac{n(n+1)}{2}=\frac{n}{2}$$

删除：删除位置 $i$ 的合法取值是 $1,2,\dots ,n$，共 $n$ 种。删除第 $i$ 个元素需要移动第 $i+1$ 至第 $n$ 个元素，共 $n-i$ 个。等概率下 $p_i={\displaystyle \frac{1}{n}}$：

$$E_{\text{del}}=\sum _{i=1}^n{p}_i(n-i)=\frac{1}{n}((n-1)+(n-2)+\cdots +1+0)=\frac{1}{n}\cdot \frac{n(n-1)}{2}=\frac{n-1}{2}$$

按值查找：设查找第 $i$ 个元素需要比较 $C_i=i$ 次，等概率 $p_i=1/n$ 下

$$\mathrm{ASL}=\sum _{i=1}^n{p}_i{C}_i=\frac{1}{n}\sum _{i=1}^{n}i=\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{n+1}{2}$$

插入与删除的对读

	插入	删除
合法位置数	$n+1$	$n$
在位置 $i$ 的移动次数	$n-i+1$	$n-i$
移动次数的取值集合	$\{0,1,\dots ,n\}$	$\{0,1,\dots ,n-1\}$
最大移动次数（发生在 $i=1$）	$n$	$n-1$
平均移动次数	${\displaystyle \frac{n}{2}}$	${\displaystyle \frac{n-1}{2}}$

考点速记

三条会被反复调用的结论：

1. 一切都来自那条约定——第 $i$ 个元素放在第 $i$ 个物理位置。随机存取是红利，插删要移动元素是账单。
2. 按位查找 $O(1)$，按值查找、插入、删除都是 $O(n)$，辅助空间一律 $O(1)$。
3. 存储密度恒为 1，这是顺序表相对链表唯一的空间优势；一旦按上限预分配出大片空闲区，优势就被抵消。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 哪个操作的平均时间是 $O(1)$：四个选项摆出查找、插入、删除、按位取值，只有按位取值是 $O(1)$。题干里"有序表"三个字是干扰——顺序查找不会因为有序变快，而折半查找是 $O({\log }_{2}n)$，仍不是 $O(1)$。
• 哪些操作必然引起元素移动：在空间充足、保持元素相对顺序的前提下，表头插入、表头删除必然移动，表尾插入、表尾删除一个都不用动。判断依据就是"约定被破坏在哪一段"。
• 换成链式存储后，哪些算法会变慢：凡是依赖随机存取的算法都会退化——希尔排序要按增量跳着取元素，堆排序要按下标算孩子结点，链式存储下这两步都得从头走。
• 大题里当数组用：循环左移、找主元素、两个升序序列的中位数、最小未出现正整数等，题面通常同时限定时间和空间，要求在数组上做到 $O(n)$ 时间、$O(1)$ 辅助空间。

易错：插入与删除的移动方向写反。 插入从后往前、删除从前往后。判据是"先动的那一格必须是马上要被覆盖掉的那一格"；写反的症状是同一个值复制满整段。

易错：把"动态分配"当成链式存储。 它拿到的仍是一整块连续空间，随机存取照样 $O(1)$。区分顺序与链式的标准是"逻辑相邻是否等于物理相邻"。

易错：位序与下标错位 1。 位序从 1 起、下标从 0 起，第 $i$ 个在 data[i-1]；插入合法范围 $1\le i\le n+1$，删除只到 $n$。

教材出处

• 顺序表插入算法与"在第 $i$ 个位置插入需从第 $n$ 个元素起依次后移、共 $n-i+1$ 个元素"， 以及按值查找平均查找长度 ${\displaystyle \frac{n+1}{2}}$ 的推导： 严蔚敏《数据结构（C 语言版）》（第 2 版），p27，2.4 节。
• 插入平均移动次数 $E_{\text{ins}}=\sum p_i(n-i+1)={\displaystyle \frac{n}{2}}$ 的完整推导 （式 2-5、2-6）：同书 p28。
• 删除算法与平均移动次数 $E_{\text{del}}=\sum p_i(n-i)={\displaystyle \frac{n-1}{2}}$ 的完整推导 （式 2-7、2-8）：同书 p29。该页末尾同时指出，顺序表随机存取的优点"也造成了这种存储 结构的缺点：在做插入或删除操作时，需移动大量元素"。
• 顺序表存储密度为 1、单链表整型结点存储密度为 0.5 的对比：同书 p41，2.6 节。

相关知识

线性表的基本概念（选型判据）｜单链表（链式存储主篇）｜折半查找（成立前提正是随机存取）｜顺序栈｜循环队列｜快速排序｜堆排序

相关文章

• 线性表基本概念
• 单链表
• 双链表
• 循环链表
• 静态链表
• 链表题的三种通用解法

交互体验

前往完整可视化页面 →

真题练习

相关真题（9题）

2026Q12分2025Q4113分2023Q12分2020Q92分2020Q4113分2018Q4113分2013Q4113分2011Q4215分2010Q4213分