一、引言
静态链表是线性表的一种链式存储结构，但与普通的链式存储结构不同，静态链表是在数组的基础上实现的。在静态链表中，我们依然使用指针来表示元素之间的逻辑关系，但指针是元素的数组下标。静态链表的好处是它在物理存储上是连续的，且没有指针域的额外开销，但在插入和删除操作中需要移动大量元素。
二、静态链表的实现
节点定义
在静态链表中，我们定义一个结构体数组来存储节点信息。每个节点包含一个数据域和一个游标（cur），游标用于指向下一个节点的数组下标。为了表示链表的结束，我们约定一个特殊值（如-1）作为空指针。
c复制代码
#define MAXSIZE 100 // 假设静态链表的最大长度为100 #define NULL -1 // 空指针定义为-1 typedef struct { int data; // 数据域 int cur; // 游标（指向下一个节点的数组下标） } Component, StaticList[MAXSIZE];
初始化静态链表
静态链表的初始化通常是将所有节点的游标初始化为-1（即空指针），并将第一个节点的游标作为头指针。
c复制代码
void InitList(StaticList space) { int i; for (i = 0; i < MAXSIZE - 1; i++) { space[i].cur = i + 1; // 初始化游标为下一个节点的数组下标 } space[MAXSIZE - 1].cur = NULL; // 最后一个节点的游标置为空 }
注意：上述初始化方法实际上是将静态链表初始化为一个循环链表，其中所有节点都链接在一起。但在实际使用中，我们通常只使用一部分节点来存储数据，并维护一个头指针来指向第一个有数据的节点。
插入元素
在静态链表中插入元素时，我们需要先找到一个空闲节点（即游标为-1的节点），然后将新元素存储在该节点中，并修改其游标以指向下一个节点。同时，我们需要更新头指针或前一个节点的游标以指向新插入的节点。
c复制代码
int ListInsert(StaticList space, int i, int e) { int j, k; if (i < 1 || i > MAXSIZE) { return 0; // 插入位置不合法 } k = space[0].cur; // 头指针指向第一个空闲节点 j = 1; // 从第二个节点开始查找空闲节点 while (space[k].cur != NULL && j < i - 1) { // 查找第i-1个节点 k = space[k].cur; j++; } if (space[k].cur == NULL) { // 没有找到第i-1个节点，插入位置不合法 return 0; } // 找到空闲节点 while (space[k].cur != NULL) { k = space[k].cur; } space[k].data = e; // 存储新元素 space[k].cur = space[j - 1].cur; // 将新节点插入到第i个位置 space[j - 1].cur = k; // 修改前一个节点的游标以指向新节点 return 1; }
删除元素
在静态链表中删除元素时，我们需要找到要删除的节点，并将其游标修改为下一个节点的游标（即删除该节点），然后修改前一个节点的游标以跳过被删除的节点。
c复制代码
int ListDelete(StaticList space, int i) { int j, k; if (i < 1 || space[0].cur == NULL) { return 0; // 删除位置不合法或链表为空 } k = space[0].cur; // 头指针指向第一个有数据的节点 j = 1; // 从第二个节点开始查找要删除的节点 while (k != NULL && j < i) { // 查找第i个节点 k = space[k].cur; j++; } if (k == NULL || j > i) { // 没有找到要删除的节点 return 0; } space[j - 1].cur = space[k].cur; // 修改前一个节点的游标以跳过被删除的节点 space[k].cur = NULL; // 将被删除节点的游标置为空 return 1
