静态链表

2026 大纲 二（二）线性表的实现 · 2 链式存储 · 本篇只写相对单链表的增量，共性内容见主篇《单链表》。静态链表是存储实现层面的变体，不是新的逻辑结构。

教材出处：四本主参（严蔚敏 / 汤小丹 / 谢希仁 / 袁春风）都没有单列这一节——严蔚敏全书只在 §8.6 基数排序里把静态链表当作实现手段用过一次。成文出处见 殷人昆《数据结构（用面向对象方法与 C++ 描述）》第 2 版 §2.6 静态链表：「如果为数组中每一个元素附加一个链接指针，就形成静态链表结构。它允许我们不改变各元素的物理位置，只要重新链接就能够改变这些元素的逻辑顺序。由于它是利用数组定义的，在整个运算过程中存储空间的大小不会变化，因此称之为静态链表。」

把指针换成下标

链表对"指针域"其实只有一条要求：能唯一定位到直接后继。 内存地址能做到这件事，数组下标同样能做到——只要所有结点都住在同一个数组里，一个整数下标就足以指认其中任何一个。

这就是静态链表：结点存在一个预先开好的数组里，指针域换成整型游标，存的是后继结点在数组中的下标。

换掉之后，主篇的每一句代码都能机械翻译过来：

动态链表	静态链表	说明
`LNode *p`	`int i`	指针变量 → 整型下标（游标）
`p->data`	`space[i].data`	取数据域
`p->next`	`space[i].cursor`	取指针域
`p = p->next`	`i = space[i].cursor`	后移一步
`p == NULL`	`i == 0`	到链尾（约定下标 0 不作数据结点用）
`malloc(sizeof(LNode))`	`Malloc_SL(space)`	申请一个结点
`free(p)`	`Free_SL(space, i)`	归还一个结点

判断有没有真学会静态链表，就看能不能把主篇的每段代码照这张表翻过来。 比如插入的两句 s->next = p->next; p->next = s;，翻译过来是 space[j].cursor = space[k].cursor; space[k].cursor = j;——连"哪句必须在前"的约束都一模一样。

🔴 游标是下标，但下标不是位序。 数据在数组里的物理次序与它在链上的逻辑次序毫无关系，取第 3 个元素仍然只能沿游标走三步， $O (n)$ 。若两者一致，它就退化成顺序表了。

先看一眼

加载可视化中...

盯着数组格子看插入和删除：被改动的只有若干个整数，数据本身一格都没挪。这就是"链式"在数组里的样子。

增量一：游标代替指针

#define MAXSIZE 100

typedef struct {
    ElemType data;  // 数据域
    int cursor;     // 游标：直接后继结点在数组中的下标；0 表示链尾
} SLinkList[MAXSIZE];

⚠️ SLinkList 是一个数组类型（长度 MAXSIZE 的结构体数组），不是结构体类型。所以参数写 SLinkList space 时传进去的是数组首地址，函数内对 space[i] 的修改会作用到实参上。

有两条约定必须先立好，后面的代码才成立：① 下标 0 不存数据元素，专作备用链的头结点——正因为 0 被占掉了，"游标为 0"才能安全地当作链尾标志；② 数据链的头结点下标另用一个变量（如 head）记。

增量二：备用空闲链表

动态链表里"哪块内存空闲"由堆管理器负责；静态链表没有这个后台，程序自己必须知道哪些格子还没被占用。给每格加一个标志位的话，找空闲格要 $O (n)$ 扫描——更好的办法是把所有空闲格子也串成一条链。

于是同一个数组里并存两条链：数据链串起有效元素，备用链串起空闲结点，共用同一套游标。

// 初始化：把整个数组串成一条备用链 0 → 1 → 2 → … → MAXSIZE-1 → 0
void InitList(SLinkList space) {
    for (int i = 0; i < MAXSIZE - 1; i++)
        space[i].cursor = i + 1;
    space[MAXSIZE - 1].cursor = 0;   // 游标置 0，表示备用链到头了
}

// 从备用链申请一个空闲结点，返回其下标；返回 0 表示空间已满
int Malloc_SL(SLinkList space) {
    int i = space[0].cursor;                // 备用链的第一个空闲结点
    if (i)                                   // i == 0 说明备用链已空
        space[0].cursor = space[i].cursor;   // 备用链头后移一位
    return i;
}

// 把下标为 k 的结点归还给备用链
void Free_SL(SLinkList space, int k) {
    space[k].cursor = space[0].cursor;   // ① 被回收结点接住原来的备用链首结点
    space[0].cursor = k;                  // ② 备用链头改指向它
}

这两段代码就是主篇里的"头删"和"头插"——连顺序约束（先接住、再覆盖）都一模一样，认出这一点就不必单独记。申请和回收都只动头部，所以都是 $O (1)$ ；也正因为只有头部操作才 $O (1)$ ，回收出来的结点天然是后进先出的——刚归还的那一格，下一次申请就会被拿走。

