Drucken Sie alle Dateien in einem bestimmten Ordner und Unterordner ohne Rekursion/Stack

Question

Ich hatte vor kurzem ein Interview mit einem seriösen Unternehmen für die Position des Software-Entwickler und dies war eine der Fragen gestellt:

„Gegeben die folgenden Methoden:

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

Wie die Namen vermuten lassen, die erste Methode eine Liste der Namen der sofortigen Unterverzeichnisse im Eingangsverzeichnis (‚Verzeichnisname‘) und die zweite Methode gibt gibt eine Liste der Namen aller Dateien in diesem Ordner

Drucken a ll die Dateien im Dateisystem. "

Ich dachte darüber nach und gab dem Interview eine ziemlich offensichtliche rekursive Lösung. Sie sagte mir dann, ich solle es ohne Rekursion tun. Da die Rekursion den Call-Stack nutzt, habe ich ihr gesagt, dass ich stattdessen einen Hilfsstapel verwenden werde, an welchem ​​Punkt sie mir sagte, ich solle auch keinen Stack verwenden. Leider war ich nicht in der Lage, eine Lösung zu finden. Ich habe gefragt, wie es ohne Rekursion/Stack gemacht werden kann, aber sie würde es nicht sagen.

Wie kann das gemacht werden?

Answer 1

Sie mögen eine Warteschlange und einen BFS-Algorithmus verwenden.

Ich denke, einige Pseudo-Code wäre schön:

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 
} 

Answer 2

Wenn ich richtig verstanden habe, sind direkte Unterverzeichnisse nur die Verzeichnisse in diesem Ordner. Ich meine, wenn I = wir haben diese drei Pfade /home/user, /home/config und /home/user/u001, können wir sagen, dass sowohl user als auch config sofortige Unterverzeichnisse von /home/ sind, aber u001 ist nicht. Gleiches gilt, wenn user und u001 Dateien sind (user ist sofort, u001 nicht).

Sie brauchen also nicht wirklich Rekursion oder Stack, um eine Liste von unmittelbaren Unterverzeichnissen oder Dateien zurückzugeben.

EDIT: Ich dachte, dass das OP die subDirectories() und filesInDirectories() Funktionen implementieren wollten.

So können Sie etwas tun, wie alle Dateien (eine Art Pseudo-Code) drucken:

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())); 
} 

Answer 3

Ich denke, dass das, was @lqs schlägt vor, ist in der Tat eine akzeptable Antwort, dass sie sein könnten suchen: Speichern Sie den vollständigen Pfad in einer Variablen, und Fügen Sie den Verzeichnisnamen an, wenn Sie ein Unterverzeichnis eingeben, und entfernen Sie den letzten Verzeichnisnamen, wenn Sie ihn verlassen. Auf diese Weise fungiert der vollständige Pfad als Zeiger auf den aktuellen Speicherort im Dateisystem.

Da der vollständige Pfad am Ende immer geändert wird, verhält sich der vollständige Pfad (nicht überraschend) wie Ihr Stapel.

Interview Fragen beiseite, ich denke ich immer noch, obwohl ein echten Stapel über String-Manipulation holen würde ...