JZTXT

链表/栈/队列/KMP

发布时间 2023-07-28 18:53:29作者: MoiLip

  • 链表

    • 用数组模拟，不同于结构体加指针
    • 调用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往前跳，相当于字串往后移