C++实现静态链表

C++实现静态链表

什么是静态链表

静态链表是使用数组实现的链表结构，也可以叫做顺序链表。使用静态链表可以避免频繁在内存中进行动态分配和释放，提高程序的运行效率。

静态链表的主要特点：

• 需要预分配一定数量的内存空间作为链表节点存储空间，因此具有固定的空间大小
• 通过数组下标和指针进行节点之间的链接
• 静态链表节点中需要额外存储指向下一个节点的指针

静态链表基本实现思路

在C++中，可以使用结构体来定义静态链表的节点，然后使用数组存储节点。定义一个静态链表时，需要预先定义好链表的长度和节点结构体。

例如：

struct Node {
    int data;
    int next;
};

const int MAX_SIZE = 1000; // 链表可以存储的最大节点数量

int head, cnt;
Node list[MAX_SIZE]; // 静态链表所使用的数组

上述代码表示了一个最多可以存储1000个节点的静态链表，并使用Node结构体来定义节点，其中data是数据域，表示节点存储的数据，next是链域，存储指向下一个节点的指针。

同时定义head为头指针，cnt为当前链表中已存储的节点数量。

接下来，需要编写相应的操作方法来实现静态链表的基本功能，包括插入节点、删除节点、输出链表等操作。

静态链表操作方法实现

插入节点

在静态链表中插入一个节点，需要将新的节点插入到链表的适当位置，同时修改相应的指针连接。插入节点的方法可以定义为：

void insert(int pos, int data) {
    if(cnt == MAX_SIZE) { // 静态链表已满
        return;
    }

    int cur = head;
    for(int i = 0; i < pos - 1; i++) {
        cur = list[cur].next; // 找到插入位置的前一个节点
    }

    int tmp = list[cur].next;
    list[cur].next = cnt; // 修改前一个节点的指向
    list[cnt].data = data;
    list[cnt].next = tmp; // 新节点指向原插入位置的后一个节点
    cnt++; // 链表长度加一
}

上述代码中，首先判断链表是否已满，如果已满则不执行插入节点操作。然后查找插入节点的前一个节点，然后修改前一个节点和当前节点的指向即可。新节点的下标即为当前链表长度cnt。

删除节点

在静态链表中删除一个节点，需要找到要删除节点的前一个节点，然后修改相应的指针连接。删除节点的方法可以定义为：

void erase(int pos) {
    if(pos <= 0 || pos > cnt) { // pos非法
        return;
    }

    int cur = head;
    for(int i = 1; i < pos; i++) {
        cur = list[cur].next; // 找到要删除节点的前一个节点
    }

    int tmp = list[cur].next;
    list[cur].next = list[tmp].next; // 修改前一个节点的指向
    cnt--; // 链表长度减一
}

上述代码中，首先判断pos是否合法，然后查找要删除的节点的前一个节点，修改前一个节点和要删除节点的指向即可。

输出链表

输出静态链表的方法可以定义为：

void print() {
    int cur = list[head].next;
    while(cur != 0) {
        cout << list[cur].data << " ";
        cur = list[cur].next;
    }
    cout << endl;
}

上述代码中，从head指针指向的第一个节点开始遍历，依次输出每一个节点的数据。

示例操作

下面我们来使用insert和erase方法分别在链表的头部和尾部插入和删除一个节点，并输出链表。

#include <iostream>
using namespace std;

struct Node {
    int data;
    int next;
};

const int MAX_SIZE = 1000;
int head, cnt;
Node list[MAX_SIZE];

void insert(int pos, int data);
void erase(int pos);
void print();

int main() {
    head = 0;
    cnt = 1;
    list[0].next = 0; // 头结点的下一个节点指向0，表示链表为空

    insert(1, 1); // 在头部插入一个节点，值为1
    insert(2, 2); // 在尾部插入一个节点，值为2
    print();

    erase(1); // 删除链表头部的节点
    erase(cnt); // 删除链表尾部的节点
    print();

    return 0;
}

void print() {
    int cur = list[head].next;
    while(cur != 0) {
        cout << list[cur].data << " ";
        cur = list[cur].next;
    }
    cout << endl;
}

void insert(int pos, int data) {
    if(cnt == MAX_SIZE) {
        return;
    }

    int cur = head;
    for(int i = 0; i < pos - 1; i++) {
        cur = list[cur].next;
    }

    int tmp = list[cur].next;
    list[cur].next = cnt;
    list[cnt].data = data;
    list[cnt].next = tmp;
    cnt++;
}

void erase(int pos) {
    if(pos <= 0 || pos > cnt) {
        return;
    }

    int cur = head;
    for(int i = 1; i < pos; i++) {
        cur = list[cur].next;
    }

    int tmp = list[cur].next;
    list[cur].next = list[tmp].next;
    cnt--;
}

运行上述程序，输出的结果为：

1 2 
2 

上述结果表示，在插入了节点1和节点2之后，链表中有两个节点，分别存储了1和2的值。删除对应节点后，链表中只剩一个节点，存储了2的值。