主题
字号
CHAPTER 02 ≈ 54 MIN READ

线性表、栈、队列与串数组

线性表是这门课第一个正式的数据结构，也是后面栈、队列、串的基础。它最简单，但「顺序实现 vs 链式实现」这套对比的思维方式，会在后面每一章重演。务必把这一章当成模板吃透。

2.1 什么是线性表

线性表是 n 个类型相同的数据元素排成的有限有序序列，记作 (a₁, a₂, ..., aₙ)。

把这个定义拆开理解：

线性表的「线性」体现在元素间的关系上：除了第一个元素没有前驱、最后一个元素没有后继，中间每个元素都恰好有一个直接前驱和一个直接后继。这就是典型的「1 对 1」线性结构。生活中的例子到处都是：一队排队的人、一串糖葫芦、字母表 A-Z。

线性表的基本操作（ADT，理解即可）：初始化、求长度、按位置取元素、按值查找、插入、删除、判空、遍历。下面我们分别用「顺序存储」和「链式存储」把这些操作实现出来——这正是本章的核心。

2.2 顺序表（线性表的顺序存储实现）

2.2.1 思想

顺序表就是用一个数组把线性表的元素挨个连续地存起来。逻辑上相邻（a₁ 挨着 a₂），物理上也相邻（数组里下标相邻）。这是最朴素、最直接的实现。

2.2.2 结构定义

#define MAXSIZE 100          // 顺序表最大容量(预先定好)
typedef int ElemType;        // 元素类型,本课约定先用 int

typedef struct {
    ElemType data[MAXSIZE];  // 存元素的数组,这就是那块"连续内存"
    int length;              // 当前实际有多少个元素(注意:不是数组容量,是实际长度)
} SqList;                    // SqList = Sequence List 顺序表

这里有个极其重要、初学者必栽的坑：length（表里实际有几个元素）和 MAXSIZE（数组最多能装几个）是两码事。数组开了 100 个格子不代表里面有 100 个元素。length 才是「这张表现在有几个元素」。

另一个关键约定：教材通常约定逻辑位序从 1 开始（第 1 个元素、第 2 个元素……），但数组下标从 0 开始。所以「第 i 个元素」存在 data[i-1]。这个「位序 i ↔ 下标 i-1」的换算，是顺序表所有代码 bug 的高发区，时刻警惕。

2.2.3 随机访问为什么是 O(1)

取第 i 个元素，直接 return L.data[i-1];，一步到位。底层是 地址 = 首地址 + (i-1) × 每个元素大小，一次乘加算出地址直接取，和表有多长完全无关。这就是顺序表最大的优点：随机访问 O(1)。

2.2.4 插入操作（核心，必考移动次数）

要在第 i 个位置插入一个新元素 e，意味着原来第 i 个及它后面的元素，都得集体往后挪一格给新元素腾位子。注意一个反直觉的细节：挪动必须从后往前进行，否则会把后面的数据覆盖掉。

// 在顺序表 L 的第 i 个位置插入元素 e。成功返回 1,失败返回 0。
// 注意第一个参数是 SqList *L (指针!) ——因为我们要修改 L 的内容(length 会变),
// 必须传地址进来(回顾 0.6 节:想改外面的东西就传地址)
int ListInsert(SqList *L, int i, ElemType e) {
    // 1. 合法性检查
    if (i < 1 || i > L->length + 1)      // 插入位置必须在 [1, length+1] 之间
        return 0;                         // (可以插在末尾的下一个位置,所以是 length+1)
    if (L->length >= MAXSIZE)            // 表满了,插不下
        return 0;

    // 2. 从最后一个元素开始,逐个往后挪,直到第 i 个位置
    //    位序 i 对应下标 i-1;最后一个元素下标是 length-1
    for (int j = L->length - 1; j >= i - 1; j--) {
        L->data[j + 1] = L->data[j];     // 把第 j 格的内容搬到第 j+1 格
    }

    // 3. 此时下标 i-1 的位置空出来了,放入新元素
    L->data[i - 1] = e;

    // 4. 表长加 1
    L->length++;
    return 1;
}

复杂度分析（高频考点）：插入的代价主要在「挪动元素」。

记牢这个结论：顺序表插入平均移动 n/2 个元素。删除是 (n-1)/2，见下。

2.2.5 删除操作

删除第 i 个元素，则它后面的元素都要往前挪一格填补空缺。这次要从前往后挪。

// 删除顺序表 L 的第 i 个元素,被删的值通过指针 e 带回去给调用者
int ListDelete(SqList *L, int i, ElemType *e) {
    if (i < 1 || i > L->length)        // 删除位置必须在 [1, length] 之间
        return 0;                       // (注意上界是 length,不是 length+1)

    *e = L->data[i - 1];               // 先把要删的元素值保存出来(通过指针带回)

    // 从第 i+1 个元素开始,逐个往前挪
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];   // 把第 j 格搬到第 j-1 格
    }

    L->length--;                       // 表长减 1
    return 1;
}

复杂度：删表尾不用挪 O(1)；删表头要挪 n-1 个 O(n)；平均移动 (n-1)/2 个元素，平均 O(n)。

2.2.6 顺序表小结

2.3 单链表（线性表的链式存储实现）

2.3.1 思想：用指针把散落的节点串起来

顺序表的痛点是「插入删除要挪一堆元素」。链表换了个思路：元素不再连续存放，而是每个元素单独打包成一个「节点」，节点里除了存数据，还额外存一个指针指向下一个节点。这样所有节点像一串珠子，靠指针线串在一起，散落在内存各处也没关系。

这样做的好处立竿见影：插入/删除只需要改几个指针，完全不用挪动其它元素。代价是：想找第 k 个元素，必须从头顺着指针一个个数过去，失去了随机访问。这正是 1.8 节说的权衡——链表用「访问慢」换来了「增删快」。

