顺序表和STL——vector【 复习笔记】
1. 顺序表
1.1 顺序表的概念
要理解顺序表，首先得理解线性表
线性表是具有相同数据类型的 n (n>=0)个数据元素的有限序列,n=0时，称为空表，线性表逻辑结构是线性结构
而线性表使用顺序存储就是顺序表，顺序表通过数组实现
1.2 顺序表的实现
1.2.1 实现方式
1. 数组采用静态分配，顺序表为静态顺序表
2. 数组采用动态分配，顺序表为动态顺序表
静态分配：直接向内存申请一大块连续的区域
动态分配：按需申请合适的空间
二者各种有各种的优缺点：
静态分配：没有动态申请释放空间的时间开销，但数据量大，空间不够，就会出现数据溢出；而数据量小，就会浪费很多空间
动态分配：可以自由分配空间，但涉及扩容会有很大的时间开销
没有一种方式是完美的，是一劳永逸的，要根据实际需求选择合适的方式
1.2.2 静态顺序表模拟实现
对于下面的实现，只是我们简单的认识，会有一些bug，比如尾插和头插，如果数组满了，就不能插入......所以，我们在调用的时候要自己判断，不合法，就不调用
#include<iostream>
using namespace std;const int N = 1e6 + 10;
int a[N];
int n;//尾插，时间复杂度O(1)
void push_back(int x)
{a[++n] = x;
}//头插，时间复杂度O(N)
void push_front(int x)
{for (int i = n; i >= 1; i--){a[i + 1] = a[i];}a[1] = x;n++;
}//任意位置插入，时间复杂度O(N)
void inert(int p, int x)
{for (int i = n; i >= p; i--){a[i + 1] = a[i];}a[p] = x;n++;
}//尾删，时间复杂度O(1)
void pop_back()
{n--;
}//头删，时间复杂度O(N)
void pop_front()
{for (int i = 2; i <= n; i--){a[i-1] = a[i];}n--;
}//任意位置删除，时间复杂度O(N)
void erase(int p)
{for (int i = p + 1; i <= n; i--){a[i - 1] = a[i];}n--;
}//查找元素，按值查找，时间复杂度O(N)
int find_x(int x)
{for (int i = 1; i <= n; i++){if (a[i] == x)return i;}return 0;
}//查找元素，按位查找，时间复杂度O(1)，这是顺序表随机存取的特性，有下标就能快速访问
int find_p(int p)
{return a[p];
}//修改元素,时间复杂度O(1)
void change(int p, int x)
{a[p] = x;
}//清空顺序表，下面代码的时间复杂度O(1)，但实际实现的严谨方式为O(N)
void clear()
{n = 0;
}1.2.3 静态顺序表的封装
如果我们需要多个顺序表来解决问题，就需要定义多个a1,a2...,n1,n2...,这不方便，我们不妨使用c++结构体和类将顺序表封装
const int N = 1e6 + 10;
class Sqlist{int a[N];int n;
public:Sqlist(){n = 0;}void push_back(int x){a[++n] = x;}void push_front(int x){for (int i = n; i >= 1; i--){a[n+1] = a[n];}a[1] = x;n++;}//......
};STL就将数据结构进行封装，我们可以使用 "." 进行调用
2. 动态顺序表 —— vector
STL提供一个封装好的容器——vector(可变长数组）
2.1 vector的认识
#include<vector>
const int N = 20;//vector的创建
void init()
{//创建空的vectorvector<int> a1;//创建的空间大小为Nvector<int> a2(N);//创建的空间大小为N，所以元素都是3vector<int> a3(N, 3);//vector初始化vector<int> a4 = { 1,2,3 };//<>里面可以放任意类型vector<string> a5;vector<vector<int>> a6;//创建N个vectorvector<int> a8[N];
}void test1()
{vector<int> a(5);for (int i = 0; i < a.size(); i++){// size：返回实际元素个数//empty:布尔类型的返回值，如果顺序表为空，返回true；否则，返回false//实际复杂度都是O(1)cout << a[i] << " ";}cout << endl;if (a.empty()) cout << "空" << endl;//begin:返回初始位置的迭代器//eng：返回结束位置的下一个位置的迭代器for (vector<int>::iterator it = a.begin(); it != a.end(); it++){cout << *it << " ";}cout << endl;}void test2()
{vector<int> a(5);//push_back:尾插一个元素//pop_bakc：尾删一个元素//实际复杂度O(1)for (int i = 1; i <= 5; i++){a.push_back(i);}//front:返回首元素//back：返回尾元素//时间复杂度O(1)cout << a.front() << " " << a.back() << endl;//resize:修改vector的大小//如果大于原来大小，多出来位置补默认值0//如果小于原来大小，少掉位置的元素删除//时间复杂度O(N)a.resize(3);//clear:清空vector//时间复杂度O(N)a.clear();cout << a.size() << endl;
}vector封装的接口还有很多，比如:insert,erase...