线性表的逻辑结构
线性表是由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;
}
