c语言

c语言静态链表是什么

小樊
83
2024-09-08 22:49:18
栏目: 编程语言

静态链表(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,用于存储当前未被使用的节点。在插入新节点时,我们首先从空闲节点列表中分配一个节点,然后将其插入到静态链表中。在删除节点时,我们将其添加回空闲节点列表。

0
看了该问题的人还看了