В ряде задач линейной структуры данных, какой является динамический массив, оказывается недостаточно. Представьте себе хотя бы разветвленную структуру каталогов на жестком диске компьютера. А как хранить в памяти генеалогическое дерево? данные о структуре сложного изделия, содержащего сотни узлов и подузлов? календарь игр между командами на чемпионате мира? Таким образом, существует необходимость в древовидной структуре для хранения информации (Рис. 10.6).
Рис. 14.6. Дерево.
Кстати, компьютерное дерево, в отличие от нормального, растет корнем вверх…
В большинстве задач из каждого узла дерева выходят ровно две ветки. Такие деревья называются бинарными(Рис. 10.7).
Рис. 14.7. Бинарное дерево.
Структура данных для представления вершины бинарного дерева должна включать не одно, а два поля с указателями – для двух выходящих из вершины веток:
TYPE Ptr =^Tnode; Tnode = RECORD data: STRING: left, right: Ptr END;
Еще лучше, если двоичное дерево будет упорядоченным. В упорядоченном дереве значение левой вершины всегда меньше или равно значения правой вершины.
Важный вопрос – алгоритм поиска нужного значения в дереве. Дерево ветвится и, казалось бы, трудно написать алгоритм, который бы перебирал все его вершины. Однако существует простой прием, упрощающий обход дерева. К дереву добавляется дополнительная вершина, называемая барьером и все конечные элементы исходного дерева "замыкаются" на вершину–барьер (Рис. 10.8).
Рис. 14.8. Добавление барьера к двоичному дереву.
Тогда функция поиска значения в упорядоченном двоичном дереве выглядит следующим образом:
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.
В 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.
