打印所有不使用遞歸/棧

的給定文件夾的文件和子文件夾我最近有一個有信譽的公司接受記者採訪時對軟件開發人員的位置，這是其中一個問題問：打印所有不使用遞歸/棧

「鑑於下面的方法：

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

打印所有不使用遞歸/棧

回答

相關問題