备考蓝桥杯：顺序表详解（静态顺序表，vector用法）

1.顺序表的概念

2.静态顺序表的实现

总代码

3.stl库动态顺序表vector

测试代码

1.顺序表的概念

要理解顺序表，我们要先了解一下什么是线性表

线性表是n个具有相同特征的数据元素的序列

这就是一个线性表 a1是表头 a4是表尾 a2是a3的前驱 a3是a2的后继

空表表示一个元素也没有，用空寂表示

用顺序存储的方式实现的线性表就叫顺序表

用链式存储的方式实现的线性表就是链表

2.静态顺序表的实现

由于实现动态顺序表要很多很多delete和new，消耗很多的时间复杂度，而且我们已经有vecor这个东西了，所以我们就不实现动态的顺序表了，我们只实现一下静态顺序表

创建静态顺序表

const int N = 1e6 + 10;
int a[N],n;

静态顺序表的尾插

void push_back(int x)
{a[++n]=x;
}

测试尾插

由此可见，尾插的时间复杂度为O（1）

静态顺序表的头插

void push_front(int x)
{//我们头插要把所有元素向右移动一位，给我们要插入的元素腾出位置出来//但是如果我们从第一个元素右移，就会有覆盖的情况，所以我们从最后一个元素开始右移//把[1,n]的元素统一后移1位 for(int i = n;i>=1;i--){a[i+1] = a[i];} a[1] = x;n++; 
}

头插的时间复杂度是O（N）

测试头插

任意位置插入

void insert(int p,int x)
{//和我们头插保持一致，在p之前插入 ，头插是在下标为0之前插入//把[p,n]的元素统一右移 for(int i =n;i>=p;i--) {a[i+1] = a[i];}a[p] = x;
}

最坏情况下就是头插，所以我们的时间复杂度还是O（N）

测试任意位置插入

尾删

我们直接把有效元素减1，就能实现尾删操作，我们尾删的时间复杂度是O（1）

void pop_back()
{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--;
}

按值查找

int find(int x)
{for(int i = 1;i<=n;i++){if(a[i]==x)return i;}
return 0;
}

测试查找操作

按位查找

int at(int p)
{return a[p];
}

清空操作

void clear()
{n = 0;
}

修改操作

void change(int p,int x)
{a[p] = x;
}

总代码

#include <iostream>
using namespace std;const int N = 1e6 + 10;
int a[N],n;
void push_back(int x)
{a[++n]=x;
}
void push_front(int x)
{//我们头插要把所有元素向右移动一位，给我们要插入的元素腾出位置出来//但是如果我们从第一个元素右移，就会有覆盖的情况，所以我们从最后一个元素开始右移//把[1,n]的元素统一后移1位 for(int i = n;i>=1;i--){a[i+1] = a[i];} a[1] = x;n++; 
}
void insert(int p,int x)
{//和我们头插保持一致，在p之前插入 ，头插是在下标为0之前插入//把[p,n]的元素统一右移 for(int i =n;i>=p;i--) {a[i+1] = a[i];}a[p] = x;
}
void pop_back()
{n--;} 
void Print()
{for(int i = 1;i<=n;i++){cout << a[i] << " ";}cout << endl;
}
void pop_front()
{for(int i = 2;i<=n;i++){a[i-1] = a[i];}n--;}
void erase(int p)
{for(int i = p+1;i<=n;i++){a[i-1] = a[i];}n--;
}
int find(int x)
{for(int i = 1;i<=n;i++){if(a[i]==x)return i;}return 0;
}
void clear()
{n = 0;
}
void change(int p,int x)
{a[p] = x;
}int at(int p)
{return a[p];
}
int main()
{push_back(2);Print();push_back(5);push_back(1);push_back(3);Print();push_front(10);Print();insert(3,0);Print();
//	cout << "尾删" << ": ";
//	pop_back();
//	Print();
//	cout << "头删" << ": ";
//	pop_front();
//	Print();
//cout << "删除" << ":";
//erase(3);
//Print(); 
for(int i = 1;i<=10;i++)
{cout << "查找" << i << ":";cout << find(i)<<" ";} 
}

3.stl库动态顺序表vector

创建vector

除此之外，我们vector的<>里还可以放stl和各种数据类型，vector<int> a[5]表示的就是创建一个元素为vector <int>的数组

三种打印方式 1 size（）返回元素个数

2.迭代器

3.范围for

resize（可以扩充元素个数，也可以缩容）

扩大的元素值默认为0

尾插和尾删，和上面静态的差不多的

不多陈述

empty()判空

front和back分别是取头元素和尾元素

clear()清空元素

测试代码

#include <iostream>
#include <vector>
using namespace std;
const int N = 10;
void Print(vector<int>& pa)
{//用size返回元素个数for (int i = 0; i < pa.size(); i++){cout << pa[i] << " ";}cout << endl;//用begin（） end（）迭代器
//	for (auto it = pa.begin(); it != pa.end(); it++)
//	{
//		cout << *it << " ";
//	}
//	cout << endl;
//	//范围for （C++11支持）
//	for (auto e : pa)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
}int main()
{vector <int> a1;//创建一个a1 的可变长数组,size为0vector <int> a2(N);//创建一个a2的可变长数组，size为N，元素值初始化为0vector <int> a3(N, 2);//创建一个a3的可变长数组，size为N 元素初始化为2vector <int> a4 = { 1,2,3,4,5 };vector <string> s1;vector <int> a[5];vector <int> aa(5, 1);aa.resize(10);aa.resize(3);for (int i = 3; i <= 6; i++){a1.push_back(i);}Print(a1);a1.pop_back();cout << "头为" << a1.front() << "尾为" << a1.back();Print(a1);//while (!a1.empty())//{//	a1.pop_back();//}a1.clear();cout << a1.size() << endl;return 0;
}