第二章数据结构（一）(数组模拟链表、队列，栈以及kmp)-拓冰建站

一、用数组表示链表

1、单链表基础插入和删除操作

#include<bits/stdc++.h>
//803 区间合并
using namespace std;
const int N=1e4+10;
//head表示头结点的下标
//e[]存结点的值
//ne[]存next指针
//idx当前已经用到哪个点了
int head,e[N],ne[N],idx;
void init()
{head=-1;idx=0;
}
//头插入操作
void add_to_head(int x)
{e[idx]=x;ne[idx]=head;head=idx;idx++;
}
//x插到k后面//插入到某个点的后一个点O（1）
void add(int x,int k)
{ne[idx]=ne[k];e[idx]=x;ne[k]=idx;idx++;
}
//将下标为k的后面的点删掉
void remove(int k)
{ne[k]=ne[ne[k]];
}

2、双链表

#include<bits/stdc++.h>
//双链表
using namespace std;
const int N=1e5+10；
int m;
int e[N],l[N],r[N],idx;
//初始化点0为左端点，1为右端点
void init()
{l[1]=0,r[0]=1,idx=1;
}//添加点可以实现在指定位置左右两边添加结点
void add(int k,int x)
{e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;
}
//删掉k下标所在的位置
void remove(int k)
{r[l[k]]=r[k];l[r[k]]=l[k];
}int main()
{}

3、模拟栈和队列

#include<bits/stdc++.h>
//双链表
using namespace std;
const int N=1e5+10；
int stk[N],tt;//初始tt=-1int main()
{//栈后进先出//插入stk[++tt]=x;//弹出t--;//判断栈是否为空if(tt>=0)not empty;else empty;//栈顶数据stk[tt];//队列int q[N],tt=0,hh=-1;//入队q[++tt]=x;//出队hh++;//判断是否非空if(hh<=tt)not empty;else empty;//取出队头元素q[hh];   
}

3、单调栈

#include<bits/stdc++.h>
//830单调栈
using namespace std;
const int N=1e5+10;
int stk[N],tt=0;//初始tt=-1
int n;
int main()
{cin.tie(0);ios::sync_with_stdio(false);//接近scanf和printfcin>>n;for(int i=0;i<n;i++){int x;cin>>x;while(tt&&stk[tt]>=x)tt--;//只要非空就一直向前找//让没用的值出栈if(tt)cout<<stk[tt]<<endl;//只要能找到且非空就输出else cout<<-1<<endl;stk[++tt]=x;//入栈}
}

4、单调队列，求滑动窗口的最大值和最小值

#include<bits/stdc++.h>
//154滑动窗口
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int n,k;
int main()
{scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&a[i]);int hh=0,tt=-1;for(int i=0;i<n;i++){if(hh<=tt&&i-k+1>q[hh])hh++;//只要在循环过程中到达的某个下标处不可能会包含q[hh]的值所在的位置，hh++//h++之后，q[hh]所在的位置一定在区间内while(hh<=tt&&a[q[tt]]>=a[i])tt--;//然后在区间内删除所有大于要插入的数值的数q[++tt]=i;//此时可能hh==tt，所以先把要插入的下标放入if(i>=k-1)printf("%d",a[q[hh]]);//hh总在区间的最左边       }
}

二、kmp算法

在模板串p与主串s进行匹配的时候，到达某个位置的时候不匹配了，按照暴力做法，从p的头开始匹配，但是存在一种情况，虽然主串s目前匹配到的位置和p串已经不匹配了，但是可以从模板串的某一个中间位置继续匹配，因为在主串不能完全匹配p的位置，可能可以匹配从p的头开始某一小段，这样就不必再从p的开头开始了。

1、暴力枚举方式

2、kmp算法next[i]=j的含义，模板串的以i为终点的部分，最长和长度为j的前缀相等。

3、算法实现（还没完善）

#include<bits/stdc++.h>
//kmp算法
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m;
int p[N];//p和s都是从1开始存
int s[M];
int ne[N];//从0开始
int main()
{//求next数组//kmp匹配的过程cin>>m>>n;for(int i=1,j=0;i<=m;i++){while(j&&s[i]!=p[j+1])j=next[j];//只要当前位置不匹配,就强行利用前缀匹配if(s[i]==p[j])j++;//如果匹配就继续if(j==n){}}
}

4、