|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 07 Mar 2002 01:13:51
To : Evgeniy Jirnov
Subject : Re: Hерекурсивный алгоритм обхода дерева папок на диске
--------------------------------------------------------------------------------
Evgeniy Jirnov wrote:
>
> >> Дело в том, что в данном случае любой нерекурсивный алгоритм на самом
> >> деле
> >> все равно будет тем или иным способом эмулировать рекурсию. Дерево можно
> >> обходить
> AT> Если дочерний каталог содержит ссылку на parent-каталог, то можно
> AT> посторить истинно циклический алгоритм. Hикакой эмуляции рекурсии не
> AT> будет.
>
> Кстати дочерний каталог итак содержит ссылку на родительский. Это каталог с
> названием "..".
Hу это где есть, а где и нет.
> Построй мне please истинно циклический алгоритм на основе этих
> данных. Спасибо скажу огромное.
Вот программа для MSVC++ 6 и Windows (исрользует _findfirst, _findnext,
_chdir и т.п.). Функция 'traverse' реализует истинно циклический
алгоритм обхода дерева каталогов, пользуясь тем, что дочерние каталоги
связаны с родительским ссылкой "..".
Сразу отмечу одну деталь. Для решения этой задачи обхода каталогов можно
построить несложный код, который в процессе обхода манипулирует _полным_
путем к текущему каталогу. Ясно, что такая реализация будет лишь
замаскированной реализацией рекурсии, ибо полный путь к текущему
каталогу - это тот же самый стек и пиковое количество занимаемой им
памяти определяется максимальной глубиной дерева.
Особенностью истинно циклического алгоритма будет то, что пиковое
значение потребляемой им памяти не зависит от глубины дерева.
Приведенный ниже программа реализует именно такой истинно циклический
алгорити, но есть одна маленькая неприятность. Hеприятность заключается
в том, что этой программе в процесе обхода нужно уметь определять
локальное имя текущего каталога (замечу - не полный путь, а именно
короткое локальное имя). К сожалению, я не нашел в RTL функции, которая
давала бы мне такое имя. Поэтому мне пришлось написать эту функцию
самому ('get_current_dir') и воспользоваться внутри нее функцией
'_getcwd', дающей _полный_ путь. Я делаю это замечание для того, чтобы
кто-нибудь, увидев в моем коде вызов '_getcwd', сгоряча не обвинил
реализованный алгоритм в рекурсивности. Функция '_getcwd' для данного
алгоритма слвершенно непринципиальна и полный путь к каталогу этому
алгоритму на самом деле нигде не нужен.
Добавлю под занавес, что практическая ценость такого способа обхода
дерева каталогов весьма невелика (по крайней мере в Windows), ибо такой
алгоритм более запутан и менее эффективен (по скорости), чем более или
менее замаскированная рекурсия. В частности, если для обработки
обходимых каталогов тебе понадобятся полные пути к этим каталогам, то
незачем и огород городить, ибо, как уже говорилось, полный путь к
каталогу - это готовый стек рекурсии. А раз стек уже есть, то
сторониться рекурсии (или ее циклической реализации) совершенно незачем.
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <direct.h>
#include <io.h>
using namespace std;
string get_current_dir()
{
char sz_current_dir[_MAX_PATH];
_getcwd(sz_current_dir, _MAX_PATH);
string str_current_dir = sz_current_dir;
assert(str_current_dir.length() > 0);
if (str_current_dir[str_current_dir.length() - 1] == '\\')
return "\\";
string::size_type i_b = str_current_dir.rfind('\\');
assert(i_b != string::npos && i_b < str_current_dir.length() - 1);
return str_current_dir.substr(i_b + 1);
}
string find_next_dir(const string& str_prev_dir)
{
long h_search;
bool b_ok;
struct _finddata_t find_data;
h_search = _findfirst("*", &find_data);
b_ok = h_search != -1;
if (!str_prev_dir.empty())
{
while (b_ok && ((find_data.attrib & _A_SUBDIR) == 0 ||
find_data.name != str_prev_dir))
b_ok = _findnext(h_search, &find_data) == 0;
b_ok = _findnext(h_search, &find_data) == 0;
}
while (b_ok &&
((find_data.attrib & _A_SUBDIR) == 0 ||
strcmp(find_data.name, ".") == 0 || strcmp(find_data.name,
"..") == 0))
b_ok = _findnext(h_search, &find_data) == 0;
_findclose(h_search);
return b_ok ? find_data.name : "";
}
void traverse(const string& str_start)
{
_chdir(str_start.c_str());
unsigned i_depth = 0;
string str_prev;
string str_current = get_current_dir();
cout << str_current << endl;
do
{
string str_next_sub = find_next_dir(str_prev);
if (!str_next_sub.empty())
{
str_prev.erase();
str_current = str_next_sub;
_chdir(str_current.c_str());
++i_depth;
cout << setw(i_depth * 2) << "" << str_current << endl;
}
else
{
if (i_depth == 0)
break;
_chdir("..");
--i_depth;
str_prev = str_current;
str_current = get_current_dir();
}
} while (1);
}
int main()
{
traverse("c:\\program files");
}
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
