线性表的定义及实现

线性表的逻辑结构

线性表是由n个类型相同的数据元素组成的有限序列，记为（a1，a2，…，ai-1，ai，ai+1，…，an）。其中，这里的数据元素可以是原子类型，也可以是结构类型。线性表的数据元素存在着序偶关系，即数据元素之间具有一定的次序。在线性表中，数据元素ai-1在ai的前面，ai又在ai+1的前面，可以把ai-1称为ai的直接前驱元素，ai称为ai+1的直接前驱元素。ai称为ai-1的直接后继元素，ai+1称为ai的直接后继元素。

image

在线性表中，除了第一个元素a1，每个元素有且仅有一个直接前驱元素；除了最后一个元素an，每个元素有且只有一个直接后继元素。

顺序表的插入：

image

顺序表的删除：

image

线性表中顺序表的实现（C++语言描述）：

#include <iostream>
#include <cstring>
using namespace std;

//自定义顺序表类Vector
class Vector {

//设置顺序表的size和length
//其中size是指顺序表的最大尺寸
//length是指顺序表中data的长度
private:
    int size, length;
    int *data;

public:

    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new int[size];
    }
    ~Vector() {
        delete[] data;
    }

    //在插入操作中，根据下标loc，插入value
    //插入后为保顺序，loc后的元素挨个向后偏移一个位置,切顺序表长度增加
    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;
}