2.3.2 节点结构定义

typedef int ElemType;

typedef struct LNode {
    ElemType      data;   // 数据域:存这个节点的值
    struct LNode *next;   // 指针域:存"下一个节点"的地址。注意类型是指向自己这种结构的指针
} LNode, *LinkList;       // 两个别名:
                          //   LNode    = struct LNode      (强调这是一个"节点")
                          //   LinkList = struct LNode *    (强调这是"指向节点的指针",常用作整个链表的头)

这里有个让初学者懵的点：结构体内部怎么能有一个「指向自己这种结构的指针」？因为指针只是个地址（大小固定），编译器完全能处理。注意这里必须写完整的 struct LNode *next，不能用还没定义完的别名。

LNode 和 LinkList 本质是同一个东西的两个名字，区别只在表达意图：用 LNode *p 强调「p 是一个节点指针」，用 LinkList L 强调「L 是一整条链表（的头指针）」。这是教材的惯用约定，跟着用就行。

2.3.3 头指针、头结点、首元结点（极易混，务必分清）

这三个名词长得像，含义不同，是单链表第一个大坑：

为什么要费力加一个不存数据的头结点？ 因为它能让代码统一、不用特判。没有头结点时，「在第一个位置插入/删除」要特殊处理（得改头指针本身）；有了头结点，第一个位置就和其它位置一模一样了（都是「改前一个节点的 next」），代码干净很多。本课默认都用「带头结点」的单链表，下面代码全部基于此。

带头结点的空表长这样：头指针 → [头结点|next=NULL]，即头结点的 next 是 NULL。判断空表就是看 L->next == NULL。

2.3.4 建立链表：头插法与尾插法

头插法：每个新节点都插在头结点后面（结果逆序）

// 头插法建表:依次读入 n 个数据,每个都插到头结点之后
// 结果链表的顺序和读入顺序"相反"(最后读入的在最前面)
LinkList CreateListHead(int n) {
    LinkList L = (LinkList)malloc(sizeof(LNode));  // 1. 创建头结点
    L->next = NULL;                                 //    初始为空表

    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));  // 2. 为新数据创建一个节点 s
        scanf("%d", &s->data);                      //    读入数据
        s->next = L->next;                          // 3. 关键两步(顺序不能反!):
                                                    //    新节点的 next 先接上原来的第一个节点
        L->next = s;                                // 4. 头结点再指向新节点 s
    }                                               //    于是 s 成了新的"第一个节点"
    return L;
}

理解第 3、4 步为什么不能交换：必须先让新节点接住后面的链，再让头结点指向新节点。如果先做第 4 步（L->next = s），就把原来 L->next 的值（指向原第一个节点的地址）覆盖丢了，后面的链全断了。「先接后断」是链表操作的铁律，画图就一目了然。

尾插法：每个新节点都接到链表尾巴（结果顺序）

// 尾插法建表:每个新节点接到当前链表的末尾,结果顺序和读入顺序一致
LinkList CreateListTail(int n) {
    LinkList L = (LinkList)malloc(sizeof(LNode));  // 头结点
    L->next = NULL;
    LNode *tail = L;                                // tail 始终指向"当前最后一个节点",初始就是头结点

    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &s->data);
        s->next = NULL;                            // 新节点将成为最后一个,它的 next 是 NULL
        tail->next = s;                            // 把它接到当前尾巴后面
        tail = s;                                  // 更新 tail,让它指向新的尾巴
    }
    return L;
}

尾插法多用了一个 tail 指针来记住尾巴，省得每次插入都从头找到尾（否则每次插入都是 O(n)，建 n 个就 O(n²)）。有了 tail，每次插入 O(1)，建表整体 O(n)。

2.3.5 按位置查找（O(n)，链表的软肋）

// 返回单链表 L 中第 i 个节点的指针;找不到返回 NULL
// (带头结点:头结点算第 0 个,第 1 个数据节点是 L->next)
LNode *GetElem(LinkList L, int i) {
    if (i < 1) return NULL;
    LNode *p = L;          // p 从头结点出发
    int j = 0;             // j 是 p 当前所在的位置编号(头结点是 0)
    while (p != NULL && j < i) {
        p = p->next;       // 往后走一步
        j++;
    }
    return p;              // 走了 i 步后,p 指向第 i 个节点(若中途到 NULL 则返回 NULL)
}

注意这就是链表的根本弱点：要找第 i 个元素，只能从头一步步走 i 步，O(n)，没有捷径。这和顺序表的 O(1) 随机访问形成鲜明对比。

2.3.6 插入操作（核心，体会「改指针」）

要在第 i 个位置插入新节点，关键是先找到第 i-1 个节点（即插入位置的前驱），然后改两个指针。

// 在带头结点单链表 L 的第 i 个位置插入元素 e
int ListInsert(LinkList L, int i, ElemType e) {
    LNode *p = GetElem(L, i - 1);     // 1. 找到第 i-1 个节点(前驱)。注意是 i-1!
    if (p == NULL) return 0;          //    前驱不存在,位置非法

    LNode *s = (LNode *)malloc(sizeof(LNode));  // 2. 创建新节点
    s->data = e;

    s->next = p->next;                // 3. "先接":新节点 s 指向原来 p 的后继
    p->next = s;                      // 4. "后断":前驱 p 改为指向新节点 s

    return 1;
}

为什么找的是第 i-1 个（前驱）而不是第 i 个？ 因为插入要修改「前一个节点的 next」让它指向新节点。你必须站在前驱身上才能改它的 next。这就是 2.3.3 节说「头结点让首位置不用特判」的好处——即使插在第 1 个位置，前驱也是头结点（第 0 个），存在且统一处理。

