考研全科复习资料

408

数据结构

DS-02-01 线性表的基本概念与抽象数据类型

一、定位信息

项目	内容
所属圈层	核心层
考点热度	H级（高频重点） — 线性表是数据结构中最基础的章节，近5年408真题中几乎每年必考，选择题+大题累计分值常达8–15分
前置知识回顾	需掌握"数据结构基本概念（数据元素、数据对象、逻辑结构、存储结构）"及"算法时间复杂度分析"（DS-01-01至DS-01-03）
知识网络定位	线性表是最基本的线性结构，是栈、队列、串等受限线性表的上位概念，也是后续学习树、图等非线性结构的基础对比参照

二、知识点讲解

2.1 线性表的定义

线性表（Linear List） 是具有相同数据类型的 $n$ （ $n \geq 0$ ）个数据元素的有限序列，记作 $L = (a_1, a_2, \ldots, a_n)$ 。

其中：

$a_1$ 称为表头元素（首元素）， $a_n$ 称为表尾元素（尾元素）
$n$ 为线性表的长度， $n=0$ 时称为空表
除 $a_1$ 外，每个元素有且仅有一个直接前驱；除 $a_n$ 外，每个元素有且仅有一个直接后继

直观理解：线性表就像一排排队的人——每个人有固定的位置（位序），每个人前面只有一个人（前驱），后面也只有一个人（后继），队伍有头有尾，人数有限。

例子：学号列表 (2024001, 2024002, 2024003, 2024004) 就是一个线性表，其中 2024001 的后继是 2024002，2024004 的前驱是 2024003。

2.2 线性表的基本特征

特征	说明
有限性	元素个数 $n$ 是有限的（ $n \geq 0$ ）
有序性	元素之间有严格的先后次序（位序从1开始）
同构性	所有元素的数据类型相同
原子性	每个元素是不可再分的数据原子（不考虑内部结构）

2.3 线性表的抽象数据类型（ADT）

抽象数据类型定义了线性表的数据对象和操作集合，与具体存储实现无关：

ADT List {
    数据对象：D = {a_i | a_i ∈ ElemType, i = 1, 2, ..., n, n ≥ 0}
    数据关系：R = {<a_i, a_{i+1}> | i = 1, 2, ..., n-1}
    
    基本操作：
        InitList(&L)          // 初始化空表
        DestroyList(&L)       // 销毁线性表
        ListInsert(&L, i, e)  // 在第i个位置插入元素e
        ListDelete(&L, i, &e) // 删除第i个位置的元素，用e返回
        GetElem(L, i, &e)     // 获取第i个位置的元素值
        LocateElem(L, e)      // 查找值为e的元素，返回其位序
        ListLength(L)         // 返回线性表长度
        PrintList(L)          // 输出线性表所有元素
        Empty(L)              // 判断是否为空表
}

为什么要定义ADT？ ADT将"做什么"和"怎么做"分离——先明确操作语义，再讨论用顺序存储还是链式存储实现。这是软件工程中接口与实现分离思想的体现。

2.4 位序与下标

408考试中需要特别注意：位序从1开始（第1个、第2个…），而数组下标从0开始。这是贯穿整个数据结构课程的约定。在算法题中，"在第 $i$ 个位置插入"意味着位序 $i$ ，对应数组下标 $i-1$ 。

三、记忆与理解辅助

技巧1：线性表的"一句话定义"口诀

"有限、序列、同类型、有前有后有头尾"

技巧2：位序 vs 下标对比表

概念	起始值	使用场景
位序（Position）	从 1 开始	题目描述、ADT操作参数
下标（Index）	从 0 开始	C/C++ 数组实现

技巧3：ADT操作分类记忆

将基本操作按功能分为四类：

生命周期：InitList → DestroyList
增删改查：ListInsert、ListDelete、GetElem、LocateElem
状态查询：ListLength、Empty
输出展示：PrintList

技巧4：线性表 vs 其他结构的核心区别

对比项	线性表	树	图
前驱个数	≤1	1（父节点）	不限
后继个数	≤1	≤2（二叉树）	不限
逻辑关系	一对一线性	一对多层次	多对多网状

四、例题与精解

例题1（基础）

命题意图：考查对线性表基本概念和ADT操作语义的理解。

题目：设线性表 $L = (a_1, a_2, a_3, a_4, a_5)$ ，依次执行以下操作后，写出结果线性表：

ListInsert(&L, 3, x) — 在第3个位置插入元素x
ListDelete(&L, 5, &e) — 删除第5个位置的元素

审题分析：

初始线性表有5个元素，位序1~5
操作1：在位序3处插入x，原位序3及之后的元素全部后移
操作2：删除位序5处的元素

解题思路：严格按照ADT操作语义，注意插入后长度变化、元素位序变化。

