Основные операции

Реализация операций будет рассматриваться для двоичных деревьев, представленных как динамическая структура.

В качестве основных операций с двоичными деревьями рассмотрим операцию прямого обхода двоичного дерева в рекурсивной и нерекурсивной форме. Реализация обратного и симметричного обхода аналогична. Операции добавления, поиска и удаления вершин дерева зависят от принятого порядка вершин, поэтому будут представлены в п. 3.3.4.1, посвященном упорядоченным деревьям.

procedure PreOrder_BinTree(Node: PTree);

{Рекурсивный обход двоичного дерева в прямом порядке}

begin

writeln(Node^.Data);

if Node^.Left <> nil then PreOrder_BinTree(Node^.Left);

if Node^.Right <> nil then PreOrder_BinTree(Node^.Right);

end;

В процедуре, реализующей нерекурсивный обход двоичного дерева, используется стек, хранящий путь от корня дерева до предка текущей вершины. Описание этого стека и операции с ним аналогичны тем, что приведены в п. 2.2.8 с одним уточнением – элементы стека хранят указатели на вершины дерева.

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

procedure NR_PreOrder_BinTree(Tree: PTree);

{Нерекурсивный обход двоичного дерева в прямом порядке}

var

Node: Ptree; {Указатель на текущую вершину}

S: ^TypeElement; {Стек указателей вершин}

begin

{Инициализация}

ClearStack(S);

Node := Tree;

while true do

if Node <> nil then begin

writeln(Node^.Data);

PushStack(Node, S);

{Исследование левого потомка вершины Node}

Node := Node^.Left;

end else begin

{Завершена исследование пути, содержащегося в стеке}

if EmptyStack(S) then return;

{Исследование правого потомка вершины Node}

PopStack(Node, S);

Node := Node^.Right;

end;

end;

4. Файлы

Ранее, при обсуждении структур данных, предполагалось, что объем данных позволяет обходиться исключительно основной (оперативной) памятью. Существуют задачи, в которых объем используемых данных намного превышает возможности основной памяти. В большинстве вычислительных системах предусмотрены устройства внешней памяти (диски, ленты), на которых можно хранить огромные объемы данных.

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

Файл – это поименованная область во внешней памяти.

Операционная система делит внешнюю память на блоки одинакового размера. Размер блока зависит от конкретного типа операционной системы. Файлы хранятся в виде определенной последовательности блоков; каждый такой блок содержит целое число записей файла.

Базовыми операциями, выполняемыми по отношению к файлам, является перенос одного блока из внешней памяти в буфер и перенос одного блока из буфера во внешнюю память. Буфер находится в основной памяти, и его размер соответствует размеру блока.

При осуществлении чтения из файла, указатель считывания указывает на одну из записей в блоке, который в данный момент находится в буфере. Когда этот указатель должен переместиться на запись, отсутствующую в буфере, происходит чтение очередного блока из внешней памяти в буфер.

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

Рассматривая операции с файлами, в первом приближении можно считать, что файлы – это просто совокупности записей, над которыми можно выполнять операции, которые уже обсуждались выше. Однако имеются две важные особенности.

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

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

Еще одной особенностью хранения данных во внешней памяти является наличие так называемых закрепленных записей. Иногда, например, в базах данных, используют указатели на записи, представляющие собой пару «физический адрес блока – смещение записи в блоке». Следствием применения подобных указателей является то, что записи, на которые имеются эти указатели, нельзя перемещать, поскольку не исключено, что какой-то неизвестный указатель после перемещений записи будет указывать неправильный адрес записи.