26. Динамические структуры: списки, деревья
Примеры программ, использующих динамические массивы, приведенные в предыдущей главе, все еще были плохими. Для того чтобы использовать динамические массивы таким образом, мы должны заранее знать размеры этих массивов. В реальных же задачах зачастую объем обрабатываемых данных заранее не известен. В этом случае удобно использовать динамические структуры данных, простейшей из которых является список. Список называется динамической структурой не только потому, что он размещается в динамической памяти, но, главным образом, потому, что его размер может меняться в процессе выполнения программы. Список не является объектом языка Паскаль и вообще никак не связан с конкретным языком программирования. Сама идея списка заключается в следующем: список есть совокупность однотипных элементов, элементы размещаются в памяти произвольным образом, но в каждом из элементов хранится адрес следующего элемента. Таким образом, для обработки списка достаточно знать один-единственный адрес - адрес первого элемента списка. Чтобы обозначить последний элемент, в нем в качестве адреса следующего элемента хранят константу Nil. Схематично список можно изобразить так:
Каждый элемент такого списка можно рассматривать как совокупность двух полей - поля данных, в котором содержится хранимая в списке информация (любого типа), и адресного поля, в котором записан адрес следующего элемента. Такой список называют односвязным, поскольку между парой элементов есть только одна связь. В некоторых случаях удобнее использовать двусвязный список, в каждом элементе которого хранятся адреса предыдущего и последующего элементов:
Деревом называют совокупность элементов, каждый из которых связан с одним элементом-предком и с несколькими элементами-потомками. Простейшее дерево, когда число потомков не превышает двух, называется бинарным. Бинарное дерево можно схематично изобразить в виде:
Каждый элемент бинарного дерева содержит поле данных и 3 (или 2) адресных поля. Рассмотрим теперь реализацию динамических структур в Паскаль-программе. Поскольку элементы будут размещаться в динамической памяти, переменные такого типа в программе не нужны, а нужны лишь указатели на них, следовательно, достаточно описать тип элемента в операторе Type. В качестве типа элемента можно, очевидно, использовать только запись. Опишем сначала элемент односвязного списка:
Type
Adres = ^Element;
Element = Record Body : тип; Next : Adres; End;
В этом случае язык Паскаль допускает использование при описании типа Adres еще не описанного идентификатора Element. Но оба типа должны быть описаны в одном операторе Type . Следующая запись синтаксически ошибочна:
Type Adres = ^Element;
Type Element = Record Body : тип; Next : Adres; End;
Можно описать тип элемента списка и другим способом, используя нетипизированный указатель:
Type Element = Record Body : тип; Next : Pointer; End;
Теперь мы легко сможем описать элементы двусвязного списка и бинарного дерева :
Type Adres2 = ^Element2;
Element2 = Record
Body : тип; Previous,Next : Adres2;
End;
Type Adres_Tree = ^Element_Tree;
Element_Tree = Record
Body: тип; [Up,]Left,Right: Adres_Tree; End;
В некоторых алгоритмах адресное поле Up - адрес элемента-предка - необходимо, в других оно не нужно. Обработка динамических структур, как правило, не составляет большого труда, единственное нетривиальное действие - это создание такой структуры. Рассмотрим алгоритм создания односвязного списка. Пусть список содержит вещественные числа, которые вводятся с клавиатуры.
Type
P_Stack = ^T_Satck;
T_Stack = Record
Num : Real;
Next : Adres;
End;
Var
Top,p : P_Stack;
Num : Real;
Begin
Top:=Nil;
While Not SeekEoLn Do Begin
Read(Num);
New(p);
p^.Num:=Num;
p^.Next:=Top;
Top:=p;
End;
{ теперь выведем полученный список }
p:=Top;
While p<>Nil Do Begin
WriteLn(p^.Num);
p:=p^.Next;
End;
End.
В этой программе список формируется по принципу стека - чем раньше введен элемент, тем глубже он находится в списке. Такие структуры данных часто называют LIFO-структурами (от английской фразы Last In First Out: последним вошел - первым вышел). Если в решаемой задаче порядок элементов в списке важен, то такой способ формирования списка не годится. Запишем другой алгоритм.
Type
P_Queue = ^T_Queue;
T_Queue = Record Num : Real; Next : T_Queue; End;
Var
Top,p,p0 : Adres;
Num : Real;
Begin
Top:=Nil;
While Not SeekEoLn Do Begin
Read(Num);
New(p);
p^.Num:=Num;
If Top=Nil Then Top:=p Else p0^.Next:=p;
p0:=p;
End;
p^.Next:=Nil;
p:=Top;
While p<>Nil Do Begin
WriteLn(p^.Num);
p:=p^.Next;
End;
End.
В нем список формируется по принципу очереди и является FIFO-структурой (First In First Out). Выполним несколько простейших операций с нашим списком. Найдем сумму чисел, содержащихся в списке:
S:=0;
p:=Top;
While p<>Nil Do Begin
S:=S+p^.Num;
p:=p^.Next;
End;
Упорядочим список по неубыванию чисел:
p1:=Top;
While p1^.Next<>Nil Do Begin
p2:=p1^.Next;
While p2<>Nil Do Begin
If p1^.Num>p2^.Num Then Begin
Num:=p1^.Num;
p1^.Num:=p2^.Num;
p2^.Num:=Num;
End;
p2:=p2^.Next;
End;
p1:=p1^.Next;
End;
Найдем наименьший элемент списка и удалим его:
p:=Top;
Min:=1.7E38;
While p<>Nil Do Begin
If p^.Num<Min Then Begin
Min:=p^.Num;
MinAdr:=p;
End;
p:=p^.Next;
End;
{мы нашли адрес наименьшего элемента, но, поскольку наш список односвязный, необходимо еще найти адрес предыдущего элемента}
If MinAdr<>Top Then Begin
p:=Top;
While p^.Next<>MinAdr Do p:=p^.Next;
End;
{теперь можем удалять}
If MinAdr=Top Then Top:=Top^.Next
Else p^.Next:=MinAdr^.Next;
Dispose(MinAdr);
Найдем наименьший элемент списка и вставим после него число 0:
p:=Top;
Min:=1.7E38;
While p<>Nil Do Begin
If p^.Num<Min Then Begin
Min:=p^.Num;
MinAdr:=p;
End;
p:=p^.Next;
End;
New(p);
p^.Num:=0;
p^.Next:=MinAdr^.Next;
MinAdr^.Next:=p;
Уничтожим весь список:
While Top<>Nil Do Begin
p:=Top^.Next;
Dispose(Top);
Top:=p;
End;
Операции с двусвязными списками, деревьями и другими сколь угодно сложными динамическими структурами выполняются аналогичным образом. Если какой-то алгоритм вызывает у вас трудности, попробуйте изобразить свою динамическую структуру на бумаге - часто это бывает полезно.