线性表

🎯 一句话秒杀：线性表是 n个数据元素的有限序列，除了第一个和最后一个各有一个前驱/后继，其他元素都有一个直接前驱和一个直接后继。

① 📊【历年真题考情】

本章（线性表）在广东专升本计算机统考中的位置：

项目	结论
出题频次	⭐⭐⭐⭐⭐（五星必考）——2026 考纲全解标注"线性表：单选、填空、简答，约15分，⭐⭐⭐⭐⭐"；数据结构模块第一重点
常考题型	单选（2024 单选12/16/17/20、2021 单选10/19、2026 单选9）、判断（2024 判断10）、简答（顺序表 vs 链表）
预估分值	10~20 分 / 200 分（约 5%~10%）
考纲归属	2026 考纲「数据结构」考点12（顺序表、链表、插入删除、复杂度）

考场真实出现过的高频题：

2024 单选12：长度为 n 的顺序表，在第 i 个元素后面插入 → O(n)
2024 单选16：链表结点 = 数据域 + 指针域
2024 单选17：带头结点单链表判空 → head->next == NULL
2024 单选20：在单链表中将 s 插入 p 后 → s->next=p->next; p->next=s;
2024 判断10：除第一个元素外，每个元素有且只有一个直接前驱 → 对
2021 单选10：非空循环单链表尾结点 p 满足 → p->next == head
2021 单选19：单链表 a 是 b 的前驱，在 a、b 间插入 c 的语句
2026 单选9：顺序表表头插入 → O(n)

🎯 学习目标：学完本章，你能 ① 手推顺序表插入/删除的复杂度；② 写出正确的链表插入语句且顺序不反；③ 判断带头结点判空条件；④ 说出循环链表尾结点特征——这四类题就是本章真题的全部考法。

② 🗣️【零基础大白话引入】

线性表是什么？ 想象一列火车车厢——每节车厢连在一起，除了第一节（没有前车）和最后一节（没有后车），中间每节车厢都有前一辆和后一辆。这就是线性表：一串排好队的数据元素。

两种存储方式——就像两种坐法：

顺序表（数组） = 电影院连坐：座位号是连续的，你坐 3 号就找 3 号座——随机存取 O(1)。但有人插队时，后面所有人都要移一个位置——插入 O(n)。
链表 = 几个人手拉手：每个人记住"下一个是谁"（指针）。插入时只需"解开两只手、重新牵上"——插入 O(1)。但想找第 3 个人必须从第 1 个开始数——查找 O(n)。

为什么插入顺序不能反？ 想象你要把新朋友 c 插入 a 和 b 之间（a 牵着 b 的手）：

正确做法：先让 c 牵住 b（c->next = b），再让 a 松开 b 牵住 c（a->next = c）
错误做法：先让 a 松开 b 牵住 c → b 就丢了！（因为没人牵着 b 了）

💡 本章主线：定义（排队）→ 顺序表（连坐）→ 链表（牵手）→ 对比（什么时候用哪个）。核心是"插入顺序不能反"和"判空条件"——这两条高频单选。

③ 📖【正式核心知识点讲解】

本章知识点 = 考纲要求 + 历年真题实际考过的内容。

3.1 线性表的定义

线性表: (a1, a2, a3, ..., an)
        ↑                   ↑
     唯一首元              唯一终元

特点：

有限：元素个数n≥0（n=0时为空表）
有序：元素间有先后顺序
相同类型：所有元素类型相同

✅ 2024 判断10："在线性表中，除了第一个元素外，每个元素有且只有一个直接前驱" → 对记忆：首元无前驱，终元无后继，中间元素各有一个前驱和后继

3.2 顺序表（顺序存储）

结构定义

#define MAXSIZE 100  // 最大长度

typedef struct {
    int data[MAXSIZE];  // 存放元素的数组
    int length;          // 当前长度
} SeqList;

基本操作

// 1. 初始化
void InitList(SeqList *L) {
    L->length = 0;
}

// 2. 按下标查找（随机存取）—— O(1)
int GetElem(SeqList L, int i) {
    return L.data[i-1];  // 第i个元素存在下标i-1
}

// 3. 按值查找——O(n)
int LocateElem(SeqList L, int x) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == x) return i+1;  // 返回位序
    return 0;  // 没找到
}

