静态链表(Static Linked List)是一种在程序运行时,链表的大小和结构不会发生变化的数据结构。它与动态链表相反,动态链表的大小和结构可以在运行时进行调整。
静态链表通常使用数组来实现,数组中的每个元素都包含两部分:数据域和指针域。数据域用于存储节点的数据,指针域用于存储指向下一个节点的索引。这里的“指针”实际上是一个整数,表示数组中的索引位置。
静态链表的主要优点是不需要动态分配内存,因此在内存管理方面更加简单和高效。但是,它的缺点是链表的大小和结构在编译时就已经确定,无法在运行时进行调整。
以下是一个简单的C语言静态链表实现示例:
#include#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 = https://www.yisu.com/ask/data;"Node %d: data = https://www.yisu.com/ask/%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
,用于存储当前未被使用的节点。在插入新节点时,我们首先从空闲节点列表中分配一个节点,然后将其插入到静态链表中。在删除节点时,我们将其添加回空闲节点列表。