Appearance
线性表的定义与基本概念
核心思想
线性表的定义
线性表（Linear List）是具有相同数据类型的 n（n ≥ 0）个数据元素的有限序列，记为：
L = (a₁, a₂, ..., aᵢ, ..., aₙ)其中：
- n 为表长，n = 0 时称为空表
- a₁ 是表头元素，aₙ 是表尾元素
- aᵢ₋₁ 是 aᵢ 的直接前驱，aᵢ₊₁ 是 aᵢ 的直接后继
逻辑结构特点
线性表的逻辑结构是线性结构，即数据元素之间存在一对一的关系：
| 特点 | 说明 |
|---|---|
| 有且仅有一个表头元素 | a₁ 没有前驱 |
| 有且仅有一个表尾元素 | aₙ 没有后继 |
| 其余元素有且仅有一个前驱和一个后继 | 一对一的线性关系 |
| 元素类型相同 | 每个元素占用相同大小的存储空间 |
存储结构分类
线性表的逻辑结构确定后，需要选择合适的存储结构（物理结构）来实现。408 考纲要求掌握两大类：
| 存储方式 | 实现 | 特点 |
|---|---|---|
| 顺序存储 | 顺序表（数组） | 逻辑相邻 = 物理相邻，支持随机访问 |
| 链式存储 | 单链表、双链表、循环链表、静态链表 | 用指针表示逻辑关系，物理位置任意 |
顺序表 vs 链表
| 比较维度 | 顺序表 | 链表 |
|---|---|---|
| 存取方式 | 随机访问 O(1) | 顺序访问 O(n) |
| 插入/删除 | 需要移动元素 O(n) | 修改指针 O(1)（已知位置时） |
| 空间分配 | 静态分配或动态扩容 | 动态分配，按需申请 |
| 存储密度 | 高（无额外指针开销） | 低（每个结点需要额外指针域） |
| 适用场景 | 表长可预估，频繁按位访问 | 频繁插入/删除，表长变化大 |
408 选择题经典问法："以下关于线性表的说法正确的是？"——注意区分逻辑结构（线性关系）和存储结构（顺序/链式），这是两个不同层面的概念。
线性表的基本操作
408 考纲要求的线性表基本操作：
| 操作 | 说明 |
|---|---|
| InitList(&L) | 初始化，构造空表 |
| Length(L) | 求表长 |
| LocateElem(L, e) | 按值查找 |
| GetElem(L, i) | 按位查找 |
| ListInsert(&L, i, e) | 在第 i 位插入元素 e |
| ListDelete(&L, i, &e) | 删除第 i 位元素 |
| PrintList(L) | 输出所有元素 |
| Empty(L) | 判空 |
| DestroyList(&L) | 销毁表 |
注意：
&表示引用传参（C++ 写法），含义是操作会修改线性表本身。408 真题的伪代码中经常出现这种写法。
考研高频考点
- ⭐ 线性表的定义与逻辑结构特点（选择题）
- ⭐ 顺序存储与链式存储的对比（选择题高频）
- ⭐ 随机访问 vs 顺序访问的区别（概念辨析）
- ⭐ 根据应用场景选择顺序表或链表（选择题/综合题）
- 逻辑结构与存储结构的区分（易混淆考点）
- 线性表基本操作的时间复杂度分析
易错：线性表是逻辑结构概念，不是存储结构。"顺序表"和"链表"才是存储结构。不能说"线性表是用数组实现的"——线性表既可以用顺序存储也可以用链式存储。