考研全科复习资料

408

数据结构

DS-02-02 线性表的顺序存储（顺序表）

一、定位信息

项目	内容
所属圈层	核心层
考点热度	H级（高频重点） — 顺序表的插入、删除、查找操作是408选择题和大题的常考点，近5年真题中频繁出现
前置知识回顾	需掌握线性表的基本概念与ADT（DS-02-01），以及数组的存储方式和时间复杂度分析（DS-01-03）
知识网络定位	顺序表是线性表的第一种物理实现方式，与链式存储（DS-02-03）构成线性表的两大存储方案，是理解栈、队列顺序实现的基础

二、知识点讲解

2.1 顺序表的定义

顺序表（Sequential List） 是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。

核心思想：用数组实现线性表。元素 $a_i$ 存储在数组下标 $i-1$ 的位置。

设线性表第一个元素的存储地址为 $\text{LOC}(a_1)$ ，每个元素占用 $c$ 个存储单元，则第 $i$ 个元素的地址为：

$\text{LOC}(a_i) = \text{LOC}(a_1) + (i-1) \times c$

这就是顺序表的随机存取特性——通过位序直接计算地址，时间复杂度 $O(1)$ 。

直观理解：顺序表就像电影院的一排座位——座位是连续编号的，知道第一个座位号就能立刻算出第 $i$ 个座位号，不需要一个一个数过去。

2.2 顺序表的存储结构定义

#define MaxSize 100              // 顺序表最大容量
typedef struct {
    ElemType data[MaxSize];      // 存放数据元素的数组
    int length;                  // 当前长度（已有元素个数）
} SqList;                        // 顺序表类型

关键属性：

data[0..MaxSize-1]：存储空间
length：当前元素个数， $0 \leq \text{length} \leq \text{MaxSize}$
有效元素存储在 data[0] 到 data[length-1]

2.3 基本操作及时间复杂度分析

（1）插入操作 ListInsert(&L, i, e)

功能：在顺序表 $L$ 的第 $i$ 个位置（ $1 \leq i \leq \text{length}+1$ ）插入新元素 $e$ 。

算法步骤：

判断插入位置 $i$ 是否合法： $1 \leq i \leq \text{length}+1$
判断表是否已满： $\text{length} \geq \text{MaxSize}$ 则无法插入
将第 $i$ 个到第 $n$ 个元素依次后移一位（从后往前移）
在位置 $i$ 放入新元素 $e$
表长度加1

// 在顺序表L的第i个位置插入元素e
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)      // ① 检查插入位置是否合法
        return false;
    if (L.length >= MaxSize)             // ② 检查表是否已满
        return false;
    for (int j = L.length; j >= i; j--)  // ③ 从后往前，逐个后移
        L.data[j] = L.data[j - 1];      //    将下标j-1的元素移到下标j
    L.data[i - 1] = e;                   // ④ 在下标i-1处放入新元素
    L.length++;                          // ⑤ 长度加1
    return true;
}

时间复杂度分析：

最好情况：在表尾插入（ $i = n+1$ ），不需要移动元素， $T(n) = O(1)$
最坏情况：在表头插入（ $i = 1$ ），需要移动全部 $n$ 个元素， $T(n) = O(n)$
平均情况：假设在每个位置插入的概率相等（均为 $\frac{1}{n+1}$ ），平均移动次数为：

$\bar{M} = \sum_{i=1}^{n+1} \frac{1}{n+1} \times (n - i + 1) = \frac{n}{2}$

因此平均时间复杂度为 $T(n) = O(n)$ 。

（2）删除操作 ListDelete(&L, i, &e)

功能：删除顺序表 $L$ 的第 $i$ 个位置（ $1 \leq i \leq \text{length}$ ）的元素，用 $e$ 返回被删元素。

// 删除顺序表L的第i个位置的元素，用e返回
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length)           // ① 检查删除位置是否合法
        return false;
    e = L.data[i - 1];                   // ② 保存被删元素
    for (int j = i; j < L.length; j++)   // ③ 从前往后，逐个前移
        L.data[j - 1] = L.data[j];      //    将下标j的元素移到下标j-1
    L.length--;                          // ④ 长度减1
    return true;
}

时间复杂度分析：

最好情况：删除表尾元素（ $i = n$ ），不需要移动元素， $T(n) = O(1)$
最坏情况：删除表头元素（ $i = 1$ ），需要移动 $n-1$ 个元素， $T(n) = O(n)$
平均情况：平均移动次数为 $\frac{n-1}{2}$ ，时间复杂度 $T(n) = O(n)$

