1 线性表定义

零个或者多个数据元素的有限序列

2 线性表抽象数据类型

ADT 线性表
DATA
T elem[100]; // T 表示C++模板
int len;
Operation
// 添加: 插入到指定的位置
void add(int location, T value);
// 添加: 从最前面插入
void addFirst(T value);
// 添加: 从最后面插入
void addLast(T value);

// 删除: 删除指定位置的元素
void removeLocation(int location);
// 删除: 删除指定元素
void removeValue(T value);

// 查找: 查找指定位置的值
T getValue(int location);
// 查找: 根据具体的值查找位置
int getLocation(T value);

// 清空:
void clear();

3 线性表顺序储存结构

3.1 什么是顺序存储结构

指用一段地址连续的存储单元依次存储线性表的数据元素

3.2 顺序存储的方式

1. 一维数组来实现顺序存储结构

2. 顺序存储结构需要的3个属性

   • 存储空间起始位置

   • 线性表最大存储容量

   • 线性表当前的长度

3.3 数据长度和线性表长度的区别

• 数据的长度是指存放在线性表的存储空间的长度(存储分配后，这个变量一般是不变的)
• 线性表的长度是指线性表中数据元素的个数(随着线性表添加、删除、清空等操作变化而变化)

4 线性表存储结构的操作

• 获取数据元素根据具体的值获取所在线性表中的位置或者根据在线性表中的位置获取具体的值

template<typename T>
int Vector<T>::getLocation(T value) {
    for (int i = 0; i < this->len; i++) {
        if (this->elem[i] == value) {
            return i;
        }
    }
    return -1;
}
template<typename T>
T Vector<T>::getValue(int location) {
    if (location >= this->len) {
        return NULL;
    }
    return this->elem[location];
}

• 添加数据元素在线性表尾添加数据元素，在线性表头添加数据元素或者在线性表指定位置添加数据元素

template<typename T>
void Vector<T>::addLast(T value) {
    this->elem[this->len] = value;
    this->len++;
}
template<typename T>
void Vector<T>::addFirst(T value) {
    for (int i = this->len; i >= 0; i--) {
        this->elem[i + 1] = this->elem[i];
    }
    this->elem[0] = value;
    this->len++;
}
template<typename T>
void Vector<T>::add(int location, T value) {
    for (int i = this->len; i >= location; i--) {
        this->elem[i + 1] = this->elem[i];
    }
    this->elem[location] = value;
    this->len++;
}

• 删除数据元素删除线性表中指定位置的数据元素或者根据具体的数据元素删除第一个匹配的值

template<typename T>
void Vector<T>::removeLocation(int location) {
    if (location >= this->len) {
        return;
    }
    for (int i = location; i < this->len; i++) {
        this->elem[i] = this->elem[i + 1];
    }
    this->len--;
}
template<typename T>
void Vector<T>::removeValue(T value) {
    int ret = this->getLocation(value);
    if (ret < 0) {
        return;
    }
    for (int i = ret; i < this->len; i++) {
        this->elem[i] = this->elem[i + 1];
    }
    this->len--;
}

• 清空数据元素清空相应的数据元素

template<typename T>
void Vector<T>::clear() {
    for (int i = 0; i < this->len; i++) {
        this->elem[i] = this->elem[this->len + 1];
    }
    this->len = 0;
}