印刷再帰/スタック

Question

を使用せずに、私は最近、ソフトウェア開発者の位置のための評判の良い会社とのインタビューを持っていたし、これは質問の一つであった：

「を考えます次の方法：

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

名前が示唆するように、第一の方法は、入力ディレクトリ（「directoryNameで」）に即時のサブディレクトリの名前のリストを返し、第2の方法は、すべてのファイルの名前のリストを返します。このフォルダの中にあります。

aファイルシステム内のファイルを削除します。 "

私はそれについて考えて、インタビューにかなり明白な再帰的な解決策を与えました。彼女はその後、再帰なしでそれをするように私に言った。再帰ではコールスタックを使用するので、代わりに補助スタックを使用すると言っていましたが、ポイントポイントではスタックを使用しないように指示しました。残念ながら、私は解決策を思いつくことができませんでした。私はそれが再帰/スタックなしでどのようにできるかを尋ねましたが、彼女は言うつもりはありません。

どうすればいいですか？

Answer 1

あなたはキューとBFSアルゴリズムを使用します。

私はいくつかの擬似コードはいいだろうと思います。私は何@lqsが示唆することは確かに彼女が探している可能性があることを許容答えだと思い

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

私が正しく理解していれば、即時のサブディレクトリはそのフォルダ内のディレクトリだけです。つまり、私たちがこれらの3つのパスを持っているとすれば、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())); 
} 

Answer 3

：変数に完全なパスを格納し、サブディレクトリを入力する場合はディレクトリ名を追加し、終了する場合は最後のディレクトリ名を切り取ります。このようにして、フルパスはファイルシステム内の現在の場所へのポインタとして機能します。

完全パスは常に最後に変更されるため、完全パスはスタックとして動作します（驚くことではありません）。

インタビューの質問はさておき、私は