// 4. 插入——O(n)（2024/2026 必考）
int Insert(SeqList *L, int i, int x) {
    if (i < 1 || i > L->length+1) return 0;  // 位置非法
    if (L->length >= MAXSIZE) return 0;      // 表满
    for (int j = L->length; j >= i; j--)
        L->data[j] = L->data[j-1];   // 从后往前移动
    L->data[i-1] = x;
    L->length++;
    return 1;
}

// 5. 删除——O(n)
int Delete(SeqList *L, int i) {
    if (i < 1 || i > L->length) return 0;
    for (int j = i; j < L->length; j++)
        L->data[j-1] = L->data[j];   // 从前往后移动
    L->length--;
    return 1;
}

3.2.1 顺序表插入/删除复杂度（2024 单选12 / 2026 单选9 必考）

顺序表插入/删除：平均移动 n/2 个元素 → 时间复杂度 O(n)

操作	移动元素个数	时间复杂度
第 i 个位置插入	n-i+1 个	O(n)
删除第 i 个元素	n-i 个	O(n)
表头插入	n 个	O(n)

顺序表插入后移 / 删除前移示意（时间复杂度 O(n)）

✅ 2024 单选12：长度为 n 的顺序表，在第 i 个元素后面插入 → C. O(n) ✅ 2026 单选9：顺序表表头插入 → C. O(n) 陷阱：A/O(1) 是链表的插入复杂度，别搞混！

🚨 红牌警告

插入删除要移动大量元素！ 平均移动 n/2 个元素第i个位置插入 → 需移动 n-i+1 个元素删除第i个元素 → 需移动 n-i 个元素

3.3 链表（链式存储）

3.3.1 单链表的结构

typedef struct Node {
    int data;            // 数据域
    struct Node *next;   // 指针域——指向下一个结点
} LNode, *LinkList;

带头结点的单链表：
head → [   |•] → [a1|•] → [a2|•] → [a3|/]
       头结点         首元结点

3.3.2 结点结构（2024 单选16 必考）

链表结点 = 数据域 + 指针域（不是"单元数"）

选项	说法	判断
A	只有一部分存放结点值	❌
B	只有指针	❌
C	值 + 所占单元数	❌（指针存地址不是单元数）
D	值 + 指针	✅

✅ 2024 单选16：结点 = D. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 记忆：结点 = data + next，不是 data + 单元数

3.3.3 头结点 vs 头指针

概念	说明
头指针	指向链表第一个结点的指针（必须有）
头结点	第一个结点前附加的结点（可选）

带头结点的优点： 对第一个位置的操作和后面的位置统一处理

3.3.4 带头结点单链表判空（2024 单选17 必考）

带头结点时，空表 = 头结点后没有数据结点 → head->next == NULL

选项	表达式	含义	判断
A	`head == NULL`	不带头结点判空，头指针本身为空	❌
B	`head->next == head`	循环链表判空	❌
C	`head->next == NULL`	带头结点判空 ✅	✅
D	其他	无关	❌

✅ 2024 单选17：带头结点单链表判空 → C. head->next == NULL 记忆：带头结点：头结点永远在，空就看它后面有没有人

3.3.5 单链表的基本操作

// 1. 初始化
LinkList InitList() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    return L;
}

// 2. 按位查找——O(n)
LNode *GetElem(LinkList L, int i) {
    LNode *p = L->next;  // 第一个数据结点
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;  // 可能为NULL（i超出范围）
}

// 3. 按值查找——O(n)
LNode *LocateElem(LinkList L, int x) {
    LNode *p = L->next;
    while (p && p->data != x)
        p = p->next;
    return p;
}

// 4. 插入（第i个位置）——O(n)
int Insert(LinkList L, int i, int x) {
    LNode *p = GetElem(L, i-1);  // 找到前驱结点
    if (!p) return 0;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;   // 新结点指向原第i个
    p->next = s;         // 前驱指向新结点
    return 1;
}

// 5. 删除第i个元素——O(n)
int Delete(LinkList L, int i) {
    LNode *p = GetElem(L, i-1);  // 前驱
    if (!p || !p->next) return 0;
    LNode *q = p->next;          // 要删除的结点
    p->next = q->next;           // 跳过q
    free(q);                     // 释放内存
    return 1;
}

3.3.6 链表插入语句顺序（2024 单选20 / 2021 单选19 必考）

将 s 插入到 p 之后：必须先 s->next = p->next，再 p->next = s——顺序不能反！

错误的顺序（先改 p->next）：

p->next = s;          // p 先指向 s，但 p 原本的后继丢了！
s->next = p->next;    // s 指向自己——形成环！

正确的顺序（先挂后连）：

