用c++语言写一个静态链表

以下是一个简单的静态链表的 C 语言实现，包括添加、删除、查找和输出链表的功能。

#include <stdio.h>

#define MAX_SIZE 100 // 定义链表的最大长度

typedef struct {
    int data; // 数据域
    int next; // 指针域，指向下一个节点
} Node;

Node list[MAX_SIZE]; // 静态链表
int head; // 头节点的下标

int initList() {
    // 初始化链表，将所有节点的 next 值都指向下一个节点
    for (int i = 0; i < MAX_SIZE; i++) {
        list[i].next = i + 1;
    }
    list[MAX_SIZE - 1].next = -1; // 最后一个节点的 next 值为 -1，表示链表结束
    head = -1; // 头节点的下标为 -1，表示当前链表为空
    return 1;
}

int addNode(int data) {
    int index = list[0].next; // 获取第一个可用节点的下标
    if (index == -1) {
        printf("链表已满，添加失败！\n");
        return 0;
    }
    list[0].next = list[index].next; // 将第一个可用节点指向下一个可用节点
    list[index].data = data; // 设置新节点的数据域
    list[index].next = head; // 将新节点指向头节点
    head = index; // 将头节点指向新节点
    printf("节点 %d 添加成功！\n", data);
    return 1;
}

int deleteNode(int data) {
    if (head == -1) {
        printf("链表为空，删除失败！\n");
        return 0;
    }
    int index = head; // 从头节点开始查找
    int pre = -1; // 记录当前节点的前一个节点的下标
    while (index != -1 && list[index].data != data) {
        pre = index;
        index = list[index].next;
    }
    if (index == -1) {
        printf("节点 %d 不存在，删除失败！\n", data);
        return 0;
    }
    if (pre == -1) {
        head = list[index].next; // 删除的是头节点，更新头节点
    } else {
        list[pre].next = list[index].next; // 删除的是中间节点，更新前一个节点的指针
    }
    list[index].next = list[0].next; // 将删除的节点指向下一个可用节点
    list[0].next = index; // 更新第一个可用节点的下标
    printf("节点 %d 删除成功！\n", data);
    return 1;
}

int searchNode(int data) {
    int index = head; // 从头节点开始查找
    while (index != -1 && list[index].data != data) {
        index = list[index].next;
    }
    if (index == -1) {
        printf("节点 %d 不存在！\n", data);
        return 0;
    }
    printf("节点 %d 的位置为 %d\n", data, index);
    return 1;
}

int printList() {
    if (head == -1) {
        printf("链表为空！\n");
        return 0;
    }
    printf("链表内容为：");
    int index = head;
    while (index != -1) {
        printf("%d ", list[index].data);
        index = list[index].next;
    }
    printf("\n");
    return 1;
}

int main() {
    initList();
    addNode(1);
    addNode(2);
    addNode(3);
    printList();
    searchNode(2);
    deleteNode(2);
    printList();
    return 0;
}

在这个实现中，我们使用一个数组来模拟链表。数组的每个元素代表一个节点，包括数据域和指针域。头节点的下标用变量 `head` 来记录，初始值为 -1，表示链表为空。第一个可用节点的下标用数组的第一个元素 `list[0].next` 来记录，初始值为 0，表示第一个可用节点为数组的第一个元素。每插入一个节点，我们都需要更新头节点和第一个可用节点的下标。

在插入、删除和查找节点时，我们都需要从头节点开始遍历整个链表，直到找到目标节点或者遍历到链表的末尾。因为静态链表的节点是固定的，所以查找效率比较低，但是插入和删除节点的效率比较高。