C++实现线性表链式存储（单链）

前言

线性表是数据结构中最基础、最常用的一种存储结构，它是由n个具有相同数据类型的元素构成的有序集合。线性表有两种主要的存储结构，即顺序存储和链式存储。本文将介绍使用C++实现线性表的链式存储（单链）。

代码实现

#include 

// 定义线性表节点结构
struct ListNode {
    int val; // 数据元素
    ListNode* next; // 指向下一个节点的指针
};

// 定义线性表类
class LinkedList {
private:
    ListNode* head; // 头指针，指向链表的第一个节点
    int size; // 线性表的大小

public:
    // 构造函数
    LinkedList() {
        head = nullptr; // 初始化头指针为空
        size = 0; // 初始大小为0
    }

    // 在链表末尾添加元素
    void add(int val) {
        ListNode* newNode = new ListNode;
        newNode->val = val;
        newNode->next = nullptr;

        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode* cur = head;
            while (cur->next != nullptr) {
                cur = cur->next;
            }
            cur->next = newNode;
        }

        size++;
    }

    // 在指定位置插入元素
    void insert(int index, int val) {
        if (index < 0 || index > size) {
            std::cout << "Invalid index." << std::endl;
            return;
        }

        if (index == 0) {
            ListNode* newNode = new ListNode;
            newNode->val = val;
            newNode->next = head;
            head = newNode;
        } else {
            ListNode* cur = head;
            for (int i = 0; i < index - 1; i++) {
                cur = cur->next;
            }

            ListNode* newNode = new ListNode;
            newNode->val = val;
            newNode->next = cur->next;
            cur->next = newNode;
        }

        size++;
    }

    // 删除指定位置的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            std::cout << "Invalid index." << std::endl;
            return;
        }

        if (index == 0) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        } else {
            ListNode* cur = head;
            for (int i = 0; i < index - 1; i++) {
                cur = cur->next;
            }

            ListNode* temp = cur->next;
            cur->next = temp->next;
            delete temp;
        }

        size--;
    }

    // 获取指定位置的元素
    int get(int index) {
        if (index < 0 || index >= size) {
            std::cout << "Invalid index." << std::endl;
            return -1;
        }

        ListNode* cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur->next;
        }

        return cur->val;
    }

    // 获取线性表的大小
    int getSize() {
        return size;
    }
};

代码分析

上述代码实现了一个简单的线性表（单链表），其中包括了常见的操作，如添加元素、插入元素、删除元素、获取元素、获取线性表大小等。以下是对代码中各个方法的功能和规范解释：

1. 构造函数：构造函数用于初始化线性表对象，将头指针设置为空指针，并将大小初始化为0。

2. add方法：在链表末尾添加元素。遍历链表找到最后一个节点，将新节点链接到最后一个节点的next指针上。如果链表为空，则将新节点作为头结点。

3. insert方法：在指定位置插入元素。首先需要进行合法性判断，如果位置超出范围，则输出错误信息。如果要在链表头插入元素，则直接插入并更新头指针；否则，需要遍历链表找到指定位置的前一个节点，将新节点链接到前一个节点和当前节点之间。

4. remove方法：删除指定位置的元素。同样需要进行合法性判断。如果要删除链表头节点，则更新头指针。否则，遍历链表找到指定位置的前一个节点，将前一个节点的next指针指向被删除节点的下一个节点，并释放被删除节点的内存。

5. get方法：获取指定位置的元素。同样需要进行合法性判断。遍历链表找到指定位置的节点，并返回其存储的元素值。

6. getSize方法：获取线性表的大小（即节点数量），直接返回私有成员变量size的值。

总结

通过以上代码实现，我们可以使用C++创建一个链式存储的线性表。该实现具备常见的操作功能，如添加元素、插入元素、删除元素和获取元素等。链表的插入和删除操作只需修改指针的链接，不需要移动元素，因此能够高效地支持动态增删操作。使用链式存储，可以灵活地管理和操作线性表中的元素。