首页/数据结构/第 2 章 线性表
408 计算机学科专业基础 数据结构 第 2 章

线性表
顺序表、链表与算法题

选择题 1–2 道,更重要的是:408 算法设计题有一大半出在数组和链表上。本章既讲基础操作,也汇总了历年算法题的最优思路。

线性表是“一个接一个排好队”的数据。两种放法——挨着放(顺序表)和用指针串起来(链表)——各有长短。学会在两者之间权衡,就学会了数据结构最核心的思维方式。

5 个考点模块 10 道历年算法题 2 张图
a1 a2 a3 a4 顺序表:连续存放 a1 a2 a3 链表:用指针串起来
00
复习策略

考频地图

★★★★☆ 高频 选择 + 算法题

线性表本身的选择题不难,但它是 408 算法设计题(13–15 分)最常见的素材:几乎每年第 41 或 42 题都要求在数组或链表上设计一个高效算法。本章最后有历年真题的思路汇总。

考点考频常见问法
顺序表的随机存取与插删★★★☆☆“插入第 i 个位置需移动多少元素”
单链表的插入删除★★★★☆“下列语句序列能正确插入结点的是”
双链表、循环链表★★★☆☆“删除尾结点 / 插入表尾,哪种链表最省时间”
顺序表 vs 链表选择★★★☆☆“最常用操作是……,宜采用”
算法设计题★★★★★数组 / 链表上的时间、空间最优算法
一句话:顺序表“查快改慢”:按下标 O(1) 存取,插删平均移动一半元素;链表“改快查慢”:已知位置时插删 O(1),但找到位置要 O(n)。链表操作的关键是指针修改顺序——先连新的,再断旧的。
01
2.1 · 基础

顺序表

★★★☆☆ 中频 选择题

用一组地址连续的存储单元依次存放线性表的元素。第 i 个元素(从 1 起)的地址:

LOC(aᵢ) = LOC(a₁) + (i − 1) × 每个元素占用的字节数  → 随机存取,O(1)

插入与删除要移动多少元素

操作移动次数最好最坏等概率平均
在第 i 个位置插入(1 ≤ i ≤ n+1)n − i + 10(表尾)n(表头)n / 2
删除第 i 个元素(1 ≤ i ≤ n)n − i0(表尾)n − 1(表头)(n − 1) / 2
按值查找比较 i 次1n(n + 1) / 2
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1 || L.length == MaxSize) return false;
    for (int j = L.length; j >= i; j--)   // 从后往前,把 i…n 后移一位
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;                      // 位序 i 对应下标 i−1
    L.length++;
    return true;
}
  • 插入时元素要从后往前移,删除时从前往后移,否则会覆盖。
  • “位序”从 1 开始,数组下标从 0 开始,题目里要分清。
03
2.3 · 对比

顺序表 vs 链表

★★★☆☆ 中频 选择题
对比顺序表链表
存取方式随机存取 O(1)顺序存取 O(n)
插入删除平均移动一半元素 O(n)修改指针 O(1)(找位置 O(n))
空间需预先分配连续空间;存储密度 = 1按需分配,不需连续;有指针开销
适合表长稳定、频繁按序号查找表长变化大、频繁插删
04
2.4 · 算法题

线性表算法题:思路与模板

★★★★★ 必考 综合题

算法设计题的评分一般是:设计思想(3–4 分)+ 代码(7–8 分)+ 复杂度(2 分)。写不出最优解时,写出正确的暴力解通常也能拿到大部分分数——不要空着。

  1. 设计思想:用 2–4 句话说清“怎么做”和“为什么对”。
  2. 代码:C/C++ 皆可,关键处写注释;给出函数头和用到的结构体定义。
  3. 复杂度:时间、空间各一句。

历年线性表算法题一览

