一、数组模拟——单链表

用数组模拟链表，因为c++中new函数太慢了，比赛中一般用数组模拟链表，一般增删元素都是增删指定元素的下一项，因为当前节点存有下个节点的地址，但是上一个节点的位置不知道。

1、思路

2、代码模板

#include<iostream>
using namespace std;
const int N=1e5+10;
int head;							//head表示头节点的下标 
int e[N];							//存放节点的值 
int ne[N];							//存放下一个节点的位置，即当前节点存的指针 
int idx;							//表当前已经用到了哪个节点 
//初始化
void init()							 
{
	head=-1;
	idx=0;
}
//将x插到头节点后面 
void add_to_head(int x) 			
{
	e[idx]=x;						//将值记录下来			
	ne[idx]=head;					//将指针指向原来头指针指向的值 
	head=idx;						//头指针指向插入的值 
	idx++;							//节点+1 
}
//在第k个点后面插入x 
void add(int k,int x)				
{
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;	
} 
//将下标是k的点的后面的点删掉 
void remove(int k)
{
	ne[k]=ne[ne[k]];				//ne[k]是下个节点的位置，ne[ne[k]]是下下个节点的位置 
}
int main()
{
	return 0;
 } 

二、数组模拟——双链表

2、代码模板：

#include<iostream>

using namespace std;

const int N=1e5+10;
int m;
int e[N],l[N],r[N],idx;

//初始化
void init()
{
	//idx中的0表示左端点，1表示右端点,从2开始记录 
	r[0]=1,l[1]=0;
	idx=2; 
} 
//在第k个数后面插入x 
void add(int k,int x)
{
	e[idx]=x;			//记录值 
	r[idx]=r[k];		//插入的点右边是原来k右边的点的地址 
	l[idx]=k;			//插入的点的左边是k,这里的k是地址 
	l[r[k]]=idx;		//先改后面的，再改前面的k 
	r[k]=idx;
} 
//删除第k个点 
void remove(int k)
{
	r[l[k]]=r[k];		//让k点左边的数，的右边，直接等于k的右边 
	l[r[k]]=l[k];		//同理 
}

三、邻接表

四、数组模拟——栈——先进后出

2、代码模板

#include<iostream>

using namespace std;

const int N=1e5+10;

int stk[N],tt;

//插入一个数
stk[++tt]=x;
//弹出一个数
tt--;
//判断栈是否为空
if(tt>0)
	printf("不为空");
else
	printf("空"); 
//栈顶
stk[tt]; 

五、数组模拟——队列——先入先出

2、代码模板：

#include<iostream>

using namespace std;

const int N=1e5+10;
//在队尾插入元素，在队头弹出元素 
int q[N],hh,tt;			//hh是头，tt是尾 
//插入元素
q[++tt]=x;
//弹出元素
hh++;					// 
//判断队列是否为空
if(hh<=tt)
	cout<<"不为空";
else
	cout<<"空";
//取出队头元素
q[tt]; 

六、单调栈

2、代码模板;

#include<iostream>

using namespace std;

const int N=1e5+10;

int n;
int stk[N],tt;

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		while(tt&&stk[tt]>=x)			//当栈不为空 且栈顶元素大于x时 
			tt--;						//去除栈顶元素 
		if(tt)
			printf("%d",stk[tt]);		//如果tt存在，输出 
		else
			printf("-1");
		stk[++tt];						//将元素x入栈 
	}
	return 0;
}

七、单调队列

1、思路

2、代码模板：

#include<iostream>

using namespace std;

const int N=1e6+10;

int n,k;
int a[N],q[N];					//a存原来的值，q存的队列,q存的数是下标 

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d %d",&a[i],&k); 
	int hh=0,tt=-1;
	for(int i=0;i<n;i++)				//滑窗里的最小值 
	{
		//判断队头是否已经滑出窗口
		
		if(hh<=tt&&i-k+1>q[hh])			//hh<=tt代表为空队列, i-k+1是当前滑窗的左端点
							// 如果左端点大于队首，代表队首出滑窗了 
			hh++;
		while(hh<=tt&&a[q[tt]]>=a[i])	//如果滑窗最后一位的值大于新加入的值 
			tt--;						//弹出 
		q[++tt]=i;						//把新插入的数加到队列 
		if(i>=k-1)						//特判，不足k个数时不输出，满足时才输出 
			printf("%d ",a[q[hh]]); 
	}
		
	hh=0,tt=-1;
	for(int i=0;i<n;i++)				//滑窗里的最小值 
	{
		//判断队头是否已经滑出窗口
		
		if(hh<=tt&&i-k+1>q[hh])			
										 
			hh++;
		while(hh<=tt&&a[q[tt]]<=a[i])	 //改成<= 
			tt--;						
		q[++tt]=i;						
		if(i>=k-1)						
			printf("%d ",a[q[hh]]); 
	}	
	return 0;
}

八、kmp

1、思路

2、代码模板：

#include<iostream>

using namespace std;
const int N=1e4+10;
const int M=1e5+10;
int n,m;
char p[N],s[M];						//s是长字符串，p是短字符串 
int ne[N];							//记录p字符串每一位对不上时要跳到哪个位置 
int main()
{
	cin>>n>>p+1>>m>>s+1;			//数组从1开始 
	//求next的过程
	for(int i=2,j=0;i<=n;i++)		//从2开始，前面都是0 
	{
		while(j&&p[i]!=p[j+1])		//
			j=ne[j];
		if(p[i]==p[j+1])	
			j++;
		ne[i]=j;
	} 
	//kmp匹配过程 
	for(int i=1,j=0;i<=m;i++)
	{
		while(j&&s[i]!=p[j+1])		//当j没有到开头，且当前两个字符串这一位不匹配 
			j=ne[j];	
		if(s[i]==p[j+1])
			j++;
		if(j==n)					//匹配成功 
		{
			printf("%d ",i-n);
			j=ne[j];
		} 
	}   
	return 0;
}