题目描述
单链表
静态链表(用数组模拟链表)
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int head,e[N],ne[N],idx;
void init()
{
head=-1;//数组中下标为-1的不存在,在链表中头结点表示指示作用,无实际意义,故将head=-1,表示位置,没有数值
idx=0; //表示链表中的第一个结点,序号为0
}
//在头结点后面插入结点
void add_to_head(int x)
{
e[idx]=x; //每个结点有两个部分,e[]中存数值
ne[idx]=head; //该结点的另一个部分ne[]存next指针,表示下一个结点的位置
head=idx; //将头结点顺次移动
idx++; //准备下一个结点
}
void remove(int k)
{
ne[k]=ne[ne[k]]; // 直接跳过k后面一个结点,指向下一个结点
}
//在第k个结点后面插入结点 插入方法类似头结点
void add(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
int main()
{
int m;
cin>>m;
init(); //先初始化,,因为循环里是操作,所以在循环外面初始化
while(m--)
{
char op;
cin>>op;
if(op=='H')
{
int x;
cin>>x;
add_to_head(x);
}
else if(op=='D')
{
int k;
cin>>k;
if(!k)head=ne[head]; //删除的是头结点,则新的头结点是之前头结点的下一个
remove(k-1); //因为初始化是从0开始,所以删除的是k+1后面的结点
}
else
{
int k,x;
cin>>k>>x;
add(k-1,x); //同删除一个道理
}
}
//遍历输出处理后的链表:从头结点开始,-1是最后一个结点的下一个位置
for(int i=head;i!=-1;i=ne[i])cout<<e[i]<<" ";
return 0;
}