AcWing算法基础课——简单数据结构模板

本文主要是介绍AcWing算法基础课——简单数据结构模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

说明

        本篇文章只给出代码模板，以及自己对该模板的理解。如果想看正确的算法思路，可以移步AcWing官网看详情。链接：常用代码模板2——数据结构 - AcWing

        如有错误，欢迎大家批评指正。

简单数据结构模板

一、链表

1.1 数组模拟单链表模板

int head,e[N],ne[N],idx;//head表示头节点，数组e[]用于存放节点的值，数组ne[]（next）用于存放当前节点的指向下一个节点的下标，idx为当前节点的下标
void init(){//链表初始化head=-1;//表示头节点的next节点为NULL（空节点）idx=0;
}
void add_to_head(int x){//头插法,x为要插入的值e[idx]=x,ne[idx]=head,head=idx++;
}
void add(int k,int x){//在第k与第k+1个节点之间插入一个节点，值为xe[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove_head(){//删除头节点head=ne[head];
}
void remove(int k){//删除第k的下一个节点ne[k]=ne[ne[k]];
}
void modify(int k,int x){//修改第k个节点的下一个节点的值为xe[ne[k]]=x;
}

1.2 数组模拟双链表模板

int e[N],l[N],r[N],idx;//数组e[]用于存放节点的值，数组l[]表示当前节点的前驱节点的下标，数组r[]表示当前节点的后继节点的下标，idx表示当前节点的下标
void init(){//链表初始化//0表示头节点的下标，1表示尾节点的下标，idx从2开始r[0]=1,l[1]=0,idx=2;
}
void add_to_head(int x){//头插法,x为要插入的值e[idx]=x,r[idx]=r[0],l[idx]=0,l[r[0]]=idx,r[0]=idx++; 
}
void add(int k,int x){//插入到第k与第k+1个节点之间插入一个节点，值为xe[idx]=x,r[idx]=r[k],l[idx]=k,l[r[k]]=idx,r[k]=idx++; 
}
void remove_head(){//删除头节点r[0]=r[r[0]],l[r[0]]=0;
}
void remove(int k){//删除第k的下一个节点l[r[k]]=l[k];r[l[k]]=r[k];
}
void modify(int k,int x){//修改第k的下一个节点的值为xe[r[k]]=x;
}

二、栈

2.1 数组模拟栈模板

int stk[N],tt=0;//数组stk[]模拟栈中的值，tt表示栈顶下标
void my_push(int x){//向栈顶插入一个数xstk[++tt]=x;
}
int my_top(){//查询栈顶元素return stk[tt];
}
void my_pop(){//弹出栈顶tt--;
}
bool my_empty(){//判断栈是否为空return tt<=0;
}

2.2 单调栈模板

//常见模型：找出每个数左边离它最近的比它大/小的数
bool check(int x,int idx){//x为要check的值，idx为下标//根据题意完善函数
}
int stk[N],tt=0;//数组stk[]模拟栈中的值，tt表示栈顶下标
for (int i = 1;i<=n;i++){while(tt&&check(stk[tt],i)) tt--;//如果不满足条件则弹出栈顶stk[++tt]=i;//下标i入栈
}

三、队列

3.1 数组模拟普通队列模板

int que[N],hh=0,tt=-1;//数组que[]模拟普通队列中的值，hh表示队头下标，tt表示队尾下标
void my_push(int x){//将x入队尾que[++tt]=x;
}
int my_front(){//查询队头元素return que[hh];
}
void my_pop(){//弹出队头hh++;
}
bool my_empty(){//判断队列是否为空return hh>tt;
}

3.2 数组模拟循环队列模板

int que[N],hh=0,tt=0;//数组que[]模拟循环队列中的值，hh表示队头下标，tt表示队尾下标
void my_push(int x){//将x入队尾que[++tt]=x;if(tt==N) tt=0;
}
int my_front(){//查询队头元素return que[hh];
}
void my_pop(){//弹出队头hh++;if(hh==N) hh=0;
}
bool my_empty(){//判断队列是否为空return hh==tt;
}

3.3 数组模拟单调队列模板

//常见模型：找出滑动窗口中的最大值/最小值
bool check_out(int x){//根据题意完善函数
}
bool check(int x,int idx){//根据题意完善函数
}
int que[N],hh=0,tt=-1;//数组que[]模拟队列中的值，hh表示队头下标，tt表示队尾下标
for(int i = 0;i<n;i++){while(hh<=tt&&check_out(que[hh])) hh++;//判断队头是否滑出窗口while(hh<=tt&&check(que[tt],i)) tt--;que[++tt]=i;//下标i入队
}

四、KMP

4.1 KMP模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的next数组：
for (int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1]) j=ne[j];if (p[i]==p[j+1]) j++;ne[i]=j;
}
//匹配
for (int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1]) j=ne[j];if(s[i]==p[j+1]) j++;if(j==m){j=ne[j];// 匹配成功后的逻辑}
}

五、Trie(字典树)

5.1 Trie模板

//Trie字符串统计
int son[N][26],cnt[N],idx;//0号点既是根节点，又是空节点,son[][]存储树中每个节点的子节点,cnt[]存储以每个节点结尾的单词数量,idx表示下标
// 插入一个字符串
void insert(char *str){int p=0;for(int i = 0;str[i];i++){int u=str[i]-'a';if(!son[p][u]) son[p][u]=++idx;p=son[p][u];}cnt[p]++;
}
// 查询字符串出现的次数
int query(char *str){int p=0;for(int i = 0;str[i];i++){int u=str[i]-'a';if(!son[p][u]) return 0;p=son[p][u];}return cnt[p];
}