（3）按位查找 GetElem(L, i, &e)

// 获取顺序表L第i个位置的元素值
bool GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length)           // ① 检查位置是否合法
        return false;
    e = L.data[i - 1];                   // ② 直接通过下标取值，O(1)
    return true;
}

时间复杂度： $O(1)$ — 这是顺序表的最大优势（随机存取）。

（4）按值查找 LocateElem(L, e)

// 查找值为e的元素，返回其位序（未找到返回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;                            // ③ 未找到返回0
}

时间复杂度：

最好情况：第一个元素就是目标， $T(n) = O(1)$
最坏情况：目标在最后或不存在， $T(n) = O(n)$
平均情况： $T(n) = O(n)$

2.4 顺序表的特点总结

特点	说明
随机存取	按位查找 $O(1)$ ，这是最大优势
存储密度高	只存数据，不存指针，存储利用率100%
插入删除慢	平均需要移动 $O(n)$ 个元素
容量固定	静态分配时空间大小编译时确定
缓存友好	数据连续存储，CPU缓存命中率高

三、记忆与理解辅助

技巧1：插入删除移动方向口诀

"插入从后往前移，删除从前往后移"

插入时从最后一个元素开始后移（避免覆盖），删除时从被删位置的下一个开始前移。

技巧2：时间复杂度速记表

操作	最好	最坏	平均	核心考点
插入	$O(1)$	$O(n)$	$O(n)$	考平均情况
删除	$O(1)$	$O(n)$	$O(n)$	考平均情况
按位查	$O(1)$	$O(1)$	$O(1)$	随机存取
按值查	$O(1)$	$O(n)$	$O(n)$	需遍历

技巧3：地址计算公式记忆法

$\text{LOC}(a_i) = \text{基地址} + (\text{位序} - 1) \times \text{元素大小}$

记忆口诀："基址加偏移，位序减一乘大小"

技巧4：顺序表 vs 链表综合对比（预览，详见DS-02-03）

对比维度	顺序表	链表
存储方式	连续空间	离散空间
随机存取	✅ 支持 $O(1)$	❌ 不支持 $O(n)$
插入/删除	$O(n)$ （需移动元素）	$O(1)$ （改指针即可）
存储密度	高（100%）	较低（需存指针）
空间大小	固定（静态分配）	动态按需分配

四、例题与精解

例题1（基础）

命题意图：考查顺序表插入操作的执行过程和元素移动次数。

题目：设顺序表 $L = (12, 25, 37, 48, 56, 68)$ ，表长 $n=6$ 。执行 ListInsert(&L, 3, 99) 后：

写出结果顺序表
共移动了多少个元素？

审题分析：

初始表： $L = (12, 25, 37, 48, 56, 68)$
在位序3处插入99
位序3对应数组下标2，该位置原存放37

解题思路：从最后一个元素开始，逐个后移一位，然后在空出的位置放入新元素。

完整步骤：

步骤	操作	数组状态（下标0~6）
初始	—	`[12, 25, 37, 48, 56, 68, _]`
第1次移动	`data[6] = data[5]`	`[12, 25, 37, 48, 56, 68, 68]`
第2次移动	`data[5] = data[4]`	`[12, 25, 37, 48, 56, 56, 68]`
第3次移动	`data[4] = data[3]`	`[12, 25, 37, 48, 48, 56, 68]`
第4次移动	`data[3] = data[2]`	`[12, 25, 37, 37, 48, 56, 68]`
插入	`data[2] = 99`	`[12, 25, 99, 37, 48, 56, 68]`

结果： $L = (12, 25, 99, 37, 48, 56, 68)$ ，共移动 4 个元素。

方法反思：

移动的元素是位序 $i$ 到位序 $n$ 的所有元素，共 $n - i + 1 = 6 - 3 + 1 = 4$ 个
一般公式：在位序 $i$ 插入需移动 $n - i + 1$ 个元素
记忆技巧：移动次数 = 表尾与插入位置之间的元素数 + 1

例题2（中等）

命题意图：综合考查顺序表的删除操作及时间复杂度分析。

题目：设顺序表 $L$ 有 $n$ 个元素。编写一个算法，删除顺序表中所有值为 $x$ 的元素，要求时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。

审题分析：