⚠️ 忘了 Free_SL 比忘了 free 更严重。 动态链表里忘了 free 只是内存泄漏，程序还能跑；静态链表里忘了归还，那个格子就永远回不到备用链，数组会被慢慢"漏"光，最后 Malloc_SL 全部返回 0。

各操作的复杂度与动态链表逐项相同：按位查找第 $i$ 个 $O (n)$ （下标不是位序，仍须沿游标走 $i$ 步）、按值查找 $O (n)$ （平均比较 $\frac{n + 1}{2}$ 次）、已知前驱下标的插删 $O (1)$ 、按位序插删 $O (n)$ 。这正是"逻辑结构没变、只换了实现"的体现。

插入 / 删除 / 查找的游标版代码（想逐句对照主篇的指针版就展开）

// 在下标为 k 的结点之后插入新元素 e
bool InsertAfter(SLinkList space, int k, ElemType e) {
    int j = Malloc_SL(space);           // 申请一个空闲结点
    if (j == 0) return false;           // 空间已满，插入失败
    space[j].data = e;
    space[j].cursor = space[k].cursor;  // ① 新结点接住 k 的原后继
    space[k].cursor = j;                // ② k 改指向新结点
    return true;
}

// 删除下标为 k 的结点之后的那个结点
bool DeleteAfter(SLinkList space, int k) {
    int j = space[k].cursor;            // j 是被删结点的下标，必须先取
    if (j == 0) return false;           // k 之后已经没有结点了
    space[k].cursor = space[j].cursor;  // ① k 越过被删结点
    Free_SL(space, j);                  // ② 归还给备用链（相当于 free）
    return true;
}

// 从 head 指向的数据链上按值查找，返回结点下标；未找到返回 0
int LocateElem(SLinkList space, int head, ElemType e) {
    int i = space[head].cursor;   // 从头结点的后继（首元结点）开始
    while (i != 0) {              // i == 0 相当于动态链表的 p == NULL
        if (space[i].data == e)
            return i;
        i = space[i].cursor;      // 沿游标后移一步
    }
    return 0;
}

①② 的顺序不能颠倒，理由与单链表的通用范式完全相同：space[k].cursor 里存的"原后继下标"只此一份，② 会覆盖它。

手工走一遍两条链：申请 → 插入 → 删除 → 回收的逐步状态（想彻底看清两条链怎么此消彼长就展开）

设 MAXSIZE = 8，初始化后 head 已申请到下标 1 并置 space[1].cursor = 0（空数据链），备用链为 $0 \to 2 \to 3 \to \dots \to 7 \to 0$ 。依次执行三次头部插入 InsertAfter(space, 1, 'C')、InsertAfter(space, 1, 'B')、InsertAfter(space, 1, 'A')：

操作	申请到的下标	数据链	备用链
初始	—	$1 \to 0$ （空）	$0 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 0$
插入 `'C'`	2	$1 \to 2 (C) \to 0$	$0 \to 3 \to 4 \to 5 \to 6 \to 7 \to 0$
插入 `'B'`	3	$1 \to 3 (B) \to 2 (C) \to 0$	$0 \to 4 \to 5 \to 6 \to 7 \to 0$
插入 `'A'`	4	$1 \to 4 (A) \to 3 (B) \to 2 (C) \to 0$	$0 \to 5 \to 6 \to 7 \to 0$

此刻数组的完整状态：

下标:    0    1    2    3    4    5    6    7
data:    -    -    C    B    A    -    -    -
cursor:  5    4    0    2    3    6    7    0
         ↑    ↑
      备用链  数据链
      头结点  头结点

从这张表里读出两条链：

数据链：head = 1 → space[1].cursor = 4 → space[4]（ $A$ ）→ cursor = 3 → space[3]（ $B$ ）→ cursor = 2 → space[2]（ $C$ ）→ cursor = 0，链尾。读出的序列是 $(A, B, C)$ ✓
备用链：space[0].cursor = 5 → space[5] → cursor = 6 → space[6] → cursor = 7 → space[7] → cursor = 0，链尾。空闲位置是 ${5, 6, 7}$ 。

接着执行 DeleteAfter(space, 4)——删除 $A$ 之后的那个结点（即 $B$ ，下标 3）：

子步骤	语句	效果
取被删下标	`j = space[4].cursor`	$j = 3$
① 越过	`space[4].cursor = space[3].cursor`	`space[4].cursor` 由 3 变为 2
② 回收	`space[3].cursor = space[0].cursor`	`space[3].cursor` 由 2 变为 5
② 回收	`space[0].cursor = 3`	备用链头由 5 变为 3

删除后的状态：

下标:    0    1    2    3    4    5    6    7
data:    -    -    C    -    A    -    -    -
cursor:  3    4    0    5    2    6    7    0

