静态链表

定义

静态链表是用数组实现的链表。它分配一整片连续空间，但元素之间的逻辑顺序不由数组下标相邻体现，而由游标 next 表示。

每个数组元素通常包含：

  • 数据域 data：存储数据元素。
  • 游标 next：存储下一个结点的数组下标。

游标相当于指针，但它存的是数组下标而不是内存地址。

结构示例

1
2
3
4
5
#define MaxSize 10
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

SLinkList a 相当于定义了一个长度为 MaxSize 的结点数组。

常用约定

  • a[0] 可充当头结点。
  • next == -1 表示已经到达表尾。
  • 可用特殊值如 -2 表示结点空闲。

具体特殊值不是固定标准，关键是题目或代码中约定一致。

基本操作思路

初始化：

  • 令头结点游标指向 -1，表示空表。
  • 将其他空闲结点标记为特殊值。

查找：

  • 从头结点出发，根据游标依次访问后继结点。

插入第 i 个位置：

  1. 找到一个空闲结点并写入数据。
  2. 从头结点出发找到第 i - 1 个结点。
  3. 修改新结点游标。
  4. 修改前驱结点游标。

删除结点：

  1. 找到被删结点的前驱。
  2. 修改前驱游标跳过被删结点。
  3. 将被删结点标记为空闲。

优缺点与适用场景

优点：插入、删除不需要大量移动元素；不依赖语言层面的指针。

缺点：不能随机存取，只能从头结点沿游标查找；容量固定，不易扩展。

适用场景：不支持指针的语言，或数据元素数量固定的场景。

关联

静态链表在逻辑上类似 单链表，在物理上使用数组连续存储，和 顺序表 有明显区别。