Применение сильноветвящихся деревьев

Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе MS Dos корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью - непустым каталогам.

Рис.4.21. Представление логической структуры каталогов и файлов в виде сильноветвящегося дерева.

Для представления такой структуры используем расширение спискового представления сильноветвящихся деревьев. Способы представления деревьев, рассмотренные ранее, являются предельно экономичными, но не очень удобными для перемещения по дереву в разных направлениях. Именно такая задача встает при просмотре структуры каталогов. Необходимо осуществлять ⌠навигацию■ √ перемещаться из текущего каталога в каталог верхнего или нижнего уровня, или от файла к файлу в пределах одного каталога.

Для облегчения этой задачи сделаем списки потомков двунаправленными. Для этого достаточно ввести дополнительный указатель на предыдущий узел ■last■. С целью упрощения перемещения по дереву от листьев к корню введем дополнительный указатель на предок текущего узла ⌠up■. Общими с традиционными способами представления являются указатели на список потомков узла ⌠down■ и следующий узел ⌠next■.

Для представления оглавления диска служат поля имя и тип файла/каталога. Рассмотрим программу, которая осуществляет чтение структуры заданного каталога или диска, позволяет осуществлять навигацию и подсчет места занимаемого любым каталогом.

program dir_tree;

uses dos;

type node=record

name: string[50]; {Имя каталога/файла}

size: longint; {Размер файла (байт) }

node_type: char; {Тип узла (файл √'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, которое включает имя диска и путь. Если программу несколько усложнить, то можно добиться более эффективного использования динамической памяти. Для этого потребуется хранить в узле дерева только имя каталога или файла, а полое имя √ вычислять при помощи цепочки имен каталогов до корневого узла.

Поиск по сайту: