C++线性表详解（从零开始掌握线性表基础实现）

线性表的两种主要实现方式

在C++中，线性表通常有两种实现方式：

• 顺序存储（数组实现）：使用连续的内存空间存储元素，支持随机访问。
• 链式存储（链表实现）：通过指针连接各个节点，不要求连续内存。

本教程将重点讲解顺序存储方式，也就是基于数组的线性表实现。

动手实现一个C++线性表

我们将创建一个名为 LinearList 的类，支持以下基本操作：

• 插入元素
• 删除元素
• 查找元素
• 获取长度
• 打印所有元素

1. 定义类结构

#include <iostream>#include <stdexcept> // 用于异常处理const int MAX_SIZE = 100; // 最大容量class LinearList {private:    int data[MAX_SIZE];   // 存储数据的数组    int length;           // 当前元素个数public:    LinearList();                     // 构造函数    bool insert(int index, int value); // 在指定位置插入    bool remove(int index);            // 删除指定位置元素    int find(int value);               // 查找元素，返回索引    int getLength() const;             // 获取当前长度    void print() const;                // 打印所有元素};

2. 实现构造函数和其他方法

// 构造函数：初始化长度为0LinearList::LinearList() : length(0) {}// 插入元素bool LinearList::insert(int index, int value) {    if (length >= MAX_SIZE) {        std::cout << "线性表已满！\n";        return false;    }    if (index < 0 || index > length) {        std::cout << "插入位置无效！\n";        return false;    }    // 将index之后的元素后移    for (int i = length; i > index; --i) {        data[i] = data[i - 1];    }    data[index] = value;    ++length;    return true;}// 删除元素bool LinearList::remove(int index) {    if (index < 0 || index >= length) {        std::cout << "删除位置无效！\n";        return false;    }    // 将index之后的元素前移    for (int i = index; i < length - 1; ++i) {        data[i] = data[i + 1];    }    --length;    return true;}// 查找元素int LinearList::find(int value) {    for (int i = 0; i < length; ++i) {        if (data[i] == value) {            return i; // 返回首次出现的位置        }    }    return -1; // 未找到}// 获取长度int LinearList::getLength() const {    return length;}// 打印所有元素void LinearList::print() const {    if (length == 0) {        std::cout << "线性表为空！\n";        return;    }    for (int i = 0; i < length; ++i) {        std::cout << data[i] << " ";    }    std::cout << "\n";}

3. 测试我们的线性表

int main() {    LinearList list;    // 插入元素    list.insert(0, 10);    list.insert(1, 20);    list.insert(2, 30);    list.print(); // 输出: 10 20 30    // 查找元素    int pos = list.find(20);    if (pos != -1) {        std::cout << "20 位于位置: " << pos << "\n";    }    // 删除元素    list.remove(1);    list.print(); // 输出: 10 30    std::cout << "当前长度: " << list.getLength() << "\n";    return 0;}

总结

通过以上步骤，我们完成了一个基础但功能完整的C++线性表实现。这个实现虽然简单，但它涵盖了线性表的核心操作，是理解更复杂数据结构（如栈、队列、动态数组等）的基础。

对于初学者来说，建议多动手编写和调试代码，加深对线性表基础实现的理解。随着你对C++数据结构的掌握越来越深入，你会发现线性表是构建更高级算法和程序的基石。

希望这篇线性表教程能帮助你顺利入门C++数据结构！如果你有任何疑问，欢迎在评论区留言交流。