变量含义:
1. idx第一个没有使用到的数组下标,e[idx]=a等价于new node();
2. 数组下标为k含义:第k+1个输入的点;
3. 数组下标pos pos—epos—nepos;
注意事项:
1. 头插法,head不断更新;
2. 删除:if 首元结点 head=ne[head];return;//不需要修改ne,
#include<iostream>
#include<string>
using namespace std;
const int N=100000;
int idx=0,head=-1,e[N],ne[N];
void add_head(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
void remove(int k)
{
if(k==-1)
{
head=ne[head];
return;
}
ne[k]=ne[ne[k]];
}
void add(int x,int k)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
int main()
{
int m;
cin>>m;
while(m--)
{
string op;
cin>>op;
if(op=="H")
{
int x;
cin>>x;
add_head(x);
}
if(op=="D")
{
int k;
cin>>k;
remove(k-1);
}
if(op=="I")
{
int k,x;
cin>>k>>x;
add(x,k-1);
}
}
for(int pos=head;pos!=-1;pos=ne[pos])cout<<e[pos]<<" ";
return 0;
}
从讨论区收获的心得:
- scanf(“%c\n”,op);会把回车和空格读入,要控制格式;
- ne[0]=head,e[o]=-1;等价于增加头结点在链表的链式表达中;
- 续2:插ne[idx]=ne[0]balabala;
- 续2:删首元结点 ne[0]=ne[ne[0]]==->和非首元节点的删除形式统一;
5.