打印所有不使用递归/栈

的给定文件夹的文件和子文件夹我最近有一个有信誉的公司接受记者采访时对软件开发人员的位置，这是其中一个问题问：打印所有不使用递归/栈

“鉴于下面的方法：

List subDirectories(String directoryName){ ... }; 
List filesInDirectory(String directoryName) { ... };

正如名称所暗示的，第一种方法返回输入目录（“目录名”），第二种方法直接子目录的名称的列表返回所有文件名列表在该文件夹。

打印一张填入文件系统中的文件。“

我想了想，给了面试很明显的递归解决方案。然后她告诉我不要递归。由于递归使用了调用堆栈，我告诉她我会使用辅助堆栈，在这一点上，她告诉我不要使用堆栈。不幸的是，我无法提出解决方案。我曾问过如何在没有递归/堆栈的情况下完成它，但她不会说。

这怎么办？

来源

2012-10-30 user1784540

是允许的全路径名存储在一个变量？ – lqs

我不确定..我没有向面试官问这个问题！ – user1784540

你想用队列和BFS算法。

我猜有些伪代码将是很好：

files = filesInDirectory("/") 
foreach (file in files) { 
    fileQ.append(file) 
} 

dirQ = subDirectories("/") 
while (dirQ != empty) { 
    dir = dirQ.pop 
    files = filesInDirectory(dir) 
    foreach (file in files) { 
     fileQ.append(file) 
    } 
    dirQ.append(subDirectories(dir)) 
} 

while (fileQ != empty) { 
    print fileQ.pop 
}

来源

2012-10-30 04:57:25 Michael

保持文件队列没有意义。只要您找到它们，您就可以将其名称打印出来。你真的只需要目录队列。 – rici

当然，全部取决于需求，但查询仍然满足：使用这两种方法打印出系统上的所有文件，并且不递归。 – Michael

我认为需要找到一份工作，这是一个面试问题。我做了很多采访，并且我使用了这样的问题，我的即时跟进将是：“您认为文件系统中所有文件名的总大小是多少？” :)只要说' – rici

如果我理解正确的话，直接子目录只在该文件夹的目录。我的意思是如果我=我们有这三条路径/home/user,/home/config和/home/user/u001，我们可以说user和config都是/home/的直接子目录，但是u001不是。这同样适用，如果user和u001是文件（user是立竿见影的，而u001不是）。

所以你并不真的需要递归或堆到回到眼前的子目录或文件的列表。

编辑：我认为，OP想要实现subDirectories()和filesInDirectories()函数。

所以，你可以这样做打印的所有文件（一种伪代码）：

List subd = subDirectories(current_dir); 
List files = filesInDirectories(current_dir); 

foreach (file in files) { 
    print file.name(); 
} 

while (!subd.empty()) { 
    dir = subd.pop(); 

    files = filesInDirectory(dir.name()); 

    foreach (file in files) { 
     print file.name(); 
    } 

    subd.append(subDirectories(dir.path())); 
}

来源

2012-10-30 04:43:03

是的，但问题是要求我打印文件系统中的所有文件，而不仅仅是在特定的目录中。这是不是意味着我需要跟踪我目前所在的目录以及以前的目录，以便我可以回溯？ – user1784540

所以，你可以用BFS lile @Michael回答。 –

我认为，@lqs表明确实是一个可以接受的答案，她可能一直在寻找：存储在一个变量的完整路径，如果您输入一个子目录，则将目录名添加到该目录中，并在离开时删除最后一个目录名。这样，您的完整路径将作为您当前位于文件系统中的指针。

因为完整路径是在最后总是修改，完整路径的行为（不奇怪）作为你的筹码。

面试的问题之外，我想我还是会挑完了字符串操作，虽然真正的堆栈...

来源

2012-10-30 11:28:53 Astrotrain

打印所有不使用递归/栈

回答

相关问题