链表/栈/队列/KMP

单链表

• 来构造邻接表
• 用于存图与树

• 基本结构：

  • head 表示头结点的下标
  • e[i] 表示节点i的值
  • ne[i] 表示节点i的下一个节点的下标
  • idx 存储当前已经用到了哪个节点，表示新节点

• 基本操作：

  • 向链表头插入一个节点
  • 在节点k后面插入一个节点
  • 删除节点k后面的一个节点

• 模板：

  int head;//头指针，指向头结点
  int e[N];//e[i]表示节点i的值
  int ne[N],//en[i]表示节点i的下一个节点 
  int idx;//存储新节点的下标
  
  //初始化
  void init(){
      head = 0; //0代表空节点
      idx = 1;//第一个插入的节点的下标为1
  }
  
  //头插法
  void add_to_head(int x){
      e[idx] = x; //存值
      ne[idx] = head; //连接
      head = idx; //转移连接
      idx ++ ; //
  }
  
  //在下标为k的节点后面插入一个数
  void add(int k, int x){
      e[idx] = x;
      ne[idx] = ne[k];
      ne[k] = idx;
      idx ++ ;
  }
  
  //删除下标为k的节点的后面的数
  void del(int k){
      ne[k] = ne[ne[k]];
  }
  
  //头删法，删除头结点
  void del_the_head(){
      head = ne[head];
  }
  
  //遍历输出所有节点
  for(int i = head; i; i = ne[i]) cout << e[i]; 
  

双链表

• 用于优化某些问题

• 基本结构：

  • l[i] 存储下标为i的节点的右边的节点
  • r[i] 存储下标为i的节点的左边的节点
  • e[i] 存储下标为i的节点的值
  • idx 存储新节点的下标
  • 默认0表示空的头结点，1 表示空的尾节点，所有节点在0与1之间插入

• 模板：

  const int N = 1e5 + 10;
  int l[N], r[N], e[N], idx;
  
  //初始化
  void init(){
  	//0表示空头节点，1表示空尾节点
      r[0] = 1; 
      l[1] = 0;
      idx = 2; //1，0已经被使用，初始化为2，表示第一个插入的节点的下标为2
  }
  
  //在下标为k的节点后面插入节点
  void add(int k, int x){
      e[idx] = x; //赋值
      l[idx] = k; //连接左
      r[idx] = r[k]; //连接右
      l[r[idx]] = idx; //转移连接
      r[l[idx]] = idx; //转移连接
      idx ++ ; //更新下标
  }
  
  //删除下标为k的节点
  void del(int k){
      r[l[k]] = r[k];
      l[r[k]] = l[k];
  }
  
  //遍历输出节点，注意起点与终点
  for(int i = r[0]; i != 1; i = r[i]) cout << e[i];
  
  //以下是统一插入个数与下标的代码
  //初始化
  void init(){
  	//0表示空头结点，N - 1表示空尾节点
  	r[0] = N - 1;
  	l[N - 1] = 0;
  	idx = 1; //0，N - 1被使用，下标从1开始，表示第一个插入的节点下标就是1
  }
  //add函数不变
  //遍历输出，注意起点和终点
  for(int i = r[0]; i != N - 1; i = r[i]) cout << e[i];
  

模板：

int stk[N], tt;//声明栈和栈顶下标
stk[ ++ tt] = x; //x入栈
tt --; //出栈
stk[tt]; //取栈顶元素
if(tt > 0) not empty //判断是否为空
else empty

单调栈：

• 应用：在一段序列中求距离某数最近的最大值/最小值

模板：

int q[N], hh, tt = -1; //声明队列，队首下标，队尾下标
q[ ++ tt] = x; //入队只能从队尾
hh --; //出队只能从队首
q[hh];//取队首
q[tt];//取队尾
if(hh <= tt)not empty //判断是否为空
else empty

单调队列（单调双端队列）：

• 引用：求固定大小的滑动窗口的最大值/最小值

模板：

int s[N], p[M];//主串和模式串，下标从1开始

//求next数组
void get_next(){
	for(int i = 2, j = 0; i <= m; ++ i){
		while(j && p[i] != p[j + 1]) j = ne[j];//j可以回跳并且匹配不成功时， j回跳
		if(p[i] == p[j + 1]) j ++ ; //匹配成功
		ne[i] = j; //存i可以回跳的位置
	}
}

//KMP
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 == n){ //当j等于模式串的长度时匹配成功
		j = ne[j]; //继续进行下一次匹配
		cout << i - n << endl; //输出匹配的起点下标
	}
}
//j = ne[j] ，j往前跳，相当于字串往后移