基礎數據結構
基礎數據結構介紹
棧 \(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}\) 將其封裝，既方便使用，又提高了程式碼的整潔度和可觀性。
