文章目录
显示
? 优质资源分享 ?
| 学习路线指引（点击解锁） | 知识定位 | 人群定位 |
|---|---|---|
| ? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。 |
| ?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
基础数据结构介绍
栈 luoguB3614luoguB3614luoguB3614
概念
一种先进后出的数据结构
实现方法
手写栈（用数组模拟）
int st[N];//模拟栈
int idx;//栈中元素数量
st[++idx]=x;//压栈
return st[idx];//取栈顶元素
if(idx) idx--;//弹出栈顶元素
idx=0;//清空栈
STL库
#include //栈所需的头文件
stack<int> st;
st.top();//返回栈顶元素
st.push(x);//压栈
st.pop();//弹出栈顶元素
st.empty();//判断栈是否为空
st.size();//返回栈中元素数量
单调栈 luogu5788luogu5788luogu5788
概念
具有单调性的栈。
维护一个单调栈（ststst）
插入
在插入时，将不满足单调性的元素弹出。
//手写
int st[N],idx=0;
inline void add(int x)
{
while(idx!=0&&st[idx] st[++idx]=x;
}
//STL
stack<int> st;
while(!st.empty()&&st.top()pop();
st.push(x);
其余操作（读取栈顶元素，返回栈顶数量等）与栈操作相同
队列 luoguB3616luoguB3616luoguB3616
概念
一种先进先出的数据结构
实现方法
手写（用数组模拟）
int q[N],h=1,t;//q为队列，h为队头，t为队尾
q[++t]=x;//将一个元素x加入队列
h++;//队首元素出队
q[h];//队头元素
q[t];//队尾元素
h=1;//清空队列
t=0;//同时也是初始化
STL库
#include //队列所需头文件
queue<int> q;//队列
q.front();//队首元素
q.back();//队尾元素
q.push(x);//将元素x添加到队列中
q.pop();//弹出队首元素
q.empty();//判断队列是否为空
q.size();//返回队列元素数量
双端队列
概念
与普通队列的不同之处在于双端队列可以在队头/队尾添加（删除）元素。
实现方法
手写双端队列（用数组模拟）
int q[N],h=1,t;//q为队列，h为队头，t为队尾
q[++t]=x;//将一个元素x加入队首
q[--h]=x;//将一个元素x加入队尾
h++;//队首元素出队
t--;//队尾元素出队
q[h];//队头元素
q[t];//队尾元素
h=1;//清空队列
t=0;//同时也是初始化
STL库
#include //双端队列所需头文件
deque<int> q;
q.front();//查询队头元素
q.back();//查询队尾元素
q.push\_back(x);//在队尾插入元素x
q.push\_front(x);//在队首插入元素x
q.pop\_back();//在队尾弹出元素
q.pop\_front();//在队首弹出元素
q.empty();//判断队列是否为空
q.size();//返回队列元素数量
单调队列 luogu1886luogu1886luogu1886
概念
具有单调性的队列。
注意：单调队列与双端队列相似，均可以在队头（队尾）进行插入或删除操作。
维护一个单调队列（qqq）
插入
int q[N],h=1,t;
inline void add(int x)
{
while(h<=t&&q[t]<=x) t--;
q[++t]=x;
}
其余操作（查询元素，判断是否为空等）与双端队列相同
优先队列（堆）
概念
堆其实是一棵完全二叉树，而优先队列是一个大根堆。
因此可以用一维数组来进行模拟堆。
堆的实现方法
手写（用一维数组模拟）
int h[N],idx;//h模拟堆，idx为堆内元素数量
void down(int x)//向下调整堆
{
int t=x;
if(x*2<=idx&&h[x*2]2;
if(x*2+1<=idx&&h[x*2+1]2+1;
if(x!=t)
{
int tmp=h[x];
h[x]=h[t];
h[t]=tmp;
down(t);
}
}
void up(int x)//向上调整堆
{
while(x/2&&h[x/2]>h[x])
{
int t=h[x/2];
h[x/2]=h[x];
h[x]=t;
x/=2;
}
}
inline void add(int x)//将元素x插入堆
{
h[++idx]=x;
up(x);
}
inline int minn()//返回堆内最小值
{
return h[1];
}
inline void delete\_minn()//删除堆内最小值
{
h[1]=h[idx];
idx--;
down(1);
}
inline void \_delete(int x)//删除堆内第x个元素
{
h[x]=h[idx];
idx--;
up(x);
down(x);
}
inline void write(int x,int y)//将第x个元素修改为第y个元素
{
h[x]=h[y];
up(x);
down(x);
}
折叠 STL库（优先队列）
#include
priority\_queue<int> q;
q.top();//查询堆顶元素
q.empty();//判断是否为空
q.size();//堆内元素数量
q.push(x);//将元素x加入堆中
q.pop();//删除堆顶
单向链表 luoguB3631luoguB3631luoguB3631
概念
一种链式数据结构。
与数组的不同点在于数组是连续存储的，而链表可以是非连续的。
链表相关操作
单向链表包括数据域和指针域，数据域用来存储当前位置所存储的值，指针域用来存储下一个数据的位置。
int e[N],ne[N],idx,h=-1;
inline void add\_front(int x)//在链表头插入元素x
{
e[idx]=e;
ne[idx]=h;
h=idx++;
}
inline void delete\_front()//删除链表头元素
{
h=ne[h];
}
inline void add(int x,int i)//在第i个元素后面插入元素x
{
e[idx]=x;
ne[idx]=ne[i];
ne[i]=idx++;
}
inline void \_delete(int i)//将第i个元素删除
{
ne[i]=ne[ne[i]];
}
双向链表
概念
与单链表的不同之处在于指针域有左右之分。
代码实现
int e[N],l[N],r[N],idx;
inline void init()//初始化
{
r[0]=1;
l[1]=0;
idx=2;
}
inline void add(int x,int i)//在第i个数据的右边插入数据x
{
e[idx]=x;
l[idx]=i;
r[idx]=r[i];
l[r[i]]=idx;
r[i]=idx++;
}
inline void \_delete(int i)//删除第i个结点
{
l[r[i]]=l[i];
r[l[i]]=r[i];
}
并查集 luogu3367luogu3367luogu3367
概念
并查集是一种类似于树的数据结构，支持合并和查询两种操作。
代码实现
int fa[N];
inline void init(int n)//初始化
{
for(register int i=1;i<=n;i++)
{
fa[i]=i;
}
}
int f(int x)//查找操作
{
if(fa[x]!=x) fa[x]=f(fa[x]);//路径压缩
return fa[x];
}
inline void unionSet(int x,int y)//合并操作
{
fa[f(x)]=f(y);
}
数据结构实际运用
- 队列 广搜
- 优先队列 dijkstra堆优化（最短路算法）
- 链表 邻接表存图（也就是若干个单链表）
- 并查集 Kruskal（最小生成树算法）
- 单调队列/单调栈 优化dp
一些建议
- 在手动模拟数据结构时，若操作较多，可用 structstruct\text {struct} 将其封装，既方便使用，又提高了代码的整洁度和可观性。
__EOF__
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GdplkpqQ-1658596126864)(https://blog.csdn.net/Mr-Lin-081122/p/16513642.html)]Mr Lin. 本文链接：https://blog.csdn.net/Mr-Lin-081122/p/16513642.html关于博主：评论和私信会在第一时间回复。或者直接私信我。版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！声援博主：如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。您的鼓励是博主的最大动力！