iis7搭建网站织梦,昆明网站建设一条龙服务,海南做网站的网络公司,精品成品中韩网站源码免费目录 1.顺序表的概念
2.静态顺序表的实现
总代码
3.stl库动态顺序表vector
测试代码 1.顺序表的概念
要理解顺序表#xff0c;我们要先了解一下什么是线性表
线性表是n个具有相同特征的数据元素的序列 这就是一个线性表 a1是表头 a4是表尾 a2是a3的前驱 a3是a2的后继
空…
目录 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;
}
测试尾插 由此可见尾插的时间复杂度为O1 静态顺序表的头插
void push_front(int x)
{//我们头插要把所有元素向右移动一位给我们要插入的元素腾出位置出来//但是如果我们从第一个元素右移就会有覆盖的情况所以我们从最后一个元素开始右移//把[1,n]的元素统一后移1位 for(int i n;i1;i--){a[i1] a[i];} a[1] x;n;
}
头插的时间复杂度是ON
测试头插 任意位置插入
void insert(int p,int x)
{//和我们头插保持一致在p之前插入 头插是在下标为0之前插入//把[p,n]的元素统一右移 for(int i n;ip;i--) {a[i1] a[i];}a[p] x;
}
最坏情况下就是头插所以我们的时间复杂度还是ON
测试任意位置插入 尾删
我们直接把有效元素减1就能实现尾删操作我们尾删的时间复杂度是O1
void pop_back()
{n--;}
测试尾删 头删
void pop_front()
{for(int i 2;in;i){a[i-1] a[i];}n--;}
我们头删的时间复杂度是ON
测试代码 任意位置删除
void erase(int p)
{for(int i p1;in;i){a[i-1] a[i];}n--;
} 按值查找
int find(int x)
{for(int i 1;in;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;i1;i--){a[i1] a[i];} a[1] x;n;
}
void insert(int p,int x)
{//和我们头插保持一致在p之前插入 头插是在下标为0之前插入//把[p,n]的元素统一右移 for(int i n;ip;i--) {a[i1] a[i];}a[p] x;
}
void pop_back()
{n--;}
void Print()
{for(int i 1;in;i){cout a[i] ;}cout endl;
}
void pop_front()
{for(int i 2;in;i){a[i-1] a[i];}n--;}
void erase(int p)
{for(int i p1;in;i){a[i-1] a[i];}n--;
}
int find(int x)
{for(int i 1;in;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;i10;i)
{cout 查找 i :;cout find(i) ;}
}
3.stl库动态顺序表vector
创建vector 除此之外我们vector的里还可以放stl和各种数据类型vectorint 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(vectorint 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 C11支持
// 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;
}
