# 第二章：线性表学习笔记

本笔记依据《数据结构 第 2 章 线性表》课件整理，页码均指原课件 PDF 页序，可配合[第二章讲义](/数据结构/线性表/)使用。全文统一约定：**位序从 1 开始，数组下标从 0 开始；单链表带头结点，头结点不计入表长；伪代码采用 C 风格**；接口示意中的 `&e` 表示输出参数，函数定义写成 `ElemType *e`，不使用 C++ 引用。

## 1. 线性表的定义与 ADT

来源：课件第 1–12 页。

线性表是由 n 个**类型相同**的数据元素构成的有限序列，记作 L=(a₁,a₂,…,aₙ)。n 为表长，n=0 时是空表。n>0 时，a₁ 是表头元素，aₙ 是表尾元素；aᵢ 的直接前驱是 aᵢ₋₁，直接后继是 aᵢ₊₁。除首尾外，每个元素有且仅有一个前驱和一个后继，这就是“一对一”的线性结构。

线性表允许元素值重复，也强调次序：(1,2,3) 与 (3,2,1) 是两张不同的表。这里的次序是位置关系，并不表示元素已按值升序排列；有序只是后续应用中的额外前提。元素可以是整数，也可以是由若干数据项组成的记录；元素内部多复杂，都不改变它在表中的位置关系。

ADT 把逻辑结构与存储实现分开。数据对象和关系可写成：

- `D = {aᵢ | aᵢ ∈ ElemSet, i=1..n, n≥0}`
- `R = {<aᵢ₋₁, aᵢ> | i=2..n}`

基本操作分三类：**整体管理**（InitList、DestroyList、ClearList）、**访问型**（ListEmpty、ListLength、GetElem、LocateElem、PriorElem、NextElem、ListTraverse）、**加工型**（SetElem、InsertElem、DeleteElem）。其中 `DestroyList` 释放存储，之后不能直接使用；`ClearList` 只把表清空，存储仍保留，二者不能混用。插入位置合法范围是 1≤i≤n+1，删除是 1≤i≤n。

ADT 的价值不在于多写一个接口，而在于先固定“允许做什么、结果是什么”，再自由替换存储实现。同一个 `GetElem`，在顺序表中 O(1)，在链表中 O(n)，但调用者只依赖 ADT 语义，算法主干不必改。位序和值还是两套坐标：`GetElem(L,i,&e)` 按房间号找人，`LocateElem(L,e)` 按人找房间号，`PriorElem`、`NextElem` 则按值找相邻元素。顺序表在已知下标时可直接算出前驱、后继；若按值调用，仍要先花 O(n) 定位。单链表中即使已知某个结点，找它的前驱也必须从头再走一遍，这正是后面引入双向链表的动机之一。

## 2. 顺序表：地址公式与基本操作

来源：课件第 18–37 页。

顺序表用一段连续空间依次存放元素，逻辑相邻与物理相邻一致。若每个元素占 c 字节，则

`Loc(aᵢ) = Loc(a₁) + (i−1) × c`，

第 i 个元素存放在下标 i−1 处。这个公式成立需要三个条件：元素等长、存储连续、基址已知；满足时 `GetElem` 为 O(1)，即随机访问。

动态顺序表常用如下结构，本章后续操作都基于它：

```c
#define LISTINITSIZE 256
#define LISTINCREMENT 128
typedef struct {
    ElemType *pData;
    int length;      /* 当前元素个数 */
    int size;        /* 当前容量 */
} SeqList;
```

`length` 与 `size` 必须满足 0≤length≤size。插入前若 `length >= size`，要先扩容；扩容可能搬移整块数据，当次代价为 O(n)。

静态顺序表把数组直接放进结构体，容量由 `MAXSIZE` 在编译期确定：`typedef struct { ElemType data[MAXSIZE]; int length; } SeqFixedList;`。它实现简单、没有额外指针，但表满即溢出；动态表能按需扩容，代价是 `realloc` 可能整块复制并要处理申请失败。表长有可靠上界时用静态表，表长难预估或需长期增长时用动态表，这是“容量确定”与“灵活扩展”的交换。

