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

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

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

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

Каждый элемент бинарного дерева содержит поле данных и 3 (или 2) адресных поля. Рассмотрим теперь реализацию динамических структур в Паскаль-программе. Поскольку элементы будут размещаться в динамической памяти, переменные такого типа в программе не нужны, а нужны лишь указатели на них, следовательно, достаточно описать тип элемента в операторе Type. В качестве типа элемента можно, очевидно, использовать только запись. Опишем сначала элемент односвязного списка: