蓝桥备赛12-顺序表和-vector上
蓝桥备赛（12）- 顺序表和 vector（上）
一、顺序表的概念
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 4
print_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 4
push_front(3);
push_front(2);
push_front(1);
//1 2 3 1 2 3 4
print_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 4
push_front(3);
push_front(2);
push_front(1);
//1 2 3 1 2 3 4
Insert(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 4
push_front(3);
push_front(2);
push_front(1);
//1 2 3 1 2 3 4
Pop_back();
Pop_back();
//1 2 3 1 2
erase(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;
}用类和结构体将代码进行封装 ，能够很大程度上减少重复的操作，使代码的复用率大幅度提升。