插入的关键是**从后往前**移动，删除的关键是**从前往后**覆盖：

```c
/* 在下标 i-1 处插入 e；参数 i 是位序 */
for (j = L->length - 1; j >= i - 1; j--)
    L->pData[j + 1] = L->pData[j];
L->pData[i - 1] = e;
L->length++;

/* 删除位序 i 的元素，先保存再前移 */
*e = L->pData[i - 1];
for (j = i; j <= L->length - 1; j++)
    L->pData[j - 1] = L->pData[j];
L->length--;
```

插入移动次数为 n−i+1，删除为 n−i。若各位置等概率，插入按 n+1 个位置（含表尾追加）平均移动 **n/2** 次；删除按 n 个位置平均移动 **(n−1)/2** 次。两者都是 O(n)，但表尾插删可以是 O(1)。平均结论依赖“等概率”和“只计元素移动”两个前提，写推导时要说明。

例：`[12,35,20,48,7]` 的第 4 位插入 20，先移 7、再移 48，结果为 `[12,35,20,20,48,7]`；删除第 2 位的 35，依次把 20、48、7 左移，逻辑内容变为 `[12,20,48,7]`。删除前必须先保存被删值，否则它会被后继覆盖。

## 3. 单链表：带头结点与指针操作

来源：课件第 38–52 页。

单链表结点由数据域和指针域组成：

```c
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
```

本章结构把入口和辅助信息放在一起：

```c
typedef struct {
    LinkList head;     /* 指向头结点 */
    LinkList tail;     /* 指向最后一个数据结点 */
    LNode *pCurNode;   /* 当前游标 */
    int length;        /* 数据结点个数 */
} SListInfo;
```

头结点不存用户数据，第一个数据结点是 `head->next`。**空表条件为 `head->next == NULL`**，此时 `tail == head`、`pCurNode == head`、`length == 0`。头结点的价值在于让表头插入、删除首结点也有统一前驱，不必单独改头指针。

按位取第 i 个元素要从第一个数据结点沿 `next` 走 i−1 步，时间 O(i)，最坏 O(n)；这是链式存储失去随机访问的直接后果。已知前驱（或游标）时，插入只需两步：

```c
s->next = L->pCurNode->next;   /* ① 先接住原后继 */
L->pCurNode->next = s;         /* ② 再让前驱指向 s */
if (L->tail == L->pCurNode) L->tail = s;
L->length++;
```

顺序不可颠倒。若先改前驱的 `next`，原后继地址就丢了，再执行第一步会得到 `s->next = s` 的自环，原后继及其后结点全部不可达。删除则是“保存值 → 改链 → 更新 tail → 释放”：

```c
p = L->pCurNode->next;
*e = p->data;
L->pCurNode->next = p->next;
if (L->pCurNode->next == NULL) L->tail = L->pCurNode;
free(p);
L->length--;
```

不能先 `free(p)` 再读 `p->next`，那属于访问已释放内存，行为不确定。给定前驱时插删是 O(1)；若只知道“第 i 位”，仍要 O(n) 找前驱，总时间 O(n)。

## 4. 双向链表、循环链表与静态链表

来源：课件第 53–60 页。

双向链表结点增加 `prev` 指针，可在 O(1) 内前后移动。在 `pCurNode` 之前插入 s 要维护四条链接：

```c
s->prev = cur->prev;
cur->prev->next = s;
s->next = cur;
cur->prev = s;
```

删除 `pCurNode` 的前驱时，若 `pCurNode->prev == head`，说明前面没有数据结点，返回失败；否则令 `p->prev->next = pCurNode; pCurNode->prev = p->prev;` 后释放 p。双向链表适合需要频繁前后移动或删除已知结点前驱的场景，代价是每个结点多一个指针域。

循环单链表把尾结点的 `next` 指回头结点，空表条件是 `head->next == head`，遍历时不能用 `p != NULL`，而要以“回到 head”为终止。它适合约瑟夫环、轮转调度等环状问题。双向循环链表把首尾两个方向都接成环，最灵活，边界维护也最复杂。静态链表用数组下标代替指针，元素含 `data` 与 `next`（本笔记约定 −1 表示空），并维护数据链和空闲链，适合不能动态分配内存的环境。