数据链： $1 \to 4 (A) \to 2 (C) \to 0$ ，读出 $(A, C)$ ✓
备用链： $0 \to 3 \to 5 \to 6 \to 7 \to 0$ ，下标 3 已回到空闲池 ✓

上面那张数组状态图里有一处值得盯一眼： $A$ 住在下标 4、 $B$ 在 3、 $C$ 在 2，而逻辑次序偏偏是 $A \to B \to C$ ——物理次序和逻辑次序正好相反。这不是巧合，而是"链式"的必然结果：结点住哪一格由备用链决定，与它在表中排第几毫无关系。

删除之后还有两个细节值得留意。一是下一次 Malloc_SL 会拿到刚刚回收的那一格，这就是前面说的"后进先出"的直接体现；二是被删格子里残留的数据无需清除——它已经不在数据链上，任何合法遍历都读不到它。这与顺序表删除后不必清理表外残值是同一个道理：数据在不在，由结构说了算，不由内容说了算。

增量三：它凭什么还存在

静态链表看起来同时继承了两边的缺点：数组的"容量固定"和链表的"不能随机存取"。它凭什么不被淘汰？

对比项	静态链表	动态链表
结点空间来源	预分配的数组，一次开好	堆，`malloc` 按需申请
指针域内容	数组下标（整数）	内存地址
空闲空间管理	自己维护备用链	交给堆管理器
容量	固定，须预先确定	只受内存总量限制
插入 / 删除	不移动元素，改游标 $O (1)$	不移动元素，改指针 $O (1)$
随机存取	不支持	不支持
内存碎片	无（就一块数组）	频繁分配释放可能产生
跨进程 / 序列化	可直接整块拷贝，下标与地址无关	指针失效，必须重建

答案在最后一行——游标是相对的，地址是绝对的。存指针的链表一旦把字节整块搬到别处，所有指针立刻失效，因为它们记的是旧位置的绝对地址；静态链表存的是数组内的相对下标，搬到哪里链的结构都不会坏。由此得到它成立的三类条件：

语言不提供指针（如早期 Fortran、BASIC）——这是它被发明出来的原始理由；
不能使用进程私有的地址——典型是多进程共享内存：同一块内存映射到不同进程时基址不同，指针不通用、下标通用；
结构要被整体持久化或传输——存盘、跨机器传输时下标天然可用，指针必须重建。

考点速记

这一节不单独成题。 它是链式存储的一种实现变体，逻辑结构和复杂度与单链表逐项相同，所以真正要会的是"能不能把主篇的代码翻译过来"，而不是另记一套结论。

三条会被调用的结论：

静态链表不是新的数据结构，是链式存储的另一种实现。 把 p->next 换成 space[i].cursor，主篇的一切结论原样成立。
备用链的存在，是因为没有 malloc / free 可用——空闲空间的账必须自己记，"串成一条链、只在头部操作"是让申请与回收都保持 $O (1)$ 的办法。
它的真实优势是位置无关性，既不是省空间也不是更快，代价是容量必须预先确定。

易错：把静态链表归成顺序存储。 它确实住在数组里，但要看的是"逻辑相邻是否等于物理相邻"——顺序表逻辑相邻即物理相邻，静态链表靠游标串起来，属于链式存储。"存在数组里"这件事不改变结论。

易错：把游标当位序。 下标只是"住在第几格"，与"排第几个"无关，按位查找仍是 $O (n)$ 。

易错：下标 0 拿去存数据。 0 被约定为备用链的头结点，正因为它不可能是数据结点，"游标为 0"才能当链尾标志用。

教材出处

⚠️ 严蔚敏《数据结构（C 语言版）》（第 2 版）在第 2 章线性表里没有设置静态链表的独立小节，静态链表在该书中是作为链式基数排序的实现载体出现的。因此本篇只引该处：

静态链表的结点类型与表类型定义（SLCell 中用 int next 作为游标域， SLList 中的数组 r 作为"静态链表的可利用空间"，并注明 r[0] 为头结点）：严蔚敏《数据结构（C 语言版）》（第 2 版），p258，8.5 节链式基数排序。书中写明采用静态链表的理由是"以便于更有效地存储和重排记录"—— 重排记录时只改游标、不搬记录本身，这与本篇讲的"插删不移动元素"是同一件事。

本篇其余内容（备用空闲链表的申请与回收机制、与动态链表的对比、适用场景）在该书中没有对应页可引，故不标注出处。

静态链表

把指针换成下标

先看一眼

增量一：游标代替指针

增量二：备用空闲链表

增量三：它凭什么还存在

考点速记

相关知识

相关文章

交互体验

真题练习

静态链表 ​

把指针换成下标 ​

先看一眼 ​

增量一：游标代替指针 ​

增量二：备用空闲链表 ​

增量三：它凭什么还存在 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

静态链表

把指针换成下标

先看一眼

增量一：游标代替指针

增量二：备用空闲链表

增量三：它凭什么还存在

考点速记

相关知识

真题练习