用shell / awk / sed能实现级联树状结构么

rm-rf

比如下面的文件

1. 
   
2. id pid name
   
3. 2 1 d
   
4. 1 0 a
   
5. 3 1 b
   
6. 4 2 c
   
7. 5 3 e
   

复制代码

id是不重复的，pid是parent的id，要求遍历所有的父子节点，实现如下的输出，用shell 或者awk / sed适合么？

1. 
   
2. 0->1->2->4 a,d,c
   
3. 0->1->3->5 a,b,e
   

复制代码

jason680

回复 1# rm-rf


$ cat FILE

id pid name
2 1 d
1 0 a
3 1 b
4 2 c
5 3 e
6 2 g
7 1 x
8 7 j
9 7 k
10 9 m
12 3 f

$ awk 'function child(v,cs,as,x){if(c[v]==""){sub(",$","",as);print cs v,as;return}while(x=index(c[v]," ")){cx=substr(c[v],1,x-1);child(cx,cs v"->",as a[v,cx]",");c[v]=substr(c[v],x+1)}child(c[v],cs v"->",as a[v,c[v]]",")}/^[0-9]/{c[$2]=c[$2]d[$2]$1;d[$2]=" ";a[$2,$1]=$3}END{child(0)}' FILE
0->1->2->4 a,d,c
0->1->2->6 a,d,g
0->1->3->5 a,b,e
0->1->3->12 a,b,f
0->1->7->8 a,x,j
0->1->7->9->10 a,x,k,m

sunzhiguolu

找了一条引用链:

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. readline;
   
6. my @aVals = map {[split]} <>;
   
7. my ($id, $pid, $name) = @{$aVals[0]};
   
8. while (grep {$id == $aVals[$_][1] ? do {($id, $pid, $name) = @{$aVals[$_]}; 1} : 0} 1 .. $#aVals){}
   
9. my ($offset, @aData);
   
10. unshift (@{$aData[0]}, $id);
    
11. unshift (@{$aData[1]}, $name);
    
12. while (grep {$pid == $aVals[$_][0] ? do {$offset = $_; 1} : 0} 0 .. $#aVals){
    
13.     ($id, $pid, $name) = @{$aVals[$offset]};
    
14.     unshift (@{$aData[0]}, $id);
    
15.     unshift (@{$aData[1]}, $name);
    
16. }
    
17. 
    
18. print join ("->", $pid, @{$aData[0]}), "\t", join (",", @{$aData[1]}), "\n";
    

复制代码

perl abc.pl a
---------------------------------------------------
0->1->2->4      a,d,c

sunzhiguolu

  理解的有偏差,,,


   

RE_HASH

$_ = do {$/=undef; <>};        #read file
s/^.+\n//;        #remove header
s/^(\d+) (\d+) /$2->$1 /gm;                #-> relationship
$tree = $_;        #keep a copy of relationship
1 while (s/^([1-9]\d*)->(.+?) /($id, $v) = ($1,$2);  $tree =~ m:^(.+)->$id (\w+):m;  "$1->$id->$v $2,"/mge);        #create a full list
for $i ($tree =~ /^(\d+)/mg ) { s/^.+->$i .+\n//gm };  #remove lines ends with pids
print;

_____
$>  cat aa|perl aa.pl
0->1->2->4 a,d,c
0->1->3->5 a,b,e
0->1->2->6 a,d,g
0->1->7->8 a,x,j
0->1->7->9->10 a,x,k,m
0->1->3->12 a,b,f

rm-rf

回复 2# jason680

太给力了，超赞!

yinyuemi

回复 1# rm-rf

1. echo 'id pid name
   
2. 2 1 d
   
3. 1 0 a
   
4. 3 1 b
   
5. 4 2 c
   
6. 5 3 e'|awk '
   
7. function ss(x,l,n,t){
   
8.   if(length(a[x])){
   
9.     l=l?l"->"x:x
   
10.         t = n
    
11.     for(j in a[x]){
    
12.       n=n?n","a[x][j]:a[x][j]
    
13.       ss(j,l,n,t)
    
14.           n=t
    
15.     }
    
16.   }else{
    
17.     print l"->"x, n;
    
18.         l=n=""
    
19.   }
    
20. }
    
21. NR>1{a[$2][$1]=$3}
    
22. END{for(i in a){ss(i,"","","")}}
    
23. '
    
24. 0->1->2->4 a,d,c
    
25. 0->1->3->5 a,b,e
    
26. 1->2->4 d,c
    
27. 1->3->5 b,e
    
28. 2->4 c
    
29. 3->5 e
    

复制代码

rm-rf

回复 2# jason680

大侠，这个脚本非常经典，感谢。能更加一步，判断里面的cycle么？比如出现cycle只打印第一次遍历出来的即可

1. id pid name
   
2. 2 1 d
   
3. 1 0 a
   
4. 3 1 b
   
5. 4 2 c
   
6. 9 10 p
   
7. 5 3 e
   
8. 6 2 g
   
9. 7 1 x
   
10. 8 7 j
    
11. 9 7 k
    
12. 2 6 m
    
13. 12 3 f
    

复制代码

结果为:

1. 0->1->2->4 a,d,c
   
2. 0->1->2->6 a,d,g
   
3. 0->1->3->5 a,b,e
   
4. 0->1->3->12 a,b,f
   
5. 0->1->7->8 a,x,j
   
6. 0->1->7->9 a,x,k

复制代码

其中0->1->2->6这个链表cycle了，只打印第一次遍历到的情况

RE_HASH

$>  cat bb|perl aa.pl
0->1->2->4 a,d,c
0->1->3->5 a,b,e
0->1->7->8 a,x,j
0->1->7->9 a,x,k
0->1->3->12 a,b,f
$>  cat aa.pl
$_ = do {$/=undef; <>}; #read file
s/^.+\n//;      #remove header
s/^(\d+) (\d+) /$2->$1 /gm;             #-> relationship
$tree = $_;     #keep a copy of relationship
while (s/^([1-9]\d*)->(.+?) /($id, $v) = ($1,$2);  $tree =~ m:^(.+)->$id (\w+):m;  "$1->$id->$v $2,"/mge)       #create a full list
{
  s/.*(\d+)->.*\1.+\n//; #Remove cycles
}
for $i ($tree =~ /^(\d+)/mg ) { s/^.+->$i .+\n//gm };  #remove lines ends with pids
print;

jason680

回复 8# rm-rf

It's hard to know what's happened

"id是不重复的，pid是parent的id..."

id pid name
2 1 d
6 2 g
2 6 m