亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: 用shell / awk / sed能實(shí)現(xiàn)級(jí)聯(lián)樹(shù)狀結(jié)構(gòu)么 [打印本頁(yè)]
作者: rm-rf    時(shí)間: 2016-08-31 21:52
標(biāo)題: 用shell / awk / sed能實(shí)現(xiàn)級(jí)聯(lián)樹(shù)狀結(jié)構(gòu)么
比如下面的文件


  2. id pid name
  3. 2 1 d
  4. 1 0 a
  5. 3 1 b
  6. 4 2 c
  7. 5 3 e
復(fù)制代碼


id是不重復(fù)的，pid是parent的id，要求遍歷所有的父子節(jié)點(diǎn)，實(shí)現(xiàn)如下的輸出，用shell 或者awk / sed適合么？


  2. 0->1->2->4 a,d,c
  3. 0->1->3->5 a,b,e
復(fù)制代碼
作者: jason680    時(shí)間: 2016-08-31 23:55
回復(fù) 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    時(shí)間: 2016-09-01 02:10
找了一條引用鏈:
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;

  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. }

  18. print join ("->", $pid, @{$aData[0]}), "\t", join (",", @{$aData[1]}), "\n";
復(fù)制代碼

perl abc.pl a
---------------------------------------------------
0->1->2->4      a,d,c
作者: sunzhiguolu    時(shí)間: 2016-09-01 02:33
本帖最后由 sunzhiguolu 于 2016-09-01 02:55 編輯

  理解的有偏差,,,


   





作者: RE_HASH    時(shí)間: 2016-09-01 06:10
$_ = 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    時(shí)間: 2016-09-01 10:48
回復(fù) 2# jason680

太給力了，超贊!
作者: yinyuemi    時(shí)間: 2016-09-01 11:34
回復(fù) 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
復(fù)制代碼
作者: rm-rf    時(shí)間: 2016-09-01 22:31
回復(fù) 2# jason680

大俠，這個(gè)腳本非常經(jīng)典，感謝。能更加一步，判斷里面的cycle么？比如出現(xiàn)cycle只打印第一次遍歷出來(lái)的即可


  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
復(fù)制代碼
結(jié)果為:

  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
復(fù)制代碼
其中0->1->2->6這個(gè)鏈表cycle了，只打印第一次遍歷到的情況
作者: RE_HASH    時(shí)間: 2016-09-01 23:05
$>  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    時(shí)間: 2016-09-02 10:17
本帖最后由 jason680 于 2016-09-02 10:27 編輯

回復(fù) 8# rm-rf

It's hard to know what's happened

"id是不重復(fù)的，pid是parent的id..."

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

作者: rm-rf    時(shí)間: 2016-09-02 13:53
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了，返回出來(lái)，
不知道這樣是否能解決cycle

作者: jason680    時(shí)間: 2016-09-02 14:11
回復(fù) 11# rm-rf


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

給源數(shù)據(jù)，別亂舉例....
   ||
   ||
  \||/
作者: jason680    時(shí)間: 2016-09-02 20:31
回復(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    時(shí)間: 2016-09-02 21:14
回復(fù) 13# jason680

作者: rm-rf    時(shí)間: 2016-09-02 21:35
回復(fù) 13# jason680

大師，這樣的代碼如何能讀��？拜托能貼出源碼么？多謝。
作者: rm-rf    時(shí)間: 2016-09-03 09:23
回復(fù) 13# jason680

大師莫怪，我把它翻譯過(guò)來(lái)了。
  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    時(shí)間: 2016-09-03 22:44
回復(fù) 16# rm-rf

good job!

你若不想做，會(huì)找到一個(gè)借口；你若想做，會(huì)找到一個(gè)方法...
作者: moperyblue    時(shí)間: 2016-09-06 14:11

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



歡迎光臨 Chinaunix (http://www.72891.cn/) Powered by Discuz! X3.2