线性表

主要参考《数据结构 第 2 章 线性表》课件。页码均采用原课件 PDF 页序；伪代码采用 C 风格，位序从 1 开始、数组下标从 0 开始，单链表默认带头结点。接口示意中的 `&e` 表示把变量地址传给输出参数，函数定义一律写成 `ElemType *e`，全章不使用 C++ 引用、`new`/`delete` 或模板。文中的静态推演不依赖交互组件，可直接阅读。

1. 本章定位：从线性结构到线性表

对应课件第 1–5 页。

线性表是“一对一”关系的抽象。课件先用银行排队、击鼓传花、信息核对等日常场景说明：许多问题中的对象都排成一个有先后次序的序列。把这类共同点抽取出来，就得到线性结构：对非空表而言，除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继；第一个元素没有前驱，最后一个元素没有后继。空表没有首元素和尾元素，但仍是合法的线性表，“唯一首/尾”的说法只对非空表成立。

本章的学习目标可以概括为四件事（课件第 2 页）：理解线性表的逻辑特征；掌握用抽象数据类型（ADT）描述线性表的方法；掌握顺序存储和链式存储两种实现及其基本操作；能分析操作的时间复杂度，并根据问题特点选择存储结构。

课件第 5 页进一步说明，线性表中的元素可以是简单值，如成绩表里的整数；也可以是记录，如学生信息，记录由若干数据项组成。无论元素内部多复杂，只要在表中占据一个位置，并与其他元素构成前后关系，它就是一个表元素。由此也可看出，表的“元素类型”必须统一，通常记作 ElemType。元素类型不同，比较、赋值和存储的具体方式不同，但线性表的逻辑框架不变。

学习路线是：先建立 ADT（2.2），再分别研究顺序表（2.3）与链式表（2.4），然后用三个应用检验结构选择（2.5），最后归纳方法与常见错误（2.6）。

2. 线性表的定义与 ADT 数据模型

对应课件第 6–8 页。

课件给出的定义是：线性表是由 n 个类型相同的数据元素构成的有限序列，记作

L = (a₁, a₂, …, aₙ)。

其中 n 称为表长；n=0 时是空表；n>0 时，a₁ 是表头元素，aₙ 是表尾元素；aᵢ 的前驱是 aᵢ₋₁，后继是 aᵢ₊₁。i 是元素在表中的位序，取值从 1 到 n。位置是相对的：同一个值若出现两次，它仍占据两个不同的位序；改变元素的先后次序，就得到不同的线性表。

用 ADT 描述时，数据对象和关系分别是（课件第 8 页）：

D = {aᵢ | aᵢ ∈ ElemSet, i = 1, 2, …, n, n ≥ 0}

R = {<aᵢ₋₁, aᵢ> | i = 2, 3, …, n}

这两行看起来抽象，实际规定了三件事：元素取自同一集合；元素之间只有相邻的前驱—后继关系；表长可以为 0。空表时 D 为空集，R 也为空，仍是一个合法的线性表。

需要区分“线性表”和“集合”。线性表强调次序，(1,2,3) 与 (3,2,1) 不同；线性表也允许元素值重复，例如 (3,3,5) 是合法的。这里的“次序”指元素在表中的位置关系，并不表示元素按值升序排列；是否按关键字有序是额外前提，后文的有序合并优化会明确依赖它。因此，后文说“集合差”时，只是借用集合运算的语义来出题，底层数据仍是线性表，重复元素的处理必须另行约定。

ADT 的意义在于把逻辑结构与存储实现分开：定义只说明“有哪些元素、元素之间是什么关系、允许哪些操作”，不规定元素放在数组里还是结点里。同一个 ADT 可以有多种实现，不同实现的运行效率不同，但都必须满足同样的前置条件与后置结果。

3. 三类基本操作与统一约定

对应课件第 9–12 页。

课件把基本操作分成三类，这个分类比逐个背函数名更重要：

销毁与清空不是一回事。 课件用宿舍作类比：DestroyList 相当于退掉宿舍并交还钥匙，之后表不能直接使用；ClearList 只是把住户清空、房间仍然保留，表还是那张表，只是 length 变成 0。因此销毁通常要释放动态内存并把指针置空，清空只需把长度置 0。把两者混用，轻则内存泄漏，重则继续访问已释放的空间。

位序与值也是两套坐标。 课件第 10 页用“房间号”和“住户”作类比：GetElem(L, i, &e) 按房间号找人；LocateElem(L, e) 按人找房间号；PriorElem 和 NextElem 找的是相邻房间里的元素。按位序访问必须先检查位置是否合法，因为房间号只能落在 1 到表长之间。

加工型操作会改变表长和元素位置（课件第 12 页）。在第 i 个位置插入时，原来的第 i 到第 n 个元素依次后移一位，表长加一；删除第 i 个元素时，原来的第 i+1 到第 n 个元素依次前移一位，表长减一。由此得到两条不能忘的合法范围：插入位置 1 ≤ i ≤ n+1，删除位置 1 ≤ i ≤ n。插入可以到 n+1，是因为可以追加在表尾；删除没有第 n+1 个元素，所以 i=n+1 非法。

4. 例 2.1：用 ADT 设计集合差

对应课件第 13–17 页。

课件用一个旅游清单问题引出 ADT 的用法：La 是小文去过的城市，Lb 是小明去过的城市，要求列出小明去过而小文没去过的城市，存入 Lc。从集合观点看，Lc = Lb − (La ∩ Lb)，也就是 Lb − La：保留属于 Lb 而不属于 La 的城市，方向和被减数不能写反。难点不在于集合公式，而在于只允许使用线性表的基本操作时，如何把公式翻译成算法。

课件给出的思路是：依次取出 Lb 的每个元素，用 LocateElem(La, e) 判断它是否在 La 中；若返回 0 表示不存在，就把 e 插入 Lc 的表尾。插入位置是当前表长加一。用顺序表作为存储载体可写成（后面会看到，换成链表时若仍按下标逐个取元素，代价会变化，需要改用游标遍历）：

Status FindNewCity(SeqList La, SeqList Lb, SeqList *Lc) {
    ElemType e;
    int i, pos;

    if (InitList(Lc) != OK)
        return OVERFLOW;

    for (i = 1; i <= ListLength(Lb); i++) {
        GetElem(Lb, i, &e);            /* 取出 Lb 的第 i 个元素 */
        pos = LocateElem(La, e);       /* 0 表示 La 中不存在该元素 */
        if (pos == 0)
            InsertElem(Lc, ListLength(*Lc) + 1, e);  /* 追加到 Lc 表尾 */
    }
    return OK;
}