完整步骤：

操作1前： $L = (a_1, a_2, a_3, a_4, a_5)$

执行 ListInsert(&L, 3, x)：

将 $a_3, a_4, a_5$ 依次后移一个位置
在位序3处放入 $x$
结果： $L = (a_1, a_2, x, a_3, a_4, a_5)$ ，长度变为6

执行 ListDelete(&L, 5, &e)：

位序5处的元素是 $a_4$ ，所以 $e = a_4$
将 $a_5, a_6$ 依次前移一个位置（注意此处 $a_6$ 即原 $a_5$ ）
结果： $L = (a_1, a_2, x, a_3, a_5)$ ，长度变为5

最终结果： $L = (a_1, a_2, x, a_3, a_5)$

方法反思：插入和删除操作会改变元素的位序，解题时一定要先确定操作后各元素的新位序，再执行下一步操作。画出每步的状态变化是最稳妥的方法。

例题2（中等）

命题意图：考查线性表ADT的综合理解和逻辑推理能力。

题目：设线性表 $L$ 有 $n$ 个元素。若要将元素 $x$ 插入到元素 $e$ 之前（假设 $e$ 一定存在于表中），请用ADT的基本操作写出伪代码，并分析时间复杂度。

审题分析：

已知： $L$ 有 $n$ 个元素， $e$ 一定存在
目标：在 $e$ 之前插入 $x$
可用操作：LocateElem、ListInsert、GetElem

解题思路：

先用 LocateElem 找到 $e$ 的位序 $i$
再用 ListInsert 在位序 $i$ 处插入 $x$

完整步骤：

// 在元素e之前插入x（假设e一定存在）
void InsertBefore(List &L, ElemType e, ElemType x) {
    int i = LocateElem(L, e);  // 找到e的位序i，时间复杂度O(n)
    ListInsert(L, i, x);       // 在位序i处插入x，时间复杂度O(n)
}
// 总时间复杂度：O(n) + O(n) = O(n)

方法反思：

此题的关键是理解"在 $e$ 之前"对应"在位序 $i$ 处插入"
如果 $e$ 不一定存在，需要先判断 LocateElem 的返回值
变式：若要"在 $e$ 之后插入"，则应 ListInsert(L, i+1, x)

五、考情分析

分析维度	说明
考查频次	线性表整体章节（含本单元及后续3个单元）近5年每年必考
常见题型	本单元概念部分主要以选择题形式考查（如线性表特征判断、ADT操作语义）
分值占比	线性表章节整体约8–15分；本单元作为概念基础，单独考查约2分
命题趋势	线性表基本概念单独出大题的概率较低，但它是后续顺序表/链表大题的审题基础；近年趋势是将概念理解与算法设计结合考查

注：热度等级基于408真题命题规律和大纲权重综合判断。精确数据待真题分析子代理输出后校准。

六、易错点提醒

易错点1

错误表现：将位序和下标混淆，写"在第0个位置插入"
错误原因：C语言数组下标从0开始的习惯根深蒂固
正确做法：408考试中，线性表的位序统一从1开始。"第 $i$ 个位置"就是位序 $i$ ，对应数组下标 $i-1$ 。牢记口诀："题目说位序，代码减一存"

易错点2

错误表现：认为空表没有操作意义，忽略 $n=0$ 的情况
错误原因：直觉上觉得"空表没什么好讨论的"
正确做法：空表是合法的线性表（ $n=0$ ）。在算法题中必须考虑空表的边界情况，如 ListInsert(&L, 1, x) 在空表上执行后，表变为只有 $x$ 一个元素

易错点3

错误表现：对"直接前驱"和"直接后继"理解有误，认为 $a_3$ 的前驱是 $a_1$
错误原因：将"前驱"理解为"前面的所有元素"
正确做法：直接前驱仅指紧邻的前一个元素。 $a_3$ 的直接前驱是 $a_2$ ， $a_1$ 没有直接前驱， $a_n$ 没有直接后继

易错点4

错误表现：忽略ADT操作中引用参数（&）的含义
错误原因：对C语言引用传递不熟悉
正确做法：&L 表示传入的是线性表的引用（地址传递），操作会修改原表；&e 表示通过引用返回值。考试中务必注意哪些参数需要加 &

七、来源标注

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

408 ​

数据结构 ​

DS-02-01 线性表的基本概念与抽象数据类型 ​

一、定位信息 ​

二、知识点讲解 ​

2.1 线性表的定义 ​

2.2 线性表的基本特征 ​

2.3 线性表的抽象数据类型（ADT） ​

2.4 位序与下标 ​

三、记忆与理解辅助 ​

四、例题与精解 ​

例题1（基础） ​

例题2（中等） ​

五、考情分析 ​

六、易错点提醒 ​

七、来源标注 ​

408