1.单链表
题目概述
输入样例：
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
思路
单链表的存储结构：
链表插入操作：
链表删除操作：
代码奉上
#include <bits/stdc++.h> using namespace std; const int N = 100010; int e[N],ne[N],idx,head=-1; void removepo(int k) //删除节点 { ne[k]=ne[ne[k]]; } void add_to_head(int x) //在头节点插入数据 { e[idx]=x; ne[idx]=head; head=idx++; } void add(int k,int x) //普通插入 { e[idx]=x; ne[idx]=ne[k]; ne[k]=idx++; } int main() { int n; cin>>n; while(n--) { int k,x; string op; cin>>op; if(op=="H") { scanf("%d",&x); add_to_head(x); } else if(op=="D") { scanf("%d",&k); if(k==0) head=ne[head]; //头节点特判 else removepo(k-1); } else { scanf("%d%d",&k,&x); add(k-1,x); } } for(int i=head;i!=-1;i=ne[i]) printf("%d ",e[i]); return 0; }
2.双链表
题目概述
数据范围
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
思路
类似单链表
初始化时偷懒，0表示头节点，1表示尾节点
删除操作：
代码奉上
#include <bits/stdc++.h> using namespace std; const int N = 100010; int l[N],r[N],e[N],idx; void init() { r[0]=1; l[1]=0; idx=2; } void removepo(int k) { r[l[k]]=r[k]; l[r[k]]=l[k]; } void add(int k,int x) { e[idx]=x; r[idx]=r[k]; l[idx]=k; l[r[k]]=idx; r[k]=idx++; } int main() { init(); int n; cin>>n; while(n--) { string m; int k,x; cin>>m; if(m=="L") { scanf("%d",&x); add(0,x); } else if(m=="R") { scanf("%d",&x); add(l[1],x); } else if(m=="D") { scanf("%d",&k); removepo(k+1); } else if(m=="IL") { scanf("%d%d",&k,&x); add(l[k+1],x); } else { scanf("%d%d",&k,&x); add(k+1,x); } } for(int i=r[0];i!=1;i=r[i]) printf("%d ",e[i]); return 0; }
