25. Динамические структуры: списки, деревья

Примеры программ, приведенные в предыдущей главе, все еще были плохи­ми. Для того, чтобы использовать динамические массивы таким образом, мы должны заранее знать размеры этих массивов. В реальных же задачах зачастую объем обрабатываемых данных заранее не известен. В этом случае удобно ис­пользовать динамические структуры данных, простейшей из которых является список. Список называется динамической структурой не только потому, что он размещается в динамической памяти, но главным образом потому, что его размер может меняться в процессе выполнения программы. Список не является объек­том языка Паскаль и вообще никак не связан с конкретным языком программи­рования. Сама идея списка заключается в следующем : список есть совокупность однотипных элементов. Элементы размещаются в памяти произвольным обра­зом, но в каждом из элементов хранится адрес следующего элемента. Таким об­разом, для обработки списка достаточно знать один единственный адрес - адрес первого элемента списка.Чтобы обозначить последний элемент, в нем в качестве адреса следующего элемента хранят константу NIL. Изобразим список:

Адрес первого элемента данные данные данные NIL

Каждый элемент такого списка можно рассматривать как совокупность двух полей - поля данных, в котором содержатся собственно хранимая в списке ин­формация (любого типа), и адресного поля, в котором записан адрес следующего элемента. Такой список называют односвязным, поскольку между парой элемен­тов есть только одна связь. В некоторых случаях удобнее использовать двусвяз-ный список, в каждом элементе которого хранятся адреса предыдущего и после­дующего элементов :

Первый элемент ни данные 3=Е

данные 3=Е

данные NIL + последний элемент

Деревом называют совокупность элементов, каждый из которых связан с од­ним элементом - предком и с несколькими элементами - потомками. Простейшее дерево - когда число потомков не превышает двух - называется бинарным. Би­нарное дерево можно изобразить в виде:

NIL

 

данные

 

1

 

данные

 

1

NIL

данные

 

1

NIL

данные

 

1

NIL

данные

 

Каждый элемент бинарного дерева содержит поле данных и три адресных поля. Рассмотрим теперь реализацию динамических структур в Паскаль-про­грамме. Поскольку элементы будут размещаться в динамической памяти, пере­менные такого типа в программе не нужны, а нужен лишь тип элемента. В каче­стве типа элемента можно, очевидно, использовать только запись. Опишем сна­чала элемент односвязного списка: 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; Теперь мы легко сможем описать элементы двусвязного списка и бинарного дерева:

TYPE Adres2 = лElement2;

Element2 = RECORD Body : тип; Previous,Next : Adres2; END; TYPE AdresTree = лElement_Tree;

ElementTree = RECORD Body: тип; Up,Left,Right: AdresTree; END; Обработка динамических структур не составляет большого труда, единствен­ное нетривиальное действие - это создание такой структуры. Рассмотрим алго­ритм создания односвязного списка. Пусть список содержит вещественные чис­ла, которые вводятся с клавиатуры: TYPE Adres = лElement;

Element = RECORD Body : Real; Next : Adres; END; VAR First,p : Adres; Num : Real; BEGIN First:=NIL;

WHILE NOT SeekEOLN DO BEGIN

READ(Num); NEW(p); pЛ.Body:=Num; pЛ.Next:=First; First:=p;

END;

{ теперь выведем полученный список } p:=First;

WHILE p<>NIL DO BEGIN WRITELN^.Body); p^.Next; END;

END.

Наша программа сформировала список, но числа записаны там в обратном порядке. В некоторых задачах это допустимо, в других, где порядок элементов важен, следует использовать, например, такой алгоритм: TYPE Adres = лElement;

Element = RECORD Body : Real; Next : Adres; END; VAR First,p,p0 : Adres; Num : Real; BEGIN First:=NIL;

WHILE NOT SeekEOLN DO BEGIN

READ(Num); NEW(p); pЛ.Body:=Num;

IF First=NIL THEN First:=p ELSE p0л.Next:=p;

p0:=p;

END;

pЛ.Next:=NIL;

{ теперь выведем полученный список } p:=First;

WHILE p<>NIL DO BEGIN WRITELNftABody); p^.Next; END;

END.

Выполним несколько простейших операций с нашим списком. Найдем сумму чисел, содержащихся в списке:

S:=0; p:=First; WHILE p<>NIL DO BEGIN S:=S+pЛ.Body; p^.Next; END; Упорядочим список по неубыванию чисел:

p1:=First;

WHILE p^.Next<>NIL DO BEGIN p2:=p^.Next;

WHILE p2<>NIL DO BEGIN

IF p1A.Body>p2A.Body THEN BEGIN

Num:=p1A.Body; p1A.Body:=p2A.Body; p2A.Body:=Num;

END;

p2:=p2A.Next; END;

p1:=p1A.Next; END;

Найдем наименьший элемент списка и удалим его: p:=First; Min:=1E38;

WHILE p<>NIL DO BEGIN

IF pA.Body<Min THEN BEGIN Min:=pA.Body; MinAdr:=p; END; p:=pA.Next;

END;

p:=First; p0:=NIL;

WHILE p<>MinAdr DO BEGIN p0:=p; p:=pA.Next; END; IF p=First THEN First:=pA.Next ELSE p0A.Next:=pA.Next; DISPOSE(p);

Найдем наименьший элемент списка и вставим после него число 0: p:=First; Min:=1E38;

WHILE p<>NIL DO BEGIN

IF pA.Body<Min THEN BEGIN Min:=pA.Body; MinAdr:=p; END; p:=pA.Next;

END;

NEW(p); pA.Body:=0; pA.Next:=MinAdrA.Next; MinAdrA.Next:=p; Уничтожим весь список: p:=First;

WHILE p<>NIL DO BEGIN p0:=pA.Next; DISPOSE(p); p:=p0; END; First:=NIL;

Операции с двусвязными списками, деревьями и другими сколь угодно сложными динамическими структурами выполняются аналогичным образом. Не отчаивайтесь, если вам поначалу будет трудно работать с динамическими струк­турами - большинство программистов прошло через это. Возьмите лист бумаги и иллюстрируйте каждый оператор вашей программы, это поможет вам отчетливо понять структуру алгоритма.