[已解决]求批处理算法：把多行上下级关系转换为树形结构的上下级关系

hnfeng

原始的txt文件内容是：左边是上级，右边是下级。有且只有一个最高级（这里就是z_033b7312.txt）
t_9057374.txt ---> t_9057375.txt
z_033b7312.txt ---> c_9060409.txt
z_033b7312.txt ---> c_9c09ff24.txt
c_9060409.txt ---> t_9057374.txt
c_9c09ff24.txt ---> t_c301154f.txt
z_033b7312.txt ---> t_80dba877.txt
t_9057374.txt ---> t_9057376.txt

为了方便，也可以把中间的字符改为TAB，如下（请按TAB分割来处理吧）

1. t_9057374.txt        t_9057375.txt
   
2. z_033b7312.txt        c_9060409.txt
   
3. z_033b7312.txt        c_9c09ff24.txt
   
4. c_9060409.txt        t_9057374.txt
   
5. c_9c09ff24.txt        t_c301154f.txt
   
6. z_033b7312.txt        t_80dba877.txt
   
7. t_9057374.txt        t_9057376.txt

复制代码

想生成的结果文件内容是：
z_033b7312.txt
    ├ c_9060409.txt
    │    └ t_9057374.txt
    │          ├ t_9057375.txt
    │          └ t_9057376.txt
    ├ c_9c09ff24.txt
    │    └ t_c301154f.txt
    └ t_80dba877.txt

为了简化代码，也可以简单一些

1. z_033b7312.txt
   
2.     c_9060409.txt
   
3.         t_9057374.txt
   
4.             t_9057375.txt
   
5.             t_9057376.txt
   
6.     c_9c09ff24.txt
   
7.         t_c301154f.txt
   
8.     t_80dba877.txt

复制代码

只有一个最高级。下级可能有多个级别

请高手们帮忙，谢谢

aloha20200628

回复 1# hnfeng

楼主能说出不同层级与其上级的隶属规律吗？尤其是当数据行增至过百上千时...此题来自的缘由？

hnfeng

回复 2# aloha20200628


    1、不同层级的关系，都在原文本文件中体现了
   2、不会有很多层，最多先按 4 层或 5 层来处理吧
   3、每行只有一个分隔符（TAB）分割两个文件名。所有文件名，不会重复

我的想法是，先在文本文件中获取所有的分隔符的 前(A1-An) 和后（B1-Bn）的内容，然后逐个找Ax是否在B中出现，如果没有在B中，说明这个就是最高级（根）
然后……，就不知道如何获取其他层级的算法了

补充:  最高级（根）找到后，貌似，所有最高级对应的Bx 都是第二级了……
如例子：
只有 z_033b7312.txt 没有出现在B中，所以 z_033b7312.txt 就是最高级,  然后，由
z_033b7312.txt        c_9060409.txt
z_033b7312.txt        c_9c09ff24.txt
z_033b7312.txt        t_80dba877.txt
可知， 这三个Bx 就是第二级
……

77七

1. @echo off
   
2. cd /d "%~dp0"
   
3. setlocal enabledelayedexpansion
   
4. for /f "useback tokens=1-2 delims=        " %%a in ("1.txt") do (
   
5.         set _%%a=!_%%a! %%b
   
6. )
   
7. >output.txt echo z_033b7312.txt
   
8. set str=   
   
9. call :1 z_033b7312.txt
   
10. pause
    
11. exit
    
12. 
    
13.         :1
    
14.         for /f "tokens=1-2 delims==" %%a in ('2^>nul set _%~1') do (
    
15.                 for %%c in (%%b) do (
    
16.                         set str=%str%   
    
17.                         >>output.txt echo %str% %%c
    
18.                         call :1 %%c
    
19.                 )
    
20.         )
    
21.         exit /b

复制代码

写了个草稿，没有写获得最高级及处理一些细节问题，大概有多个最高级，也是可以实现的，楼主再自行修改吧。