第 3、4 步又是「先接后断」，顺序绝不能反，否则 p->next 被覆盖、后面的链全丢。画个图：插入前 p → q，要变成 p → s → q。先让 s->next 接住 q（此时 p 还指着 q，没丢），再让 p->next 改指 s。完美。

复杂度：改指针本身是 O(1)，但找第 i-1 个节点要 O(n)，所以整体 O(n)。注意：如果题目说「已知指向某节点的指针，在它后面插入」，那就是纯 O(1)，不用找——这是链表插入相比顺序表的真正优势所在（已知位置时 O(1)）。

2.3.7 删除操作

删除第 i 个节点，同样要先找到它的前驱（第 i-1 个），然后让前驱「跳过」被删节点。

// 删除带头结点单链表 L 的第 i 个节点,值带回给 *e
int ListDelete(LinkList L, int i, ElemType *e) {
    LNode *p = GetElem(L, i - 1);          // 1. 找到第 i-1 个节点(前驱)
    if (p == NULL || p->next == NULL)      //    前驱不存在,或前驱没有后继(第 i 个不存在)
        return 0;

    LNode *q = p->next;                    // 2. q 指向真正要删的第 i 个节点
    *e = q->data;                          //    保存它的值

    p->next = q->next;                     // 3. 前驱跳过 q,直接指向 q 的后继
    free(q);                               // 4. 别忘了释放被删节点的内存!

    return 1;
}

第 4 步 free(q) 千万不能漏——这是链表和顺序表的一大区别。顺序表删除只是挪数据，链表删除是真把一个节点「干掉并归还内存」。漏了 free 就内存泄漏。另外注意删除前先用 q 记住要删的节点，否则 p->next = q->next 之后就找不到它、没法 free 了。

复杂度：O(n)（瓶颈仍是找前驱）。

2.3.8 单链表小结

2.4 循环链表与双链表（变体，了解 + 会基本操作）

2.4.1 循环链表

把单链表最后一个节点的 next 由 NULL 改为指向头结点，整条链就首尾相连成一个环。好处是从任意一个节点出发都能遍历到所有节点（不会像单链表那样走到 NULL 就到头）。判空条件相应变成 L->next == L（头结点指向自己）。

2.4.2 双链表（双向链表）

单链表只能往后走（只有 next），想找一个节点的前驱得从头再来一遍，很亏。双链表给每个节点额外加一个 prior 指针指向前驱，于是前后都能走。

typedef struct DNode {
    ElemType      data;
    struct DNode *prior;   // 指向前驱
    struct DNode *next;    // 指向后继
} DNode, *DLinkList;

代价是每个节点多存一个指针（更费空间）、插入删除要多维护一组指针。双链表插入节点 s 到 p 之后，要改四个指针（顺序有讲究，仍是「先接后断」的思路）：

s->next = p->next;        // s 的后继 = p 原来的后继
p->next->prior = s;       // p 原后继的"前驱"改成 s  (注意:这步要在 p->next 被改之前做)
s->prior = p;             // s 的前驱 = p
p->next = s;              // p 的后继 = s

顺序的关键：凡是要用到 p->next（p 的原后继）的语句，必须放在 p->next = s 之前，否则原后继就找不到了。这类「四指针顺序题」考试爱考，画图就清楚。

2.4.3 静态链表（了解，选择题偶尔考）

静态链表用数组模拟链表：数组每个元素含 data 和一个 cur（游标，存「下一个元素的数组下标」而非真正的指针）。它在没有指针的语言里也能实现链式结构，本质是「用数组下标当指针」。特点：仍是链式逻辑（插入删除改游标、不挪数据），但容量像数组一样预先固定。考点：知道「静态链表 = 数组下标代替指针」即可。

这几个变体不用死记代码，理解「循环 = 尾连头」「双向 = 多一个前驱指针」「静态 = 下标当指针」的动机和判空/操作要点即可。考试常考填空和画图。

2.5 顺序表 vs 链表（必考对比，做成一张表记死）

对比维度 顺序表（数组） 链表（指针串）
存储方式 一块连续内存 散落，靠指针连接
随机访问第 i 个 O(1) 直接算地址 O(n) 从头数
插入/删除（已知位置） O(n) 要挪元素 O(1) 只改指针
插入/删除（按位序，含查找） O(n) O(n)（瓶颈在找位置）
空间：是否预分配 要预先定容量，可能浪费/不够 用多少分多少，动态
空间：额外开销 无（紧凑） 每节点多一个指针
适用场景 查多改少、要随机访问 改多查少、长度多变

怎么选的考点逻辑：「主要操作是按下标查找」→ 顺序表；「主要操作是频繁插入删除」→ 链表；「长度难以预估」→ 链表；「内存紧张且元素小」→ 顺序表（指针开销占比大时链表反而费）。

2.6 经典题型（这些是后续刷题的高频原型，先理解思路）

这几个是链表的「明星问题」，原理在这里讲清，代码你后续 3 天自己练手：

  1. 反转单链表：用三个指针 prev、cur、next 滚动。每一步：先用 next 记住 cur 的下一个（防止断链），把 cur->next 掉头指向 prev，然后三个指针整体后移一位。走到尾，prev 就是新的头。O(n)、O(1) 空间。

  2. 找倒数第 k 个 / 找中点（快慢指针）：让 fast 指针先走 k 步，再让 fast 和 slow 一起走，fast 到头时 slow 正好在倒数第 k 个。找中点则让 fast 一次走两步、slow 一次走一步，fast 到尾时 slow 在正中间。快慢指针是链表的核心技巧，务必理解。

  3. 判断链表是否有环：快慢指针，fast 走两步 slow 走一步，若有环两者必然在环内相遇；若 fast 走到 NULL 则无环。（这叫 Floyd 判圈法）

  4. 合并两个有序链表：两个指针分别扫两条链，每次把较小的节点接到结果链尾，类似归并排序的「合并」步骤。O(m+n)。