这段算法的核心是“枚举 + 查找 + 追加”。它只调用 ADT 接口，不关心 La、Lb、Lc 是数组还是链表，这正体现了抽象数据类型分离逻辑与实现的价值。LocateElem 返回 0 而不是某个下标，是因为合法的位序从 1 开始，0 可以安全地充当“未找到”的哨兵。

逐步演算一个例子。设 La = (南京, 苏州)，Lb = (苏州, 杭州, 黄山, 苏州)：

注意最后得到的 Lc 并不总像数学集合差那样“去重”：若 Lb 中某个值出现了两次，而它不在 La 中，两次都会被保留。线性表允许重复，所以把“集合差”直接套到线性表上时，必须约定是按值去重，还是按出现次数处理。课件例题默认每个城市只出现一次，这个前提不能忽略。

时间复杂度取决于 LocateElem。外层循环执行 m = |Lb| 次，每次在 La 中顺序查找平均要比较 O(n) 次，因此总时间为 O(nm)，即 O(|La| × |Lb|)。这里的时间以顺序表为存储载体：GetElem(Lb, i, &e) 按下标直接取元素是 O(1)，LocateElem(La, e) 是顺序扫描 O(n)，ListLength 也是 O(1)。若换成单链表却仍用 GetElem(Lb, i, &e) 按位序取元素，每次都要从头走 i 步，仅取出 Lb 全部元素就要 Σi = O(m²)，再乘查找代价，总时间不再是 O(nm)；链表版必须改成沿 Lb 的 next 指针顺序游标遍历、逐结点处理，才能保持相同的量级。因此“算法结构不变”只在抽象层面的枚举—查找—追加上成立，具体到存储结构，取元素方式必须随实现调整；ListLength 为 O(1) 只是必要条件之一。课件第 17 页进一步指出，若 La、Lb 已经按城市编号升序排列，可以用两个指针边走边比，每个元素最多扫描一次，时间降为 O(|La| + |Lb|)。这个结论以“输入已经有序”为前提，不含排序预处理的时间；若原表无序，要先排序，排序本身通常需要 O(n log n) 量级，不能把总代价仍写成 O(n+m)。这说明：算法的复杂度不仅取决于 ADT 操作，还取决于数据是否有序等额外前提。有序链表的实现将在第 20 节展开。

5. 顺序表：连续存储与地址公式

对应课件第 18–21 页。

顺序表用一段连续的存储单元依次存放线性表的元素，通常借助一维数组实现。因为第 i 个元素和第 i+1 个元素在内存中相邻，所以逻辑上的相邻关系与物理位置完全一致。课件第 20 页列出四个特点：元素顺序存放、可随机访问、容量可在编译期或运行期分配、表容量受数组空间约束。

随机访问来自地址公式：

Loc(aᵢ) = Loc(a₁) + (i − 1) × c，其中 c = sizeof(ElemType)。

基址加上偏移量就能直接算出第 i 个元素的地址，不需要从头遍历，所以 GetElem 的时间复杂度是 O(1)。这个结论有明确的成立条件：元素必须等长、存储必须连续、基址必须已知。如果元素是变长记录，或数据分散在链式结点中，公式就不成立，只能顺序查找。

最容易出错的是把位序直接当下标用。第 i 个元素的数组下标是 i-1：取第 1 个元素用 data[0]，取第 n 个用 data[n-1]。做插入删除时，循环变量 j 若表示下标，范围也随之下移一位。位序与下标的转换是本章后续所有边界错误的源头，建议每次写循环前先标出“这是第几个”和“这是哪个下标”。

合法位序是 1 ≤ i ≤ n。i<1 或 i>n 都属于越界访问，必须返回错误而不是读取数组；空表时任何按位访问都不合法。

6. 静态存储与动态存储

对应课件第 22–24 页。

顺序表有两种容量管理方式。静态存储在结构中直接放数组，容量由宏 MAXSIZE 在编译期确定：

#define MAXSIZE 256
typedef struct {
    ElemType data[MAXSIZE];
    int length;
} SeqFixedList;

动态存储则只放一个指向堆区数组的指针，再记录当前表长 length 和容量 size：

#define LISTINITSIZE 256
#define LISTINCREMENT 128
typedef struct {
    ElemType *pData;
    int length;
    int size;
} SeqList;

两者都用 length 表示实际元素个数，但动态结构多了一个 size。length 是“现在住了多少人”，size 是“房间最多能住多少人”，必须始终满足 0 ≤ length ≤ size。初始化时通常申请 LISTINITSIZE 个元素的空间；插入时若 length >= size，用 realloc 再扩 LISTINCREMENT 个元素的空间。

课件后续统一采用动态存储，因为它能较自然地处理表长增长。但扩容不是免费的：realloc 可能把整块数据搬到新地址，并把原有元素复制过去，当次代价是 O(n)；如果扩容后旧地址失效，之前保存的指向数组内部的指针也会变成悬空指针。严谨的工程写法还会先把 realloc 的返回值存入临时指针，确认非空后再赋给 pData，避免申请失败时丢失原数组。课件的 exit(OVERFLOW) 是教学伪代码的处理方式，表示“内存不足，程序终止”。

7. 顺序表的生命周期：初始化、销毁与清空

对应课件第 25–27 页。

三个整体操作分别对应“建立”“释放”“清空”：

Status InitList(SeqList *L) {
    L->pData = (ElemType *)malloc(LISTINITSIZE * sizeof(ElemType));
    if (L->pData == NULL)
        exit(OVERFLOW);
    L->size = LISTINITSIZE;
    L->length = 0;
    return OK;
}

Status DestroyList(SeqList *L) {
    free(L->pData);          /* 归还堆区空间 */
    L->pData = NULL;         /* 防止悬空指针 */
    L->size = 0;
    L->length = 0;
    return OK;
}

Status ClearList(SeqList *L) {
    L->length = 0;           /* 只清空逻辑内容，保留存储空间 */
    return OK;
}

初始化的关键在失败检查：malloc 可能返回空指针，不能直接解引用。销毁的关键在 free 之后置空：堆区空间已经交还，继续用 pData 访问就是未定义行为；把指针置为 NULL、容量和表长清零，可以防止误用。清空只改 length，原来的元素值可能还留在内存里，但它们已经不属于这张表，任何按位访问都应被 length 拦住。

边界情况：对空表执行 ClearList 是允许的，结果仍是空表；对已销毁的表执行任何操作都违反前置条件；重复销毁需要额外保护（例如先判断指针是否为空），不能假设 free 能修复所有状态。清空后 size 不变，后续插入仍可复用原有容量。

8. 顺序表的按位取值与按值查找