s->next = p->next;    // ① 先让 s 指向 p 的后继（挂上）
p->next = s;          // ② 再让 p 指向 s（连上）

图示推演：

链表插入"先挂后连"两步操作图（顺序不能反）

✅ 2024 单选20：在单链表中将 s 插入 p 后 → D. s->next = p->next; p->next = s; 陷阱：B 第一步 s->next = p->next 正确，但第二步 p->next = s->next 把 p 指向了 s 原本的后继（即 p 原来的后继），等于没插进去！ ✅ 2021 单选19：a 是 b 的前驱，在 a、b 间插入 c → 同样套路：先 c 挂 b，再 a 连 c

3.3.7 头插法建表——常用于逆置

LinkList HeadInsert(int arr[], int n) {
    LinkList L = InitList();
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = arr[i];
        s->next = L->next;
        L->next = s;
    }
    return L;
}

💡 头插法结果逆序：arr = [1,2,3] 建出链表 [3,2,1]——因为每次插在最前面。

3.3.8 尾插法建表

LinkList TailInsert(int arr[], int n) {
    LinkList L = InitList();
    LNode *r = L;  // 尾指针
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = arr[i];
        s->next = NULL;
        r->next = s;
        r = s;  // 尾指针后移
    }
    return L;
}

💡 尾插法结果正序：arr = [1,2,3] 建出链表 [1,2,3]。

3.3.9 循环链表（2021 单选10 必考）

循环链表：尾结点的 next 指向头结点（不是 NULL）——p->next == head

循环链表：
head → [a1|•] → [a2|•] → [a3|•] → [a1]（尾指向头）

链表类型	尾结点特征	判空条件
单链表（带头结点）	`p->next == NULL`	`head->next == NULL`
循环单链表	`p->next == head`	`head->next == head`

✅ 2021 单选10：非空循环单链表 head，尾结点 p 满足 → C. p->next == head 陷阱：A p->next==NULL 是单链表；B p==NULL 是空表；D p==head 是只有一个结点的循环链表

3.4 顺序表 vs 链表对比

比较项目	顺序表	单链表
存取方式	随机存取 O(1)	顺序存取 O(n)
插入删除	需移动元素 O(n)	改指针 O(1)（已知位置）
存储密度	高(=1)	低(<1, 有指针额外空间)
空间分配	预分配（可能溢出/浪费）	动态分配（灵活）
适用场景	频繁查找、长度确定	频繁插入删除、长度不定

🔑 秒杀秘籍

什么时候用顺序表？ 读多写少 √ 什么时候用链表？ 读少写多 √ 存储密度： 顺序表100%存数据，链表还要存指针

④ 🧪【真题同源例题】

例题 1：入门基础题

顺序表长度为 n，在第 1 个位置插入一个元素，需要移动多少个元素？时间复杂度？

逐项推演：

第 1 个位置插入，所有 n 个元素都必须后移
移动元素数 = n 个
时间复杂度：O(n)

对比：链表在第 1 个位置插入只需改指针 → O(1)。顺序表插入必 O(n)。

例题 2：2024 真题改编（结点结构）

链表结点由哪两部分组成？

A. 数据域 + 单元数　　B. 数据域 + 指针域　　C. 指针域 + 单元数　　D. 数据域 + 索引

逐项分析：

链表结点 = data（存值）+ next（存地址）→ 数据域 + 指针域
答案：B. 数据域 + 指针域

✅ 对应 2024 单选16。陷阱：C"单元数"——指针存的是地址，不是单元数。

例题 3：2024 真题改编（带头结点判空）

带头结点的单链表，头指针为 head，表示单链表为空的选项是（　　）

A. head == NULL　　B. head->next == head　　C. head->next == NULL　　D. head != NULL

逐项分析：

A：head == NULL——不带头结点判空 ❌
B：head->next == head——循环链表判空 ❌
C：head->next == NULL——带头结点：头结点在，但后面无数据 ✅
D：head != NULL——头结点永远在，非空 ❌

✅ 答案 C（2024 单选17 原题）。记忆：带头结点判空看 head->next 是不是 NULL

例题 4：2024 真题改编（插入语句顺序）

在单链表中，要将 s 所指向结点插入到 p 所指向结点之后，其语句应为（　　）

A. s->next = p + 1; p->next = s; B. s->next = p->next; p->next = s->next; C. (*p).next->s; (*s).next = (*p).next; D. s->next = p->next; p->next = s;

逐项分析：

