14.4. Деревья

В ряде задач линейной структуры данных, какой является динамический массив, оказывается недостаточно. Представьте себе хотя бы разветвленную структуру каталогов на жестком диске компьютера. А как хранить в памяти генеалогическое дерево? данные о структуре сложного изделия, содержащего сотни узлов и подузлов? календарь игр между командами на чемпионате мира? Таким образом, существует необходимость в древовидной структуре для хранения информации (Рис. 14 .45).

Рис. 14.45. Дерево.

Кстати, компьютерное дерево, в отличие от нормального, растет корнем вверх…

В большинстве задач из каждого узла дерева выходят ровно две ветки. Такие деревья называются бинарными (Рис. 14 .46).

Рис. 14.46. Бинарное дерево.

Структура данных для представления вершины бинарного дерева должна включать не одно, а два поля с указателями – для двух выходящих из вершины веток:

TYPE Ptr =^Tnode; Tnode = RECORD data: STRING: left, right: Ptr END;

Еще лучше, если двоичное дерево будет упорядоченным. В упорядоченном дереве значение левой вершины всегда меньше или равно значения правой вершины.

Важный вопрос – алгоритм поиска нужного значения в дереве. Дерево ветвится и, казалось бы, трудно написать алгоритм, который бы перебирал все его вершины. Однако существует простой прием, упрощающий обход дерева. К дереву добавляется дополнительная вершина, называемая барьером и все конечные элементы исходного дерева "замыкаются" на вершину–барьер (Рис. 14 .47).

Рис. 14.47. Добавление барьера к двоичному дереву.

Тогда функция поиска значения в упорядоченном двоичном дереве выглядит следующим образом:

FUNCTION Locate(x:WORD; t:Ptr):Ptr;

{ x – искомое значение; t – указатель на корень дерева } BEGIN WHILE (t<>NIL) AND (t^.data<>x) DO

IF t^.data<x THEN t := t^.right ELSE t := t^.left; Locate :=t END.

14.5. Потоки в памяти

В Delphi предусмотрено специальное средство для хранения в динамической памяти неструктурированных данных – поток памяти (memory stream). В поток можно сохранить любые данные – текст, графику, звук. Поток очень удобен для передачи больших объемов информации между различными объектами: большая часть объектов в Delphi поддерживает работу с потоками.

Название "поток" не очень удачно и сбивает с толку: кажется, что речь идет о каком-то потоке данных, перемещающихся в памяти. На самом деле поток в памяти – это, скорее, не поток, а озеро. Потоком является область в динамической памяти, размер которой автоматически меняется при загрузке в поток данных. У потока есть свойство Position, указывающее, с какого места данные из потока будут считываться (аналогично работе с типизированными файлами).

Рассмотрим следующую задачу. Нa форме имеются компоненты ComboBox1 типа TComboBox и Memo1 типа TMemo. Необходимо скопировать все пункты из раскрывающегося списка компонента ComboBox1 в Memo1. Первое, что приходит в голову:

VAR i:BYTE;

BEGIN

Memo1.Lines.Clear;

FOR i:=0 TO ComboBox1.Items.Count-1 DO

Memo1.Lines.Add(ComboBox1.Items[i]);

Согласитесь, код получился некрасивый, да и неэффективный. Решим ту же задачу при помощи потока:

VAR m:TMemoryStream;

begin

// создание потока

m:=TMemoryStream.Create;

// запись пунктов списка в поток

ComboBox1.Items.SaveToStream(m);

// переход к началу потока

m.Position:=0;

// загрузка данных из потока

Memo1.Lines.LoadFromStream(m);

// удаление потока из памяти

m.Free

end;

Как видно, список элементов Items имеет специальный метод сохранения в поток SaveToStream. После сохранения внутренний указатель на текущий элемент потока (свойство Position) будет указывать на самый последний загруженный в поток байт. Так как нам нужно считывать информацию из потока с первого байта (имеющего порядковый номер 0), необходимо установить указатель в 0. Если этого не сделать, из потока ничего прочитать не удастся. Собственно чтение данных выполняется методом LoadFromStream, относящимся к объекту Lines компонента Memo1. После чтения данных из потока его указатель перемещается к концу потока, но сами данные в потоке остаются. Для освобождения занимаемой потоком памяти следует использовать метод Free.