1.顺序表的概念1 线性表的定义线性表是n个具有相同特征的数据元素的有序序列。线性表在逻辑上可以想象成是连续的一条线线段上有很多个点比如下图因此线性表是一个比较简单和基础的数据结构。2 顺序表用顺序存储实现的线性表顺序储存逻辑上相邻的元素在内存中也存放在相邻位置2.顺序表的模拟实现2.1顺序表的实现方式动态实现通过new和delete来申请和释放空间int *a//接收new出来的数组的地址int capacity//标记当前数组的大小int n//标记有效元素的个数优点按需所需需要多少空间就申请多少空间缺点动态实现会进行空间的申请与释放以及数据的拷贝而这些操作都是非常耗时的因此关于动态实现我们只演示原理不去模拟实现静态实现直接创建一个足够大的数组来充当顺序表优点不需要动态管理内存代码书写上会比较方便没有动态管理内存中申请以及释放空间的时间开销缺点一旦空间占满新来的数据就会溢出如果为了保险而申请很大的空间数据量小的情况下会浪费很多空间在算法竞赛中我们主要关心的其实是时间开销空间上是基本够用的。因此定义一个超大的静态数组来解决问题是完全可以接受的。因此关于顺序表采用的就是静态实现的方式2.2创建1.创建一个足够大的数组充当顺序表int a[1000010];2.同时还需要一个变量用来标记顺序表当前有多少个元素int n 0;2.3添加一个元素添加一个元素一共分为三种2.3.1尾插在顺序表表位的后面插入一个新元素//尾插 void push_back(int x) { a[n] x;//下标为0的位置空出来 }2.3.2头插在顺序表表头的前面插入一个新元素实现步骤1.将[1,n]内所有元素右移一位2.新的元素放在表头3.修改元素个数。2.3.3任意位置插入在位置p处插入一个新元素实现步骤1.将[p,n]内所有元素统一右移2.然后把新的元素放在p位置上3.元素个数12.4删除一个元素删除操作同样分三种2.4.1尾删删除顺序表中最后一个元素//尾删 void pop_back() { n--; }2.4.2头删删除顺序表的表头元素//头删 void pop_front() { //先把[2,n]区间内的所有元素统一左移一位 for(int i 2;i n;i) { a[i-1] a[i]; } n--; }2.4.3任意位置删除删除顺序表中位置为p的元素//任意位置删除 void erase(int p) { //把[p1,n]的元素统一左移一位 for(int i p1;i n;i) { a[i-1] a[i]; } n--; }2.5查找元素2.5.1按值查找查找顺序表中数值x存储的位置//查找这个数第一次出现的位置找不到返回0 int find(int x) { for (int i1;in;i) { if(a[i] x) return i; } return 0; }2.5.2按位查找返回顺序表中第p位的元素//按位查找 int at(int p) { return a[p]; }2.6修改元素//把p位置的数修改成x void change(int p, int x) { a[p] x; }2.7清空顺序表//清空顺序表 void clear() { n 0; }3.封装静态顺序表# include iostream using namespace std; const int N 50; //使用类或者结构体封装一个静态顺序表 class SqList { int a[N]; int n; public: //构造函数 SqList() { n 0; } //尾插 void push_back(int x) { a[n] x; } //打印 void print() { for(int i1i n;i) { cout a[i] ; } cout end1; } }; int main() { SqList s1,s2; //创造了两个顺序表 for(int i1; i5;i) { s1.push_back(i); s2.push_back(i*2); } s1.print(); s2.print(); return 0; }用结构体和类将代码进行封装能很大程度上减少重复的操作使代码的复用率大大提升4.动态顺序表 - vector4.1创建vectorusing namespace std; const int N 10; struct node { int a,b; string s; }; int main() { //创建vector vectorint a1; //创建了一个名字为a1的空的可变长数组里面都是int类型的数据 vectorint a2(N); //创建了一个大小为10的可变长数组里面的值默认都是 0 vectorint a3(N,2); //创建了一个大小为10的可变长数组里面的值都初始化为2 vectorint a4 {1,2,3,4,5}; //初始化列表的创建方式 // 里面可以存放任意的数据类型这就体现了模板的作用也体现了模板的强大之处 //这样vector里面就可以存放我们见过的所有的数据类型甚至是STL本身 vectorstring a5; //存字符串 vectornode a6; //存结构体 vectorvectorint a7; //创建了一个二维的可变长数组 vectorint a8[N]; //创建了一个大小为N的vector数组 return 0; }4.2size/empty1.size:返回实际元素的个数//size void test_size() { //创建一个一维数组 vectorint a1(6,8); for(int i0;ia1.size();i) { cout a1[i] ; } cout endl; }2.empty返回顺序表是否为空因此是一个bool类型的返回值if(a1.empty()) cout 空 endl; else cout 不空 endl;4.3 begin/end1.begin:返回起始位置的迭代器左闭2.end:返回终点位置的下一个位置的迭代器右开利用迭代器可以访问整个vector存在迭代器的容器就可以使用范围for遍历void print(vectorint a) { //利用迭代器来遍历 - 迭代器类型 vectorint::iterator for(auto it a.begin();it ! a.end();i) { cout *it ; } cout endl; //使用语法糖 - 范围for for(auto x:a) { cout x ; } cout endl; }4.4 push_back/pop_back1.push_back:尾部添加一个元素2.pop_back:尾部删除一个元素//尾插以及尾删 for(int i0;i5;i) { a1.push_back(i); print(a1); } while(!a1.empty()) { print(a1); a1.pop_back(); }4.5 front/back1.front:返回首元素2.back:返回尾元素//首元素和尾元素 void test_fb() { vectorint a(5); for (int i0;i5;i) { a[i] i1; } cout a.front() a.back() endl; }4.6 resize修改vector的大小如果大于原始的大小多出来的位置会补上默认值一般是0如果小于原始的大小相当于把后面的元素全部删掉//resize vectorint aa(5,1); print(aa); // 扩大成10 aa.resize(10); print(aa); //缩小成3 aa.resize(3); print(aa);4.7 clear清空vector底层实现的时候会遍历整个元素一个一个删除因此时间复杂度O(N)//clear cout aa.size() endl; aa.clear(): cout aa.size() endl;