首页 > 代码库 > 左儿子右兄弟表示法

左儿子右兄弟表示法

2024-07-12 19:21:43   224人阅读

 

顾名思义 

每个节点一个为儿子指针，一个为兄弟指针（在加个父亲）

这样就避免了儿子个数不均带来的问题

 

TOJ　　 TOJ4077

用一个指针记录当前在哪个节点，需要注意的是可以有多个重名的文件，但是不能在一个目录下。

所以用文件名和其父亲节点作为一个文件的id（区分其他）。

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <set>#include <map>using namespace std;typedef long long LL;const int N=100100;char ma[N][20];int mma[N];char ans[N][20];struct node {    int son,fa;    int bro;}root,a[N];int cnt;int cur;void add(int x,char *s){    strcpy(ma[cnt],s);    mma[cnt]=x;    int p=a[x].son;    a[cnt].bro=-1;    a[cnt].fa=x;    a[cnt].son=-1;    if(p==-1){        a[x].son=cnt;    }    else{        while(a[p].bro!=-1)p=a[p].bro;        a[p].bro=cnt;    }    cnt++;}void dele(int x,int y){    int p=a[x].son;    if(p==-1)return;    if(p==y){        a[x].son=a[p].bro;    }    else{        while(p!=-1&&a[p].bro!=y)p=a[p].bro;        if(p==-1)return;        a[p].bro=a[a[p].bro].bro;        return;    }}void init(){    a[0].fa=-1;    a[0].son=-1;    a[0].bro=-1;    cnt=1;    add(0,"home");    add(1,"brotherkai");    cur=2;}int fin(int x,char str[]){    for(int i=0;i<cnt;i++){        if(strcmp(ma[i],str)==0&&mma[i]==x){            return i;        }    }    return -1;}int r[N];int cmp(int a,int b){    if(strcmp(ans[a],ans[b])<=0)return 1;    return 0;}void dfs(int x){    mma[x]=-1;    for(int i=a[x].son;i!=-1;i=a[i].bro){        dfs(i);    }    return;}void solve(char str[]){    char op1[50],op2[50];    if(str[0]==‘l‘){        int nu=0;        for(int i=a[cur].son;i!=-1;i=a[i].bro){            strcpy(ans[nu++],ma[i]);        }        for(int i=0;i<nu;i++)r[i]=i;        if(nu){            sort(r,r+nu,cmp);            printf("%s",ans[r[0]]);            for(int i=1;i<nu;i++){                printf(" %s",ans[r[i]]);            }        }        printf("\n");    }    else if(str[0]==‘c‘){        scanf("%s",op1);        if(op1[0]==‘/‘){            cur=0;        }else if(op1[0]==‘.‘){            if(cur!=0)                cur=a[cur].fa;        }        else{            int x=fin(cur,op1);            if(x==-1)return;            cur=x;        }    }    else if(str[0]==‘r‘){        scanf("%s%s",op2,op1);        int x=fin(cur,op1);        if(x==-1)return;        else{            mma[x]=-1;            dfs(x);            dele(cur,x);        }    }    else if(str[0]==‘m‘){        scanf("%s",op1);        int x=fin(cur,op1);        if(x==-1){            add(cur,op1);        }    }    return;}int main(){    char str[30];    init();    while(scanf("%s",str),str[0]!=‘e‘){        solve(str);    }    return 0;}
View Code


联系
我们