4

我正在尝试制作一个迭代器，该迭代器对特定文件夹中的所有文件和文件夹执行广度优先遍历。我已经用深度优先遍历完成了这个，它返回，例如：

\A
\A\1
\A\1\x
\A\1\y
\A\2
\B
\B\1

等等

现在我正在尝试制作一个程序，该程序将返回广度优先的结果：（或逐级）

\A
\B
\A\1
\A\2
\B\1
\A\1\x
\A\1\y

对于相同的层次结构。但是，我遇到了一个绊脚石：假设我希望这些以正确的顺序发生（特别是，不是相反的顺序），我找不到任何方法来执行此操作而最终需要 O(n) 内存，其中n是驱动器上文件/文件夹的数量，因为在我看来，我最终需要将整个驱动器层次结构保留在内存中，而对于 DFS，我可以完全忽略我之前在层次结构中的同一级别。

所以我的问题是：有没有比线性更好的方式来使用内存来遍历文件夹？

4

1 回答 1

3

如果您的平台支持 的概念inode number，则您可以为每个目录存储一个数字，以指示您为该特定目录访问过的最大 inode 编号。如果您按数字顺序访问 inode，跟踪单个条目就足以知道“下一个”条目在哪里。

这是一个小小的收获，因为您仍然需要为系统上的每个目录维护一个 inode 编号，但您不需要关心目录的内容。

当然，请记住，任何遍历机制都会受到可怕的竞争条件的影响，您必须有一定程度的保证，即文件系统是静止的，或者您的代码对被删除、创建、移动等的目录/文件具有弹性。 ，而您的代码正在进行中。

于 2011-03-12T09:16:02.197 回答