## 5. 结构选择与常见错误

来源：课件第 50、61–63 页。

| 操作              | 顺序表           | 带头结点单链表 |
| ----------------- | ---------------- | -------------- |
| 按位取第 i 个     | O(1)             | O(n)           |
| 按值查找          | O(n)             | O(n)           |
| 已知前驱插入/删除 | O(n)（移动元素） | O(1)（改指针） |
| 表长变化          | 固定或扩容复制   | 按需申请、释放 |
| 额外空间          | 可能预留空位     | 每结点一个指针 |

选择依据是操作组合：频繁按位读取、表长稳定、需要二分查找时选顺序表；频繁在表头或中间插删、表长变化大、不需要随机访问时选链表。注意“链表插删 O(1)”只在**已定位前驱**时成立；按位插删仍是 O(n)。

常见错误有六类：顺序表插入从前向后移动，覆盖未搬走的数据；链表插入先改前驱 `next`，丢失后继；删除先 `free` 再改链；位序与下标混用；忘记维护 `tail`、`pCurNode`、`length`；混淆 `DestroyList` 与 `ClearList`。

## 6. 典型应用

来源：课件第 64–74 页。

**有序集合差。** 两链表按 cityNo 升序，要求 Lc=Lb−La。用两个游标分别扫 La、Lb：若 La 当前编号小于 bi，La 后移；相等则跳过；否则把 bi 尾插 Lc。每个指针只前进，时间 O(|La|+|Lb|)，空间 O(1)（不计输出）。若无序，则每个 Lb 元素都要在 La 中查找，退化为 O(|La|×|Lb|)。这里的 O(|La|+|Lb|) 以“沿 `next` 顺序推进的游标”为前提；若用按位 `GetElem` 逐个取出 Lb 元素，取出成本为 Σi=O(m²)，总时间不再是 O(n+m)。顺序表存储时按位 `GetElem` 是 O(1)，但 `ListLength` 为 O(1) 也只是必要条件之一。前提是两表按同一关键字有序，且重复元素的语义已约定。

**输入法词频调整。** 词条按频度降序存放在双向链表中；查到时频度加一，若前驱频度已经不小于它就不动，否则摘下结点，沿 `prev` 越过所有频度更小的结点后插回。查找 O(n)，移动最多 O(n)，总时间 O(n)。用双向链表是因为摘下和插回都要同时改前驱、后继。

**约瑟夫环。** n 人围成环，从当前人报 1，报到 m 出列。用带头结点的循环链表，头结点不报数；每轮走 m−1 步（当前算第 1 个），跳过 head，删除当前结点并输出。n=5、m=3 的出列顺序为 `3,1,5,2,4`；例如 n=7、m=3 时为 `3,6,2,7,5,1,4`，最后剩下 4 号。每轮 O(m)，共 n 轮，时间 O(nm)，空间 O(n)。

## 7. 自测与答案

来源：课件第 81–88 页；题目依据课后思考题与课堂练习改编。

**题 1：** 长度 n=8 的顺序表，删除第 1 个与删除第 8 个各移动多少次？在第 1 位与第 9 位插入各移动多少次？

答：删除第 1 个移动 n−1=7 次，删除第 8 个移动 0 次；第 1 位插入移动 n=8 次，第 9 位（表尾追加）移动 0 次。可见 O(n) 是最坏与平均结论，边界位置可能 O(1)。

**题 2：** 单链表在 `pCurNode` 之后插入 s，为什么必须先执行 `s->next = pCurNode->next`？

答：第一步保存原后继，第二步才能安全地把前驱改为 s。若先执行 `pCurNode->next = s`，原后继地址丢失，再读 `pCurNode->next` 得到的是 s 自己，会形成自环并丢掉后续结点。

**题 3：** 带头结点循环单链表如何判空？约瑟夫算法为什么在报数时要跳过 head？

答：空表条件为 `head->next == head`。head 是头结点，不是参与者；报数只数数据结点，遇到 head 必须跳过，否则人数和报数都会错。删除时还要保证 `pre` 始终是当前结点的前驱，这样 `pre->next = p->next` 才能正确摘链。