年份题意最优思路时间 / 空间
2009单链表倒数第 k 个结点双指针:先让快指针走 k 步,再快慢同步走,快指针到表尾时慢指针即所求O(n) / O(1)
2010数组循环左移 p 位三次逆置:逆置前 p 个、逆置后 n−p 个、再整体逆置O(n) / O(1)
2011两个等长升序序列的中位数比较两序列中位数 a、b:相等即答案;a < b 则舍弃 A 的较小半与 B 的较大半,递归O(log n) / O(1)
2012两个单词链表的共同后缀起点先求两表长度,长表先走差值步,然后同步走,第一个相同地址的结点O(m + n) / O(1)
2013找数组的主元素(出现 > n/2 次)摩尔投票:候选 c、计数 count,相同 +1 不同 −1,减到 0 换候选;最后再数一遍确认O(n) / O(1)
2015删除链表中绝对值重复的结点(|data| ≤ n)开辅助数组 flag[n+1] 标记出现过的绝对值,再次出现就删O(m) / O(n)
2016把集合分成两半使元素个数差最小、和之差最大基于快排划分找第 ⌊n/2⌋ 小元素平均 O(n) / O(1)
2018数组中未出现的最小正整数辅助数组 B[1..n] 标记 1~n 中出现过的数,第一个未标记的下标即答案O(n) / O(n)
2019链表重排为 a₁, aₙ, a₂, aₙ₋₁, …快慢指针找中点 → 逆置后半段 → 两段交替合并O(n) / O(1)
2020三个升序数组中三元组的最小距离三指针,每次让当前最小值的指针后移,同时更新最小距离O(n) / O(1)

三个必须能默写的小算法

原地逆置数组 a[l..r]
void Reverse(int a[], int l, int r) {
    while (l < r) {
        int t = a[l]; a[l] = a[r]; a[r] = t;
        l++; r--;
    }
}
单链表逆置(头插法,带头结点)
void ReverseList(LinkList L) {
    LNode *p = L->next, *r;
    L->next = NULL;
    while (p) {
        r = p->next;          // 先记住后继
        p->next = L->next;    // 头插
        L->next = p;
        p = r;
    }
}
快慢指针找中间结点
LNode *slow = L->next, *fast = L->next;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow 指向中间(偶数个时为后半段第一个)
合并两个有序表
while (i < m && j < n)
    C[k++] = A[i] <= B[j] ? A[i++] : B[j++];
while (i < m) C[k++] = A[i++];
while (j < n) C[k++] = B[j++];
05
实战

真题与自测

★★★★☆ 收口 选择 + 算法题

一、真题问法

问法 1:“在长度为 n 的顺序表第 i 个位置插入元素,需后移几个元素?”→ n − i + 1。

问法 2:“某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用哪种存储最节省运算时间?”→ 仅有尾指针的单循环链表。

问法 3(算法题):见上表;高频套路是双指针、逆置、辅助数组标记、摩尔投票。

二、折叠自测

1. 顺序表第 1 个元素地址为 100,每个元素 4 字节,第 5 个元素的地址?

100 + (5 − 1) × 4 = 116。

2. 在单链表 p 结点之后插入 s,正确的语句顺序?

s->next = p->next; p->next = s;

3. 为什么要设头结点?

使在第一个位置插入删除的操作与其他位置一致;空表与非空表处理一致。

4. 长度为 n 的单链表,已知尾指针,删除尾结点的时间复杂度?

O(n):需要找到尾结点的前驱,单链表只能从头遍历。

5. 静态链表中的“指针”是什么?

下一个元素在数组中的下标(游标)。

6. 数组循环左移 p 位,如何做到 O(1) 空间?

三次逆置:Reverse(0, p−1)、Reverse(p, n−1)、Reverse(0, n−1)。

三、考前速览

3 句话

顺序表随机存取,插删移动一半。
链表先连新链,再断旧链。
算法题:思想 + 代码 + 复杂度。

3 个易错

① 插入从后往前移,删除从前往后移。
② 单链表删尾结点是 O(n)。
③ 位序从 1、下标从 0。