对应课件第 28–29 页。

按位取值直接利用地址公式：

Status GetElem(SeqList L, int i, ElemType *e) {
    if (i < 1 || i > L.length)
        return PARA_ERROR;
    *e = L.pData[i - 1];
    return OK;
}

参数 i 是位序，所以访问下标 i-1。先判合法性再取元素，任何越界都不会发生。时间复杂度 O(1)，与表长无关。

按值查找则需要从头比较：

int LocateElem(SeqList L, ElemType e) {
    int i;
    for (i = 0; i < L.length; i++) {
        if (L.pData[i] == e)
            return i + 1;     /* 返回位序，不是下标 */
    }
    return 0;                 /* 0 表示未找到 */
}

若找到，返回的是位序 i+1；若没找到，返回 0。返回 0 而不是返回下标，是为了让“未找到”与合法位序区分开。若表中有重复值，这个循环返回第一次出现的位置；若业务需要最后一次或全部位置，必须改写循环或另行收集。

复杂度：最好情况第 1 个就命中，比较 1 次；最坏情况比较 n 次；若每个位置等概率出现且元素一定存在，平均比较 (n+1)/2 次；若元素可能不存在，还要算上扫描完整表的 n 次。无论哪种，都是 O(n)。这里的成立条件是单次比较为 O(1)；若元素是长字符串或复杂记录，比较本身可能不止常数时间，需要按实际比较代价分析。对记录类型，通常只比较能唯一标识记录的关键字，而不是逐字段比较整个结构。

9. 顺序表插入：合法范围、扩容与移动方向

对应课件第 30–33 页。

顺序表插入要同时处理三件事：位置是否合法、容量是否足够、元素如何后移。算法如下：

Status InsertElem(SeqList *L, int i, ElemType e) {
    int j;
    if (i < 1 || i > L->length + 1)
        return PARA_ERROR;                 /* 只能插在第 1 到 n+1 位 */

    if (L->length >= L->size) {            /* 先确保有空位 */
        ElemType *p = (ElemType *)realloc(
            L->pData, (L->size + LISTINCREMENT) * sizeof(ElemType));
        if (p == NULL)
            exit(OVERFLOW);
        L->pData = p;
        L->size += LISTINCREMENT;
    }

    for (j = L->length - 1; j >= i - 1; j--)
        L->pData[j + 1] = L->pData[j];     /* 从后往前移，腾出下标 i-1 */

    L->pData[i - 1] = e;
    L->length++;
    return OK;
}

执行顺序不能随意调换：先检查参数，再保证容量，然后移动，最后写入并增加表长。移动必须从后往前：第 n 个先移到第 n+1 个位置，第 n-1 个再移到第 n 个位置，依此类推，直到把第 i 个位置空出来。如果从前往后移，刚写过去的值会覆盖尚未移动的源元素，造成数据丢失。

把课件第 32–33 页的例子逐步展开。原表 [12, 35, 20, 48, 7]，length = 5，在下标 3（逻辑第 4 位）插入 20：

线性表允许重复值，所以结果中两个 20 都是合法元素，不能误以为发生了覆盖错误。移动次数为 (n-1)-(i-1)+1 = n-i+1：插在表尾 i=n+1 时移动 0 次，插在表头 i=1 时移动 n 次。最好 O(1)、最坏 O(n)，平均 O(n)。

10. 顺序表删除：覆盖方向与平均移动次数

对应课件第 34–36 页。

删除要先把被删元素保存到输出参数，再把它后面的元素逐个前移覆盖：

Status DeleteElem(SeqList *L, int i, ElemType *e) {
    int j;
    if (i < 1 || i > L->length)
        return PARA_ERROR;              /* 只能删第 1 到 n 位 */

    *e = L->pData[i - 1];               /* 先保存，否则被覆盖后取不回 */
    for (j = i; j <= L->length - 1; j++)
        L->pData[j - 1] = L->pData[j];  /* 从前往后依次左移 */

    L->length--;
    return OK;
}

循环从下标 i（被删元素的后一个）开始，依次赋值给前一个位置，直到下标 n-1。移动次数是 (n-1)-i+1 = n-i：删除表尾 i=n 时移动 0 次，删除表头 i=1 时移动 n-1 次。若先 length-- 再移动，循环上界会提前缩小，最后一个元素搬不过来；若先移动再保存 e，被删元素已被覆盖，输出参数就错了。

课件第 35 页的例子：[12, 35, 20, 48, 7] 删除逻辑第 2 位（下标 1）的 35。

下标 4 的 7 是残留值，已超出 length，不属于线性表。访问表中元素必须以 0..length-1 为界，不能看到数组里还有值就当作有效数据。

删除前移必须从前往后做。若从后往前，先执行 data[j-1] = data[j] 会把后面的源值提前覆盖，下一步再读 data[j-1] 时拿到的已不是原值，数据会连锁丢失。

在等概率假设下，可以算出平均移动次数（AMN）。课件把插入位置取为 1,…,n+1（含表尾追加），共 n+1 个位置，移动次数为 n-i+1，故

AMN_insert = (1/(n+1)) · Σ(i=1..n+1) (n−i+1) = n/2。

删除位置只能取 1,…,n，移动次数为 n-i，故

AMN_delete = (1/n) · Σ(i=1..n) (n−i) = (n−1)/2。

两者都是 O(n)。这里的“平均”依赖等概率假设；若实际总是在表尾操作，代价接近 O(1)。若插入只在已有的 n 个位序中等概率选位（不统计追加），平均移动为 (n+1)/2，量级仍是 O(n)。推导时必须先交代位置集合，否则 n/2 与 (n+1)/2 的差别会被误当成矛盾。

11. 顺序表的复杂度边界与适用场景

对应课件第 36–37 页。

把顺序表的主要操作汇总如下（n 为表长）：

顺序表的优点：结构简单，只需一段连续空间；按位访问快；存储密度高，不需要为每个元素额外保存指针；若表有序，还可以用二分查找把按值查找降到 O(log n)（这是课件第 62 页选择场景提到的优势，链式结构不具备）。

缺点也同样明确：插入删除要成批移动元素；容量固定，或者扩容时整块复制；动态扩容后旧地址可能失效。因此它适合表长相对稳定、频繁按位读取、插入删除较少的问题；如果插入删除集中在表尾，且能预估容量，顺序表往往比链表更简单高效。反之，若经常在表头或中间插入删除，或表长变化很大，就应考虑链式存储。

12. 链式存储的基本思想与结点结构

对应课件第 38–41 页。

