题目描述
题面
有动态数组列表L,L列表的末尾有一个名为END的特殊元素,L的元素可以通过一个指向元素的指针来访问。
对于动态整数列表L,我们可以执行以下操作序列。
insert(x):在指针指示的元素之前插入x。执行此操作后,指针将指向插入的元素。
move(d):如果d为正,将指针移动到d的末端。如果d为负值,将指针向前移动d。
erase():删除指针指示的元素。执行此操作后,指针将指向已删除元素的下一个元素。如果没有这样的元素,指针应该指向END。
注意:在初始状态下,L为空,指针指向END。
输入
最开始输入一个q,代表询问组数:
q
接下来会输入q组询问:
0 x 代表insert(x)
1 d 代表move(d)
2 代表erase()
输出
执行给定操作完成后,按顺序打印列表的所有元素。打印一行中的元素。
数据限制
1<=q<=500,000
指针指示操作之可能指向在L中的元素或END
当指针指向END时,将不执行擦除操作
-1,000,000,000<=x<=1,000,000,000
执行所有操作后,L不为空
指针的移动距离总和不超过1,000,000
输入样例
5
0 1
0 2
0 3
1 1
2
输出样例
3
1
算法1
STL
C++ 代码
#include <bits/stdc++.h>
//0代表前插,1代表移动指针,2代表删除指针所指元素
using namespace std;
int main()
{
list<int> l;
auto it=l.end();//指向空
int q;
cin>>q;
while(q--)
{
int op;
cin>>op;
if(op==0)
{
int x;
cin>>x;
it=l.insert(it,x);//it前插x,若为it=l.inser(++it,x)则为后插
}
else if(op==1)//移动指针
{
int d;
cin>>d;
if(d>0)
{
while(d--) it++;//迭代器后移
}
else while(d++) it--;
}
else//删除指针所指元素
{
if(it!=l.end())
it=l.erase(it);
}
}
for(it=l.begin();it!=l.end();it++)//遍历链表
{
cout<<*it<<endl;
}
}