2.7 线性表自测

  1. 线性表定义里的「有序」指的是什么序？空表的长度是多少？
  2. 顺序表里 length 和 MAXSIZE 有什么区别？「第 i 个元素」存在数组的哪个下标？
  3. 顺序表插入/删除平均要移动多少个元素？时间复杂度多少？
  4. 头指针、头结点、首元结点分别是什么？为什么要加头结点？
  5. 链表插入时为什么要先找第 i-1 个节点？「先接后断」是什么意思，反了会怎样？
  6. 链表删除节点为什么必须 free？漏了会怎样？
  7. 单链表为什么不能 O(1) 随机访问？双链表比单链表多了什么、代价是什么？
  8. 默写顺序表 vs 链表的对比表（至少访问、增删、空间三行）。
  9. 快慢指针怎么找链表中点？怎么判断有环？

栈和队列本质上都是「操作受限的线性表」——它们还是线性表（元素排成一队），只是规定了「只能在特定的位置增删」。正是这种「受限」让它们在特定问题里特别好用。这一章概念不难，但应用（表达式求值、循环队列判满判空）是高频考点。

2.8 栈（Stack）

2.8.1 定义与核心规则 LIFO

栈是一种只能在一端进行插入和删除的线性表。这一端叫栈顶（top），另一端叫栈底（bottom）。

它的核心规则是 LIFO（Last In First Out，后进先出）：最后放进去的元素，最先被拿出来。生活中的完美例子是一摞盘子：你只能往最上面放盘子（入栈/push），也只能从最上面拿盘子（出栈/pop），最后放上去的盘子最先被拿走。再比如手枪弹匣、浏览器的「后退」、编辑器的「撤销」，都是栈。

两个基本操作的术语：

2.8.2 顺序栈（用数组实现）

用一个数组存元素，再用一个整数 top 记录栈顶位置。

#define MAXSIZE 100
typedef int ElemType;

typedef struct {
    ElemType data[MAXSIZE];
    int top;                 // 栈顶指针(其实是数组下标)。约定 top 指向"当前栈顶元素"
} SqStack;

// 初始化:空栈。约定 top = -1 表示空(因为还没有任何元素,栈顶下标无效)
void InitStack(SqStack *S) {
    S->top = -1;
}

// 判空:top 回到 -1 即为空
int StackEmpty(SqStack *S) {
    return S->top == -1;
}

// 入栈
int Push(SqStack *S, ElemType e) {
    if (S->top == MAXSIZE - 1)    // 栈满(top 已到达最大下标),溢出
        return 0;
    S->top++;                     // 先让 top 上移一格
    S->data[S->top] = e;          // 再把元素放到新的栈顶位置
    return 1;
}

// 出栈:弹出的值带回给 *e
int Pop(SqStack *S, ElemType *e) {
    if (S->top == -1)             // 栈空,无可弹
        return 0;
    *e = S->data[S->top];         // 先取出当前栈顶元素
    S->top--;                     // top 下移一格(那个元素就"出栈"了)
    return 1;
}

关于 top 的约定要统一：上面约定「top 指向当前栈顶元素，空栈 top = -1」。也有教材约定「top 指向栈顶元素的下一个空位，空栈 top = 0」——两种都对，但一套代码里必须自始至终用同一种，否则判满判空全乱。考试看清题目用哪种约定。 本讲义统一用「top 指向栈顶元素，空栈 -1，满栈 MAXSIZE-1」。

2.8.3 链栈（用链表实现）

也可以用链表实现栈，规定只在链表头部插入和删除（头部就是栈顶）。因为链表头部增删是 O(1)，天然适合做栈，而且没有「栈满」的烦恼（只要内存够）。入栈就是头插，出栈就是删头节点。结构和单链表头插法几乎一样，这里不重复代码，理解「链栈 = 只在头部操作的单链表」即可。

2.8.4 栈的应用（高频考点，重点理解）

栈的威力在于它「记住来路、原路返回」的特性，适合一切「后遇到的先处理」的场景。

应用一：括号匹配

检查 ( [ { } ] ) 这类括号是否正确配对。算法：从左到右扫描，遇到左括号就入栈；遇到右括号，就看栈顶——如果栈顶是与之匹配的左括号，就弹出（配对成功）；否则匹配失败。扫描结束时栈恰好为空，才算全部匹配。