顺序表的插入删除之所以慢，是因为元素必须连续存放，插入删除会引发整段移动；容量固定则来自数组上界的约束。链式存储换了一个思路：元素不必相邻，每个元素单独申请一个结点，结点中除了数据，还保存下一个结点的地址。逻辑上的“后继”由指针表达，物理位置可以任意分散。

单链表结点定义为：

typedef struct LNode {
    ElemType data;          /* 数据域 */
    struct LNode *next;     /* 指针域，指向直接后继 */
} LNode, *LinkList;

struct LNode 在定义内部引用自己，必须写 struct LNode *，不能只写 LNode *。LinkList 是指向结点的指针类型，习惯上用它表示“链表的头指针”。最后一个结点的 next 为 NULL，表示没有后继；空链表则没有任何数据结点。

课件第 41 页概括了链式存储的五个特点：物理位置不一定相邻，逻辑关系由指针表示；结点按需申请，较易扩展；只能从头顺序访问，不能随机访问；插入删除通过修改指针完成；每个结点需要额外的指针空间。这里的“插入删除快”有严格前提：已经定位到插入位置的前驱（或当前结点），并且只讨论链接操作本身。如果还要从头找第 i 个结点，查找仍是 O(n)，总时间不会低于 O(n)。这是后文反复强调的复杂度成立条件。

13. 带头结点的单链表与辅助信息

对应课件第 42–44 页。

单链表可以只用一个头指针表示，也可以额外分配一个头结点。头结点不存放用户元素，它的 next 指向第一个数据结点。课件采用带头结点的约定，并给出包含辅助信息的结构：

typedef struct {
    LinkList head;      /* 指向头结点，头结点不存数据 */
    LinkList tail;      /* 指向最后一个数据结点，空表时指向头结点 */
    LNode *pCurNode;    /* 当前操作位置，作为遍历或局部操作的游标 */
    int length;         /* 数据结点个数，不含头结点 */
} SListInfo;

四个成员各有用途：head 是链表的入口；tail 让表尾插入不必从头遍历；pCurNode 记录当前结点，配合“在当前结点之后插入/删除”的操作；length 让取表长、判空等操作不必遍历。课件第 43 页把这种做法概括为“以空间换时间”：多存几个辅助信息，换取操作上的便利，但辅助信息必须及时更新，否则会变成错误线索。

初始化算法 2.9：

Status InitList(SListInfo *L) {
    L->head = (LNode *)malloc(sizeof(LNode));
    if (L->head == NULL)
        exit(OVERFLOW);
    L->head->next = NULL;
    L->tail = L->head;
    L->pCurNode = L->head;
    L->length = 0;
    return OK;
}

头结点让“空表”有了统一的表示：head 始终非空，空表条件是 head->next == NULL；tail 和 pCurNode 都指向 head。更重要的是，第一个数据结点也有前驱（头结点），因此“在表头插入”“删除第一个结点”不再需要特殊修改头指针，可以和其他位置用同一套指针操作处理。

不变量可以写成四句话：头结点的 next 指向第一个数据结点；tail 指向最后一个数据结点（空表时等于 head）；pCurNode 指向某个已知结点，且必须与当前算法约定一致；length 等于数据结点个数。插入、删除、遍历后都要检查这些不变量，尤其是 tail 和 length。

14. 单链表的按位访问与遍历

对应课件第 45 页。

单链表没有地址公式，取第 i 个元素只能从第一个数据结点开始，沿 next 走 i-1 步：

Status GetElem(SListInfo *L, int i, ElemType *e) {
    int j = 1;
    LNode *p;

    if (i < 1 || i > L->length)
        return PARA_ERROR;

    p = L->head->next;          /* 第一个数据结点，位序 1 */
    while (j < i) {
        p = p->next;
        j++;
    }
    *e = p->data;
    L->pCurNode = p;            /* 记录当前位置，便于后续局部操作 */
    return OK;
}

循环执行 i-1 次，因此时间复杂度是 O(i)，最坏为 O(n)；最好情况取第 1 个元素，是 O(1)。与顺序表的 GetElem 对比：同样的“取第 i 个”操作，顺序表 O(1)，单链表 O(n)。这不是实现技巧的差异，而是存储方式决定的：顺序表能算地址，单链表只能沿链走。

边界检查依赖 length 正确。若 length 没有维护好，参数检查可能放行一个不存在的位序，循环随后访问 NULL 而崩溃。因此“维护 length”不是可选优化，而是这些操作正确性的前提。取到元素后把 pCurNode 更新为 p，是为了让后续“在当前结点之后插入/删除”可以直接使用，不必再次定位。

15. 单链表插入：两行赋值的顺序与尾指针维护

对应课件第 46–47、51 页。

课件把插入设计为“在 pCurNode 之后插入”这一局部操作。只要游标已经指向目标前驱，插入本身只改两个指针：

Status InsertElemAfterCurNode(SListInfo *L, ElemType e) {
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
        exit(OVERFLOW);

    s->data = e;
    s->next = L->pCurNode->next;    /* ① 先让 s 接住原来的后继 */
    L->pCurNode->next = s;          /* ② 再让前驱指向 s */

    if (L->tail == L->pCurNode)     /* 若原来在表尾之后插入 */
        L->tail = s;
    L->length++;
    return OK;
}

顺序不能交换。若先执行 L->pCurNode->next = s，前驱原来的后继地址就丢失了；再执行 s->next = L->pCurNode->next，读到的已经是 s 自己，于是 s->next = s，新结点自指，原后继及其后的整段链表全部丢失。课件第 51 页专门用图示提醒这个错误。

用具体链表演示。设 head → A → B，pCurNode 指向 A，插入 X：

若 A 是尾结点，原 A->next == NULL，步骤 1 得到 s->next = NULL，步骤 2 后 tail 必须改为 s，否则 tail 仍指向 A，尾插等操作就会出错。若 A 是头结点（空表或表头插入），上述代码同样成立：s 成为第一个数据结点，若原表为空，tail 从 head 改为 s。

给定 pCurNode 时，插入是 O(1)；若目标位置只知道“第 i 位”，还需要先遍历到第 i-1 个结点，总时间为 O(n)。另外，插入不需要移动已有元素，这是相对顺序表的核心优势；代价是每个结点多一个指针域，以及一次动态申请。

16. 单链表删除：先重新链接，再释放结点

对应课件第 48–49、52 页。

与插入对称，课件把删除设计为“删除 pCurNode 的后继”：

