详解数据结构线性表 c++实现

线性表

线性表是一种非常基础且重要的数据结构，它是具有相同数据类型的 n（n≥0）个数据元素的有限序列。这里的 “有限” 意味着元素的数量是确定的，“序列” 则表示元素之间存在着顺序关系。

顺序表

顺序表是线性表的一种顺序存储结构，它使用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的长度是固定的，后期不能增长

初始化
初始化操作是创建一个空的线性表，为后续的操作做好准备。

class SequenceList {
public:
    explicit SequenceList(size_t size)
        : _maxSize(size), _data(new int[size])
    { }
    ~SequenceList() { }
private:
    int *_data;
    size_t _size{0}, _maxSize;
};

_size表示当前有多少数据，_maxSize表示最多能放多少个数据，*_data表示数组的头指针

插入
插入操作是在指定位置插入一个新的元素。对于顺序表，插入操作可能需要移动大量的元素。插入操作的平均时间复杂度为 O(n)（顺序表）。

判断插入位置i是否合法（i>=1&&i<=_maxSize）,若不合法返回ERROR。
判断顺序表的存储空间是否已满，若满则返回ERROR。
将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时无需移动）。
将要插入的新元素e放入第i个位置。
表长加1。

bool push_back(int value) {
    if (_size == _maxSize) return false;
    _data[_size] = value;
    _size++;
    return true;
}
bool insert(size_t index, int value) {
	if (_size == _maxSize) return false;
    if (index >= 1 && index <= _maxSize) return false;
    if (index > _size) return push_back(value);
    for (int i = _size; i >= index; i--) {
        _data[i] = _data[i - 1];
    }
    _data[index - 1] = value;
    _size++;
    return true;
}

删除
删除操作是删除指定位置的元素。对于顺序表，删除操作可能需要移动大量的元素。删除操作的平均时间复杂度为 O(n)（顺序表）

判断删除位置是否合法（i>=1&&i<=n）,若不合法则返回ERROR。
将第i+1个至第n个元素依次向前移动一个位置（i=n时无需移动）
表长减1

bool removeValue(int value){
    for (size_t i = 0; i < _size; i++){
        if (_data[i] == value){
            removeIndex(i + 1);
            return true;
        }
    }
    return false;
}
bool removeIndex(size_t index){
    if (_maxSize < index) return false;
    if (index > _size) return false;
    for (int i = index - 1; i < _size; i++){
        _data[i] = _data[i + 1];
    }
    _size--;
    return true;
}

链表

链表（Linked List）是一种通过 指针（或引用） 将 零散的内存块 串联起来的线性数据结构。与顺序表（数组）不同，链表不需要连续的内存空间，而是通过每个节点保存数据和 指向下一个节点的指针 来维护逻辑上的顺序关系。链表的内存是动态分配的，可以按需扩展或收缩，避免了顺序表扩容的代价。每个节点只占用必要的内存，没有闲置空间。

struct ListNode
{
    ListNode* next;
    int data;
    ListNode(int d, ListNode* n = nullptr)
        :data(d), next(n) {}
};

上面定义了一个名为ListNode的结构体，它代表链表中的一个节点。next是一个指向ListNode类型的指针，用于指向下一个节点。data是一个整数类型的变量，用于存储节点的数据。

class LinkedList {
public:
    LinkedList()
         : _root(new ListNode(0))
    {}
    ~LinkedList(){
		ListNode* temp = _root;
	    while (temp) {
	        ListNode* next = temp->next;
	        delete temp;
	        temp = next;
	    }
	}
private:
    ListNode* _root;
};

类中定义了变量_root是一个指向ListNode类型的指针，它是链表的头节点。在构造函数中，通过new ListNode(0)创建了一个值为 0 的头节点。这里我们头节点的数据代表链表的长度

    bool insert_back(int value){
        ListNode* node = new ListNode(value);
        if (node == nullptr) return false;
        ListNode* temp = _root;
        while(temp->next){
            temp = temp->next;
        }
        temp->next = node;
        _root->data++;
        return true;
    }
    bool insert(size_t inxde, int value){
        if (inxde == 0) return false;
        if (inxde > _root->data) return insert_back(value);
        ListNode* temp = _root;
        for (int i = 0; i < inxde; i++){
            temp = temp->next;
        }
        ListNode* node = new ListNode(value, temp->next);
        temp->next = node;
        _root->data++;
        return true;
    }

检查inxde是否为 0，如果是则返回false，因为不允许在位置 0 插入（头节点之后才是有效位置）。
检查inxde是否大于链表的长度（即_root->data），如果是则调用insert_back函数将元素插入到链表尾部。
使用temp指针从_root开始遍历链表，直到找到第inxde个节点。
创建一个新节点node，并将其next指针指向temp->next。
将temp的next指针指向新节点node。
增加头节点的data成员，用于记录链表的长度。
返回true表示插入成功。

    bool remove(size_t inxde){
        if (inxde == 0 || inxde > _root->data) return false;
        ListNode* temp = _root;
        for (int i = 1; i < inxde; i++){
            temp = temp->next;
        }
        ListNode* node = temp->next;
        temp->next = node->next;
        delete node;
        _root->data--;
        return true;
    }

检查inxde是否为 0 或大于链表的长度（即_root->data），如果是则返回false。
使用temp指针从_root开始遍历链表，直到找到第inxde - 1个节点。
用node指针指向要删除的节点（即temp->next）。
将temp的next指针指向node->next，跳过要删除的节点。
使用delete关键字释放node所指向的内存。
减少头节点的data成员，用于记录链表的长度。
返回true表示删除成功。

单链表：每个节点只包含指向下一个节点的指针。
双向链表：节点包含前驱和后继指针，支持双向遍历。
循环链表：尾节点指向头节点，形成闭环。

秒客网

详解数据结构线性表 c++实现

线性表

顺序表

链表

相关文章