C++简单数据结构
0.前言
由于本人是 xxs，数据结构学的不多，文章有错误还请多多谅解。
1. 栈
定义：
栈是一种后进先出的数据结构。栈只有一段能够进出元素，我们一般称这一端为栈顶，另一端为栈底。添加或删除栈中元素时，我们只能将其插入到栈顶（进栈），或者把栈顶元素从栈中取出（出栈），一般用于 DFS 。
实现：luogu-B3614【模板】栈
非STL实现：
#include<bits/stdc++.h>
using namespace std;
int sta[100005],top;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int op,x;
cin>>op;
if(op==1)cin>>x,sta[++top]=x;//入栈
else if(op==2)
{
if(top==0)cout<<"sta is empty!\n";//如果栈为空
else top--;//弹栈
}
else if(op==3)cout<<top<<"\n";//栈的大小
else cout<<sta[top]<<"\n";//输出栈顶
}
return 0;
}
STL 实现
引入 STL 工具 stack
我们给这个栈叫 sta
操作
基础操作
sta.push();//入栈
sta.pop();//出栈
sta.top();//访问栈顶元素
sta.empty();//判断栈是否空
sta.size();//栈的大小
代码：
#include<bits/stdc++.h>
using namespace std;
stack<int>sta;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int op,x;
cin>>op;
if(op==1)cin>>x,sta.push(x);
else if(op==2)
{
if(sta.empty())cout<<"sta is empty!\n";
else sta.pop();
}
else if(op==3)cout<<sta.size()<<"\n";
else cout<<sta.top()<<"\n";
}
return 0;
}
例题
1. 简单题
本题我们可使用一个类似于求中位数的对顶堆的算法，对顶栈建立两个栈，栈 sta1 存储从序列开头到当前光标位置的这一段子序列，栈 sta2 存储从当前光标位置到的这一段子序列序列结尾，二者均以光标为栈顶，两个栈合起来就保存了整个序列。我们用 ans 维护栈的最大前缀和，设 sta 的栈顶位置下标时 top1, sta 是序列 sta1 的前缀和数组。
2. 经典题
\(后缀表达式求值\)
1. 建立一个存数字的栈，注意扫描这个后缀表达式的元素。
（1）如果遇到一个数，则把该数入栈。
（2）如果遇到运算符，就取出栈顶两个数进行计算，把结果入栈。
2. 扫描完成后，栈内恰好剩下一个数，就是答案。
#include<bits/stdc++.h>
using namespace std;
stack<int>q;
int main()
{
string s,t;
cin>>s;
for(int i=0;i!='@';i++)
{
if(s[i]>='0'&&s[i]<='9')t+=s[i];
else
{
int d=0;
for(int j=0;j<t.size();j++)d=d*10+t[j]-'0';
t="";
if(d!=0)q.push(d);
if(s[i]=='.')continue;
if(s[i]=='+')
{
int a=q.top();q.pop();
int b=q.top();q.pop();
q.push(a+b);
}
else if(s[i]=='-')
{
int a=q.top();q.pop();
int b=q.top();q.pop();
q.push(b-a);
}
else if(s[i]=='*')
{
int a=q.top();q.pop();
int b=q.top();q.pop();
q.push(a*b);
}
else if(s[i]=='/')
{
int a=q.top();q.pop();
int b=q.top();q.pop();
q.push(b/a);
}
}
}
cout<<q.top();
return 0;
}
前缀表达式同理就不给代码了，只是加了个转换，也可用栈解决
3. 拓展题
大家应该很熟悉汉诺塔了把，这里就不解释了。
自己可以去看看题解。
练习
2. 链表
定义
链表是由一系列节点组成，每个节点包含数据元素和指向下一个节点的指针的线性数据结构。链表分为单向链表和双向链表，单向链表较少使用，而双向链表则较为常用
作用
相比于大家更熟悉的数组，链表的插入和删除是很快很简单的，操作次数是 \(O(1)\)，但链表的寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 \(O(n)\)。
在链表中删除数据时，本质上就是在改变一个个节点之间的连线，让被删除的节点与前后两个节点的“连线”去掉：
(来源：OI WIKI)
在链表中插入数据时，本质上也是在改变一个个节点之间的连线，并且加入了一个新节点：
(来源：OI WIKI)
实现
非 STL 实现：
（1） 单向链表：luogu-B3631 单向链表
#include<bits/stdc++.h>
using namespace std;
int q,it,x,y;
int a[1000010];//数组模拟链表
int main()
{
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>it;
if(it==1)
{
cin>>x>>y;
a[y]=a[x];
a[x]=y;
}//将元素y插入到x后面
else if(it==2)
{
cin>>x;
cout<<a[x]<<endl;
}//询问x后面的元素是什么。
else if(it==3)
{
cin>>x;
a[x]=a[a[x]];
}//从表中删除元素x后面的那个元素。
}
return 0;
}
（2） 双向链表：luogu-B4324 【模板】双向链表
代码主体部分如下：
一，构建链表：
struct Node{
int value;
int pre,nex;
}s[1010];
int tot;
二，查找：
int find(int x){
int now=1;
while(now&&s[now].value!=x)now=s[now].nex;
return now;
}
三，插入：
void ins_back(int x,int y){
int now=find(x);
s[++tot]=node(y,now,s[now].nex);
s[s[now].pre].pre=tot;
s[now].nex=tot;
}
void ins_front(int x,int y){
int now=find(x);
s[++tot]=node(y,s[now].pre,now);
s[s[now].pre].nex=tot;
s[now].pre=tot;
}
四，删除：
void del(int x){
int now=find(x);
int le=s[now].pre,rt=s[noe].nex;
s[le].nex=rt;
s[rt].pre=le;
}
例题
1. 简单题
看完题目，我们可以发现，我们可以用一个双向链表维护这个队伍，和模板差别不算太大。我们只需用数组 index 记录同学的编号，在插入删除时找到他就可以了。
2. 经典题
乍一看题大家可能都会想用队列，不过链表也是可以的。
在这里我们引入链表的 STL 实现：list
list 的常用方法较多，这里仅介绍一点点：
list<int>::iterator it;//定义一个叫it的指针。
front(),back()//获取首尾元素。
push_front(),push_back()//头插,尾插。
pop_front(),pop_back()//头删,尾删。
insert(pos, val)//在pos迭代器位置插入val。
erase(pos)//删除pos位置的元素。
for(it=a.begin();it!=a.end();it++)//遍历链表a。
接下来模拟题意就可以啦（代码自己打~~）
3. 拓展题
正解dancing-links，是一种特殊的链表，自己看看题解吧，拓展一下。
练习
P4269 [USACO18FEB] Snow Boots G
3.队列
定义
和栈正好相反，它是 先进先出 的，一般用于 BFS 。
实现
队列的实现是相对简单的：
struct st
{
int end=0,head=1;
int a[12000];
int size(){
return end-head+1;
}
void pop(){
head++;
}
int front(){
return a[head];
}
void push(int x){
a[++end]=x;
}
};
st s;
例题
1.简单题
很简单的一道队列，几乎就是模板。
2.经典题
队列加上 BFS ，这道题是一般的队列的难度：用来维护 BFS 。
代码比较简单，自己打一打吧。
3.拓展题
单调队列，一种神秘的队列。
这种队列可以用 deque 来实现，用于优化很多别的算法。
练习
4.并查集
定义
并查集可以简单的分为集、并、查。
这里的集是集合的意思,也可以看做是树或是联通块,所以并查集这个算法主要是对集合进行的操作。那怎么存储集合呢？此时我们可以把集合看成树，存储时取任意一个结点作为根结点，通过一个fa[]数组来存储每个节点的祖先就可以了。
并指的其实就是合并这个操作,主要是把两个不同的集合合并,这里把集合看成树更好理解,合并的大概过程如下图所示：
来源：Ryan_X
这里提到了一个并查集中非常重要的一个函数：find(x)
这个函数主要是通过树状的结点连接关系递归来查询根结点的。它的核心代码如下：
int find(int x){
if(fa[x]==x)return x;
return find(fa[x]);
}
这里还有一个初始化的问题，在查询的过程中如何判断这个节点是否就是根节点呢？我们可以一开始的时候就把每个结点的祖先初始化为它本身，只要查询到祖先为自己本身的结点就说明它是根结点了。大概过程如下图：
来源：Ryan_X
有些题目这样写还是会超时，此时我们就要优化这个递归。我们此时就可以使用路径压缩,它的原理如下图所示：
来源：Ryan_X
核心代码如下：
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
查指的是查询操作，它主要是查询两个不同的结点在不在同一个集合里,核心代码如下：
int t1=find(x),t2=find(y);
if(t1!=t2)fa[t1]=t2;
实现：P3367 【模板】并查集
模板题，主要考察并查集的基本操作。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[200010];
int find(int x){
if(x==p[x])return x;
return p[x]=find(p[x]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i;
int x,y,z;
while(m--){
cin>>z>>x>>y;
x=find(x);
y=find(y);
if(z==1)p[x]=y;
else{
if(x==y)cout<<"Y";
else cout<<"N";
}
}
return 0;
}
例题
1.简单题
这道题没什么好说的，十分基础的并查集。
2.经典题
这道题我们可以先把相等的变量放在同一个集合里，输入完后再扫描一遍不相等的关系，再判断有没有冲突。
#include<bits/stdc++.h>
using namespace std;
int t;
map<int,int>p;
int find(int x){
if(p[x]==x)return x;
return p[x]=find(p[x]);
}
int x[110000],y[110000],e[110000];
int main(){
cin>>t;
while(t--){
p.clear();
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>e[i];
if(!p[x[i]])p[x[i]]=x[i];
if(!p[y[i]])p[y[i]]=y[i];
if(e[i]){
p[find(x[i])]=find(y[i]);
}
}
bool flag=0;
for(int i=1;i<=n;i++){
if(!e[i]){
if(find(x[i])==find(y[i])){
flag=1;
break;
}
}
}
if(flag)cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
3.拓展题
一道水蓝，正解并查集，不过模拟也能\(AC\)。
参考资料
致谢
作者在这里感谢zhangleyi0417、Ryan_X对本文撰写的贡献。
浙公网安备 33010602011771号