Структуры и алгоритмы обработки данных

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


Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе 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 вычислять при помощи цепочки имен каталогов до корневого узла.




Содержание раздела