数据结构—顺序表
数据结构—顺序表
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的
数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性
表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表
概念与结构
概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。
顺序表
逻辑结构：线性
物理结构（存储结构：线性
顺序表和数组区别
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口
数组 ⊆ 线性表 数组 \subseteq 线性表 数组⊆线性表
分类
静态顺序表
概念：使用定长数组存储元素
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费
但是在竞赛中经常用静态申请数组的方式，接下来也会说到
动态顺序表
动态顺序表按需申请，不会造成浪费
动态顺序表模拟实现
定义动态顺序表结构
·头文件中
//定义动态顺序表的结构typedefint SLTDataType;typedefstructSeqList{ SLTDataType* arr;//存储数据int size;//有效数据个数int capacity;//空间大小}SL;顺序表初始化
voidSLInit(SL* ps){ ps->arr =NULL; ps->size = ps->capacity =0;}顺序表销毁
voidSLDestroy(SL* ps){if(ps->arr)//避免重复释放free(ps->arr); ps->arr =NULL; ps->size = ps->capacity =0;}顺序表打印
voidSLPrint(SL* ps){for(int i =0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");}顺序表动态扩容
voidSLCheckCapacity(SL* ps){if(ps->size == ps->capacity){int newCapacity = ps->capacity ==0?4:2* ps->capacity;//增容 SLTDataType* tmp =(SLTDataType*)realloc(ps->arr, newCapacity *sizeof(SLTDataType));if(tmp ==NULL){perror("realloc fail!");exit(1);} ps->arr = tmp; ps->capacity = newCapacity;}}尾插
//尾插voidSLPushBack(SL* ps, SLTDataType x){assert(ps);//空间不够SLCheckCapacity(ps);//空间足够 ps->arr[ps->size++]= x;}头插
//头插voidSLPushFront(SL* ps, SLTDataType x){//温柔的处理方式//if (ps == NULL)//{// return;//}assert(ps !=NULL);//等价于assert(ps）//空间不够SLCheckCapacity(ps);//数据整体向后挪动一位for(int i = ps->size; i >0; i--){ ps->arr[i]= ps->arr[i -1];} ps->arr[0]= x; ps->size++;}尾删
//尾删voidSLPopBack(SL* ps){assert(ps && ps->size); ps->size--;}头删
//头删voidSLPopFront(SL* ps){assert(ps && ps->size);//数据整体向前挪动一位for(int i =0; i < ps->size -1; i++){ ps->arr[i]= ps->arr[i +1];} ps->size--;}查找
//查找intSLFind(SL* ps, SLTDataType x){assert(ps);for(int i =0; i < ps->size; i++){if(ps->arr[i]== x){//找到了return i;}}//未找到return-1;}指定位置之前插入
//指定位置之前插⼊voidSLInsert(SL* ps,int pos, SLTDataType x){assert(ps);//0<= pos < ps->sizeassert(pos >=0&& pos < ps->size);//判断空间是否足够SLCheckCapacity(ps);//pos及之后数据向后挪动一位for(int i = ps->size; i > pos; i--){ ps->arr[i]= ps->arr[i -1];} ps->arr[pos]= x; ps->size++;}删除pos位置的数据
//删除pos位置的数据voidSLErase(SL* ps,int pos){assert(ps);//pos:[0，ps->size)assert(pos >=0&& pos < ps->size);//pos后面的数据向前挪动一位for(int i = pos; i < ps->size -1; i++){ ps->arr[i]= ps->arr[i +1];} ps->size--;}竞赛中的静态顺序表
静态申请数组
1.单个顺序表
//1·单个顺序表#include<iostream> using namespace std;constint N =1e6+10;// 根据实际情况而定// 创建顺序表int a[N];// 用足够大的数组来模拟顺序表int n;// 标记顺序表里面有多少个元素// 打印顺序表voidprint(){for(int i =1; i <= n; i++){ cout << a[i]<<" ";} cout << endl << endl;}//尾插voidpush_back(int x){ a[++n]= x;}// 头插voidpush_front(int x){// 1. 先把 [1, n] 的元素统一向后移动一位for(int i = n; i >=1; i--){ a[i +1]= a[i];}// 2. 把 x 放在表头 a[1]= x; n++;// 元素个数 +1}// 在任意位置插入voidinsert(int p,int x){// 1. 先把 [p, n] 的元素统一向后移动一位for(int i = n; i >= p; i--){ a[i +1]= a[i];} a[p]= x; n++;}// 尾删voidpop_back(){ n--;}// 头删voidpop_front(){// 1. 先把 [2, n] 区间内的所有元素，统一左移一位for(int i =2; i <= n; i++){ a[i -1]= a[i];} n--;}// 任意位置删除voiderase(int p){// 把 [p + 1, n] 的元素，统一左移一位for(int i = p +1; i <= n; i++){ a[i -1]= a[i];} n--;}// 按值查找intfind(int x){for(int i =1; i <= n; i++){if(a[i]== x)return i;}return0;}// 按位查找intat(int p){return a[p];}// 按位修改voidchange(int p,int x){ a[p]= x;}// 清空操作voidclear(){ n =0;}2.多个顺序表
只需要在传入一个参数：对应的数组（传引用节省空间）
// 1. 需要多个顺序表，才能解决问题int a1[N], n1;int a2[N], n2;int a3[N], n3;//修改上面的代码 例如// 尾插voidpush_back(int a[],int& n,int x){ a[++n]= x;}//测试尾插voidtest(){push_back(a1, n1,1);push_back(a3, n3,2);}封装静态顺序表
// 使用类或者结构体封装一个静态顺序表 class SqList {int a[N];int n; public:// 构造函数SqList(){ n =0;}// 尾插voidpush_back(int x){ a[++n]= x;}// 尾删voidpop_back(){ n--;}// 打印voidprint(){for(int i =1; i <= n; i++){ cout << a[i]<<" ";} cout << endl;}};intmain(){ SqList s1, s2;// 创建了两个顺序表for(int i =1; i <=5; i++){ s1.push_back(i); s2.push_back(i *2);} s1.print(); s2.print();return0;}//封装 通过调用 各种各样的接口//已经写好的 STL 可以通过 "." 调⽤各种各样的接⼝ 不用再人为重复造轮子//比如 vector 动态顺序表动态顺序表–vector
如果需要用动态顺序表，有更好的⽅式：C++ 的 STL 提供了⼀个已经封装好的容器 - vector
有的地⽅也叫作可变⻓的数组。vector 的底层就是⼀个会⾃动扩容的顺序表，
其中创建以及增删查改等等的逻辑已经实现好了，并且也完成了封装
创建vector
// 1. 创建 vector 常用的四种方式 vector<int> a1;// 创建了一个名字为 a1 的空的可变长数组，里面都是 int 类型的数据 vector<int>a2(N);// 创建了一个大小为 10 的可变长数组，里面的值默认都是 0 vector<int>a3(N,2);// 创建了一个大小为 10 的可变长数组，里面的值都初始化为 2 vector<int> a4 ={1,2,3,4,5};// 初始化列表的创建方式// <> 里面可以存放任意的数据类型，这就体现了模板的作用，也体现了模板的强大之处// 这样，vector里面就可以存放我们见过的所有的数据类型，甚至是 STL 本身 vector<string> a5;// 存字符串 vector<node> a6;// 存结构体 vector<vector<int>> a7;// 创建了一个二维的可变长数组//vector<array<int, 5>> a8;// 二维数组 代替c风格数组 需要包含头文件arrayint a10[N];// 创建了一个大小为 N 的 int类型数组 数组名叫a10 vector<int> a9[N];// 创建了一个大小为 N 的 vector 数组 数组名叫a9size / empty
// 2. size / empty//size 返回实际元素的个数print(a2);print(a3);print(a4);//empty 返回顺序表是否为空，返回类型是⼀个 bool 类型的返回值。// 如果为空返回 true，不空返回 falseif(a2.empty()) cout <<"空"<< endl;else cout <<"不空"<< endl;if(a1.empty()) cout <<"空"<< endl;else cout <<"不空"<< endl;begin / end
begin 返回起始位置的迭代器（左闭) end 返回终点位置的下⼀个位置的迭代器（右开） 利⽤迭代器可以访问整个 vector 存在迭代器的容器就可以使⽤范围 for 遍历 迭代器类型 vector<int>::iterator 用auto voidtest_it(){ vector<int>a(10,1);// 迭代器的类型是 vector<int>::iterator，但是⼀般使⽤ auto 简化for(auto it = a.begin(); it != a.end(); it++){ cout <<*it <<" ";} cout << endl << endl;// 使⽤语法糖 - 范围 for 遍历for(auto x : a){ cout << x <<" ";} cout << endl << endl;}push_back / pop_back
// 4. 尾插以及尾删for(int i =0; i <5; i++){ a1.push_back(i);print(a1);}while(!a1.empty()){ a1.pop_back();print(a1);}front / back
// 5. front / back// front ：返回⾸元素；// back ：返回尾元素；//cout << a4.front() << " " << a4.back() << endl;voidtest_fb(){ vector<int>a(5);for(int i =0; i <5; i++){ a[i]= i +1;} cout << a.front()<<" "<< a.back()<< endl;}resize
如果⼤于原始的⼤⼩，多出来的位置会补上默认值，⼀般是 0 。
如果⼩于原始的⼤⼩，相当于把后⾯的元素全部删掉。
// 如果不加引⽤，会拷⻉⼀份，时间开销很⼤voidprint(vector<int>& a){for(auto x : a){ cout << x <<" ";} cout << endl;}// 6. resizevoidtest_resize(){ vector<int>a(5,1); a.resize(10);// 扩⼤print(a); a.resize(3);// 缩⼩print(a);// 扩大成 5，并且多余的修改为 2 a.resize(5,2);print(a);}clear
清空vector
//底层实现的时候，会遍历整个元素，⼀个⼀个删除，因此时间复杂度 O(N) cout << a.size()<< endl; a.clear(); cout << a.size()<< endl;insert / erase
//8.insert/erase 参数为迭代器 a4.insert(a4.begin()+2,0);print(a4); a4.erase(a4.begin()+2);print(a4);return0;}仓库—代码总结
感谢大佬们三连，你的鼓励就是对我创作的激励！！！ \color{purple}{感谢大佬们三连，你的鼓励就是对我创作的激励！！！} 感谢大佬们三连，你的鼓励就是对我创作的激励！！！