Five66

1. 
   
2. @set @do_not_save_as_utf8=1;/*&echo off
   
3. 
   
4. type "1.txt"|cscript //nologo //e:jscript "%~f0"
   
5. 
   
6. pause&exit /b 0 */
   
7. 
   
8. var str=WScript.StdIn.ReadAll().split(/\r?\n/);
   
9. var node=function(v){this.value=v;this.next=[];}
   
10. var root=null,root_table=[],node_table={};
    
11. var switch_root=function(r){
    
12. for(var k=0;k<root_table.length;k++){
    
13. if(r==root_table[k][1])return root_table[k][0];}
    
14. return 0;
    
15. }
    
16. 
    
17. for(var  i=0;i<str.length;i++){
    
18. var a=str[i].split("\t");
    
19. 
    
20. if(node_table["@@"+a[0]]){;}else{
    
21. var _node=new node(a[0]);
    
22. node_table["@@"+a[0]]=_node;
    
23. }
    
24. 
    
25. if(node_table["@@"+a[1]]){;}else{
    
26. var _node=new node(a[1]);
    
27. node_table["@@"+a[1]]=_node;
    
28. }
    
29. 
    
30. node_table["@@"+a[0]].next.push(node_table["@@"+a[1]]);
    
31. root_table.push(["@@"+a[0],"@@"+a[1]]);
    
32. 
    
33. if(root){
    
34. while(1){
    
35. var _root=switch_root(root);
    
36. if(_root){root=_root;}else{break;}
    
37. }
    
38. }else{
    
39. root="@@"+node_table["@@"+a[0]].value;
    
40. }
    
41. 
    
42. }
    
43. 
    
44. var print=function (x,y){
    
45. for(var i=0;i<x.length;i++){
    
46. if(x[i].next.length){
    
47. WScript.Echo(y+x[i].value);
    
48. print(x[i].next,y+'    ');
    
49. }else{WScript.Echo(y+x[i].value);}
    
50. }}
    
51. WScript.Echo(node_table[root].value);
    
52. print(node_table[root].next,'    ');
    

复制代码

hnfeng

回复 4# 77七


    谢谢，高手啊

虽然需要先指定最高级的文件名，但是也不是多麻烦，很好的得到了结果
算法很精妙，我要细细研究学习。
非常感谢

hnfeng

回复 5# Five66


    谢谢。我不懂JS，输出结果也准确，只是能否输出结果到文件中？目前只是显示在cmd窗口中

idwma

1. #@&cls&powershell "type '%~0'|out-string|iex"&pause&exit
   
2. $a=@{}
   
3. $b=@{}
   
4. gc a.txt|%{
   
5.   $d=$_ -split "`t"
   
6.   $a[$d[0]]+=@{$d[1]=''}
   
7.   $b[$d[1]]=$d[0]
   
8. }
   
9. 
   
10. while($a.count -ne 1){
    
11.   $a.keys.clone()|%{
    
12.     $d=1
    
13.     $a[$_].keys|%{
    
14.       $c=$_
    
15.       if($a[$c] -ne $null){$d=0}
    
16.     }
    
17.     if($d){$a[$b[$_]][$_]=$a[$_];$a.remove($_)}
    
18.   }
    
19. }
    
20. 
    
21. function z($a,$b){
    
22.   $a.keys|sort|%{
    
23.     '{0}{1}' -f $b,$_
    
24.     if($a[$_] -ne ''){z $a[$_] ('    '+$b)}
    
25.   }
    
26. }
    
27. z $a
    
28. #z $a|sc o.txt

复制代码

77七

回复 6# hnfeng


   我模仿的以前terse大佬写的查找空文件夹代码的方法写的。
这个题目像是左边是老板，右边是员工（也可能是下级员工的老板），所以找到最大的老板的方法就是看他是不是也有员工身份，还是很简单的。

以下写了个完整代码，不限制一个最大老板

1. @echo off
   
