左⼉⼦右兄弟表⽰法
顾名思义
每个节点⼀个为⼉⼦指针，⼀个为兄弟指针（在加个⽗亲）
这样就避免了⼉⼦个数不均带来的问题
TOJ 
⽤⼀个指针记录当前在哪个节点，需要注意的是可以有多个重名的⽂件，但是不能在⼀个⽬录下。所以⽤⽂件名和其⽗亲节点作为⼀个⽂件的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)return1; return0;
}
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'){
cstring转为int
solve(str);
}
return0;
}
View Code

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。