cpp线性表的代码实现

在C++中，线性表是一种基础的数据结构，通常可以使用数组（Array）或链表（Linked List）来实现。这里分别给出简单版本的数组和链表实现。

### 1. 数组实现 (动态数组 - std::vector)

#include <iostream>
#include <vector>

// 数组版本的线性表
class ArrayLinearList {
public:
    // 构造函数，初始化大小
    ArrayLinearList(size_t size) : data(size), capacity(size) {}

    // 添加元素到列表尾部，自动扩容
    void push_back(int value) {
        if (data.size() == capacity) {
            resize(capacity * 2);  // 扩容两倍
        }
        data.push_back(value);
    }

    // 访问指定索引的元素
    int get(int index) const {
        return data[index];
    }

private:
    std::vector<int> data;
    size_t capacity;  // 当前存储容量
    void resize(size_t new_capacity) {
        data.resize(new_capacity);
    }
};

int main() {
    ArrayLinearList list(5);
    list.push_back(1);
    list.push_back(2);
    std::cout << "Element at index 0: " << list.get(0) << std::endl;
    return 0;
}

### 2. 链表实现 (单向链表)

#include <iostream>

// 单向链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 链表版本的线性表
class LinkedListLinearList {
public:
    void push_back(int value) {
        ListNode* newNode = new ListNode(value);
        if (!head) {
            head = newNode;
        } else {
            ListNode* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 返回当前链表长度，如果为空则返回0
    size_t size() const {
        size_t count = 0;
        for (ListNode* node = head; node != nullptr; ++node, ++count) {}
        return count;
    }

private:
    ListNode* head;
};

int main() {
    LinkedListLinearList list;
    list.push_back(1);
    list.push_back(2);
    std::cout << "Length of the list: " << list.size() << std::endl;
    return 0;
}