六、并查集

6.1 朴素并查集模板

int fa[N];//存储每个节点的根节点（父节点、祖宗节点）
int find(int x){//返回x的根节点if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}
void solve(){//根节点的初始化,假定节点编号是1~nfor(int i = 1;i<=n;i++) fa[i]=i;//合并x,y两个节点所在的集合fa[find(x)]=find(y);
}

6.2 维护size的并查集模板

int fa[N],size[N];//fa[]存储每个节点的根节点, size[]只有根节点的有意义，表示根节点所在集合中的点的数量
int find(int x){//返回x的根节点if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}
void solve(){//根节点的初始化,假定节点编号是1~nfor(int i = 1;i<=n;i++) fa[i]=i,size[i]=1;//合并x,y两个节点所在的集合size[find(y)]+=size[find(x)];fa[find(x)]=find(y);
}

6.3 维护到根节点距离的并查集模板

int fa[N],d[N];//fa[]存储每个节点的根节点, d[x]存储x到fa[x]的距离
int find(int x){//返回x的根节点if(x!=fa[x]){int u=find(fa[x]);d[x]+=d[fa[x]];fa[x]=u;}return fa[x];
}
void solve(){//根节点的初始化,假定节点编号是1~nfor(int i = 1;i<=n;i++) fa[i]=i,d[i]=0;//合并x,y两个节点所在的集合fa[find(x)]=find(y);d[find(x)]=distance;//根据具体问题，初始化find(x)的偏移量
}

七、堆

7.1 数组模拟堆模板

//h[N]存储堆中的值,h[1]是堆顶的值，x的左儿子是2x,右儿子是2x+1，ph[k]存储第k个插入的点在堆中的位置，hp[k]存储堆中下标是k的点是第几个插入的,heap_size为堆的大小,m为ph[]和hp[]的大小
int h[N],ph[N],hp[N],heap_size,m;
void heap_swap(int a,int b){//交换两个点及其映射关系swap(ph[hp[a]],ph[hp[b]]);swap(hp[a],hp[b]);swap(h[a],h[b]);
}
void down(int u){//下调下标为u的数int t=u;if (u*2<=size&&h[u*2]<h[t]) t=u*2;if (u*2+1<=size&&h[u*2+1]<h[t]) t=u*2+1;if (u!=t){heap_swap(u,t);down(t);}
}
void up(int u){//上调下标为u的数while(u/2&&h[u]<h[u/2]){heap_swap(u,u/2);u>>=1;}
}
void my_push(int x){//将x入堆heap_size++,m++;ph[m]=heap_size;hp[heap_size]=m;h[heap_size]=x;up(heap_size);
}
int my_top(){//取出堆顶元素return h[1];
}
void my_pop(){//弹出堆顶元素heap_swap(1,heap_size);heap_size--;down(1);
}
void my_remove(int k){//删除第k个插入的数k=ph[k];//将k映射成堆中的下标heap_swap(k,heap_size);heap_size--;down(k),up(k);//down(),up()只会做其中的一个操作
}
void my_modify(int k,int x){//修改第k个插入的数为xk=ph[k];//将k映射成堆中的下标h[k]=x;down(k),up(k);
}
void solve(){//快速建堆，时间复杂度是O(n)的级别for (int i = n/2;i;i--) down(i);//根据题意进行操作//……
}

八、哈希

8.1 一般哈希模板1（拉链法）

//用到邻接表（前向星实现，使用了单链表（用之前数组模拟单链表实现））
const int N = 2e5+5,
int h[N],e[N],ne[N],idx;
void insert(int x){//向哈希表中插入一个数int k=(x%N+N)%N;e[idx]=x;ne[idx]=h[k];h[k]=idx++;
}
bool find(int x){//查找一个数是否在hash表内int k=(x%N+N)%N;for(int i=h[k];i!=-1;i=ne[i]){if(e[i]==x) return true;}return false;
}
void solve(){memset(h,-1,sizeof h);//插入xinsert(x);//查询x是否在哈希表中，如果在哈希表中返回Yes，否则返回Nocout << (find(x)?"Yes":"No") << endl;
}

8.2 一般哈希模板2（开放寻址法）

const int N = 2e5+5,null = 0x3f3f3f3f;
int h[N];
int find(int x){//如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置int t=(x%N+N)%N;while(h[t]!=null&&h[t]!=x){t++;if(t==N) t=0;}return t;
}
void solve(){memset(h,0x3f,sizeof h);int t = find(x);//预处理，因为后续的插入和查询操作都需要用到find()函数//插入xh[t]=x;//查询x是否在哈希表中，如果在哈希表中返回Yes，否则返回Nocout << (h[t]!=null?"Yes":"No") << endl;
}

8.3 字符串哈希模板

//核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
//小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
using ull = unsigned long long;
const int N = 1e5+5,P = 131;//数据范围为1e5
char s[N];
ull h[N],p[N];//h[k]存储字符串前k个字母的哈希值, p[k]存储(p^k)%(2^64)
ull get(int l,int r){return h[r]-h[l-1]*p[r-l+1];
}
void solve(){cin >> s+1;//读入字符串，下标从1开始//初始化p[0]=1;for(int i = 1;i<=n;i++){h[i]=h[i-1]*P+s[i];p[i]=p[i-1]*P;}//计算子串 str[l~r]的哈希值ull ans = get(l,r);
}

这篇关于AcWing算法基础课——简单数据结构模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---