用shell / awk / sed能實(shí)現(xiàn)級聯(lián)樹狀結(jié)構(gòu)么

rm-rf

jason680 發(fā)表于 2016-09-02 10:17
回復(fù) 8# rm-rf

It's hard to know what's happened

是的，理論上id不重復(fù)，也不會(huì)cycle，但是現(xiàn)實(shí)生活總是不遵守規(guī)矩，我發(fā)現(xiàn)了源文件的一些數(shù)據(jù)cycle了

比如 id為1，2，3的元素形成了一個(gè)閉環(huán)，1->2->3->1 程序會(huì)死循環(huán)   

現(xiàn)在我在考慮在child函數(shù)中加一個(gè)判斷，當(dāng)新傳入的pid與鏈表上已有的元素重復(fù)時(shí)，就認(rèn)為cycle了，返回出來，
不知道這樣是否能解決cycle

jason680

回復(fù) 11# rm-rf


>> "...但是現(xiàn)實(shí)生活總是不遵守規(guī)矩，..."

給源數(shù)據(jù)，別亂舉例....
   ||
   ||
  \||/

jason680

回復(fù) 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

回復(fù) 13# jason680

rm-rf

回復(fù) 13# jason680

大師，這樣的代碼如何能讀啊？拜托能貼出源碼么？多謝。

rm-rf

回復(fù) 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)}

復(fù)制代碼

jason680

回復(fù) 16# rm-rf

good job!

你若不想做，會(huì)找到一個(gè)借口；你若想做，會(huì)找到一個(gè)方法...

moperyblue

樓主 這需求是什么應(yīng)用場景
id重復(fù)的話name怎么取?
根id只有一個(gè)(0)嗎?
同級葉子節(jié)點(diǎn)只保留一個(gè)嗎?