A：p+1 错误（链表不能直接用地址偏移）❌
B：第一步正确，但第二步 p->next = s->next 把 p 指向了 s 原本的 next（即 p 原本的后继）→ 等于没插 ❌
C：语法错误（->s 不合语法）❌
D：先 s->next = p->next（挂上），再 p->next = s（连上） ✅

✅ 答案 D（2024 单选20 原题）。顺序口诀：先挂后连，顺序不能反！

例题 5：2021 真题改编（循环链表尾结点）

非空循环单链表 head，尾结点 p 满足（　　）

A. p->next == NULL　　B. p == NULL　　C. p->next == head　　D. p == head

逐项分析：

A：p->next == NULL——单链表不是循环 ❌
B：p == NULL——空表 ❌
C：p->next == head——循环链表尾指向头 ✅
D：p == head——只有一个结点时也是，但"非空且尾结点"不一定是头 ❌

✅ 答案 C（2021 单选10 原题）。记忆：循环链表尾结点指向头结点，不是 NULL

⑤ ⚠️【历年真题高频扣分坑】

#	陷阱	错误做法	正确做法	出处
1	插入语句顺序反	先写 `p->next=s`	必须先 `s->next=p->next` 再 `p->next=s`	2024 单选20
2	头结点判空	`head==NULL` 当判空	带头结点空表 = `head->next==NULL`	2024 单选17
3	循环链表尾	`p->next==NULL`	循环链表尾 `p->next==head`	2021 单选10
4	结点结构	以为存"单元数"	结点 = 数据域 + 指针域	2024 单选16
5	顺序表插入复杂度	以为 O(1)	要移动元素 → O(n)	2024/2026
6	链表插入复杂度	以为要移动元素	改指针 → O(1)（已知位置）	经典
7	前驱后继	以为首元也有前驱	首元无前驱，终元无后继	2024 判断10
8	头插逆序	以为头插正序	头插法结果逆序	经典
9	存储密度	以为链表密度高	顺序表密度高(=1)，链表低	经典
10	循环链表判空	`head->next==NULL`	循环链表判空 = `head->next==head`	经典

📌 最值钱的一条：第 1 条（插入语句顺序）是 2024 单选20 和 2021 单选19 的核心——"先挂后连，顺序不能反" 一句口诀拿 6 分。

⑥ 📝【课后自测练习题】

1. 长度为 n 的顺序表，删除第 1 个元素的时间复杂度是（　　）（2024 真题风格）

A. O(1)　　B. O(log n)　　C. O(n)　　D. O(n²)

2. 带头结点的单链表，表示单链表为空的选项是（　　）（2024 真题风格）

A. head == NULL　　B. head->next == head　　C. head->next == NULL　　D. head != NULL

3. 在单链表中，将 s 插入到 p 之后，正确的语句序列是（　　）（2024 真题风格）

A. p->next = s; s->next = p->next;　　B. s->next = p->next; p->next = s;　　C. s->next = p; p->next = s;　　D. p->next = s; s->next = p;

4. 非空循环单链表中，尾结点 p 满足（　　）（2021 真题风格）

A. p->next == NULL　　B. p == NULL　　C. p->next == head　　D. p == head

5. 链表结点由哪两部分组成？（　　）（2024 真题风格）

A. 数据域 + 单元数　　B. 数据域 + 指针域　　C. 指针域 + 单元数　　D. 数据域 + 索引

👆 点击展开参考答案与解析

第1题：C. O(n)

删除第1个元素，需将后面 n-1 个元素全部前移，平均移动 n/2 → O(n)

第2题：C. head->next == NULL

带头结点时头结点始终存在，空表 = 头结点后无数据结点（2024 单选17 原题）

第3题：B. s->next = p->next; p->next = s;

先挂后连，顺序不能反（2024 单选20 原题）

第4题：C. p->next == head

循环链表尾结点指向头结点，不是 NULL（2021 单选10 原题）

第5题：B. 数据域 + 指针域

结点 = data（存值）+ next（存地址），不是"单元数"（2024 单选16 原题）

📝 原有闭卷真题挑战（保留原内容 + 扩充至 10 题）

（点击下方空白查看答案）

1. 线性表的特点是什么？

2. 顺序表中插入元素的时间复杂度？

3. 单链表为什么要带头结点？

4. 头插法建立的链表和原数组顺序有什么关系？

5. 顺序表和链表各适合什么场景？

（扩充题）

6. 带头结点单链表判空条件？

