3. 线性表基础：逻辑结构、存储结构与基本操作
线性表是数据结构中最基本、最常用的一种结构，也是后续学习栈、队列、串、数组和广义表的基础。本章将围绕线性表的逻辑结构、两种物理存储方式（顺序存储与链式存储）的优缺点对比，以及插入、删除、查找等核心操作的实现与时间复杂度分析展开。理解线性表的核心在于：逻辑上相邻的元素，在物理内存中如何组织？ 这决定了操作的效率与适用场景。
3.1 线性表的逻辑结构
线性表是由 n（n ≥ 0）个相同类型的数据元素组成的有限序列。当 n = 0 时称为空表。其逻辑特征为：存在唯一的“第一个”元素和唯一的“最后一个”元素；除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。 这种一对一的关系构成了线性序列。
在考研中，需要区分线性表的逻辑结构与物理结构。逻辑结构描述数据元素之间的抽象关系，而物理结构（存储结构）则讨论如何在计算机内存中表示这种关系。线性表的逻辑结构是线性结构，但物理实现既可以是顺序的，也可以是链式的。
3.2 顺序存储：顺序表
顺序表是用一组地址连续的存储单元依次存储线性表的元素。在 C 语言中通常用一维数组实现。设线性表首元素 a1 的存储地址为 LOC(a1)，每个元素占用 c 个字节，则第 i 个元素 ai 的存储地址为：
LOC(ai) = LOC(a1) + (i - 1) * c这一公式意味着顺序表支持随机存取，即只要知道下标，就可以在 O(1) 时间内访问任意元素。这是顺序表最大的优势。
3.2.1 顺序表的基本操作实现
以下为顺序表插入、删除、按值查找的核心代码逻辑（以静态数组为例）：
#define MaxSize 100
typedef struct {
int data[MaxSize];
int length; // 当前长度
} SqList;
// 插入：在第 i 个位置插入 e（i 从 1 开始）
bool ListInsert(SqList &L, int i, int 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]; // 后移元素
}
L.data[i - 1] = e;
L.length++;
return true;
}
// 删除：删除第 i 个元素，并用 e 返回
bool ListDelete(SqList &L, int i, int &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]; // 前移元素
}
L.length--;
return true;
}
// 按值查找：返回第一个值为 e 的元素下标（从 1 开始），找不到返回 0
int LocateElem(SqList L, int e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) return i + 1;
}
return 0;
}3.2.2 复杂度分析
| 操作 | 最好情况 | 最坏情况 | 平均情况 | 说明 |
|---|---|---|---|---|
| 按位查找（i） | O(1) | O(1) | O(1) | 随机存取，直接计算地址 |
| 按值查找 | O(1)（首元素） | O(n)（末元素） | O(n) | 需要逐个比较 |
| 插入 | O(1)（表尾插入） | O(n)（表头插入） | O(n) | 平均移动 n/2 个元素 |
| 删除 | O(1)（删除表尾） | O(n)（删除表头） | O(n) | 平均移动 (n-1)/2 个元素 |
3.3 链式存储：单链表
单链表通过一组任意的存储单元存储线性表元素，每个节点包含数据域和指针域。节点结构为：
typedef struct LNode {
int data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;链表的逻辑顺序通过指针链接实现，因此插入和删除操作只需修改指针指向，不需要移动元素。但链表不支持随机存取，查找某个位置的节点必须从头开始遍历。
3.3.1 单链表基本操作实现
// 头插法建立单链表（逆序）
LinkList List_HeadInsert(LinkList &L) {
LNode *s; int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 带头节点
scanf("%d", &x);
while (x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s; // 插入到表头
scanf("%d", &x);
}
return L;
}
// 按序号查找节点
LNode* GetElem(LinkList L, int i) {
if (i < 1) return NULL;
LNode *p = L->next; // 第一个数据节点
int j = 1;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
// 在第 i 个位置插入节点（带头节点）
bool ListInsert(LinkList &L, int i, int e) {
LNode *p = GetElem(L, i - 1); // 找到前驱
if (p == NULL) return false;
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
// 删除第 i 个节点
bool ListDelete(LinkList &L, int i, int &e) {
LNode *p = GetElem(L, i - 1);
if (p == NULL || p->next == NULL) return false;
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}3.3.2 复杂度分析
- 按位查找：需要从头遍历，平均比较 n/2 次，时间复杂度 O(n)。
- 插入/删除：如果已知前驱节点指针，修改指针的操作是 O(1)；但通常需要先查找前驱，因此整体是 O(n)。
- 头插法/尾插法建表：头插法每次在头部插入，时间复杂度 O(1)，但元素顺序与输入相反；尾插法需要维护尾指针，每次插入 O(1)，元素顺序与输入一致。
3.4 顺序表与链表的对比与选型
| 比较维度 | 顺序表 | 链表 |
|---|---|---|
| 存储空间 | 静态分配（或动态扩容），空间连续 | 动态分配，空间不连续，额外存储指针 |
| 随机访问 | O(1) 支持 | O(n) 不支持 |
| 插入/删除 | O(n) 需移动元素 | O(n) 需查找位置，但修改指针 O(1) |
| 空间利用率 | 无指针开销，但可能浪费预分配空间 | 有指针开销（4/8字节每节点），但按需分配 |
| 适用场景 | 频繁按位查找、元素个数稳定 | 频繁插入/删除、元素个数动态变化 |
3.5 实战案例：学生成绩管理系统的存储结构选型
背景：某高校开发学生成绩管理系统，需要存储 5000 名学生的成绩（学号、姓名、成绩）。系统主要操作包括：按学号查询成绩（高频）、按成绩排序（中频）、新增/删除学生（低频）。
分析过程：
- 查询需求：按学号查询是最高频操作，学号可以映射为数组下标（或通过哈希），顺序表随机访问 O(1) 优势明显。
- 排序需求：顺序表在排序时可以利用局部性原理，缓存友好，效率更高。
- 插入/删除：低频操作，即使 O(n) 的移动成本也可接受。
决策：选择顺序表存储。若使用链表，每次按学号查询需要 O(n) 遍历，5000 条数据平均 2500 次比较，性能瓶颈明显。
结果：采用顺序表后，查询响应时间从平均 2ms 降至 0.01ms，排序效率提升 40%。
复盘：当“读多写少”时，顺序表是更优选择；若系统变为“频繁插入删除”（如实时更新的选课系统），则需重新评估链表方案。