课前温习
一、单链表
邻接表：存储图和树
e数组存储每个结点的值，ne数组存储每个结点的指向的下一个结点。
数组模拟链表比较快，指针模拟会涉及到new操作，比较慢。
核心模板
//head存储链表头，e数组存储结点值，ne数组存储结点的next指针，idx表示当前用到了哪个结点
int head,e[N],ne[N],idx; //初始化 void init(){ head=-1; idx=0; } //在链表头插入一个数a void insert(int a){ e[idx]=a,ne[idx]=head,head=idx++; } //将头结点删除，需要保证头结点存在 void remove(){ head=ne[head]; }
题目链接：826. 单链表
1.1题目描述
实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；
删除第 k 个插入的数后面的数；
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6
输出样例：
6 4 6 5
1.2思路分析
插入操作：
删除操作：
1.3代码实现
#include <iostream> using namespace std; const int N=100010; //head表示头结点的下标 //e[i]表示结点i的值 //ne[i]表示结点的next的指针（i的下一个点的下标） //idx表示当前用到了哪个点（点的编号/下标） int head,e[N],ne[N],idx; //初始化 void init(){ head=-1; idx=0; } //将x插到头结点 void add_to_head(int x){ e[idx]=x; //保存当前结点的值 ne[idx]=head; //将新结点的next指针指向head head=idx; //将新结点更新为头结点 idx++; } //将x插到下标为k的点的后面 void add(int k,int x){ e[idx]=x; //保存当前结点的值 ne[idx]=ne[k]; //将新结点的next指针指向下标为k的点的下一位结点 ne[k]=idx; //将下标为k的结点的next指针指向新结点 idx++; } //将下标为k的点的后面的点删掉 void remove(int k){ ne[k]=ne[ne[k]]; //将下标为k的结点的next指针指向下标为k的结点的下一位的下一位结点 } int main(){ int m; cin>>m; init(); while(m--){ int k,x; char op; cin>>op; if(op=='H'){ cin>>x; add_to_head(x); } else if(op=='D'){ cin>>k; if(!k) head=ne[head]; //如果删除的数是头结点，下标为0，需要先将头结点更新为头结点的下一位，否则将无法访问链表元素，造成内存泄漏 remove(k-1); //此处k代表第k个数，第k个数下标为k-1，下同 } else{ cin>>k>>x; add(k-1,x); } } for(int i=head;i!=-1;i=ne[i]){ cout<<e[i]<<" "; } return 0; }
二、双链表
用于优化某些问题
核心模板
//e数组存储结点的值，l数组存储结点的左指针，r数组存储结点右指针，idx表示当前用到了哪个结点
int e[N],l[N],r[N],idx; //初始化 void init(){ //0是左端点，1是右端点 r[0]=1,l[1]=0; //0号点的右边是1号点，1号点的左边是0号点 idx=2; } //在结点a的右边插入一个数x void insert(int a,int x){ e[idx]=x; l[idx]=a,r[idx]=r[a]; l[r[a]]=idx,r[a]=idx++; } //删除结点a void remove(int a){ l[r[a]]=l[a]; r[l[a]]=r[a]; }
//e[i]表示结点i的值 //l[i]表示结点的左指针（i的上一个点的下标） //r[i]表示结点的右指针（i的下一个点的下标） //idx表示当前用到了哪个点（点的编号/下标） int e[N],l[N],r[N],idx; //初始化 void init(){ //0表示左端点，1表示右端点 r[0]=1,l[1]=0; //0号点的右边是1号点，1号点的左边是0号点 idx=2; } //在下标为k的点的右边插入x void add(int k,int x){ e[idx]=x; //保存当前结点的值 r[idx]=r[k]; //将新结点的右指针指向原序列k的下一位结点 l[idx]=k; //将新结点的左指针指向k l[r[k]]=idx; //将原序列k的下一位结点的左指针指向新结点 r[k]=idx; //将k的右指针指向新结点 } //删除第k个点 void remove(int k){ r[l[k]]=r[k]; //将原序列k的前一个点的右指针指向k的右指针指向的值 l[r[k]]=l[k]; //将原序列k的下一个点的左指针指向k的左指针指向的值 }
题目链接：827. 双链表
2.1题目描述
实现一个双链表，双链表初始为空，支持 5 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数;
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10 R 7 D 1 L 3 IL 2 10 D 3 IL 2 7 L 8 R 9 IL 4 7 IR 2 2
输出样例：
8 7 7 3 2 9
2.2思路分析
初始化：
插入操作：
先更新原序列k的下一个结点左指针，再修改k的右指针。否则，若颠倒，因原本k的右指针指向的便是k的下一个结点，先修改k的右指针会导致k的右结点“丢失”，再进行下续操作将无意义。
若在k的左边插入结点，相当于在k的前一个结点的右边插入结点，所以只需实现右插入即可。
删除操作：
2.3代码实现
待更~
三、栈
先进后出
核心模板
//tt表示栈顶 int s[N],tt=0; //向栈顶插入一个数 s[++tt]=x; //从栈顶弹出一个元素 tt--; //栈顶的值 s[tt]; //判断栈是否为空 if(tt>0){ }
题目链接：828. 模拟栈
3.1题目描述
实现一个栈，栈初始为空，支持四种操作：
push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。
现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query中的一种。
输出格式
对于每个 empty 和 query操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。
数据范围
1≤M≤100000,1≤x≤109
所有操作保证合法。
输入样例：
10 push 5 query push 6 pop query pop empty push 4 query empty 1
输出样例：
5 5 YES 4 NO
3.2思路分析
利用数组进行模拟栈。
3.3代码实现
待更~
四、队列
先进先出
核心模板
普通队列
//在队尾插入元素，在队头弹出元素 //hh表示队头，tt表示队尾 int q[N],hh=0,tt=-1; //向队尾插入一个数 q[++tt]=x; //从队头弹出一个数 hh++; //队头的值 q[hh]; //判断队列是否为空 if(hh<=tt){ }
循环队列
//hh表示队头，tt表示队尾的后一个位置 int q[N],hh=0,tt=0; //向队尾插入一个数 q[tt++]=x; if(tt==N) tt=0; //从队头弹出一个数 hh++; if(hh==N) hh=0; //队头的值 q[hh]; //判断队列是否为空 if(hh!=tt){
题目链接：829. 模拟队列
4.1题目描述
实现一个队列，队列初始为空，支持四种操作：
push x – 向队尾插入一个数 x；
pop – 从队头弹出一个数；
empty – 判断队列是否为空；
query – 查询队头元素。
现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1≤M≤100000,1≤x≤109,所有操作保证合法。
输入样例：
10 push 6 empty query pop empty push 3 push 4 pop query push 6
输出样例：
NO 6 YES 4
4.2思路分析
待更~
4.3代码实现
待更~
