链表/栈/队列/KMP

  • 链表

    • 用数组模拟,不同于结构体加指针
    • 调用new关键字开上万级别的节点非常慢,基本会超时
    • 单链表

      • 来构造邻接表
      • 用于存图与树
      • 基本结构:
        • 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
      
    • 单调队列(单调双端队列):
      • 引用:求固定大小的滑动窗口的最大值/最小值
  • KMP

    • 模式串匹配算法
    • 模板:
      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往前跳,相当于字串往后移
      

热门相关:洪荒二郎传   富贵不能吟   上神来了   办公室关系   今天也没变成玩偶呢