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


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


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

pic4_21.gif (4489 bytes)

Рис.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')}




Начало  Назад  Вперед



Книжный магазин