题目
这就相当于一条序列就好比让你使用指针操作一样。
分别有三种操作插入和删除以及修改起始点。
三个操作都很简单。
因为这里面所包含的只需要两个信息,当前点的序号以及下个点的位置。
结构体的话就能轻松实现但实际上如果理解到位的话数组也是可以的。(用数组貌似理解会更深?)
三种操作如果不熟悉可以画图一定要在纸上画出来,因为口头叙述终究还是没有自己画出来的有用。
结构体版
#include<iostream>
using namespace std;
const int sz=1e5+1;
int ct;
struct nd{
int x,y;
nd(){x=y=0;}
}a[sz];
char c;
void add(int x,int y){a[++ct].x=y,a[ct].y=a[x].y;a[x].y=ct;}
int main()
{
int n,i,x,y;
cin>>n;
while(n--)
{
cin>>c>>x;
if(c=='I')cin>>y,add(x,y);
else if(c=='H')add(0,x);
else a[x].y=a[a[x].y].y;
}
for(i=a[0].y;i;i=a[i].y)cout<<a[i].x<<' ';
return 0;
}
数组模拟版
#include<iostream>
using namespace std;
const int sz=1e5+1;
int v[sz],h[sz],t,ct;
void add(int x,int y){v[++ct]=y,h[ct]=h[x],h[x]=ct;}
int main()
{
int i,x,y,n;char c;
cin>>n;
while(n--)
{
cin>>c>>x;
if(c=='H')add(0,x);
else if(c=='I')cin>>y,add(x,y);
else h[x]=h[h[x]];
}
for(i=h[0];i;i=h[i])cout<<v[i]<<' ';
return 0;
}