基础数据结构

基础数据结构介绍

\(luoguB3614\)

概念

一种先进后出的数据结构

实现方法

手写栈(用数组模拟)

int st[N];//模拟栈 
int idx;//栈中元素数量 

st[++idx]=x;//压栈 

return st[idx];//取栈顶元素 

if(idx) idx--;//弹出栈顶元素

idx=0;//清空栈 

STL库

#include <stack>//栈所需的头文件

stack<int> st;

st.top();//返回栈顶元素 

st.push(x);//压栈 

st.pop();//弹出栈顶元素 

st.empty();//判断栈是否为空 

st.size();//返回栈中元素数量 

单调栈 \(luogu5788\)

概念

具有单调性的栈。

维护一个单调栈(\(st\)

插入

在插入时,将不满足单调性的元素弹出。

//手写
int st[N],idx=0;

inline void add(int x)
{
	while(idx!=0&&st[idx]<x) idx--;
	st[++idx]=x;
}

//STL
stack<int> st;

while(!st.empty()&&st.top()<x) st.pop();
st.push(x);

其余操作(读取栈顶元素,返回栈顶数量等)与栈操作相同

队列 \(luoguB3616\)

概念

一种先进先出的数据结构

实现方法

手写(用数组模拟)

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>//队列所需头文件

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>//双端队列所需头文件

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();//返回队列元素数量 

单调队列 \(luogu1886\)

概念

具有单调性的队列。

注意:单调队列与双端队列相似,均可以在队头(队尾)进行插入或删除操作。

维护一个单调队列(\(q\)

插入

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]<h[t]) t=x*2;
	if(x*2+1<=idx&&h[x*2+1]<h[t]) t=x*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 <queue>

priority_queue<int> q;

q.top();//查询堆顶元素 

q.empty();//判断是否为空

q.size();//堆内元素数量

q.push(x);//将元素x加入堆中

q.pop();//删除堆顶 

单向链表 \(luoguB3631\)

概念

一种链式数据结构。

与数组的不同点在于数组是连续存储的,而链表可以是非连续的。

链表相关操作

单向链表包括数据域和指针域,数据域用来存储当前位置所存储的值,指针域用来存储下一个数据的位置。

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];
}

并查集 \(luogu3367\)

概念

并查集是一种类似于树的数据结构,支持合并和查询两种操作。

代码实现

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

一些建议

  • 在手动模拟数据结构时,若操作较多,可用 \(\text {struct}\) 将其封装,既方便使用,又提高了代码的整洁度和可观性。
    原文作者:Mr-Lin
    原文地址: https://www.cnblogs.com/Mr-Lin-081122/p/16513642.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