为什么用栈？因为括号是「最近打开的最先需要关闭」——典型 LIFO。比如 ([])，遇到 ] 时，最近打开的是 [（正在栈顶），正好匹配。

应用二：表达式求值与中缀转后缀（经典大题）

我们平时写的 3 + 4 * 2 叫中缀表达式（运算符在两个操作数中间），人好懂但机器难算（要考虑优先级、括号）。计算机喜欢后缀表达式（又叫逆波兰式），运算符放在操作数后面，比如上式变成 3 4 2 * +。后缀表达式没有括号、不用考虑优先级，机器一遍扫描就能算。

后缀表达式求值（用一个栈）：从左到右扫描——遇到操作数就入栈；遇到运算符，就弹出栈顶两个操作数做运算，结果再压回栈。扫描结束栈里剩的唯一一个数就是答案。

注意弹出两个操作数做减法/除法时的顺序：先弹出的是右操作数。比如算 a b -，先弹出的 b 是减数，结果是 （后弹的 a） - （先弹的 b）。这个顺序考试爱挖坑。

举例算 3 4 2 * +：

中缀转后缀也用栈（栈这次存运算符）。扫描中缀式，对每个 token 按下面四条规则处理（背下来）：

  1. 操作数：直接输出到后缀式。
  2. 左括号 (：直接入栈（它像一道「墙」，括号内的运算自成一体）。
  3. 右括号 )：连续弹出栈顶运算符并输出，直到遇到左括号，然后把那个左括号弹掉丢弃（括号本身不进入后缀式）。
  4. 运算符 op：当栈非空、栈顶不是 (、且栈顶运算符优先级 ≥ op 的优先级时，反复弹出栈顶并输出；然后把 op 入栈。
  5. 扫描结束后，把栈里剩余的运算符全部弹出输出。

优先级：* / 高于 + -。关键陷阱：栈顶优先级「等于」当前运算符时也要先弹出（保证同级运算左结合，先算左边）。

完整手算示例：中缀 A + B * C - D 转后缀。

读到 动作 输出(后缀) 栈(底→顶)
A 操作数,输出 A （空）
+ 栈空,入栈 A +
B 操作数,输出 A B +
* *>+,不弹,入栈 A B + *
C 操作数,输出 A B C + *
- *≥-弹*、+≥-弹+,再入- A B C * + -
D 操作数,输出 A B C * + D -
结束 弹出栈中剩余 A B C * + D - （空）

结果后缀式：A B C * + D -。

带括号示例：A * (B + C) → 读 A(输出)、*(入栈)、((入栈)、B(输出)、+(栈顶是(不比较,入栈)、C(输出)、)(弹出+输出,弹掉()、结束弹出* → 后缀 A B C + *。

考点固定：① 给中缀式手算后缀（用上面表格逐步走）；② 反过来给后缀式求值（用 3.1.4 应用二的方法）。两者都是机械送分题，多练两个就稳。

应用三：函数调用与递归

程序运行时，每调用一个函数，系统就把「返回地址、参数、局部变量」打包成一个栈帧（Stack Frame）压入系统栈；函数返回时弹出栈帧、回到调用处。这天然是 LIFO（最后调用的函数最先返回）。递归就是函数自己调自己，每深一层就多压一个栈帧——所以递归太深会「栈溢出」，所以递归的空间复杂度要算栈的深度（回顾 1.7 节）。任何递归都能用一个栈改写成非递归，本质就是手动模拟系统栈干的事。

栈帧机制（c03 可能出简答/选择，了解即可）：两个关键寄存器——SP（栈指针）指向当前栈顶、BP（基址指针）指向当前栈帧的底部（用来稳定地访问参数和局部变量）。一次函数调用的大致过程：实参压栈 → 返回地址压栈 → 保存调用者的 BP → 设新 BP → 分配局部变量 → 执行函数体 → 恢复 BP → 弹返回地址 → 清理参数。多数体系里系统栈是向下增长的（从高地址向低地址）。这些是「为什么递归=压栈、为什么能改成非递归」的底层原理，简答题答到「每次调用建一个栈帧、LIFO、递归靠系统栈」即可得分。

应用四：判断合法出栈序列（⭐选择/填空最高频）

这是栈这一章的头号考点，几乎每年以选择/填空出现，务必练熟。

题型：元素按 1,2,3,...,n 的顺序依次入栈（注意是「依次」，不是一次全压进去），入栈和出栈可以任意交错。问：给定一个序列，它是否可能是一个合法的出栈序列？

核心规则（必须理解）：入栈顺序固定为 1→2→…→n，但每个元素入栈后可以立刻出、也可以压着等会儿出。所以同一个入栈序列能产生多种出栈序列。

判断方法一：模拟法（最稳，一定对） 准备一个栈，一个指针指向「下一个待入栈的数」（从 1 开始）。逐个核对目标出栈序列的每个数 x：

例：入栈序 1 2 3 4 5，判断 4 5 3 2 1 是否合法。

目标4: push1,2,3,4 → 栈[1,2,3,4]，顶=4 ✓ pop → 栈[1,2,3]
目标5: push5 → 栈[1,2,3,5]，顶=5 ✓ pop → 栈[1,2,3]
目标3: 顶=3 ✓ pop → 栈[1,2]
目标2: 顶=2 ✓ pop → 栈[1]
目标1: 顶=1 ✓ pop → 栈空。全部匹配 → 合法 ✓

再判断 4 3 5 1 2：到目标1 时栈里是 [1,2]，顶=2≠1 → 非法。

判断方法二：口诀法（快速排除） 已经出栈的元素中，比某个数大的若干个数，它们的相对出栈顺序必须是递减的。更实用的一句话陷阱判据：对出栈序列，若存在三个位置 i<j<k 使得 序列[j] < 序列[k] < 序列[i]，则非法（即不能出现「中间小、后面中、前面大」这种 312 模式）。考试时方法一模拟最不容易错，方法二用来快速秒杀选择题。

送分结论（直接记）：n 个元素依次入栈，可能的合法出栈序列总数 = 卡特兰数 C(2n, n)/(n+1)。

2.9 队列（Queue）

2.9.1 定义与核心规则 FIFO

队列也是操作受限的线性表，但和栈相反：它在一端插入、在另一端删除。插入的一端叫队尾（rear），删除的一端叫队头（front）。

核心规则是 FIFO（First In First Out，先进先出），完美对应生活中的排队：先来的人先办事先离开，后来的人排在队尾等。

两个基本操作：

2.9.2 队列的顺序实现与「假溢出」问题

用数组实现队列，配两个指针 front（队头）和 rear（队尾）。入队 rear 往后移，出队 front 往后移。问题来了：随着不断入队出队，front 和 rear 都只增不减、一路往数组后面跑。即使前面出队腾出了大量空位，rear 一旦到达数组末尾就「满了」入不了队——可前面明明是空的！ 这种「明明有空间却报满」的现象叫假溢出。

2.9.3 循环队列（解决假溢出，必考）

循环队列的思路：把数组想象成首尾相接的一个圆环。当指针走到数组末尾时，下一步绕回到数组开头（下标 0），这样后面腾出的空位就能重新利用。绕回靠取模运算 % MAXSIZE 实现：

下一个位置 = (当前位置 + 1) % MAXSIZE

比如 MAXSIZE=5，rear 在下标 4，(4+1)%5 = 0，自动绕回开头。

关键难点：怎么区分「队空」和「队满」

这是循环队列最大的考点。麻烦在于：队空时 front == rear；可如果元素填满整圈，rear 绕一圈又追上 front，也会 front == rear。两种情况下指针长得一模一样，没法区分！

主流解决办法（教材标准做法）：牺牲一个存储单元不用。即规定「当 rear 的下一个位置就是 front 时，就算满」，这样队满时 front 和 rear 之间永远空一格，就和队空区分开了：

#define MAXSIZE 100
typedef int ElemType;

typedef struct {
    ElemType data[MAXSIZE];
    int front;    // 指向队头元素
    int rear;     // 指向队尾元素的"下一个"位置(约定)
} SqQueue;

void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;        // 初始都指向 0
}

// 判空:队头追上队尾
int QueueEmpty(SqQueue *Q) {
    return Q->front == Q->rear;
}

// 判满:rear 的下一个位置就是 front(中间空一格)
int QueueFull(SqQueue *Q) {
    return (Q->rear + 1) % MAXSIZE == Q->front;
}

// 入队
int EnQueue(SqQueue *Q, ElemType e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front)   // 满
        return 0;
    Q->data[Q->rear] = e;                       // 元素放到队尾位置
    Q->rear = (Q->rear + 1) % MAXSIZE;          // rear 后移(可能绕回)
    return 1;
}

// 出队
int DeQueue(SqQueue *Q, ElemType *e) {
    if (Q->front == Q->rear)                    // 空
        return 0;
    *e = Q->data[Q->front];                     // 取队头元素
    Q->front = (Q->front + 1) % MAXSIZE;        // front 后移(可能绕回)
    return 1;
}

必背的三个公式

这是送分点，背死：

除了「牺牲一个单元」，还有另一种区分空满的办法：额外加一个 size 计数器（或一个标志位 tag）记录当前元素个数，size==0 为空、size==MAXSIZE 为满。这样能用满整个数组。考试两种都可能考，看题目要求。

⚠️ 必看易错点：front/rear 的定义不止一种，公式不能死套！ 本讲义用的是「front 指向队头元素、rear 指向队尾的下一个空位」。但有的教材/题目用另一套约定：「front 指向队头元素的前一个位置、rear 指向队尾元素本身」。两套约定下，入队/出队谁先动指针、判空判满公式都不同。做题第一步永远是先看清题目给的是哪套定义，再套相应公式。例如在「front 指队头前一位、rear 指队尾」这套里，入队是「先 rear=(rear+1)%M 再放元素」、元素个数仍是 (rear-front+M)%M。核心思想（取模绕回、牺牲一格区分空满）不变，变的只是指针落点。

2.9.4 链队列（用链表实现）

用链表实现队列，需要两个指针：front 指向链表头（队头，从这删）、rear 指向链表尾（队尾，往这加）。带头结点的链队列入队是尾插、出队是删头结点之后的节点，都是 O(1)，且没有「满」的限制。链队列适合长度变化大、上限不好预估的场景。

2.9.5 队列的应用与变体

2.10 栈 vs 队列（一句话对比）

栈 Stack 队列 Queue
规则 LIFO 后进先出 FIFO 先进先出
操作位置 同一端（栈顶）进出 一端进（队尾）、另一端出（队头）
生活类比 一摞盘子 排队
典型应用 括号匹配、表达式求值、递归 BFS、任务调度、缓冲区

2.11 栈与队列自测

  1. 栈和队列为什么叫「操作受限的线性表」？各受了什么限制？
  2. LIFO 和 FIFO 分别是什么？各举一个生活例子。
  3. 顺序栈用 top=-1 表示空，那么判满条件是什么？入栈时是先动 top 还是先放元素？
  4. 后缀表达式 5 1 2 + 4 * + 3 - 的值是多少？（动手用栈模拟一遍）
  5. 什么是「假溢出」？循环队列怎么解决它？
  6. 写出循环队列（牺牲一个单元方案）的判空、判满、求元素个数三个公式。
  7. 求元素个数的公式里为什么要 + MAXSIZE 再取模？
  8. 为什么递归会导致栈溢出？递归和栈是什么关系？
  9. BFS 为什么用队列而不是栈？

这一章包含两个相对独立的主题：串（字符串，重点是 KMP 模式匹配算法）和数组（重点是多维数组地址计算与特殊矩阵压缩存储）。KMP 是本章——也是整个线性结构部分——最硬的一块骨头，我们慢慢啃。

2.12 串（String）

2.12.1 定义

串就是由零个或多个字符组成的有限序列，也就是我们常说的「字符串」，比如 "hello"。它本质上是一种元素为字符的特殊线性表，所以前面线性表的存储思想（顺序/链式）都适用。一些术语：

串大多数操作（求长、连接、求子串等）都比较直观，本章真正的核心、也是必考的难点，是模式匹配——在一个主串里查找一个子串第一次出现的位置。

2.12.2 朴素模式匹配（BF 算法）

问题：在主串 S 中，找模式串 P 第一次出现的位置。

朴素（Brute Force，暴力）思路：拿 P 去和 S 的每一个可能的起始位置逐字符比对。从 S 的第 0 位开始，逐字符比 P；一旦某个字符不匹配，就让 P 整体右移一位，从 S 的第 1 位重新开始整段比对……如此直到匹配成功或 S 走完。

// 在主串 S 中查找模式串 P,返回 P 首次出现的位置下标(从 0 开始);找不到返回 -1
int BF(char *S, char *P) {
    int n = strlen(S), m = strlen(P);
    int i = 0;                       // i 扫描主串 S
    int j = 0;                       // j 扫描模式串 P
    while (i < n && j < m) {
        if (S[i] == P[j]) {          // 当前字符匹配:两个指针都前进
            i++;
            j++;
        } else {                     // 失配:i 回退到本次起点的下一个,j 归零重来
            i = i - j + 1;           // i - j 是本次起点,+1 就是下一个起点
            j = 0;
        }
    }
    if (j == m) return i - m;        // j 走完整个 P,说明匹配成功,返回起始位置
    else return -1;                  // 没找到
}

复杂度：最坏情况（比如 S = "aaaaaaab"，P = "aaab"），每个起点都要比到最后才失配，总共约 n×m 次比较，O(n×m)。问题出在那句 i = i - j + 1——每次失配，主串指针 i 都要退回去，之前比过的字符白比了，这是浪费的根源。

2.12.3 KMP 算法（必考重点，全章最硬）

KMP 的核心思想：失配时，主串指针 i 永不回退

KMP 的天才之处在于发现：失配时，那些已经匹配成功的字符里，藏着有用的信息。利用这些信息，模式串 P 可以「聪明地」往右滑动一大段，而主串指针 i 完全不用回退。这样整个匹配过程 i 一路向前走到底，复杂度降到 O(n+m)。

用例子建立直觉

假设主串 S = a b a b a b c，模式串 P = a b a b c。

S: a b a b a b c
P: a b a b c
   0 1 2 3 4

匹配到 P[4]='c' 和 S[4]='a' 时失配。此时 P 的前 4 个字符 abab 已经和 S 对应位置匹配过了。朴素算法会把 i 退回到 1，P 退回 0 重头比。但 KMP 注意到：模式串 abab 的开头的 ab 和结尾的 ab 是一样的（这叫「最长相等前后缀」）。既然结尾的 ab 已经和主串匹配了，而开头的 ab 又和结尾的 ab 相同，那把 P 往右滑、让开头的 ab 对齐到刚才结尾 ab 的位置，这两个字符必然还是匹配的，不用重新比！于是 j 直接跳到 2（对齐到开头 ab 之后），i 不动，从 P[2] 继续比。

next 数组：失配后 j 该跳到哪

KMP 把「失配后 j 该跳到哪」这个信息预先算好，存成一个数组，叫 next 数组。next[j] 的含义是：当模式串第 j 个字符失配时，j 应该跳回到 next[j] 这个位置继续比（i 不动）。

而 next[j] 的值，本质上等于 P 中 P[0..j-1] 这段子串的「最长相等前后缀」的长度。

例子，P = a b a b c，手算每个位置的 next（这里用「next[j] = P[0..j-1] 的最长相等前后缀长度」这一常见定义，next[0] 规定为 -1 或 0，依教材；这里令 next[0]=0、next[1]=0 起步说明含义）：

j P[j] P[0..j-1] 最长相等前后缀 next[j]
0 a （空） — -1（特殊，约定）
1 b "a" 无（单字符无前后缀） 0
2 a "ab" 无 0
3 b "aba" "a"（前缀a=后缀a）长度1 1
4 c "abab" "ab"（前缀ab=后缀ab）长度2 2

重要提醒：next 数组的具体定义（从 0 还是从 1 开始、next[0] 取 -1 还是 0、有没有「nextval 优化版」）各教材不统一。中科大课本用哪一种，以你课本为准——但核心思想完全一样：next[j] 就是「P[0..j-1] 的最长相等前后缀长度」，记住这个本质，碰到任何定义都能换算。考试如果给定了定义，照定义算即可。

KMP 匹配过程代码

// 假设 next 数组已经算好。在主串 S 中匹配模式串 P
int KMP(char *S, char *P, int *next) {
    int n = strlen(S), m = strlen(P);
    int i = 0;                  // 主串指针,全程只增不减(这就是 KMP 的关键!)
    int j = 0;                  // 模式串指针
    while (i < n && j < m) {
        if (j == -1 || S[i] == P[j]) {   // j==-1 表示模式串第一个就失配,i,j 都前进
            i++;
            j++;
        } else {
            j = next[j];        // 失配:i 不动,j 跳到 next[j](利用已匹配信息)
        }
    }
    if (j == m) return i - m;   // 匹配成功
    else return -1;
}

对比朴素算法，唯一的区别就是失配那一支：朴素是 i 回退、j 归零，KMP 是 i 不动、j = next[j]。就这一改，复杂度从 O(nm) 降到 O(n+m)。

next 数组怎么计算（手算 + 代码）

手算方法（考试这么做）：对模式串每个前缀 P[0..j-1]，写出它的所有前缀和后缀，找最长的相等的那对，长度就是 next[j]。多算几个例子（比如 "aabaaf"、"abcabc"）就熟了，这是必考的机械送分题，务必练到闭眼会。

求 next 的代码（思想是「用 P 自己和自己做 KMP」，理解即可，先记住会查表用）：

void GetNext(char *P, int *next) {
    int m = strlen(P);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < m - 1) {
        if (j == -1 || P[i] == P[j]) {
            i++; j++;
            next[i] = j;        // 记录当前位置的最长相等前后缀长度
        } else {
            j = next[j];        // 这里又用到了 next 自己,是个精妙的递推
        }
    }
}

手算 next 的「错位」速算法（考试这样最快）

考试手算 next 不用真去枚举前后缀，用这个机械口诀更快（以 next[1]=0、next[2]=1 起步，下标从 1 开始 的常见课本定义为例）：

完整示例：模式串 P = a b a a b c a c（下标 1~8），求 next（课本定义，next[j]=最长相等前后缀长+1）：

j 1 2 3 4 5 6 7 8
P[j] a b a a b c a c
next[j] 0 1 1 2 2 3 1 2

注：若课本用「next[0]=-1、从 0 下标」的版本，数值会整体差 1，本质完全一样，对应代码里 j=-1 表示「模式串第一个就失配」。考试给哪套定义就用哪套，先抄题目的 next[1]（或 next[0]）起始值。

nextval（next 的优化版，常考）

next 还能再优化成 nextval：当模式串里 P[j] == P[next[j]] 时，跳到 next[j] 后还会立刻再次失配（因为字符相同），白跳一步，于是直接令 nextval[j] = nextval[next[j]]，一步到位。

规则（手算）：先求出 next，再逐个修正：

接着上例（a b a a b c a c）求 nextval：

j 1 2 3 4 5 6 7 8
P[j] a b a a b c a c
next 0 1 1 2 2 3 1 2
nextval 0 1 0 2 1 3 0 2

（如 j=3：P[3]='a'，P[next[3]]=P[1]='a'，相同 → nextval[3]=nextval[1]=0。）

KMP 小结与考点

2.13 数组

2.13.1 多维数组的存储与地址计算

数组（尤其二维数组/矩阵）虽然逻辑上是「行列」的二维结构，但内存是一维线性的，所以必须把二维「压平」成一维来存。有两种压平顺序：

地址计算公式（必考）：设二维数组 A 有 m 行 n 列，每个元素占 L 个字节，首元素 A[0][0] 的地址为 Loc(0,0)，按行优先存储，则元素 A[i][j] 的地址为：

Loc(i, j) = Loc(0, 0) + (i × n + j) × L

理解：A[i][j] 前面有「完整的 i 行」（共 i×n 个元素）加上「本行 j 列前面的 j 个元素」，一共 (i×n + j) 个元素，每个占 L 字节，所以从首地址偏移这么多。列优先则是 Loc(i,j) = Loc(0,0) + (j × m + i) × L（先数完整的 j 列，每列 m 个）。

考点就是给你行列数、起始地址、按行还是按列、某元素下标，让你算它的物理地址。代入公式即可，注意下标从 0 还是从 1 开始（题目会说明，从 1 开始时公式里要相应 -1）。

三维数组地址公式（也会考，套路相同）：设三维数组 A[m₁][m₂][m₃]（即第二维大小 n=m₂、第三维大小 p=m₃），按行优先（最右下标变化最快），元素 A[i][j][k] 的地址为：

Loc(i,j,k) = Loc(0,0,0) + (i × m₂ × m₃ + j × m₃ + k) × L

理解：跳过 i 个「完整的二维面」（每面 m₂×m₃ 个元素）+ 本面跳过 j 个「完整行」（每行 m₃ 个）+ 本行再走 k 个。口诀：每一维的「权」= 它后面所有维大小的乘积。 推广到任意维都是这个规律。下标从 1 开始时，把每个下标各减 1 再代入。

2.13.2 特殊矩阵的压缩存储

有些矩阵有大量规律性的、重复或为零的元素，全存太浪费。压缩存储的思想是：只存有用的元素，省掉规律性的部分，用公式建立「矩阵下标 ↔ 一维数组下标」的映射。

对称矩阵

满足 a[i][j] == a[j][i] 的方阵。既然上三角和下三角对称相等，只需存一半（比如下三角，含对角线），另一半用对称性现算。n 阶对称矩阵只存 n(n+1)/2 个元素。把下三角按行存进一维数组 B，元素 a[i][j]（i≥j，下标从 1 开始）对应 B 的下标公式：

k = i(i-1)/2 + j - 1     (i ≥ j,下三角区)
当 i < j(上三角)时,利用对称性,改用 a[j][i] 的位置: k = j(j-1)/2 + i - 1

理解：第 i 行（下三角）前面有 1+2+...+(i-1) = i(i-1)/2 个元素，本行第 j 个再加 j，减 1 转成从 0 开始的下标。

三角矩阵、对角矩阵

这些都是同一个思路：找出规律 → 只存不规律的部分 → 用公式做下标映射。考点是给定矩阵和压缩方式，求某元素在一维数组里的下标，或反过来。

稀疏矩阵

稀疏矩阵指非零元素极少（远少于零元素）的矩阵。如果还按常规存，绝大部分空间都浪费在存 0 上。压缩办法是只存非零元素，常用两种：

考点：理解三元组怎么表示一个给定稀疏矩阵；了解十字链表的动机。

2.14 串与数组自测

  1. 串是什么特殊的线性表？什么是子串、主串、子串的位置？
  2. 朴素模式匹配的时间复杂度是多少？瓶颈（浪费）出在哪一步？
  3. KMP 的核心思想一句话概括是什么？它的时间复杂度？
  4. next[j] 的本质含义是什么（用「前后缀」描述）？手算 P="ababa" 的 next 数组。
  5. KMP 匹配过程里，失配时 i 和 j 分别怎么变？（和朴素算法对比）
  6. 二维数组 A[m][n] 按行优先，A[i][j] 的地址公式是什么？解释每一项的含义。
  7. n 阶对称矩阵压缩后只需存多少个元素？为什么？
  8. 稀疏矩阵的三元组表示法存的是什么？

2.15 本段总自测清单

C 基础

导论 + 复杂度

线性表

栈与队列

串和数组

前两章到此告一段落。 这两章把「地基（C+复杂度）」和「线性世界（表/栈/队列/串/数组）」打通了。最重要的三块硬骨头是：指针与链表的「改指针」操作、循环队列判空判满、KMP 的 next 数组——这三处务必动手画图、手算到熟练。

读完、自测过关后，下面进入第三、四章：树与二叉树 + 图（全课最大的重头）。读的过程中任何卡壳，随时回头复习。