目录
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;
}