Status DeleteElemAfterCurNode(SListInfo *L, ElemType *e) {
    LNode *p;

    if (L->pCurNode->next == NULL)      /* 后面没有结点 */
        return DELE_FAIL;

    p = L->pCurNode->next;
    *e = p->data;                       /* 先保存被删元素 */
    L->pCurNode->next = p->next;        /* 重新链接，摘掉 p */
    if (L->pCurNode->next == NULL)      /* 删的是最后一个数据结点 */
        L->tail = L->pCurNode;
    free(p);                            /* 链接完成后再释放 */
    L->length--;
    return OK;
}

操作顺序是“保存值 → 改链 → 更新尾指针 → 释放”。free 必须放在改链之后：如果先 free(p)，p->next 以及 p->data 都不应再访问，后续重新链接就成了使用已释放内存的未定义行为；即使某些环境“碰巧”还能读到值，也不能依赖。改链完成后，p 已从链表摘下，此时释放它不会影响链表。

具体演示：head → A → B → C，pCurNode 指向 A，删除 A 的后继 B。执行 p = A->next（B），保存 e = B.data，令 A->next = B->next（C），此时链序为 head → A → C；B 已脱链，再 free(B)。若 C 不存在（B 是尾结点），删除后 A->next == NULL，尾指针改为 A。

边界情况：pCurNode 本身是尾结点时，pCurNode->next == NULL，没有可删结点，返回 DELE_FAIL；空表时 pCurNode 是头结点，同样没有后继；若删除的是唯一的数据结点，删除后 head->next == NULL，tail 回到 head，length 变为 0。给定前驱时删除是 O(1)，但若只知道“删除第 i 个”，仍需从头找第 i-1 个，总时间为 O(n)。

17. 单链表性能与顺序表的选择

对应课件第 50、61–63 页。

把两种存储放在同一张表中比较，才能看清“谁更快”到底依赖什么：

表中的“已知位置”必须分清含义。对顺序表，已知逻辑位置 i 仍要移动 n-i+1 或 n-i 个元素；对单链表，只知道逻辑位置 i 还不够，仍要从头走到第 i-1 个结点，只有已知前驱结点（或游标已经停在那里）时，改指针才是 O(1)。因此不能把“链表插入删除 O(1)”无条件套到“按第 i 位插入删除”上。课件第 50 页强调的“与顺序表最好最坏情况正好相反”，指的也是这个精确定位前提。

选择结构时先看操作组合，而不是只看表长：若经常按位读取、很少插删、表长可预估，选顺序表；若经常在表头或中间插删、表长变化大、不需要随机访问，选链表。若表有序且需要频繁查找，顺序表还能用二分查找，链表则不能。实际工程中还可以组合结构，或给链表增加 tail、length 等辅助信息来优化特定操作。

课件第 63 页总结了六类常见错误，值得逐条对照：

1. 顺序表插入时从前向后移动，覆盖尚未搬走的数据。
2. 链表插入时先改前驱的 next，丢失原后继。
3. 链表删除时先 free 再改链，访问已释放内存。
4. 把逻辑位序与数组下标混用，边界差一。
5. 忘记维护 tail、pCurNode、length，辅助信息失真。
6. 混淆 DestroyList 与 ClearList，造成悬空访问或内存泄漏。

18. 双向链表：四指针插入与两指针删除

对应课件第 53–56 页。

单链表只能沿 next 向后走，要找某结点的前驱必须从头再来。双向链表给每个结点增加 prev 指针，使前后两个方向都能在 O(1) 内到达：

typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prev;
    struct DuLNode *next;
} DuLNode, *DuLinkList;

为了与单链表的 SListInfo 对称，本讲义把入口与辅助信息组织成如下结构；head 指向头结点，头结点的 next 指向第一个数据结点，tail 指向最后一个数据结点，空表时二者是同一个头结点，length 只数数据结点：

typedef struct {
    DuLinkList head;
    DuLNode *tail;
    DuLNode *pCurNode;
    int length;
} DuListInfo;

本讲义约定前插/前删只对数据结点调用，头结点的 prev 不参与这些操作；因此本节的普通双向链表维护 next 与 prev 两个方向的线性链接（不构成环），只是不把 head->prev 当作尾指针使用；循环形式留到第 19 节讨论。在 pCurNode 之前插入 s，需要同时维护四条链接（课件算法 2.14）：

Status InsertElemBeforeCurNode(DuListInfo *L, ElemType e) {
    DuLNode *s = (DuLNode *)malloc(sizeof(DuLNode));
    if (s == NULL)
        exit(OVERFLOW);

    s->data = e;
    s->prev = L->pCurNode->prev;        /* ① s 的前驱 */
    L->pCurNode->prev->next = s;        /* ② 原前驱的后继改为 s */
    s->next = L->pCurNode;              /* ③ s 的后继 */
    L->pCurNode->prev = s;              /* ④ 当前结点的前驱改为 s */
    L->length++;
    return OK;
}

四步完成后的局部关系是：原前驱 → s，s → 当前结点，s 的 prev 指原前驱，当前结点的 prev 指 s。若当前结点是第一个数据结点，它的 prev 是头结点，插入后 s 成为第一个数据结点，头结点的 next 随之更新，不需要额外分支。

删除 pCurNode 的前驱（课件算法 2.15）：

Status DeleteElemBeforeCurNode(DuListInfo *L, ElemType *e) {
    DuLNode *p;

    if (L->pCurNode->prev == L->head)   /* 前面是头结点，没有数据结点 */
        return DELE_FAIL;

    p = L->pCurNode->prev;
    *e = p->data;
    p->prev->next = L->pCurNode;        /* 前驱的前驱越过 p */
    L->pCurNode->prev = p->prev;        /* 当前结点回指 */
    free(p);
    L->length--;
    return OK;
}

双向链表的主要优势是前后插删对称：已知当前结点时，在它之前或之后插入、删除都是 O(1)，且不需要再找前驱。代价是每个结点多一个指针，插入删除要维护的链接更多，任何一处漏改都会破坏双向一致性。课件第 56 页的删除条件 pCurNode->prev == head 只覆盖“当前结点是第一个数据结点”的情况；实现时还应约定当前结点不能是头结点本身，否则它的 prev 无有效数据域，需显式拒绝。本讲义约定这类操作的 pCurNode 指向数据结点，头结点的 prev 不参与前插/前删。

19. 循环链表、双向循环链表与静态链表

对应课件第 57–60 页。

单链表的尾结点 next 为 NULL；循环链表把尾结点的 next 改为指向头结点，使整条链形成环。带头结点的循环单链表空表条件是 head->next == head，而不是 NULL。课件给出 CircListInfo，只需 head、pCurNode、length 三个成员，不再需要 tail：

typedef struct {
    LinkList head;      /* 指向头结点 */
    LNode *pCurNode;    /* 当前数据结点 */
    int length;         /* 数据结点个数 */
} CircListInfo;

