4

インタビュー中に、再帰もスタックもキューも使用せずに、ディレクトリとそのサブディレクトリ¹内のファイルの名前をリストするように求められました。

私が知っている唯一の非再帰的な方法はスタックを使用しているため、この質問に答えることができませんでした。

インタビュアーが解決策を説明しましたが、理解できませんでした。私が覚えている唯一のことは、それが1つではなく2つの方法を含んでいたということです。

再帰やスタックやキューなしでディレクトリとそのサブディレクトリにファイルを一覧表示できるようにするこのアプローチは何ですか？

¹解決策は言語に依存しません。サブディレクトリのリストは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 に答える