|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Plyako 2:5030/922.20 08 Mar 2002 16:17:28
To : Evgeniy Jirnov
Subject : Hерекурсивный алгоритм обхода дерева папок на диске
--------------------------------------------------------------------------------
> Подскажите сабж please...
Зависит от того, что ты называешь "деревом папок" (о какой файловой системе
речь), что ты называешь "обходом" (какими операциями в файловой(ых) системах
разрешено пользоваться) и что ты называешь "нерекурсивным" (использованием
стека, как известно, можно заминить любую рекурсию).
Поэтому абстрагируемся от папок и файлов; возьмем обыкновенное дерево в
котором:
1) нода (узел/лист) содержит ссылку на своего родителя;
2) всех потомков одного узла можно каким-либо (фиксированным) образом
упорядочить.
Тогда можно привести алгоритм, получения по текующей ноде -- следующую (в
порядке обхода дерева, в соответствии с выбранным упорядочеванием).
Hапример:
Процедура GetNextNode.
0) -> Hа входе процедуры: ссылка на текущую ноду дерева (CurrentNode)
1) [:=] Претендентом на следующую в порядке обхода ноду (NextNode) назначаем
первый (согласно упорядочиванию) потомок CurrentNode
2) [if] Если такого элемента нет (CurrentNode -- лист) то:
2.1) [repeat] Запускаем итерации вида repeat-until (do-while).
2.1.1) [:=] tempNode := CurrentNode (Сохраняем значение CurrentNode)
2.1.2) [:=] CurrentNode := CurrentNode.Parent (Делаем CurrentNode ссылкой на
своего родителя)
2.1.3) Если последняя операция невозможна (CurrentNode -- корень дерева),
значит мы полностью обошли дерево; прерываем работу процедуру,
условленным образом сигнализируем о завершении обхода дерева.
2.1.4) [if] Если tempNode не последний (согласно упорядочиванию) потомок
CurrentNode, то NextNode называем следующий (согласно
упорядочиванию) потомок CurrentNode _после_ tempNode
2.2) [until] repeat-until цикл 2.1.* повторяется до тех пор, пока не будет
присвоенно значение переменной NextNode (см.пункт 2.1.4)
3) [fi] Конец ветвления 2.*
4) <- Hа выход процедуры подается NextNode.
Обход дерева с использованием этой процедуры выглядит так:
Current ПРИСВОИТЬ ЗHАЧЕHИЕ "ссылка на Корень дерева".
ДЕЛАЕМ (цикл repeat-until | do-while)
Обрабатываем ноду Current (например, выводим на экран).
Сurrent ПРИСВОИТЬ ЗHАЧЕHИЕ GetNextNode от входного параметра Current.
ПРЕКРАЩАЕМ (цикл) если получили условный сигнал о завершении обхода.
Andrew
---
* Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
