C++ 数据结构学习——线性表

1 总述

线性表是最简单且应用最广泛的一种数据结构，其基本特点是结构中各元素之间满足线性关系。所谓的线性关系是指数据元素之间存在一对一关系，即存在唯一的开始元素和唯一的终止元素。
线性结构拥有两个特点：均匀性和有序性

2 分类

按底层存储数据的方式可以分为两种，其一是定长的顺序存储结构，即顺序表；其二是变长的线性存储结构，即链表。
线性表的基本构成代码如下

template<typename T>
class List {
    // 清空线性表
    virtual void clear() = 0;
    // 判断线性表是否为空
    virtual bool isEmpty() = 0;
    // 获取线性表长度
    virtual uint size() = 0;
    // 向线性表末尾添加元素
    virtual bool append(const T &src) = 0;
    // 向线性表中间插入元素
    virtual bool insert(uint pos, const T &src) = 0;
    // 移除某一元素
    virtual bool remove(uint pos) = 0;
    // 获取某一元素
    virtual T &getValue(uint pos) = 0;
    // 设置某一元素
    virtual bool setValue(uint pos, const T &src) = 0;
    // 获取某个元素的下标
    virtual int getPos(const T &src) = 0;
    // 重载[]运算符
    virtual T &operator[](int pos) = 0;
    // 从start下标到end下标依次做opt处理
    virtual void forEach(uint start, uint end, void (*opt)(T &)) = 0;
};

所有的函数都被标记为纯虚函数，强制要求子类必须实现

2.1 顺序表

顺序表的特点是随机读取速度很快，所以我们读取数据写起来很简单

T &getValue(uint pos) override {
    if (pos >= length) return nullptr;
    return data[pos];
}
bool setValue(uint pos, const T &src) override {
    if (pos >= length) return false;
    data[pos] = src;
}
int getPos(const T &src) override {
    for (int i = 0; i < length; ++i) {
        if (data[i] == src) {
            return i;
        }
    }
    return -1;
}
T &operator[](int pos) override {
    if (pos >= length) return nullptr;
    return data[pos];
}

但是有得到就有失去，顺序表的短处就是插入数据，特别是在中间添加数据，对于顺序表来说要移动很多元素，当n->∞时，时间复杂度会爆炸。
代码如下

bool append(const T &src) override {
    if (length < capacity) {
        data[length++] = src;
        return true;
    }
    resize(capacity * 2);
    data[length++] = src;
    return true;
}
bool insert(uint pos, const T &src) override {
    if (pos >= capacity) return false;
    if (length >= capacity) {
        resize(capacity * 2);
    }
    for (int i = length - 1; i > pos + 1; --i) {
        data[i] = data[i - 1];
    }
    data[pos] = src;
    length++;
}
bool remove(uint pos) override {
    if (pos >= length) return false;
    for (int i = pos; i < length - 1; ++i) {
        data[i] = data[i + 1];
    }
    length--;
    if (length < capacity / 4 && capacity / 2 > ARRAY_MINIMUM_SIZE){
        resize(capacity / 2);
    }
}

还有一个特别的函数——ForEach
它运用了函数指针来对列表的每一个元素执行一定操作 （对没错就是std::any_of）

void forEach(uint start, uint end, void (*opt)(T &)) override {
    if (end > length) return;
    for (int i = start; i < end; ++i) {
        opt(data[i]);
    }
}