C++ 实现静态链表的简单实例

C++ 实现静态链表的简单实例

静态链表是一种用数组模拟链表的数据结构，它可以在不施加缩容操作的情况下随时增长，且可以通过给数组预分配较大的内存空间来节省插入和删除元素时的内存分配操作。下面将介绍如何使用 C++ 实现静态链表，并给出实例说明。

静态链表的实现思路

静态链表由两个数组组成：数据数组和结点数组。结点数组用于描述结点之间的链接关系，数据数组则存储实际的数据。由于静态链表是数组模拟链表，因此需要在结点数组中维护一个指向下一个结点的指针索引，这个指针索引的取值范围是 [0, 数组长度 - 1]，其中当指针值为 0 时，表示链表的结尾。下面是静态链表的结点定义：

struct Node {
    int data; // 存储实际数据
    int next; // 存储下一个结点的索引
};

实现过程说明

下面是一个简单的使用 C++ 实现静态链表的过程：

1. 头文件中定义结点结构体

// list.h
#ifndef LIST_H
#define LIST_H

struct Node {
    int data; // 存储实际数据
    int next; // 存储下一个结点的索引
};

#endif

1. 实现静态链表类及其方法

// static_list.cpp
#include "list.h"

class StaticList {
public:
    StaticList(int max_size);
    ~StaticList();
    int insert(int index, int value);
    int remove(int index);
    int find(int value);
    void display();

private:
    Node *node_list_; // 结点数组
    int head_; // 链表头结点的索引
    int max_size_; // 结点数组的最大长度
    int size_; // 结点数组的当前长度
};

StaticList::StaticList(int max_size) {
    max_size_ = max_size;
    size_ = 0;
    node_list_ = new Node[max_size_];
    head_ = 0; // 链表初始为空，头结点的 next 指针为 0
    for (int i = 0; i < max_size_; i++) {
        node_list_[i].next = i + 1; // 每个结点的 next 指针指向下一个位置
    }
    node_list_[max_size_ - 1].next = 0; // 最后一个结点的 next 指针指向 0，表示链表结尾
}

StaticList::~StaticList() {
    if (node_list_ != nullptr) {
        delete[] node_list_;
        node_list_ = nullptr;
    }
}

int StaticList::insert(int index, int value) {
    // 链表已满，无法插入新结点
    if (size_ >= max_size_ - 1) {
        return -1;
    }
    // 插入位置不合法
    if (index < 0 || index > size_) {
        return -1;
    }
    int current_index = head_;
    int next_index = node_list_[current_index].next;
    int insert_index = 0;
    // 寻找要插入的结点的前一个结点 current_index 和 next_index
    for (int i = 0; i < index; i++) {
        current_index = next_index;
        next_index = node_list_[current_index].next;
    }
    // 获取一个新的结点插入到 current_index 和 next_index 之间
    insert_index = node_list_[max_size_ - 1].next;
    node_list_[max_size_ - 1].next = node_list_[insert_index].next;
    node_list_[insert_index].data = value;
    node_list_[insert_index].next = next_index;
    node_list_[current_index].next = insert_index;
    size_++;
    return 0;
}

int StaticList::remove(int index) {
    // 插入位置不合法
    if (index < 0 || index >= size_) {
        return -1;
    }
    int current_index = head_;
    int next_index = node_list_[current_index].next;
    // 寻找要删除的结点的前一个结点 current_index 和 next_index
    for (int i = 0; i < index; i++) {
        current_index = next_index;
        next_index = node_list_[current_index].next;
    }
    // 将要删除的结点从链表中去除，并将其放回缓存池中
    node_list_[current_index].next = node_list_[next_index].next;
    node_list_[next_index].next = node_list_[max_size_ - 1].next;
    node_list_[max_size_ - 1].next = next_index;
    size_--;
    return 0;
}

int StaticList::find(int value) {
    int current_index = head_;
    int next_index = node_list_[current_index].next;
    // 遍历整个链表，寻找值为 value 的结点
    while (next_index) {
        if (node_list_[next_index].data == value) {
            return next_index;
        }
        current_index = next_index;
        next_index = node_list_[current_index].next;
    }
    // 遍历完毕，未找到指定值的结点
    return 0;
}

void StaticList::display() {
    int current_index = head_;
    int next_index = node_list_[current_index].next;
    // 遍历整个链表，输出各个结点的值
    while (next_index) {
        std::cout << node_list_[next_index].data << " ";
        current_index = next_index;
        next_index = node_list_[current_index].next;
    }
    std::cout << std::endl;
}

示例说明

下面给出两个使用静态链表的实例：

1. 求 1~1000000 中所有质数的个数

#include "static_list.h"

bool is_prime(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    const int MAX_SIZE = 1000000;
    StaticList list(MAX_SIZE + 1);
    for (int i = 2; i <= MAX_SIZE; i++) {
        list.insert(i - 2, i);
    }
    int count = 0;
    for (int i = 2; i <= MAX_SIZE; i++) {
        int index = list.find(i);
        if (index) {
            count++;
            int current_index = index;
            int next_index = list.node_list_[current_index].next;
            while (next_index) {
                if (node_list_[next_index].data % i == 0) {
                    list.remove(next_index - 2);
                }
                current_index = next_index;
                next_index = list.node_list_[current_index].next;
            }
        }
    }
    std::cout << count << std::endl;
    return 0;
}

1. N 个人围成一圈，每 M 个人中选出一个，最后剩下的人的编号

#include "static_list.h"

int last_man_standing(int n, int m) {
    StaticList list(n);
    for (int i = 0; i < n; i++) {
        list.insert(i, i + 1);
    }
    int current_index = 0;
    int next_index = list.node_list_[current_index].next;
    while (next_index != current_index) {
        int count = m % list.size_;
        for (int i = 0; i < count - 1; i++) {
            current_index = next_index;
            next_index = list.node_list_[current_index].next;
        }
        list.remove(next_index);
        current_index = next_index;
        next_index = list.node_list_[current_index].next;
    }
    return next_index + 1;
}

int main() {
    std::cout << last_man_standing(10, 3) << std::endl; // 4
    return 0;
}

以上就是 C++ 实现静态链表的简单实例和攻略。