7. 将 s 插入 p 后，正确的语句顺序？

8. 循环链表尾结点特征？

9. 链表结点由哪两部分组成？

10. 顺序表在第 i 个位置插入，需移动多少元素？

👆 点击展开答案

有限序列，除首尾外每个元素有唯一前驱和唯一后继
O(n)（平均移动n/2个元素）
对第一个位置的操作和后面统一处理（不用单独判断是否第一个结点）
逆序关系——头插法每次插到最前面，原数组[1,2,3]建出来的链表是[3,2,1]
顺序表→频繁查找、长度已知；链表→频繁插入删除、长度不确定
head->next == NULL（头结点在但无数据）
先 s->next = p->next 再 p->next = s（先挂后连）
p->next == head（指向头，不是 NULL）
数据域 + 指针域（data + next）
n-i+1 个（平均移动 n/2）

📖 教材习题对照

教材习题	知识点	难度
习题2.1~2.2	线性表定义与特点	⭐
习题2.3~2.5	顺序表操作	⭐⭐
习题2.6~2.8	链表操作	⭐⭐⭐
习题2.11	头插法与尾插法	⭐⭐⭐

对应教材：严蔚敏《数据结构》C语言版第2版 → 第2章线性表 对应考试大纲：考点13 — 线性表

📺 配套视频

复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。

严蔚敏华科大 P4~P6 第二章线性表 · 顺序/链式

2.2 线性表

线性表 ​

① 📊【历年真题考情】 ​

② 🗣️【零基础大白话引入】 ​

③ 📖【正式核心知识点讲解】 ​

3.1 线性表的定义 ​

3.2 顺序表（顺序存储） ​

结构定义 ​

基本操作 ​

3.2.1 顺序表插入/删除复杂度（2024 单选12 / 2026 单选9 必考） ​

🚨 红牌警告 ​

3.3 链表（链式存储） ​

3.3.1 单链表的结构 ​

3.3.2 结点结构（2024 单选16 必考） ​

3.3.3 头结点 vs 头指针 ​

3.3.4 带头结点单链表判空（2024 单选17 必考） ​

3.3.5 单链表的基本操作 ​

3.3.6 链表插入语句顺序（2024 单选20 / 2021 单选19 必考） ​

3.3.7 头插法建表——常用于逆置 ​

3.3.8 尾插法建表 ​

3.3.9 循环链表（2021 单选10 必考） ​

3.4 顺序表 vs 链表对比 ​

🔑 秒杀秘籍 ​

④ 🧪【真题同源例题】 ​

例题 1：入门基础题 ​

例题 2：2024 真题改编（结点结构） ​

例题 3：2024 真题改编（带头结点判空） ​

例题 4：2024 真题改编（插入语句顺序） ​

例题 5：2021 真题改编（循环链表尾结点） ​

⑤ ⚠️【历年真题高频扣分坑】 ​

⑥ 📝【课后自测练习题】 ​

📝 原有闭卷真题挑战（保留原内容 + 扩充至 10 题） ​

📖 教材习题对照 ​

📺 配套视频 ​

线性表

① 📊【历年真题考情】

② 🗣️【零基础大白话引入】

③ 📖【正式核心知识点讲解】

3.1 线性表的定义

3.2 顺序表（顺序存储）

结构定义

基本操作

3.2.1 顺序表插入/删除复杂度（2024 单选12 / 2026 单选9 必考）

🚨 红牌警告

3.3 链表（链式存储）

3.3.1 单链表的结构

3.3.2 结点结构（2024 单选16 必考）

3.3.3 头结点 vs 头指针

3.3.4 带头结点单链表判空（2024 单选17 必考）

3.3.5 单链表的基本操作

3.3.6 链表插入语句顺序（2024 单选20 / 2021 单选19 必考）

3.3.7 头插法建表——常用于逆置

3.3.8 尾插法建表

3.3.9 循环链表（2021 单选10 必考）

3.4 顺序表 vs 链表对比

🔑 秒杀秘籍

④ 🧪【真题同源例题】

例题 1：入门基础题

例题 2：2024 真题改编（结点结构）

例题 3：2024 真题改编（带头结点判空）

例题 4：2024 真题改编（插入语句顺序）

例题 5：2021 真题改编（循环链表尾结点）

⑤ ⚠️【历年真题高频扣分坑】

⑥ 📝【课后自测练习题】

📝 原有闭卷真题挑战（保留原内容 + 扩充至 10 题）

📖 教材习题对照

📺 配套视频