什么是静态链表？
静态链表是一种特殊的链表结构，它用数组来模拟链表的操作。你可以把它想象成一个“固定大小的链表”，每个节点都存储在一个固定的位置（数组下标），并通过一个“游标”来指向下一个节点。
静态链表的特点是：
-
用数组实现：节点存储在数组中，数组的大小是固定的。
-
游标代替指针：用数组下标（游标）来模拟指针，指向下一个节点。
-
适合内存受限的场景：因为不需要动态分配内存，适合嵌入式系统等内存受限的环境。
静态链表的原理
静态链表的底层是一个数组，数组的每个元素（节点）包含两部分：
-
数据：存储实际的数据（比如数字、字符串等）。
-
游标：存储下一个节点的数组下标。
静态链表的核心思想是：
-
用数组的下标来模拟指针，游标为
-1表示链表的结束。 -
需要一个额外的“空闲链表”来管理未使用的数组空间。
静态链表的基本操作
静态链表的基本操作包括：增、删、查、改。下面我们用大白话解释这些操作。
-
增加节点：
-
从空闲链表中分配一个节点，插入到链表的指定位置。
-
修改前后节点的游标，使其指向新节点。
-
-
删除节点：
-
找到要删除的节点，修改前后节点的游标。
-
将被删除的节点放回空闲链表。
-
-
查找节点：
-
从头节点开始，依次遍历每个节点，直到找到目标节点。
-
-
修改节点：
-
找到目标节点后，直接修改它的数据。
-
C 语言实现静态链表
下面是一个简单的静态链表实现代码，包含初始化、插入、删除、查找和打印功能。
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 10 // 静态链表的最大容量// 定义静态链表节点结构体
typedef struct {int data; // 数据int next; // 游标，指向下一个节点的下标
} Node;Node list[MAX_SIZE]; // 静态链表数组
int head; // 头节点下标
int freeListHead; // 空闲链表的头节点下标// 初始化静态链表
void InitList() {// 初始化空闲链表for (int i = 0; i < MAX_SIZE - 1; i++) {list[i].next = i + 1; // 每个节点指向下一个节点}list[MAX_SIZE - 1].next = -1; // 最后一个节点的游标为 -1freeListHead = 0; // 空闲链表的头节点下标为 0// 初始化静态链表head = -1; // 头节点初始化为 -1
}// 从空闲链表中分配一个节点
int MallocNode() {if (freeListHead == -1) {return -1; // 空闲链表为空，分配失败}int newNodeIndex = freeListHead; // 分配空闲链表的头节点freeListHead = list[freeListHead].next; // 更新空闲链表的头节点return newNodeIndex;
}// 将节点放回空闲链表
void FreeNode(int index) {list[index].next = freeListHead; // 将节点插入空闲链表的头部freeListHead = index; // 更新空闲链表的头节点
}// 在链表头部插入节点
void InsertHead(int value) {int newNodeIndex = MallocNode(); // 分配一个新节点if (newNodeIndex == -1) {printf("链表已满，无法插入新节点\n");return;}list[newNodeIndex].data = value; // 设置新节点的数据list[newNodeIndex].next = head; // 新节点指向原来的头节点head = newNodeIndex; // 更新头节点
}// 删除链表中指定值的节点
void DeleteNode(int value) {int prev = -1; // 前一个节点的下标int current = head;while (current != -1) {if (list[current].data == value) {if (prev == -1) {// 如果要删除的是头节点head = list[current].next;} else {// 如果要删除的是中间或尾节点list[prev].next = list[current].next;}FreeNode(current); // 将被删除的节点放回空闲链表return;}prev = current;current = list[current].next;}printf("未找到要删除的节点\n");
}// 查找链表中指定值的节点
int FindNode(int value) {int current = head;while (current != -1) {if (list[current].data == value) {return current; // 找到目标节点}current = list[current].next;}return -1; // 未找到目标节点
}// 打印链表
void PrintList() {int current = head;printf("链表内容：");while (current != -1) {printf("%d -> ", list[current].data);current = list[current].next;}printf("NULL\n");
}int main() {InitList(); // 初始化静态链表// 插入节点InsertHead(10); // 在头部插入 10InsertHead(20); // 在头部插入 20InsertHead(30); // 在头部插入 30PrintList(); // 打印链表// 删除节点DeleteNode(20); // 删除值为 20 的节点PrintList(); // 打印链表// 查找节点int index = FindNode(30);if (index != -1) {printf("找到节点：%d，下标：%d\n", list[index].data, index);} else {printf("未找到节点\n");}return 0;
}静态链表的使用场景
-
内存受限的场景：比如嵌入式系统，无法动态分配内存。
-
固定大小的数据存储：比如实现一个固定大小的任务队列。
-
文件系统：某些文件系统用静态链表来管理磁盘块。
图片介绍
下面是一个静态链表的示意图：
头节点下标：1 空闲链表头节点下标：3数组下标：0 1 2 3 4 5 数据： [_, 20, 10, _, _, _] 游标： [2, 2, -1, 4, 5, -1]
-
数组下标表示节点的位置。
-
数据存储实际的值，游标指向下一个节点的下标。
-
空闲链表管理未使用的数组空间。
应用实例：任务调度器
任务调度器可以用静态链表实现：
-
任务队列：用静态链表存储待执行的任务。
-
空闲链表：管理未使用的任务槽。
-
插入任务：从空闲链表中分配一个节点，插入到任务队列。
-
删除任务：将已完成的任务放回空闲链表。
总结
静态链表是一种用数组模拟链表的数据结构，适合内存受限的场景。虽然它的灵活性不如动态链表，但在某些场景下非常高效。希望通过这篇文章，你能轻松掌握静态链表！