[ACW]826.单链表

今天药忘吃喽~ 2023-08-17 16:18 32阅读 0赞

[题链][Link 1]

tips:

1.数组模拟单链表，快

2.一些边界条件的考虑出题人已经除去了

3.题意的理解

4.下标用来索引，指针，逻辑与物理的区别，每个元素插入时物理顺序(数组存储位置idx)已经固定

5.单链表-邻接表：n个链表；常用应用：存储树和图

6.双链表：用来优化某些问题

7.e和ne用下标关联起来，不是像结构体那样，封装在一起

8.被卡点：第k个插入的数，存储地址一定在k-1，即使有删除操作，但是删除操作是逻辑上的(8这一点被2给保证了)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*struct Node{
        int val;
        struct Node* next;
    }
    动态链表 new Node;非常慢
    笔试题数组规模一般是10w~100w级别
    */
    
    // (2) 删除第k个插入的数后面的数；
    /*
     第k个插入的数，存储地址一定在k-1，即使有删除操作，但是删除操作是逻辑上的
     第k个插入的数其物理地址已经固定，索引下标是k-1,
     删除其后面的数，是逻辑上后面的数
    */
    #include<iostream>
    
    using namespace std;
    
    const int N=100010;
    
    //head表示头结点的下标
    //e[i]表示结点i的值
    //ne[i] 表示结点i的next指针是多少
    //idx 存储当前已经用到了哪个点
    int head,e[N],ne[N],idx;
    
    void init(){
        head = -1;
        idx = 0;
    }
    
    //将x插到头结点
    void add_to_head(int x){
        e[idx]=x;
        ne[idx]=head;
        head=idx;
        idx++;
    }
    
    // 将x插到下标是k的点后面
    void add(int k,int x){
        e[idx]=x;
        ne[idx]=ne[k];
        ne[k]=idx;
        idx++;
    }
    
    // 将下标是k的点后面的点删掉(逻辑上的)
    void rremove(int k){
        ne[k]=ne[ne[k]];
    }
    int main(){
        int m;
        cin>> m;
        init();
        while(m--){
            int k,x;
            char op;
            cin>>op;
    
            if(op == 'H'){
                cin>>x;
                add_to_head(x);
            }
            else if(op == 'D'){
                cin>>k;
                if(!k) head=ne[head];
                rremove(k-1);
            }
            else{
                cin>>k>>x;
                add(k-1,x);
            }
        }
    
        for(int i=head; i!=-1; i=ne[i]) cout<<e[i]<<' ';
        cout<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/SUMaywlx/p/11440862.html

[Link 1]: https://www.acwing.com/problem/content/828/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/083d6c6cbc6243c69a0587da522af203.png