русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 1027; Нарушение авторских прав


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



<== предыдущая лекция | следующая лекция ==>
Представление сильноветвящихся деревьев | Алгоритмы на графах


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.