首页/数据结构/线性表/静态链表 🔗 在 Obsidian 中打开
数据结构 · 线性表

静态链表

重要度 ⭐⭐ 线性表静态链表游标备用链表
速查
静态链表用数组模拟链表：每个元素含 data 与 next（游标，存数组下标）。下标 0 是数据链表头、MaxSize-1 是备用链表头；游标 0 表示链表结束。容量最多 MaxSize-2。

核心概念 ▾

静态链表是用数组模拟链表操作的一种数据结构。每个数组元素包含两个域：

  • data 域：存储数据元素
  • next 域（游标 cursor）：存储下一个元素在数组中的下标（而非指针）
#define MaxSize 100
typedef struct {
    ElemType data;
    int next;  // 游标，存放下一个元素的数组下标
} SLinkList[MaxSize];
特性动态链表静态链表
存储分配malloc/free 动态分配预先分配固定大小数组
指针/游标指针（内存地址）整数下标
适用场景有动态内存管理的系统无指针语言（如 Basic、Fortran）
空间利用按需分配，灵活可能浪费或不足
数组组织下标 0：充当"头结点"角色，其 next 指向第一个实际数据元素；下标 MaxSize-1：充当"备用链表头"，管理未使用空间。
备用链表把空闲空间串成一个链表：data[MaxSize-1].next 指向第一个空闲位置；分配空间从备用链表头部取结点，释放空间则插回备用链表头部。

关键性质 ▾

  1. 容量固定：声明时确定 MaxSize，运行时不可扩展。
  2. 无指针：用整数下标代替指针，适合无指针语言。
  3. 随机访问丧失：底层虽是数组，但逻辑上是链式存储，不支持随机访问。
  4. 空间预分配：数组空间一次性分配，可能浪费也可能不足。

基本操作 ▾

初始化

void InitList(SLinkList L) {
    L[MaxSize-1].next = 0;  // 备用链表为空
    for (int i = 0; i < MaxSize - 1; i++)
        L[i].next = i + 1;  // 默认全部串起来
}

分配节点（MALLOC）

int MALLOC(SLinkList L) {
    int i = L[MaxSize-1].next;  // 取备用链表第一个结点
    if (i != 0)
        L[MaxSize-1].next = L[i].next;  // 备用链表头指向下一个
    return i;
}

释放节点（FREE）

void FREE(SLinkList L, int k) {
    L[k].next = L[MaxSize-1].next;  // k 的 next 指向原备用链表头
    L[MaxSize-1].next = k;          // 备用链表头指向 k
}

手算示例 ▾

插入操作

假设数组大小 6，已有元素 A(下标1)→B(下标3)→C(下标4)，在第 i 个位置插入 e：

  1. 从备用链表分配一个空闲结点 $j = MALLOC(L)$
  2. 设置 $L[j].data = e$
  3. 找到第 i-1 个结点的位置 p
  4. $L[j].next = L[p].next$（新结点指向原第 i 个）
  5. $L[p].next = j$（第 i-1 个指向新结点）
下标:  0    1    2    3    4    5
data:  -    A    -    B    C    -
next:  1    3    -    4    0    2
       ↑头                  ↑尾  ↑备用链表头

备用链表：5→2→0（下标 5 的 next 是 2，下标 2 的 next 是 0 表示结束）

数据链表：0→1→3→4→0（A→B→C→结束）

查找与删除

删除元素 B：

  1. 找到 B 的前驱结点（下标 1，即 A）
  2. $L[1].next = L[3].next = 4$（A 直接指向 C）
  3. FREE(L, 3)，将下标 3 还给备用链表

常见考法 ▾

题型一 · 容量计算一个静态链表有 n 个元素，最多容纳 MaxSize - 2 个（下标 0 和 MaxSize-1 被占用）。
题型二画出静态链表执行一系列插入删除后的状态（注意备用链表的变化）。
题型三用静态链表实现两个有序表的合并。

易错点 ▾

易错清单
  1. 下标 0 和 MaxSize-1 不存数据：容易忘记这两个位置被"系统"占用。
  2. 备用链表的管理：分配和释放要同时维护备用链表。
  3. next 存的是下标不是地址：不能用指针的方式理解。
  4. 空表判断：$L[0].next == 0$ 表示空表。
  5. 游标 0 的含义：next 值为 0 表示链表结束（类似 NULL）。

核心结论 ▾

  • 静态链表本质是用数组模拟链表，用游标（整数下标）代替指针。
  • 适合无指针语言或嵌入式环境。
  • 空间管理需要维护备用链表：MALLOC 从备用链表分配，FREE 归还。
  • 容量固定为 MaxSize - 2（减去头结点和备用链表头）。
  • 时间复杂度与动态链表相同：查找 O(n)，插入/删除 O(1)（已知位置时）。

记忆卡片 ▾

下标 0 和 MaxSize-1 的作用？
0 是数据链表头（next 指向首元素）；MaxSize-1 是备用链表头（管理空闲空间）。
MALLOC 做了什么？
取备用链表头 i，令 $L[MaxSize-1].next = L[i].next$，返回 i。
与动态链表时间复杂度的区别？
无区别：查找 O(n)、已知位置增删 O(1)；只是存储管理方式不同。
如何判空？游标 0 含义？
$L[0].next == 0$ 为空表；游标 0 = NULL（下标 0 不分配给数据）。

交互动画 · 游标链与备用链表 ▾

橙色：数据链表　紫色：备用链表 头next=10 Anext=31 -next=?2 Bnext=43 Cnext=04 -next=25 数据链 0→1→3→4→0；备用链 5→2→0（5 是 MaxSize-1）
静态链表初始状态：数据链 A→B→C，备用链 [5]→[2]→0
观察 MALLOC / 插入 / FREE 如何维护两条链
next 存的是数组下标而非地址；游标 0 相当于 NULL。分配/释放都要同步维护备用链表。

相关知识点

（暂无关联知识点）

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。