从任一结点出发都能走遍全表，表尾就是“next 回到 head 之前的那个结点”。遍历的终止条件也随之改变，不能再用 p != NULL，而要在回到 head 时停止。

循环结构适合本身具有周期性的问题，例如约瑟夫环、轮转调度。它的优点是尾到头衔接自然，从任意位置都能继续遍历；缺点是稍不注意就会死循环，所有“找尾”“判空”“遍历”的终止条件都必须重写。

双向循环链表同时维护两个环：尾结点的 next 指向头结点，头结点的 prev 指向尾结点。它是四种链式形式中最灵活的一种：已知任一结点，前后移动、插入、删除都方便；但每个结点有两个指针，边界维护最复杂，空间开销也最大。

静态链表用数组模拟链表：每个数组元素存 data 和一个整数 next，用下标代替指针：

typedef struct {
    ElemType data;
    int next;       /* 下一个结点的数组下标；本讲义约定 -1 表示空指针 */
} SLinkNode;

静态链表通常维护两条链：一条是数据链，按逻辑顺序链接有效元素；另一条是空闲链，把所有未使用的位置串起来。插入时从空闲链摘下一个结点，接到数据链的指定位置；删除时把结点从数据链摘下，再挂回空闲链。它不需要指针和动态内存，适合不支持动态分配或需要固定内存布局的环境；代价是容量固定、空闲空间要手工管理，插入删除的“指针”操作变成了下标修改，边界同样容易出错。

20. 应用一：有序单链表的集合差

对应课件第 64–68 页。

课件第 66 页把例 2.1 落到单链表，并增加一个关键前提：La、Lb 都已按城市编号 cityNo 升序排列，输出仍是 Lb − La。结点元素类型包含编号和城市名：

typedef struct {
    int cityNo;
    char cityName[48];
} ElemType;

有序带来一个重要的算法机会：不必对每个 Lb 元素都在 La 中从头查找。两个指针分别沿 La、Lb 前进，La 的指针只会在“当前编号小于待比较编号”时后移，因此 La 最多扫描一遍，Lb 也最多扫描一遍。用带游标的单链表实现（课件算法 2.16）：

Status FindNewCity(SListInfo La, SListInfo Lb, SListInfo *Lc) {
    ElemType bi;

    if (InitList(Lc) != OK)
        return OVERFLOW;
    if (Lb.head->next == NULL)
        return LIST_EMPTY;

    La.pCurNode = La.head->next;        /* 结构体按值传递，游标是副本 */
    Lb.pCurNode = Lb.head->next;
    Lc->pCurNode = Lc->head;            /* Lc 从头结点开始尾插 */

    while (Lb.pCurNode != NULL) {
        bi = Lb.pCurNode->data;

        while (La.pCurNode != NULL &&
               La.pCurNode->data.cityNo < bi.cityNo)
            La.pCurNode = La.pCurNode->next;

        if (La.pCurNode != NULL &&
            La.pCurNode->data.cityNo == bi.cityNo) {
            La.pCurNode = La.pCurNode->next;   /* 小文去过，跳过 */
        } else {
            InsertElemAfterCurNode(Lc, bi);    /* 接在 Lc 尾部 */
            Lc->pCurNode = Lc->pCurNode->next;
        }
        Lb.pCurNode = Lb.pCurNode->next;
    }
    return OK;
}

La、Lb 按值传入，函数拿到的是结构体副本，但副本中的 head 仍指向同一批结点；移动副本里的 pCurNode 不会改动调用者的游标。Lc 通过指针传入，插入后把头结点或新尾结点作为游标，保证下一次仍能在表尾追加。

逐步演算。设 La 的城市编号为 (1, 3, 5)，Lb 为 (2, 3, 4, 6)：

每个指针只向前走，La 走 O(|La|) 步，Lb 走 O(|Lb|) 步，插入借助 pCurNode 是 O(1)，总时间复杂度 O(|La| + |Lb|)，空间除输出链表外为 O(1)。对照第 4 节的 O(|La| × |Lb|)，差距来自两个前提：数据有序和用游标顺序推进。没有有序前提，双指针无法保证不回退。

边界与前提：Lb 为空时返回 LIST_EMPTY；La 为空时，第一个 while 不执行，Lc 复制 Lb 的全部元素；某个表先耗尽时，另一表的剩余部分继续按规则处理。算法默认同一表中的 cityNo 不重复。若允许重复，双指针的推进方式会使“集合差”的语义变得含糊：例如 La = (1)、Lb = (1, 1)，第一个 1 消耗掉 La 的唯一匹配后，第二个 1 会被当作“新城市”插入。因此要么先明确去重，要么把问题定义成多重集差，并在比较与推进逻辑中显式处理计数。

21. 应用二：输入法词频调整（双向链表）

对应课件第 69–71 页。

输入法常把常用词排在前面。一种实现是把词条按使用频度从高到低组织成双向链表；每输入一个词，频度加一，然后把它向前移动到合适位置，使链表仍保持频度降序。元素类型为：

typedef struct {
    char word[48];
    int freq;
} ElemType;

课件算法 2.17 的步骤是：查找词条；频度加一；若前驱频度已经不小于它，位置不变；否则把结点摘下，向前越过所有频度更小的结点，再插回。摘取与插回都需要修改前驱和后继，这正是双向链表擅长的操作。用本讲义统一的 DuListInfo（含 head、tail、pCurNode、length）写出：

Status Locate(DuListInfo *L, const char word[], ElemType *found) {
    DuLNode *p = L->head->next;
    DuLNode *q;

    while (p != NULL && strcmp(p->data.word, word) != 0)
        p = p->next;
    if (p == NULL)
        return FAILURE;                 /* 词条不存在 */

    p->data.freq++;
    *found = p->data;
    q = p->prev;
    if (q == L->head || q->data.freq >= p->data.freq)
        return OK;                      /* 仍在前驱之后，无需移动 */

    /* 从链表中摘下 p */
    q->next = p->next;
    if (p->next != NULL)
        p->next->prev = q;
    else
        L->tail = q;

    /* 向前找插入位置：q 为 head 或频度不小于 p 时停止 */
    while (q != L->head && q->data.freq < p->data.freq)
        q = q->prev;

    /* 把 p 插回 q 之后 */
    p->next = q->next;
    q->next = p;
    p->prev = q;
    if (p->next != NULL)
        p->next->prev = p;
    else
        L->tail = p;

    return OK;
}

