C++实现静态链表

#include <iostream>
using namespace std;

// 定义静态链表的最大容量
const int MAX_SIZE = 100;

// 节点类
class Node {
public:
    int data;  // 节点存储的数据
    int next;  // 节点指向下一个节点的索引（在数组中的位置）

    // 默认构造函数
    Node() : data(0), next(-1) {}
};

// 静态链表类
class StaticLinkedList {
private:
    Node nodes[MAX_SIZE]; // 存储链表节点的数组
    int head;             // 链表的头节点索引
    int freeIndex;        // 可用节点的索引

public:
    // 构造函数，初始化静态链表
    StaticLinkedList() {
        head = -1;           // 初始化头节点索引为 -1，表示链表为空
        freeIndex = 0;       // 自由节点的索引从0开始
        // 初始化所有节点的 next 为 -1，表示链表的末尾
        for (int i = 0; i < MAX_SIZE; ++i) {
            nodes[i].next = -1;
        }
    }

    // 检查链表是否为空
    bool isEmpty() const {
        return head == -1;
    }

    // 检查链表是否已满
    bool isFull() const {
        return freeIndex >= MAX_SIZE;
    }

    // 插入节点到链表末尾
    void append(int value) {
        if (isFull()) {
            cout << "链表已满，无法插入新节点" << endl;
            return;
        }

        int newNodeIndex = freeIndex; // 获取新节点的索引
        nodes[newNodeIndex].data = value;   // 设置节点数据
        nodes[newNodeIndex].next = -1;      // 新节点的 next 设为 -1（即链表末尾）

        if (isEmpty()) {
            head = newNodeIndex; // 如果链表为空，新节点成为头节点
        }
        else {
            int current = head; // 从头节点开始遍历
            while (nodes[current].next != -1) {
                current = nodes[current].next; // 移动到下一个节点
            }
            nodes[current].next = newNodeIndex; // 将新节点连接到链表末尾
        }

        ++freeIndex; // 更新自由节点索引
    }

    // 删除链表中指定值的节点
    void deleteNode(int value) {
        if (isEmpty()) {
            cout << "链表为空，无法删除节点" << endl;
            return;
        }

        int current = head;
        int previous = -1;

        while (current != -1 && nodes[current].data != value) {
            previous = current;
            current = nodes[current].next;
        }

        if (current == -1) {
            cout << "未找到值为 " << value << " 的节点" << endl;
            return;
        }

        if (previous == -1) {
            head = nodes[current].next; // 删除的是头节点
        }
        else {
            nodes[previous].next = nodes[current].next; // 删除非头节点
        }

        // 将删除的节点放回自由节点数组
        nodes[current].next = freeIndex;
        freeIndex = current;
    }

    // 查找链表中是否存在指定值的节点
    bool search(int value) const {
        int current = head;
        while (current != -1) {
            if (nodes[current].data == value) {
                return true; // 找到节点
            }
            current = nodes[current].next; // 移动到下一个节点
        }
        return false; // 未找到节点
    }

    // 打印链表中的所有节点
    void display() const {
        if (isEmpty()) {
            cout << "链表为空" << endl;
            return;
        }

        int current = head;
        while (current != -1) {
            cout << nodes[current].data << " -> "; // 输出当前节点的数据
            current = nodes[current].next; // 移动到下一个节点
        }
        cout << "NULL" << endl; // 链表末尾
    }

    // 逆置链表
    void reverse() {
        if (isEmpty() || nodes[head].next == -1) {
            // 空链表或仅有一个节点，不需要逆置
            return;
        }

        int prev = -1;
        int current = head;
        int nextNode = nodes[current].next;

        while (current != -1) {
            nodes[current].next = prev; // 逆置当前节点的指针
            prev = current; // 移动 prev 到当前节点
            current = nextNode; // 移动到下一个节点
            if (current != -1) {
                nextNode = nodes[current].next; // 更新 next 指针
            }
        }

        head = prev; // 更新头节点为最后一个节点
    }
};

// 主函数
int main() {
    StaticLinkedList list; // 创建静态链表实例
    int choice, value;

    do {
        cout << "菜单:" << endl;
        cout << "1. 添加节点" << endl;
        cout << "2. 删除节点" << endl;
        cout << "3. 查找节点" << endl;
        cout << "4. 显示链表" << endl;
        cout << "5. 逆置链表" << endl;
        cout << "0. 退出" << endl;
        cout << "请输入您的选择: ";
        cin >> choice; // 获取用户选择

        switch (choice) {
        case 1:
            cout << "请输入要添加的值: ";
            cin >> value; // 获取用户输入的值
            list.append(value); // 调用添加函数
            break;
        case 2:
            cout << "请输入要删除的值: ";
            cin >> value; // 获取用户输入的值
            list.deleteNode(value); // 调用删除函数
            break;
        case 3:
            cout << "请输入要查找的值: ";
            cin >> value; // 获取用户输入的值
            if (list.search(value)) {
                cout << "值在链表中找到。" << endl;
            }
            else {
                cout << "值不在链表中。" << endl;
            }
            break;
        case 4:
            list.display(); // 调用显示函数
            break;
        case 5:
            list.reverse(); // 调用逆置函数
            cout << "链表已逆置。" << endl;
            break;
        case 0:
            cout << "退出程序。" << endl;
            break;
        default:
            cout << "无效选择，请重新输入。" << endl;
        }
    } while (choice != 0); // 用户选择0时退出

    return 0; // 返回0表示程序正常结束
}