4

在一次采访中，我被要求在不使用递归、堆栈或队列的情况下列出目录及其子目录中的文件名¹。

由于我知道的唯一非递归方式使用堆栈，因此我无法回答这个问题。

面试官解释了解决方案，但我无法理解。我唯一记得的是它涉及两种方法而不是一种。

这种允许在没有递归、没有堆栈或队列的情况下列出目录及其子目录中的文件的方法是什么？

¹ 解决方案与语言无关。子目录列表由ListDirectories(string directoryPath)方法提供，文件由ListFiles(string directoryPath). 我们事先并不知道子目录的深度。

4

2 回答 2

4

在深度优先搜索中，当前路径本质上是一个堆栈。以深度优先的方式列出名称，按照您的预期进行，但不要费心记录堆栈...当您在目录中列出文件后，您可以通过注意最后一个目录是什么来“弹出”堆栈您所在的位置，然后从父目录中的那一点继续。

于 2012-04-13T13:38:12.617 回答
1

尝试这样的事情（伪代码）：

baseDirectory = "/usr"
list = [baseDirectory] // list of directories to traversal
files = []
while (list not empty) {
  d = list.getFirst(); // get directory
  directories = ListDirectories(d);
  files.add(ListFiles(d)); // add all files from current directory
  list.add(directories); //add all directories from current directory to traversal
  list.remove(d); // remove traversed dir
}

我们只使用列表 :) 但这种方法与堆栈/队列解决方案非常相似

于 2012-04-13T14:16:01.523 回答