一、用数组表示链表
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=-1
int 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和printf
cin>>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、
