线性表

线性表是n个相同数据类型的元素组成的有限序列。
线性表按照存储结构可分为顺序表和链表。
顺序表都是内存地址连续的元素组成的！

顺序表的构建

• 定义元素个数和顺序表最大容量，初始化指针
• 在构造函数中传参来确定size；length设为0；初始化指针地址。

#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
    int size, length;
    int *data;
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new int[size];
    }
    ~Vector() {
        delete[] data;   // 析构函数中进行删除
    }
};
int main() {
    Vector a(2);
    return 0;
}

顺序表的插入:

在insert方法中定义了参数loc，value。loc为插入的位置，value代表插入的数值。每次插入都要将序列loc之后的元素向后移动一位，并且长度length增加1。成功返回true，否则false。

• 判断loc位置是否合法。位于0到length之间（包括length），有元素在序列上才可以进行插入，所以开始为空时要顺序插入。并且元素左右两边都可插入（所以位置为length时依然合法）。
• 判断元素个数是否超出最大容量（长度相等时就不能插入了，再插溢出）。
• 将loc（包括loc）之后的元素右移。
• 插入赋值。
• 元素个数加1。

在构造函数中添加insert方法

    bool insert(int loc, int value) {
        if(loc < 0 || loc > length){
        return false;
        }
        if (length >= size){
        return false;
        }
        
        for (int i = length; i > loc; i--){
            data[i] = data[i-1];
        }
        data[loc] = value;
        length += 1;
        return true;
    }

顺序表的扩容：

通产来说，扩容通常是将容量修改为以前的两倍；扩容时要重新开辟一块空间并把原有数据 依次 拷贝过去，再将原来的 空间 释放

• 保存原始数据到旧指针。
• 容量加倍。
• 指针指向新size开辟的新空间。
• 数据拷贝。
• 在insert中调用 回收

    bool insert(int loc, int value) {
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            //return false;
            expand();
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }
    void expand(){
        int *old_data = data
        size = size * 2;
        data = new int[size] ;
        
        for(int i = 0; i <length;i ++){
            data[i] = old_data[i];
       
    }
        delete[] old_data;
    }

顺序表的查找

接收一个int类型的value，返回该值对应的下表，没有返回－1

从零循环到小于length，枚举匹配：

int search(int value) {
        for(int i=0; i < length; i++){
            if (data[i] == value){
                return i
            }
        }
        return -1;
    }

顺序表的删除：index之后的元素向前移动一位。

• 判断index是否在元素中
• index之后的元素向前移动
• 元素个素减1，返回true

bool remove(int index) {
        if(index < 0 || index >= length){
            return false
        }
        for(int i = index + 1; i < length; i++){
            data[i-1] = data[i];
        }
        length -= 1;
        return true;
    }

顺序表的遍历

把顺序表的所有元素输出到一行，并用空格分开。

• 判断第一个元素，不要输出空格
• 循坏遍历输出

void print() {
        for(int i = 0; i<length; i++){
            if(i > 0){
                cout << " ";
            }
            cout << data[i];
        }
        cout << endl; //输出空行
    }

---

完整代码：

#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
    int size, length;
    int *data;
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new int[size];
    }
    ~Vector() {
        delete[] data;
    }
    bool insert(int loc, int value) {
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            return false;
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }
    int search(int value) {
        for (int i = 0; i < length; ++i) {
            if (data[i] == value) {
                return i;
            }
        }
        return -1;
    }
    bool remove(int index) {
        if (index < 0 || index >= length) {
            return false;
        }
        for (int i = index + 1; i < length; ++i) {
            data[i - 1] = data[i];
        }
        length = length - 1;
        return true;
    }
    void print() {
        for(int i = 0; i<length; i++){
            if(i > 0){
                cout << " ";
            }
            cout << data[i];
        }
        cout << endl
    }
};
int main() {
    Vector a(2);
    cout << a.insert(0, 1) << endl;
    cout << a.insert(0, 2) << endl;
    a.print();
    cout << a.remove(1) << endl;
    a.print();
    cout << a.search(0) << endl;
    cout << a.search(1) << endl;
    return 0;
}

引用：计蒜客