一、顺序表的概念
1.1 线性表的定义
线性表是 n 个具有 相同特性 的数据元素的有序序列 。
线性表在逻辑上可以想象成是连续的一条线段 ， 线段上有很多点 ， 比如下图：
相关术语：
线性表是一个比较简单 和 基础的数据结构 。
1.2 线性表的顺序存储 - 顺序表
1）顺序存储：逻辑上相邻的元素 ， 在内存中也存在相邻的位置。
2）顺序表就是通过数组来实现的 。
二、顺序表的模拟实现
2.1 顺序表的表示方法
按照数组的申请方式，有两种实现方式：
1）数组采用静态分配，此时的顺序表称为静态顺序表
2）数组采用动态分配，此时的顺序表称为动态顺序表
---> 静态分配就是直接向内存申请一大块连续的区域 ， 然后将需要存放的数组放在一大块连续的区域 。
---> 动态分配就是按需所取 ， 按照需要存放的数据的数量 ， 合理的申请大小合适的空间来存放数据 。
2.2 创建
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;//根据实际情况而定//创建顺序表
int arr[N];//用足够大的数组来模拟顺序表
int n;//标记顺序表里面有多少个元素int main()
{return 0;} 2.3 添加一个元素
2.3.1 尾插
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;//根据实际情况而定//创建顺序表
int arr[N];//用足够大的数组来模拟顺序表
int n;//标记顺序表里面有多少个元素//打印数组void print_Arr(){for(int i = 0;i<n ; i++){cout << arr[i] << " "; } cout << endl;
} //尾插void push_back(int x){arr[n++] = x;} int main()
{push_back(1);push_back(2);push_back(3);push_back(4);//1 2 3 4print_Arr();return 0;} 
时间复杂度：O(1)
2.3.2 头插
方法：
1）从最右边的元素开始 ， 依次往后移动一位
2）然后把 新的数据 放入到a[0] 上
3） 不要忘记n++
4) 注意不要从前往后依次移动 ， 因为会导致后一个值 被 前一个值覆盖 ！！！
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;//根据实际情况而定//创建顺序表
int arr[N];//用足够大的数组来模拟顺序表
int n;//标记顺序表里面有多少个元素//打印数组void print_Arr(){for(int i = 0;i<n ; i++){cout << arr[i] << " "; } cout << endl;
} //尾插void push_back(int x){arr[n++] = x;} //头插
void push_front(int x)
{for(int i = n;i>=0;i--){arr[i+1] = arr[i];}arr[0] = x;n++;} int main()
{push_back(1);push_back(2);push_back(3);push_back(4);//1 2 3 4push_front(3);push_front(2);push_front(1);//1 2 3 1 2 3 4print_Arr();return 0;} 
时间复杂度：由于需要将所有元素右移一位 ， 所以时间复杂度为 O(N）
2.3.3 任意位置插入
1）指定插入位置 之后的所有数据 ， 从右往左依次向后移动一位 。
2）指定位置插入新的元素
3）不要忘记了 n++;(因为插入了一个新的元素）
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;//根据实际情况而定//创建顺序表
int arr[N];//用足够大的数组来模拟顺序表
int n;//标记顺序表里面有多少个元素//打印数组void print_Arr(){for(int i = 0;i<n ; i++){cout << arr[i] << " "; } cout << endl;
} //尾插void push_back(int x){arr[n++] = x;} //头插
void push_front(int x)
{for(int i = n;i>=0;i--){arr[i+1] = arr[i];}arr[0] = x;n++;} //任意插入数据void Insert(int p,int x){for(int i = n;i>=p;i--){arr[ i + 1] = arr[i]; }arr[p] = x;n++; }
int main()
{push_back(1);push_back(2);push_back(3);push_back(4);//1 2 3 4push_front(3);push_front(2);push_front(1);//1 2 3 1 2 3 4Insert(1,99);print_Arr();return 0;} 时间复杂度：O(N) , 最坏的情况下 ， 数组中的所有元素需要往后移动 (任意插入的位置指定为数组第一个元素的位置)
其实上面的三个函数 ， 都存在一个BUG ， 因为需要判断数组是否存满 ， 如果数组存满了，就不能在继续存数据了；这里我们通过自己来判断数组是否存满，如果不合法，一般我们并不会调用。其次，任意位置插入的p位置也需要合法；
2.4 删除一个元素
2.4.1 尾删
直接 n-- , 不识别n 之后的数据 ， 就会达到我们想尾删的目的
//尾删void Pop_back(){n--;} 1）时间复杂度：O(1)
2 ) 这里也有一个小BUG ， 因为删除数据的时候需要判断数组是否存在元素，如果数组没元素 ，还删除，编译器会报错
2.4.2 头删
//头删
void Pop_front()
{for(int i = 0;i<n;i++){arr[i] = arr[i+1]; }n--;
} 1）时间复杂度：O(n)
2 ) 这里也有一个小BUG ， 因为删除数据的时候需要判断数组是否存在元素，如果数组没元素 ，还删除，编译器会报错
2.4.3 任意位置删除
//任意位置删除
void erase(int p)
{for(int i = p;i<=n;i++){arr[i] = arr[i+1];}n--;
}1）时间复杂度：O(n)
2 ) 这里也有一个小BUG ， 因为删除数据的时候需要判断数组是否存在元素，如果数组没元素 ，还删除，编译器会报错 ； 同时 p 位置不能非法 ；
2.5 查找元素
2.5.1 按值查找
//查找元素
int find(int x)
{for(int i = 0;i<n ; i++){if(arr[i] == x)return i; }return 0;} 1）时间复杂度：O(1)
2 ) 顺序表能直接通过下标 ， 快速访问到元素
2.5.2 按位查找
想找第几位，就返回第几位的元素：
// 返回 p 位置的数
int at(int p)
{return a[p];
}1）时间复杂度：O(1)
2 ) 顺序表能直接通过下标 ， 快速访问到元素
// p 的位置应该是合法的 [1,n]
2.6 修改元素
// 把 p 位置的数修改成 x
void change(int p, int x)
{a[p] = x;
}// 思考，这个函数有 bug 么？
// 位置 p 要是合法的才⾏1）时间复杂度：O(1)
2 ) 顺序表能直接通过下标 ， 快速访问到元素 ， 然后直接修改值就好了
2.7 清空顺序表
// 清空顺序表
void clear()
{n = 0;
}时间复杂度：1 . 要注意，我们自己实现的简单形式是 O(1) 。2 . 但是，严谨的方式应该是 O(N) （如果数组元素存储的不是int 类型，而是我们new出来的空间，如果不一个一个的释放，会导致内存泄漏）。
总代码：
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;//根据实际情况而定//创建顺序表
int arr[N];//用足够大的数组来模拟顺序表
int n;//标记顺序表里面有多少个元素//打印数组void print_Arr(){for(int i = 0;i<n ; i++){cout << arr[i] << " "; } cout << endl;
} //尾插void push_back(int x){arr[n++] = x;} //头插
void push_front(int x)
{for(int i = n;i>=0;i--){arr[i+1] = arr[i];}arr[0] = x;n++;} //任意插入数据void Insert(int p,int x){for(int i = n;i>=p;i--){arr[ i + 1] = arr[i]; }arr[p] = x;n++; } //尾删void Pop_back(){n--;}//头删
void Pop_front()
{for(int i = 0;i<n;i++){arr[i] = arr[i+1]; }n--;
}
//任意位置删除
void erase(int p)
{for(int i = p;i<=n;i++){arr[i] = arr[i+1];}n--;
}
//按值查找
int find(int x)
{for(int i = 0;i<n ; i++){if(arr[i] == x)return i; }return 0;} // 按位查找
int at(int p)
{return a[p];
}// 按位修改
int change(int p, int x)
{a[p] = x;
} //清空操作
void clear()
{n = 0;} int main()
{push_back(1);push_back(2);push_back(3);push_back(4);//1 2 3 4push_front(3);push_front(2);push_front(1);//1 2 3 1 2 3 4Pop_back();Pop_back();//1 2 3 1 2erase(1);erase(2);print_Arr();return 0;} 三、封装静态顺序表
思考： 如果实际情况需要特别多的顺序表来解决问题，上述的写法有什么问题么？
如果需要两个及以上的顺序表：
利用C++结构体和类 把我们实现的顺序表封装起来 ， 就能简化操作。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;//根据实际情况而定//将顺序表的创建以及增删查改封装在一个类中
class SqList
{int a[N];int n;public://构造函数，初始化SqList(){n = 0; } //尾插 void push_back(int x){a[n++] = x;}//打印void print_Arr(){for(int i = 1;i<=n;i++){cout << a[i] << " ";}cout << endl;}
};int main()
{SqList s1,s2;for(int i = 1;i <= 5 ; i++){s1.push_back(i);s2.push_back(i + 2); }s1.print_Arr() ;s2.print_Arr() ;return 0;
}