2. cd /d "%~dp0"
   
3. setlocal enabledelayedexpansion
   
4. for /f "useback tokens=1-2 delims=        " %%a in ("1.txt") do (
   
5.         set #"%%b"=1
   
6.         set _"%%a"= !_"%%a"! "%%b"
   
7. )
   
8. (for /f "useback tokens=1-2 delims=        " %%a in ("1.txt") do (
   
9.         if not defined #"%%a" (
   
10.                 set #"%%a"=1
    
11.                 set "str=        "
    
12.                 echo %%a
    
13.                 call :1 "%%a"
    
14.         )
    
15. )) > "output.txt"
    
16. endlocal
    
17. pause
    
18. exit
    
19. 
    
20.         :1
    
21.         for %%d in (!_"%~1"!) do (
    
22.                 set "str=%str%        "
    
23.                 echo %str%%%~d
    
24.                 call :1 "%%~d"
    
25.         )
    
26.         exit /b

复制代码

Five66

回复 7# hnfeng


    5楼代码第3行末尾加上重定向到文件的代码就能输出到文件了 ,例如加上 >2.txt ,输出结果保存到2.txt文件

hnfeng

回复 9# 77七


    多谢多谢，完美
厉害，高手

hnfeng

回复 10# Five66


        多谢多谢，完美实现。厉害，高手

aloha20200628

回复 3# hnfeng

根据楼主补充说明，如果看作是解析一组相对路径进而构建其完整目录树，则采用其深度递归方法确实比较简捷...
以下的批处代码》
   先读取一楼用跳格作为分隔符的示例文件（1.txt）获取根目录；
   再获取每个节点直属的子节点链表；
   最后用递归输出完整目录树（存为 2.txt），根据递归步进和返回确定每个节点在目录树中的位置...

1. 
   
2. @echo off &setlocal enabledelayedexpansion &set "st="
   
3. for /f "delims=        " %%a in (1.txt) do findstr /irc:"        %%a" 1.txt>nul 2>nul||set "r=%%a"
   
4. for /f "tokens=1-2 delims=        " %%a in (1.txt) do (set "_#%%a=!_#%%a! %%b")
   
5. (call :xxx "%r%")>"2.txt" &exit/b
   
6. :xxx
   
7.    if "%~1"=="" (exit/b) else (echo,!st!%~1&set "st=!st!        ")
   
8.    for %%x in (!_#%~1!) do (call :xxx "%%~x")
   
9.    set "st=!st:~0,-1!" &exit/b
   

复制代码

flashercs

注意防止 堆栈溢出
例如下面的文本:

1. t_9057374.txt        t_9057375.txt
   
2. z_033b7312.txt        c_9060409.txt
   
3. z_033b7312.txt        c_9c09ff24.txt
   
4. c_9060409.txt        t_9057374.txt
   
5. c_9c09ff24.txt        t_c301154f.txt
   
6. z_033b7312.txt        t_80dba877.txt
   
7. t_9057374.txt        t_9057376.txt
   
8. t_9057375.txt        c_9060409.txt
   

复制代码

会导致

1. ******  B A T C H   R E C U R S I O N  exceeds STACK limits ******
   
2. Recursion Count=212, Stack Usage=90 percent
   
3. ******       B A T C H   PROCESSING IS   A B O R T E D      ******

复制代码

交换机有个重要协议STP:
STP协议（生成树协议）是用于消除二层网络环路的通信协议，由Radia Perlman于1985年设计，后成为IEEE 802.1D标准。该协议通过选举根网桥（基于网桥ID优先级和MAC地址）、根端口（最小根路径成本）及指定端口，逻辑阻断冗余链路构建无环树形拓扑，防止广播风暴和MAC地址表震荡。交换机间通过BPDU报文交互拓扑信息，实现路径故障切换。

hnfeng

回复 13# aloha20200628


    多谢多谢，也很完美。厉害，谢谢上面的各位高手