递归迭代

Question

我正在使用Java的Windows桌面应用程序中工作。在我的应用程序中，需要搜索所有.php文件。为此，我使用递归方法。

import java.io.File; 

public class Copier { 

    public static void find(String source,String rep) { 
     File src = new File(rep); 
     if (src!= null && src.exists() && src.isDirectory()) { 
      String[] tab = src.list(); 
      if (tab != null) { 
       for(String s : tab) { 
        File srcc = new File(rep+"\\"+s); 
        if (srcc.isFile()) { 
         if (srcc.getName().matches(".*"+source+"$")) { 
          System.out.println(s); 
         } 
        } else { 
         find(source,srcc.getAbsolutePath()); 
        } 
       } 
      } else { 
       //System.out.println(" list is null"); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     try { 
      find(".java", "C:\\"); 
     } catch (Exception e) { 
      e.printStackTrace(); 
     } 
    } 
} 

是否可以用迭代算法做到这一点？

Answer 1

我不明白为什么你想摆脱递归虽然理论上你正在寻找的是可能的。

但是，获得更快程序的好方法是在列出目录的子目录时使用filefilter。一个用于目录，另一个用于匹配文件（这个应该使用java.util.regexp.Pattern）。

- 更新

你可以找到的File.list超负荷使用here的文档。而对于这个模式，你可以像局部变量那样（在循环之外或者使用递归的数据成员）。

Pattern p = Pattern.compile(".*"+source+".*"); 
boolean found = p.matcher(p.matcher(srcc.getName()).matches()); 

哦，顺便说一句，不要将srcc转换成文件！使用字符串并尽可能少地构建对象。

Answer 2

当然。与队列一起使用breadth-first-search。您从C:\开始，并在每一步从队列中弹出顶级文件夹并将所有子文件夹推送到队列末尾。

伪代码如下：

queue.push("C:\"); 
while (!queue.empty()) { 
    String topFolder = queue.pop(); 
    foreach (subFolder of topFolder) { 
     queue.push(subFolder); 
    } 
} 

Answer 3

您始终可以使用队列来代替递归。在这种情况下，我认为它使代码看起来更容易阅读。通常你会从迭代实现中获得比递归更好的性能，尽管在这种情况下，它们的运行速度几乎相同（至少在我的机器上）。

public static List<String> find(final String source, final String directory) 
{ 
    List<String> results = new LinkedList<String>(); 
    Stack<String> stack = new Stack<String>(); 

    stack.add(directory); 

    String rep; 
    while (!stack.isEmpty()) { 
     rep = stack.pop(); 
     File src = new File(rep); 
     if (src != null && src.exists() && src.isDirectory()) { 
      String[] tab = src.list(); 
      if (tab != null) { 
       for (String s : tab) { 
        File srcc = new File(rep + File.separatorChar + s); 
        if (srcc.isFile()) { 
         if (srcc.getName().matches(".*" + source + "$")) { 
          // System.out.println(s); 
          results.add(s); 
         } 
        } else { 
         stack.add(srcc.getAbsolutePath()); 
        } 
       } 
      } else { 
       // System.out.println(" list is null"); 
      } 
     } 
    } 
    return results; 
}