数据结构 单链表

#include<iostream>

using namespace std;

const int N=100010;
int head,e[N],ne[N],idx;

void init(){
    head=-1;
    idx=0;
}

void add_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++;
}

void remove(int k){
    ne[k]=ne[ne[k]];
}

int main(){
    init();
    int m;
    scanf("%d",&m);
    
    while(m--){
        char op;
        int k,x;
        cin>>op;
        
        if(op=='H'){
            scanf("%d",&x);
            add_head(x);
        }else if(op=='D'){
            scanf("%d",&k);
            if(!k){
                head=ne[head];
            }else{
                remove(k-1);
            }
        }else{
            scanf("%d%d",&k,&x);
            add(k-1,x);
        }
    }
    
    for(int i=head;~i;i=ne[i]){
        printf("%d ",e[i]);
    }
    printf("\n");
    
    return 0;
}

把模板记住就好了。这题的 $k$ 是从 $1$ 开始的，但是我们的 $idx$ 是从 $0$ 开始的，$idx$ 是索引下标，需要注意一下。另外删除的时候注意假设我们删除的元素是第一个插入的元素，也就是下标是 $0$ 的元素，这个时候需要特判一下。防止数组越界。

head=idx++;
//等价于下面的
head=idx;
idx++;

这是因为 idx++ 是使用完了之后再更新。也就是使用的是更新之前的数值。可以记为 $idx$ 在 $+$ 的前面，所以用的是前面（之前的，未更新的）的数值。

原文地址：https://blog.csdn.net/L3102250566/article/details/145283607

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！