输入：顺序表 $L$ ，元素值 $x$
输出：删除所有值为 $x$ 的元素后的 $L$
约束： $T(n) = O(n)$ ， $S(n) = O(1)$ （原地算法，不能创建新数组）

解题思路：用双指针法（也叫"快慢指针"）。k 指向新表的末尾，i 遍历原表。若 data[i] != x，则将其放入 data[k] 并 k++。

完整步骤：

// 删除顺序表中所有值为x的元素（原地算法）
void DeleteAllX(SqList &L, ElemType x) {
    int k = 0;                           // ① k：新表的末尾指针（慢指针）
    for (int i = 0; i < L.length; i++) { // ② i：遍历指针（快指针）
        if (L.data[i] != x) {           // ③ 若当前元素不等于x
            L.data[k] = L.data[i];      // ④ 将其放入新表末尾
            k++;                         // ⑤ 新表末尾后移
        }
        // 若data[i] == x，跳过（不放入新表）
    }
    L.length = k;                        // ⑥ 更新表长
}

逐行分析：

第①行：k 初始为0，指向新表的第一个位置
第②行：i 从0到 L.length-1 遍历每个元素
第③行：只有不等于 x 的元素才保留
第④行：将保留的元素"压缩"到前面
第⑥行：更新表长为 k（保留的元素个数）

复杂度分析：

时间：只遍历一次， $T(n) = O(n)$ ✅
空间：只用了常数个变量， $S(n) = O(1)$ ✅

方法反思：

这是经典的双指针/快慢指针技巧，在数组类题目中极为常用
变式：保留满足某种条件的元素、去重等都可以用类似思路
易错点：最后一定要更新 L.length = k，否则表长不正确

五、考情分析

分析维度	说明
考查频次	顺序表操作几乎每年都会出题，选择题1–2道或大题1道
常见题型	选择题（如求插入/删除的移动次数、地址计算）；大题（如设计算法实现特定功能）
分值占比	约4–8分（选择题2分/道，大题可到8分）
命题趋势	近年趋势：算法大题越来越强调"最优时间复杂度"要求，双指针、二分等技巧是高频考点；顺序表与链表的对比也常作为选择题考查

六、易错点提醒

易错点1

错误表现：插入操作从前向后移元素，导致数据被覆盖
错误原因：没有理解移动方向的必要性
正确做法：插入必须从后向前移动（先移最后的元素），因为从前向后移会导致后面的元素被前面的值覆盖。删除则相反，从前向后移

易错点2

错误表现：忘记检查插入/删除位置的合法性，直接操作
错误原因：算法题中只关注核心逻辑，忽略边界检查
正确做法：插入合法范围是 $1 \leq i \leq n+1$ ，删除合法范围是 $1 \leq i \leq n$ 。408算法大题中，缺少合法性检查会被扣分

易错点3

错误表现：按位查找与按值查找的时间复杂度搞混
错误原因：认为"查找"一定是 $O(n)$
正确做法：按位查找（已知位序求元素）是 $O(1)$ ，因为可以直接计算地址；按值查找（已知元素求位序）是 $O(n)$ ，因为必须逐个比较。顺序表的随机存取只对按位查找有效

易错点4

错误表现：混淆"表长"和"数组大小"
错误原因：对 length 和 MaxSize 的区别不清楚
正确做法：MaxSize 是数组的最大容量（静态分配时固定），length 是当前实际存储的元素个数。length 可以从 0 变到 MaxSize，但不能超过 MaxSize

七、来源标注

依据2026考研统考大纲——数据结构部分"线性表的顺序存储"
依据《数据结构（C语言版）》严蔚敏版第二章
依据《数据结构》王道考研辅导讲义

408 ​

数据结构 ​

DS-02-02 线性表的顺序存储（顺序表） ​

一、定位信息 ​

二、知识点讲解 ​

2.1 顺序表的定义 ​

2.2 顺序表的存储结构定义 ​

2.3 基本操作及时间复杂度分析 ​

（1）插入操作 ListInsert(&L, i, e) ​

（2）删除操作 ListDelete(&L, i, &e) ​

（3）按位查找 GetElem(L, i, &e) ​

（4）按值查找 LocateElem(L, e) ​

2.4 顺序表的特点总结 ​

三、记忆与理解辅助 ​

四、例题与精解 ​

例题1（基础） ​

例题2（中等） ​

五、考情分析 ​

六、易错点提醒 ​

七、来源标注 ​

408