静态链表(Static Linked List)是一种在程序运行时,链表的大小和结构不会发生变化的数据结构。它与动态链表相反,动态链表的大小和结构可以在运行时进行调整。
静态链表通常使用数组来实现,数组中的每个元素都包含两部分:数据域和指针域。数据域用于存储节点的数据,指针域用于存储指向下一个节点的索引。这里的“指针”实际上是一个整数,表示数组中的索引位置。
静态链表的主要优点是不需要动态分配内存,因此在内存管理方面更加简单和高效。但是,它的缺点是链表的大小和结构在编译时就已经确定,无法在运行时进行调整。
以下是一个简单的C语言静态链表实现示例:
#include<stdio.h>
#define MAX_SIZE 10 // 定义静态链表的最大容量
typedef struct {
int data; // 数据域
int next; // 指针域,存储下一个节点的索引
} Node;
Node staticLinkedList[MAX_SIZE]; // 定义一个静态链表,最多可以存储10个节点
int freeList[MAX_SIZE]; // 空闲节点列表
int freeCount = MAX_SIZE; // 空闲节点计数器
// 初始化静态链表
void initStaticLinkedList() {
for (int i = 0; i < MAX_SIZE; i++) {
freeList[i] = i;
staticLinkedList[i].next = -1;
}
}
// 分配一个新节点
int allocateNode() {
if (freeCount == 0) {
return -1; // 没有空闲节点可用
}
int index = freeList[freeCount - 1];
freeCount--;
return index;
}
// 释放一个节点
void freeNode(int index) {
freeList[freeCount] = index;
freeCount++;
}
// 在静态链表中插入一个新节点
void insertNode(int data, int position) {
int newIndex = allocateNode();
if (newIndex == -1) {
printf("No free node available.\n");
return;
}
staticLinkedList[newIndex].data = data;
staticLinkedList[newIndex].next = position;
for (int i = 0; i < MAX_SIZE; i++) {
if (staticLinkedList[i].next == position) {
staticLinkedList[i].next = newIndex;
break;
}
}
}
// 打印静态链表
void printStaticLinkedList() {
for (int i = 0; i < MAX_SIZE; i++) {
if (staticLinkedList[i].next != -1) {
printf("Node %d: data = %d, next = %d\n", i, staticLinkedList[i].data, staticLinkedList[i].next);
}
}
}
int main() {
initStaticLinkedList();
insertNode(1, 1);
insertNode(2, 2);
insertNode(3, 3);
printStaticLinkedList();
return 0;
}
这个示例中,我们定义了一个静态链表staticLinkedList
,最多可以存储10个节点。我们还定义了一个空闲节点列表freeList
,用于存储当前未被使用的节点。在插入新节点时,我们首先从空闲节点列表中分配一个节点,然后将其插入到静态链表中。在删除节点时,我们将其添加回空闲节点列表。