Создание и редактирование сильноветвящихся деревьев

Пример сильноветвящихся деревьев для чтения структуры заданного каталога или диска, навигации и подсчета места, занимаемого каталогом. Операции по просмотру содержимого каталогов и подсчету занимаемого объема производятся не с физическими каталогами и файлами, а с созданным динамическим списковым представлением их логической структуры в виде сильноветвящегося дерева. В примере для каждого файла или каталога хранится его полное имя.

Для чтения оглавления диска используются стандартные функции FindFirst() и FindNext(), которые возвращают сведения о первом и последующих элементах в оглавлении текущего каталога. В процессе чтения корневого каталога строится первый уровень потомков в списковой структуре дерева. Процедура построения поддерева вызывается для каждого узла в корневом каталоге. Процесс повторяется для всех непустых каталогов до тех пор, пока не будет построена полная структура оглавления.

program dirtree;

{$APPTYPE CONSOLE}

uses SysUtils;

Type

TNode = record

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

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

node_type: Char; { Тип узла (файл - 'f' / каталог-'c') }

up, down: Pointer; { Указатели на предка и список потомков }

last, next: Pointer; { Указатели на соседние узлы }

end;

Var

n, i, l, error: Integer;

current_root: Pointer;

pnt, current: ^TNode;

str: string;

{ Отображение физического оглавления диска в логическую структуру }

procedure CreateTree(local_root:Pointer);

var s: TSearchRec; local_node, local_r_node, local_last: ^TNode;

{ Создание нового узла в дереве каталогов и файлов }

procedure NewNode;

Begin

New(local_node);

local_node^.last:=local_last;

if 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 faDirectory = 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;

error:=FindFirst(local_r_node^.name+'\*.*',faAnyFile,s);

if error = 0 then

Begin

if (s.name<>'.') and (s.name<>'..') then NewNode;

while error = 0 do

Begin

error:=FindNext(s);

if (error = 0) and (s.name<>'.') and (s.name<>'..') then NewNode;

end;

end;

if local_r_node^.down <> nil then

Begin

local_node:=local_r_node^.down;

Repeat

{ Рекурсивный вызов }

if local_node^.node_type = 'c' then CreateTree(local_node);

local_node:=local_node^.next

until local_node = nil;

end;

end;

{ Вывод оглавления текущего каталога }

procedure CurrentList;

Begin

current:=current_root;

WriteLn('Current directory - ', current^.name);

if current^.node_type = 'c' then

Begin

pnt:=current^.down;

i:=1;

{ Проходим каталог в дереве }

Repeat

WriteLn(i:4,'-',pnt^.name);

pnt:=pnt^.next;

Inc(i);

until pnt = nil;

end;

end;

{ Навигация в дереве каталогов. Перемещение на один уровень вниз }

procedure MoveDown;

Begin

current:=current_root;

if current^.down <> nil then

Begin

current:=current^.down;

WriteLn('Id in list');

Read(l);

i:=1;

while (i < l) and (current^.next <> nil) do

Begin

current:=current^.next;

Inc(i);

end;

if (current^.node_type = 'c') and (current^.down <> nil)

then current_root:= current;

end;

end;

{ Навигация в дереве каталогов. Перемещение на один уровень вверх }

procedure MoveUp;

Begin

current:=current_root;

if 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: ^TNode;

Begin

local_r_node:=local_root;

if local_r_node^.down <> nil then

Begin

local_node:=local_r_node^.down;

Repeat

if local_node^.node_type = 'f' then

Inc(n_files) else

Begin

Inc(n_cats);

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('files : ',n_files, ' directories: ', n_cats);

end;

{ Расчет физического объема иерархической структуры каталога }

procedure CountMem;

var mem: LongInt;

procedure count_m_in(local_root: Pointer);

var local_node, local_r_node: ^TNode;

Begin

local_r_node:=local_root;

if 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);

{ Инициализация корня дерева каталогов и указателей для навигации }

current_root:=current;

WriteLn('Directory ?');

Read(str);

WriteLn(str);

current^.name:=str;

current^.last:=nil;

current^.next:=nil;

current^.up:=nil;

current^.down:=nil;

current^.node_type:='c';

{ Создание дерева каталогов }

CreateTree(current);

if current^.down = nil then

current^.node_type:=' ';

Repeat

WriteLn('1-List');

WriteLn('2-Down');

WriteLn('3-Up');

WriteLn('4-Files');

WriteLn('5-Volume');

Readln(n);

if n = 1 then CurrentList;

if n = 2 then MoveDown;

if n = 3 then MoveUp;

if n = 4 then Count;

if n = 5 then CountMem;

until n = 0;

end.