链表/栈/队列/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往前跳，相当于字串往后移