C语言实现静态链表

什么是静态链表

静态链表是一种数组表示链表结构的方法。它本质上是一个数组，但数组的每个元素都拥有两个属性：data 和 next。其中 data 属性保存了该节点的数据，next 属性则保存了指向下一个节点在数组中的下标。

如何实现静态链表

静态链表的实现步骤如下：

1. 创建一个数组作为静态链表的容器
2. 定义一个变量 head 作为链表的头节点
3. 对于每个节点，定义一个结构体，其包含两个属性： data 和 next
4. 按照顺序，将每个节点依次存储到数组中
5. 将每个节点的 next 属性设置为下一个节点在数组中的下标，最后一个节点设置为 -1 表示链表的结尾

下面是一个示例代码，用于创建一个静态链表，并输出其中的元素：

#include <stdio.h>

#define MAX_SIZE 100

typedef struct{
    int data;
    int next;
} Node;

Node list[MAX_SIZE];
int head;

/**
 * 在静态链表的末尾添加一个节点
 * @param data 新节点的数据
 */
void addNode(int data){
    // 找到链表的末尾
    int i = head;
    while(list[i].next != -1){
        i = list[i].next;
    }

    // 在链表末尾插入新节点
    int j = 0;
    for(j=0; j<MAX_SIZE; j++){
        if(list[j].next == -2){
            break;
        }
    }
    list[j].data = data;
    list[j].next = -1;
    list[i].next = j;
}

/**
 * 输出静态链表中的所有数据
 */
void printList(){
    printf("当前链表中的元素：\n");
    int i = head;
    while(list[i].next != -1){
        printf("%d ", list[i].data);
        i = list[i].next;
    }
    printf("%d\n", list[i].data);
}

int main(){
    // 初始化链表
    int i;
    for(i=0; i<MAX_SIZE; i++){
        list[i].next = -2;
    }
    head = 0;
    list[0].next = -1;

    // 往链表中添加元素
    addNode(1);
    addNode(2);
    addNode(3);

    // 输出链表中所有元素
    printList();

    return 0;
}

在上面的示例代码中，我们首先定义了一个结构体 Node，其包含两个属性：data 和 next。然后我们定义了一个静态数组 list，其元素为 Node 结构体。

接着，在 main() 函数中，我们先初始化了链表头 head，将链表头节点的 next 属性设置为 -1。然后，我们使用 addNode() 函数往静态链表中添加元素，该函数会将新元素插入到链表末尾。最后，我们调用 printList() 函数，输出整个链表中的所有元素。

两个示例说明

示例一：从后往前输出链表

下面给出一个示例代码，用于从后往前输出静态链表中的所有元素：

/**
 * 从后往前输出静态链表中的所有元素
 */
void printListReverse(){
    printf("当前链表中的元素（反向）：\n");

    // 找到链表的末尾
    int i = head;
    while(list[i].next != -1){
        i = list[i].next;
    }

    // 从末尾往前遍历链表
    while(i != head){
        int j = head;
        while(list[j].next != i){
            j = list[j].next;
        }
        printf("%d ", list[i].data);
        i = j;
    }
    printf("%d\n", list[i].data);
}

在 printListReverse() 函数中，我们首先找到静态链表的末尾。然后，从末尾往前遍历链表，直到链表头。在遍历中，每次从 head 开始查找下一个节点，直到找到指向当前节点的节点。最后，输出当前节点的数据。

示例二：删除链表中的元素

下面给出一个示例代码，用于从静态链表中删除元素：

/**
 * 从静态链表中删除指定数据的节点
 * @param data 待删除的数据
 */
void removeNode(int data){
    int i = head;
    while(list[i].next != -1){
        if(list[list[i].next].data == data){
            int j = list[i].next;
            list[i].next = list[j].next;
            list[j].next = -2;
        } else {
            i = list[i].next;
        }
    }
}

在 removeNode() 函数中，我们首先从链表头开始遍历链表，寻找待删除节点的前一个节点。如果找到，就将其指向待删除节点的指针改为指向待删除节点的下一个。最后，将待删除节点的 next 属性设置为 -2，表示该节点已经被删除。