1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110

/**************************************************************** 
 * Description: 静态链表,用过的结点要回收
 * Author: Alex Li
 * Date: 2022-08-04 11:22:42
 * LastEditTime: 2024-08-05 19:39:49
****************************************************************/
#include <iostream>
using namespace std;

const int N = 100010; // 定义常量N，表示数组的最大长度
int n = 0; // 当前链表节点数
int node[N], node_next[N]; // 分别存储节点的值和下一个节点的下标
int head, idx; // 头节点下标和当前可用的节点下标
int free_list_head; // 空闲链表的头节点

// 初始化链表
void init(){
    head = -1; // 初始头节点下标设为-1
    idx = 0; // 初始可用节点下标设为0
    free_list_head = -1; // 初始空闲链表头节点设为-1
}

// 从空闲链表中获取一个空闲下标
int get_free_index() {
    if (free_list_head == -1) {
        return idx++; // 如果空闲链表为空，返回当前可用下标并自增
    } else {
        int free_idx = free_list_head; // 获取空闲链表的头节点
        free_list_head = node_next[free_list_head]; // 更新空闲链表头节点
        return free_idx; // 返回空闲下标
    }
}

// 将x插入到头节点上
void firstNode(int x){
    int new_idx = get_free_index(); // 获取一个空闲下标
    node[new_idx] = x; // 在该下标处插入节点值x
    node_next[new_idx] = head; // 当前节点的next指向之前的头节点
    head = new_idx; // 更新头节点下标为当前节点下标
    n++; // 节点数加1
}

// 将x插入到下标为k的点的后面
void add(int k, int x){
    int new_idx = get_free_index(); // 获取一个空闲下标
    node[new_idx] = x; // 在该下标处插入节点值x
    node_next[new_idx] = node_next[k]; // 当前节点的next指向下标为k节点的下一个节点
    node_next[k] = new_idx; // 更新下标为k节点的next指向当前节点下标
    n++; // 节点数加1
}

// 删除下标为k的节点的后一个节点
void remove(int k){
    if (node_next[k] != -1) { // 确保k节点后面有节点
        int remove_idx = node_next[k]; // 获取要删除节点的下标
        node_next[k] = node_next[remove_idx]; // 更新k节点的next指向被删除节点的next
        node_next[remove_idx] = free_list_head; // 将被删除节点插入到空闲链表的头部
        free_list_head = remove_idx; // 更新空闲链表头节点
        n--; // 节点数减1
    }
}

// 打印链表中的所有节点
void printNode(){
    int i = head; // 从头节点开始
    while (i != -1) { // 遍历链表直到末尾
        cout << node[i] << " "; // 打印当前节点值
        i = node_next[i]; // 移动到下一个节点
    }
    cout << endl;
}

int main(){
    int k, option, position, value;
    init(); // 初始化链表
    do {
        cout << "请选择要执行的操作，输入选项编号：" << endl;
        cout << "0. 退出" << endl;
        cout << "1. 插入头节点" << endl;
        cout << "2. 插入新节点" << endl;
        cout << "3. 删除节点" << endl;
        cout << "4. 打印链表" << endl;
        cin >> option; // 输入选项编号
        switch (option) {
            case 0: 
                break;
            case 1: 
                cout << "输入头节点的值：" << endl; 
                cin >> value; 
                firstNode(value); 
                break; 
            case 2: 
                cout << "输入新节点的位置（插入到k后面）和值：" << endl;
                cin >> k >> value;
                add(k, value); 
                break; 
            case 3:
                cout << "输入要删除的节点位置：" << endl;
                cin >> k;
                remove(k);
                break; 
            case 4: 
                printNode();
                break;
            default: 
                cout << "请输入正确的选项编号" << endl;
        } 
    } while (option != 0); 
    return 0;
}