为什么只向前移动、且一旦前驱频度不小于它就停止？操作前链表按频度降序；只有 p 的频度增加了 1，可能破坏的顺序关系只发生在 p 与它前面的结点之间。向前越过所有频度严格小于 p 的结点，停在频度不小于 p 的结点之后，局部有序即可恢复。对频度相等的结点不再越过，可以保持它们原来的相对次序，避免每次查询都无谓地重排。

例子：链表为 数据结构:3 → 算法:3 → 网络:1，输入“算法”后频度变为 4。摘下算法后，q 指向数据结构，频度 3 小于 4，继续向前到 head；把算法插在 head 之后，得到 算法:4 → 数据结构:3 → 网络:1。若输入的是“网络”，频度从 1 变 2，前驱算法频度 3 不小于 2，位置不变。

课件代码在判断 q->data.freq >= p->data.freq 时，q 可能已经是头结点；头结点的 data 域并不存放有效词频。本讲义在读取前先判断 q == L->head，把“已经到表头”作为停止条件，这是对边界的安全化处理。对于不存在的词，课件算法返回 FAILURE；真实输入法可以另行决定“插入新词、频度置 1”的策略，这属于应用层扩展，不改变上述移动逻辑。

下面把“频度加一、向前移动、摘链、插回”四个动作放进一条完整的静态时间线。初始链表按频度降序为 数据结构:3 → 算法:2 → 网络:1（只画数据结点，头结点在 数据结构 之前）：

这张表对应三类关键判断。第一，是否需要移动只看前驱：q->freq >= p->freq 时，p 已处在合法位置；相等也不越过，因而同频词条的原有先后次序得以保留。第二，摘下结点要区分三种位置：尾结点要更新 tail（第二行），中间结点要同时维护前后两个方向（第三行），表头结点没有前驱可断（本组没有出现）。第三，插回位置是 head 或第一个频度不小于 p 的结点之后；插入后若 p->next != NULL，还要让后继的 prev 指回 p，只有插在末尾才需要改 tail。

以第二行为例核对指针：摘下前 算法->next = 网络、网络->prev = 算法；摘下时先让 算法->next = 网络->next = NULL，再令 tail = 算法。此时 网络 已脱离链表，但仍保留旧的前驱指针，插回时会被重新赋值。找到插入点 数据结构 后，执行 网络->next = 数据结构->next（算法）、数据结构->next = 网络、网络->prev = 数据结构、算法->prev = 网络。四个方向全部接好，才能继续下一次查找。

复杂度：查找词条 O(n)；最坏情况下结点要一路移到表头，摘链与插链本身是 O(1)，移动过程沿 prev 走 O(n) 步，因此总时间 O(n)，额外空间 O(1)。若用单链表，找前驱又要 O(n)，移动时无法高效回退，这正是选择双向链表的原因。

22. 应用三：约瑟夫环

对应课件第 72–74 页。

约瑟夫问题：n 个人围成一圈，从某人开始报数，报到 m 的人出列，再由下一个人从 1 重新报数，直到所有人出列。用循环链表模拟最自然：每个人是一个结点，尾结点指向头结点形成环，报数就是沿 next 走，出列就是删除当前结点。

课件算法 2.18 使用带头结点的循环单链表，头结点不参与报数。用本讲义约定重写为：

Status Josephus(CircListInfo *L, int m, void (*visit)(ElemType)) {
    LNode *pre, *p;

    if (m < 1)
        return PARA_ERROR;
    if (L->head->next == L->head)
        return LIST_EMPTY;

    pre = L->head;
    p = L->head->next;                  /* p 是当前报 1 的人 */

    while (L->head->next != L->head) {  /* 还有数据结点 */
        for (int i = 1; i < m; i++) {   /* 当前算第 1 个，再走 m−1 步 */
            pre = p;
            p = p->next;
            if (p == L->head) {         /* 头结点不报数，跳过 */
                pre = p;
                p = p->next;
            }
        }
        visit(p->data);                 /* 报到 m，输出并出列 */
        pre->next = p->next;
        free(p);
        L->length--;

        p = pre->next;
        if (p == L->head) {             /* 下一个仍可能是头结点 */
            pre = p;
            p = p->next;
        }
    }
    return OK;
}

关键在“当前结点算第 1 个”。若 m=3，从 1 开始，报数序列是 1、2、3，循环只需再走 m-1=2 步。走到头结点时必须跳过，因为它不是人；跳过时把 pre 设为头结点，保证删除当前结点时 pre 正好是它的前驱。删除后从 pre->next 继续，如果又遇到头结点，同样跳过。

以 n=5、m=3 为例，初始环为 head → 1 → 2 → 3 → 4 → 5 → head：

出列顺序为 3, 1, 5, 2, 4。注意每轮“当前”是上一轮出列者的后继：3 出列后从 4 报 1；1 出列后从 2 报 1；依此类推。例如 n=7、m=3 时，出列顺序为 3, 6, 2, 7, 5, 1, 4，最后剩下（最后出列）的是 4 号；这与 n=5 的例子使用同一条规则，只是规模不同。

复杂度：每出列一人需要沿链走 O(m) 步（m 可能跨越多个剩余结点），共 n 人，总时间 O(nm)；结点数为 n，空间 O(n)。边界：n=0 返回 LIST_EMPTY；n=1 时无论 m 多大，最后只剩一人，出列一次；m=1 时每轮删除当前结点，相当于按当前顺序逐个出列；m<1 在本讲义中视为非法参数。若不带头结点，则空表条件、尾结点判断和删除首结点的处理都要改写，这也从反面说明头结点带来的统一性。

23. 本章小结：结构对照、公式与设计方法

对应课件第 75–80 页。

本章的主线可以画成：逻辑结构（线性关系）→ ADT（数据对象、关系、操作）→ 存储实现（顺序/链式）→ 应用算法（集合差、词频、约瑟夫）。同一套 ADT 操作在不同存储下代价不同，算法设计时必须把“操作组合”和“数据前提”一起考虑。

四种链式形式的对照：

核心公式与结论速查：

课件第 80 页给出算法设计的一般思路：先选逻辑结构与存储结构；再用 ADT 基本操作描述算法，不急于陷入指针细节；然后针对所选存储把操作落实为具体代码；最后分析复杂度，寻找利用有序性、辅助指针或辅助信息优化的机会。这个顺序能避免“一上来就写指针，写到一半才发现结构选错”。

复习时还应检查四条约定：位序从 1 起、下标从 0 起；单链表头结点不计入表长；空链表与空循环链表的判断条件不同；已知位置与已知结点是两种不同的前提。把这四条与第 17 节的六类错误对照，基本可以覆盖本章的易错点。

24. 习题选讲：逆置、判环、倒数第 k 与归并

对应课件第 81–88 页。

