基础数据结构

技术分享 2年前 (2022-07-24) 0 999+

关注

基础数据结构介绍

栈 (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); }