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

rm-rf

jason680 发表于 2016-09-02 10:17
回复 8# rm-rf

It's hard to know what's happened

是的，理论上id不重复，也不会cycle，但是现实生活总是不遵守规矩，我发现了源文件的一些数据cycle了

比如 id为1，2，3的元素形成了一个闭环，1->2->3->1 程序会死循环   

现在我在考虑在child函数中加一个判断，当新传入的pid与链表上已有的元素重复时，就认为cycle了，返回出来，
不知道这样是否能解决cycle

jason680

回复 11# rm-rf


>> "...但是现实生活总是不遵守规矩，..."

给源数据，别乱举例....
   ||
   ||
  \||/

jason680

回复 8# rm-rf

$ awk -f tree_nocycle.awk 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 a,x,k

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

$ cat tree_nocycle.awk
BEGIN{_000O0O="=="=="==";_000O00="--"-"---";_0OO0O0="**"*"***";_0O0OO0="&&"&&"&&";_O000O0=">";_00OOOO="||"||"||";_0OO00O=_00OOOO-_000O0O;_00OO00=_0OO0O0+_0O0OO0*_000O0O+_0OO00O+_00OOOO;_00O00O="";_0O00OO=_000O00+_00OOOO*_0O0OO0+_0OO0O0+_000O0O;_0O00O0=" ";_0OO000=_0OO00O+_000O0O*_00OOOO+_000O00+_0O0OO0;_0000O0=",";_00000O=_0O00OO*_0OO000+_000O00-_000O0O;_00O0OO="$";_00O0O0=_0OO000*_00OO00+_0OO00O-_0O0OO0;_0O0O0O="-";_0O0O00=_00OO00*_0O00OO+_0OO0O0-_00OOOO;_0OOOO0=_0O0O0O _O000O0;}function _0O0OOO(_00O000,_0OOO00){while(_O0000O[_0OOO00]!=_00O00O){if(_00O000==_O0000O[_0OOO00])return(_000O0O);_0OOO00=_O0000O[_0OOO00]}}function _0OO0OO(_0OOO0O,_00OO0O,_00OOO0,_0O0000,_0OOOOO,_O00000){if(_000OOO[_0OOO0O]==_00O00O){sub(_0000O0 _00O0OO,_00O00O,_00OOO0);print _00OO0O _0OOO0O,_00OOO0;return}while(_0O0000=index(_000OOO[_0OOO0O],_0O00O0)){_0000OO=substr(_000OOO[_0OOO0O],_0O0OO0,_0O0000-_00OOOO);_0OO0OO(_0000OO,_00OO0O _0OOO0O _0OOOO0,_00OOO0 _000OO0[_0OOO0O,_0000OO]_0000O0);_000OOO[_0OOO0O]=substr(_000OOO[_0OOO0O],_0O0000+_000O0O)}_0OO0OO(_000OOO[_0OOO0O],_00OO0O _0OOO0O _0OOOO0,_00OOO0 _000OO0[_0OOO0O,_000OOO[_0OOO0O]]_0000O0)}/^[0-9]/{if(_0O0OOO($_00OOOO,$_00OO00))next;_000OOO[$_0O00OO]=_000OOO[$_00OO00]_0O000O[$_0OO000]$_00OOOO;_O0000O[$_000O0O]=$_0O00OO;_0O000O[$_00OO00]=_0O00O0;_000OO0[$_0O00OO,$_000O0O]=$_00O0O0;}END{_0OO0OO(_0OO00O)}

rm-rf

回复 13# jason680

rm-rf

回复 13# jason680

大师，这样的代码如何能读啊？拜托能贴出源码么？多谢。

rm-rf

回复 13# jason680

大师莫怪，我把它翻译过来了。

1. function iscycle(col1,col2){
   
2.   while(k[col2]!=""){
   
3.     if(col1==k[col2]) return(1)
   
4.     col2=k[col2]
   
5.   }
   
6. }
   
7. function child(v,cs,as,x){
   
8.   if(c[v]==""){
   
9.     sub(/,$/,"",as)
   
10.     print cs v,as
    
11.     return
    
12.   }
    
13.   while(x=index(c[v]," ")){
    
14.     cx=substr(c[v],1,x-1)
    
15.     child(cx,cs v "->",as a[v,cx]",")
    
16.     c[v]=substr(c[v],x+1)
    
17.   }
    
18.   child(c[v],cs v "->",as a[v,c[v]]",")
    
19. }
    
20. /^[0-9]/{
    
21.   if(iscycle($1,$2)) next
    
22.   c[$2]=c[$2]d[$2]$1
    
23.   k[$1]=$2
    
24.   d[$2]=" "
    
25.   a[$2,$1]=$3
    
26. }
    
27. END{child(0)}

复制代码

jason680

回复 16# rm-rf

good job!

你若不想做，会找到一个借口；你若想做，会找到一个方法...

moperyblue

楼主 这需求是什么应用场景
id重复的话name怎么取?
根id只有一个(0)吗?
同级叶子节点只保留一个吗?