【模板】链表

· · 个人记录

P1160 AC代码

#include <cstdio>
using namespace std;
class List{
    private:
        struct node{
            int l,r;
            node():l(-1),r(-1){}
        } *a;
    public:
        List(int size=1e5){
            a=new node[size+10];
            a[0].r=1,a[1].l=0;
        }
        ~List(){
            delete []a;
        }
        void addl(int x,int pos){
            a[x].r=pos;
            if(~a[pos].l) a[a[pos].l].r=x;
            a[x].l=a[pos].l;
            a[pos].l=x;
        }
        void addr(int x,int pos){
            a[x].l=pos;
            if(~a[pos].r) a[a[pos].r].l=x;
            a[x].r=a[pos].r;
            a[pos].r=x;
        }
        void del(int x){
            if(~a[x].l) a[a[x].l].r=a[x].r;
            if(~a[x].r) a[a[x].r].l=a[x].l;
            a[x].l=a[x].r=-1;
        }
        void run(){
            for(int i=a[0].r;~i;i=a[i].r){
                printf("%d ",i);
            }
        }
};
List a;
int n,m;
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){int pos,op;
        scanf("%d%d",&pos,&op);
        if(op==0) a.addl(i,pos);
        else a.addr(i,pos);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){int x;
        scanf("%d",&x);
        a.del(x);
    }
    a.run();
    return 0;
}

过不了模板（查找太慢），但功能多

#include <cstdio>
using namespace std;
template<typename T=int>
class Linked_list{
    private:
        struct node{
            T num;
            node *l,*r;
            node(const T &num,node *l=NULL,node *r=NULL):num(num),l(l),r(r){}
            node():l(NULL),r(NULL){}
            void del(){if(r!=NULL) r->del(),delete r;}
        } head;
    public:
        ~Linked_list(){
            head.del();
        }
        node* find(const T &num){
            for(node *i=head.r;i!=NULL;i=i->r){
                if(i->num==num) return i;
            }
            return NULL;
        }
        int findidx(const T &num){
            int now=1;
            for(node *i=head.r;i!=NULL;i=i->r,now++){
                if(i->num==num) return now;
            }
            return 0;
        }
        void addempty(const T &num){
            node *tmp=new node(num,&head,NULL);
            head.r=tmp;
        }
        void addl(const T &num,const T &posnum){
            node *pos=find(posnum);
            node *tmp=new node(num,pos->l,pos);
            if(pos->l!=NULL) pos->l->r=tmp;
            pos->l=tmp;
        }
        void addr(const T &num,const T &posnum){
            node *pos=find(posnum);
            node *tmp=new node(num,pos,pos->r);
            if(pos->r!=NULL) pos->r->l=tmp;
            pos->r=tmp;
        }
        void del(const T &num){
            node *tmp=find(num);
            if(tmp==NULL) return ;
            if(tmp->l!=NULL) tmp->l->r=tmp->r;
            if(tmp->r!=NULL) tmp->r->l=tmp->l;
            delete tmp;
        }
        template<typename function>
        void run(function opt){
            for(node *i=head.r;i!=NULL;i=i->r){
                opt(i->num);
            }
        }
};
int n,m;
Linked_list<> a;
void opt(int x){printf("%d ",x);}
int main(){
    a.addempty(1);
    scanf("%d",&n);
    for(int i=2;i<=n;i++){int pos,op;
        scanf("%d%d",&pos,&op);
        if(op==0) a.addl(i,pos);
        else a.addr(i,pos);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){int x;
        scanf("%d",&x);
        a.del(x);
    }
    a.run(opt);
    return 0;
}
/*
in:
10
1 0
1 1
1 1
1 1
4 1
2 1
2 0
7 1
7 1
5
6
3
4
7
6
out:
8 2 10 9 1 5 
*/

map优化查询

#include <cstdio>
#include <map>
using namespace std;
template<typename T=int>
class Linked_list{
    private:
        struct node{
            T num;
            node *l,*r;
            node(const T &num,node *l=NULL,node *r=NULL):num(num),l(l),r(r){}
            node():l(NULL),r(NULL){}
            void del(){if(r!=NULL) r->del(),delete r;}
        } head;
        map<T,node*> nodes;
    public:
        ~Linked_list(){head.del();}
        node* find(const T &num){
            return nodes[num];
        }
        void addempty(const T &num){
            node *tmp=new node(num,&head,NULL);
            head.r=tmp;
            nodes[num]=tmp;
        }
        void addl(const T &num,const T &posnum){
            node *pos=find(posnum);
            node *tmp=new node(num,pos->l,pos);
            if(pos->l!=NULL) pos->l->r=tmp;
            pos->l=tmp;
            nodes[num]=tmp;
        }
        void addr(const T &num,const T &posnum){
            node *pos=find(posnum);
            node *tmp=new node(num,pos,pos->r);
            if(pos->r!=NULL) pos->r->l=tmp;
            pos->r=tmp;
            nodes[num]=tmp;
        }
        void del(const T &num){
            node *tmp=find(num);
            if(tmp==NULL) return ;
            if(tmp->l!=NULL) tmp->l->r=tmp->r;
            if(tmp->r!=NULL) tmp->r->l=tmp->l;
            nodes.erase(nodes.find(num));
            delete tmp;
        }
        template<typename function>
        void run(function opt){
            for(node *i=head.r;i!=NULL;i=i->r){
                opt(i->num);
            }
        }
};
int n,m;
Linked_list<> a;
void opt(int x){printf("%d ",x);}
int main(){
    //freopen("test.in","r",stdin);
    a.addempty(1);
    scanf("%d",&n);
    for(int i=2;i<=n;i++){int pos,op;
        scanf("%d%d",&pos,&op);
        if(op==0) a.addl(i,pos);
        else a.addr(i,pos);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){int x;
        scanf("%d",&x);
        a.del(x);
    }
    a.run(opt);
    return 0;
}
/*
in:
10
1 0
1 1
1 1
1 1
4 1
2 1
2 0
7 1
7 1
5
6
3
4
7
6
out:
8 2 10 9 1 5 
*/