Применение сильноветвящихся деревьев
Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе MS Dos корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью - непустым каталогам.
Рис.4.21. Представление логической структуры каталогов и файлов в виде сильноветвящегося дерева.
Для представления такой структуры используем расширение спискового представления сильноветвящихся деревьев. Способы представления деревьев, рассмотренные ранее, являются предельно экономичными, но не очень удобными для перемещения по дереву в разных направлениях. Именно такая задача встает при просмотре структуры каталогов. Необходимо осуществлять навигацию¦ v перемещаться из текущего каталога в каталог верхнего или нижнего уровня, или от файла к файлу в пределах одного каталога.
Для облегчения этой задачи сделаем списки потомков двунаправленными. Для этого достаточно ввести дополнительный указатель на предыдущий узел ¦last¦. С целью упрощения перемещения по дереву от листьев к корню введем дополнительный указатель на предок текущего узла up¦. Общими с традиционными способами представления являются указатели на список потомков узла down¦ и следующий узел next¦.
Для представления оглавления диска служат поля имя и тип файла/каталога. Рассмотрим программу, которая осуществляет чтение структуры заданного каталога или диска, позволяет осуществлять навигацию и подсчет места занимаемого любым каталогом.
program dir_tree;
uses dos;
type node=record
name: string[50]; {Имя каталога/файла}
size: longint; {Размер файла (байт) }
node_type: char; {Тип узла (файл v'f' / каталог-'c')}
up,down: pointer; {Указатели на предка и список потомков}
l last,next: pointer; {Указатели на соседние узлы}
end;
var
n,i,l:integer;
root, current_root: pointer;
pnt, current:^node;
s : searchrec;
str: string;
procedure create_tree(local_root:pointer);
{ Отображение физического оглавления диска в логическую структуру}
var
local_node, local_r_node, local_last : ^node;
procedure new_node;
{Создание нового узла в дереве каталогов и файлов}
begin
new(local_node);
local_node^.last:=local_last;
if not(local_last=nil) then local_last^.next:=local_node;
local_node^.next:=nil;
local_node^.down:=nil;
local_node^.up:=local_r_node;
if local_r_node^.down =nil then local_r_node^.down:=local_node;
local_node^.name:=local_r_node^.name+'\'+s.name;
if s.attr and Directory = 0 then local_node^.node_type:='f'
else local_node^.node_type:='c';
local_node^.size:=s.size;
local_last:=local_node;
end;
begin {Собственно процедура}
local_r_node:=local_root;
local_last:=nil;
findfirst(local_r_node^.name+'\*.*',anyfile,s);
if doserror = 0 then
begin
if (s.name<>'.') and (s.name<>'..') and (s.attr and VolumeID = 0)
then new_node;
while doserror=0 do begin
findnext(s);
if (doserror = 0) and (s.name<>'.') and (s.name<>'..') and (s.attr and VolumeID = 0)
then new_node;
end
end;
if not (local_r_node^.down=nil) then
begin
local_node:=local_r_node^.down;
repeat
if local_node^.node_type='c' then create_tree(local_node);{Рекурсия}
local_node:=local_node^.next
until local_node=nil
end
end;
procedure current_list;
{Вывод оглавления текущего каталога}
begin
current:=current_root;
writeln('текущий каталог - ', current^.name);
if current^.node_type='c'then
begin
pnt:=current^.down;
i:=1;
repeat {Проходим каталог в дереве}
writeln (i:4,'-',pnt^.name);
pnt:=pnt^.next;
i:=i+1
until pnt=nil
end;
end;
procedure down;
{Навигация в дереве каталогов. Перемещение на один уровень вниз}
begin
current:=current_root;
if not (current^.down=nil) then
begin
current:= current^.down;
writeln('номер в оглавлении'); readln; read(l);
i:=1;
while (i<l) and not (current^.next=nil) do
begin
current:=current^.next;
i:=i+1
end;
if (current^.node_type='c') and not (current^.down=nil)
then current_root:= current;
end;
end;
procedure up;
{Навигация в дереве каталогов. Перемещение на один уровень вверх}
begin
current:=current_root;
if not (current^.up=nil) then current_root:=current^.up;
end;
procedure count;
{Расчет числа файлов и подкаталогов иерархической структуры каталога}
var
n_files, n_cats :integer;
procedure count_in (local_root : pointer);
var
local_node, local_r_node: ^node;
begin
local_r_node:=local_root;
if not (local_r_node^.down=nil) then
begin
local_node:=local_r_node^.down;
repeat
if local_node^.node_type='f' then
n_files:=n_files+1
else
begin
n_cats:=n_cats+1;
count_in (local_node)
end;
local_node:=local_node^.next
until local_node=nil
end
end;
begin {Собственно процедура}
n_files:=0; n_cats:=0;
count_in (current_root);
writeln ('файлы : ',n_files, ' каталоги: ', n_cats);
end;
procedure count_mem;
{ Расчет физического объема иерархической структуры каталога}
var
mem :longint;
procedure count_m_in (local_root : pointer);
var
local_node, local_r_node: ^node;
begin
local_r_node:=local_root;
if not (local_r_node^.down=nil) then
begin
local_node:=local_r_node^.down;
repeat
if local_node^.node_type='f' then
mem:=mem+local_node^.size
else
count_m_in (local_node);
local_node:=local_node^.next
until local_node=nil
end
end;
begin {Собственно процедура}
mem:=0;
count_m_in (current_root);
writeln ('mem ', mem, ' bytes');
end;
{----------основная программа----------}
begin
new(current);
{Инициализация корня дерева каталогов и указателей для навигации}
root:=current; current_root:=current;
writeln('каталог '); read(str); writeln(str);
current^.name:=str;
current^.last:=nil; current^.next:=nil;
current^.up:=nil; current^.down:=nil;
current^.node_type:='c';
{Создание дерева каталогов}
create_tree(current);
if current^.down=nil then current^.node_type:=' ';
repeat
{ Интерактивная навигация }
writeln ('1-список');
writeln('2-вниз');
writeln('3-вверх');
writeln('4-число файлов');
writeln('5-объем');
readln(n);
if n=1 then current_list;
if n=2 then down;
if n=3 then up;
if n=4 then count;
if n=5 then count_mem;
until n=0
end.
Для чтения оглавления диска в данной программе используются стандартные процедуры findfirst и findnext, которые возвращают сведения о первом и последующих элементах в оглавлении текущего каталога.
В процессе чтения корневого каталога строится первый уровень потомков в списковой структуре дерева. Далее процедура построения поддерева вызывается для каждого узла в корневом каталоге. Затем процесс повторяется для всех непустых какталогов до тех пор, пока не будет построена полная структура оглавления.
Все операции по просмотру содержимого каталогов и подсчету занимаемого объема производятся не с физическими каталогами и файлами, а с созданным динамическим списковым представлением их логической структуры в виде сильноветвящегося дерева.
В данном примере программы для каждого файла или каталога хранится его полное имя в MS-DOS, которое включает имя диска и путь.Если программу несколько усложнить, то можно добиться более эффективного использования динамической памяти. Для этого потребуется хранить в узле дерева только имя каталога или файла, а полое имя v вычислять при помощи цепочки имен каталогов до корневого узла.