课件第 81 页列出五个指针练习，下面给出关键实现，重点看边界与辅助信息维护。

（1）原地逆置。 依次摘下原链表结点，头插到头结点之后。逆置后原首结点变成尾结点，所以第一个插入的结点要赋给 tail；循环前必须把 head->next 置空，否则旧链会污染新链。

void ReverseList(SListInfo *L) {
    LNode *p = L->head->next;
    LNode *q;

    L->head->next = NULL;
    L->tail = L->head;
    while (p != NULL) {
        q = p->next;                /* 先记住原后继 */
        p->next = L->head->next;    /* 头插 */
        L->head->next = p;
        if (L->tail == L->head)     /* 第一个被插入的结点将成为尾 */
            L->tail = p;
        p = q;
    }
    L->pCurNode = L->head;
}

时间 O(n)，空间 O(1)。空表时循环不执行，tail 仍为 head；只有一个结点时它既是首又是尾。

（2）判环。 快指针每次走两步，慢指针走一步；两者相遇则有环，快指针遇到 NULL 则无环。解引用前必须先检查 fast 与 fast->next 非空。时间 O(n)，空间 O(1)。

int HasCycle(SListInfo *L) {
    LNode *slow = L->head->next;
    LNode *fast = L->head->next;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1;
    }
    return 0;
}

（3）倒数第 k 个。 前指针先走 k 步，后指针从头结点出发，再与前指针同步前进；前指针到 NULL 时，后指针的下一结点就是倒数第 k 个。k<1 或 k>n 非法；k=n 时前指针走满 k 步恰为 NULL，仍合法。若不用 length 判 n，可在走步时判断是否提前遇到 NULL。

（4）合并两个有序链表。 比较两表当前结点，把较小者接到 Lc 尾部；一表耗尽后整体接上另一表剩余段。每个结点只访问一次，时间 O(|La|+|Lb|)，最少比较 min(|La|,|Lb|) 次。下面的代码假设 ElemType 可直接用 <= 比较；若元素是记录，应改为比较关键字。

Status MergeList(SListInfo La, SListInfo Lb, SListInfo *Lc) {
    if (InitList(Lc) != OK) return OVERFLOW;
    La.pCurNode = La.head->next;
    Lb.pCurNode = Lb.head->next;
    Lc->pCurNode = Lc->head;
    while (La.pCurNode != NULL && Lb.pCurNode != NULL) {
        if (La.pCurNode->data <= Lb.pCurNode->data) {
            InsertElemAfterCurNode(Lc, La.pCurNode->data);
            La.pCurNode = La.pCurNode->next;
        } else {
            InsertElemAfterCurNode(Lc, Lb.pCurNode->data);
            Lb.pCurNode = Lb.pCurNode->next;
        }
        Lc->pCurNode = Lc->pCurNode->next;
    }
    while (La.pCurNode != NULL) {
        InsertElemAfterCurNode(Lc, La.pCurNode->data);
        Lc->pCurNode = Lc->pCurNode->next;
        La.pCurNode = La.pCurNode->next;
    }
    while (Lb.pCurNode != NULL) {
        InsertElemAfterCurNode(Lc, Lb.pCurNode->data);
        Lc->pCurNode = Lc->pCurNode->next;
        Lb.pCurNode = Lb.pCurNode->next;
    }
    return OK;
}

以上实现用 InsertElemAfterCurNode，每次插入后要把 Lc 的游标后移；若直接重接原结点可省去复制数据、空间降为 O(1)，但会改变输入表。

（5）删除有序表重复元素。 p 指向当前保留结点，q = p->next；若关键字相同则删除 q，否则 p = q。时间 O(n)，空间 O(1)，删除后同步更新 length 与 tail。

课堂练习速查（第 82–85 页）：

第 86 页编程练习与第 87–88 页项目（快递驿站、进程统计）都是本章操作的组合：取件对应查找与删除，进程增减对应头插、尾插与双向摘链。第 86 页还给出区间删除、集合交/并/差、一元多项式相加与求导等题：区间删除训练连续区间的批量移动，集合题复用双表归并，多项式题把“同类项合并”落成有序表的合并与系数处理，仍以本章基本操作为积木。动手前先画清前驱、当前结点和必须同步的辅助信息，再补空表、表头、表尾、容量不足等测试。

25. 延伸：链表的历史、应用与进阶主题

对应课件第 89–94 页。

链表的思想与早期存储设备有关：在顺序访问的存储介质上，让数据块携带下一块的地址，可以不必依赖物理相邻来组织逻辑关系。20 世纪 50—60 年代，表处理语言与编译器的实践推动了链接表示的发展，环形链表、双向链表等变体也在此期间被讨论和使用；Knuth 在《计算机程序设计艺术》中系统整理了顺序表示与链接表示。具体人物、年份与优先权细节可查阅课件第 89–94 页列出的文献，本讲义不展开考据。

今天链表广泛用于操作系统（进程控制块、空闲内存块、设备队列）、编译器（符号表与作用域）、数据库（缓冲区、日志）、图形学（场景图）、浏览器（前进/后退历史）和播放器（播放列表）。LRU 缓存是“哈希表 + 双向链表”的经典组合：哈希表负责 O(1) 定位，双向链表把刚访问的结点移到表头并淘汰表尾。

进阶结构包括跳表（多层索引，查找期望 O(log n)，注意是概率意义而非最坏保证）、哈希链表、惰性链表和内存池。它们保留了“用链接表示关系”的核心，只在查找效率、空间管理或计算时机上扩展。课件第 94 页列出参考文献，可作为沿历史脉络继续阅读的线索；第 95 页为结束页。

参考来源与学习要求

课件页序对照：线性结构与 ADT 第 1–17 页；顺序表第 18–37 页；单链表、双向链表、循环链表与静态链表第 38–63 页；三个应用第 64–74 页；小结、习题与项目第 75–88 页；历史、应用与进阶第 89–93 页、参考文献第 94 页、结束页第 95 页。课件第 71 页的词频算法在 q 可能为头结点时直接读 q->data.freq，本讲义改为先判 q == head；第 73–74 页的约瑟夫算法以“当前结点报 1”为约定，本讲义保留该约定并补充 m < 1 的参数检查。

学完本章，应能：用自己的话定义线性表及其 ADT；区分位序与数组下标；写出顺序表与带头结点单链表的初始化、取值、查找、插入、删除；解释顺序表插删的平均移动次数及等概率前提；说明链表 O(1) 插删的成立条件；根据操作组合选择存储结构；独立完成逆置、判环、合并、去重等练习，并检查空表、表头、表尾、容量不足等边界。