2.4. Динамические структуры данных

Объект данных обладает динамической структурой, если его размер изменяется в процессе выполнения программы или он потенциально бесконечен. Описанные выше механизмы определения типов позволяют создавать динамические структуры данных. Очевидно, большинство объектов простых типов имеют статическую структуру. Единственным исключением здесь являются типы integer и real с неограниченными диапазонами значений. Все до сих пор приводимые примеры данных структурных типов (кроме объединений) имеют статическую структуру. Однако структурные типы позволяют и легко описывать динамические структуры данных. Например, описание

type СПИСОК is гесогd

ПЕРВЫИ: ЭЛЕМЕНТ;

ПРОДОЛЖЕНИЕ: СПИСОК;

епd гесогd;

вводит тип данных СПИСОК, который представляет собой список из бесконечного числа элементов типа ЭЛЕМЕНТ.

Семантика этого описания соответствует интуитивному пониманию списка как объекта, состоящего из некоторого первого элемента и продолжения списка, являющегося тоже списком (рис. 2. 1). Такие описания типов называются ре курсивными.

Эл1 Эл2 ЭлЗ Эл4 .......

|---------------------------------|

Первый 

элемент Продолжение продолжения

продолжения

|---------------------------------------------------|



Первый

элемент Продолжение списка

списка

|----------------------------------------------------------|



Список

рис.2.1

Именно рекурсивные описания позволяют вводить динамические структуры данных. Рекурсивные описания широко используются в программировании: они отражают один из фундаментальных способов образования понятий человеком.

Рекурсивные описания определяют новый тип через нем самого, могут использовать и прямую рекурсию (как при описании типа СПИСОК, где этот тип определяется не посредственно через самого себя), и косвенную, когда

новый тип определяется через другие типы, которые, в свою очередь, определяются через этот новый тип. Очевидно, что объекты данных введенного нами типа СПИСОК содержат бесконечное число компонент типа ЭЛЕМЕНТ. Однако реально в программе можно обработать лишь конечное число этих компонент. Следовательно, и хранить в памяти ЭВМ следует только эти обрабатываемые компоненты: сначала список вообще не занимает места в памяти; как только в программе потребуется впервые обработать некоторую компоненту списка, автоматически выделяется область памяти под нее. Этот метод позволяет обрабатывать потенциально бесконечные объекты.

Некоторые способы обработки списков рассмотрены в следующих примерах.

П р и м е р 2. 17. Реализация линейного списка с использованием прямой рекурсии:

type ЭЛЕМЕНТ is integer;

type СПИСОК is record

ПЕРВЫИ: ЭЛЕМЕНТ;

ПРОДОЛЖЕНИЕ: СПИСОК;

еnd record;

ЧИСЛА: СПИСОК;

ДАННЫИ: ЭЛЕМЕНТ;

КОЛИЧЕСТВО: natural;

Пусть требуется добавлять, удалять и искать ДАННЫИ элемент в списке ЧИСЛА. Переменная КОЛИЧЕСТВО содержит количество элементов в списке, в начале она равна О.

Запишем сначала программу добавления элемента, считая, что элементы в списке хранятся в порядке возрастания:

function

ДОБ (СТАРЫИ: СПИСОК; ДЛИНА: natural;

ЭЛ: ЭЛЕМЕНТ) retuгn(НОВЫИ: СПИСОК) is

begin

if (ДЛИН А=О) then -- список был пуст

НОВЫИ. ПЕРВЫИ:=ЭЛ;

еlsif (СТАРЫИ. ПЕРВЫЙ>ЭЛ) then -- новый элемент

НОВЫИ:=СПИСОК(ЭЛ, СТАРЫИ); -- стал первым

еlse -- новый элемент добавляется к продолжению

НОВЫИ:=СПИСОК(СТАРЫИ. ПЕРВЫИ,

ДОБ(СТАРЫИ. ПРОДОЛЖЕНИЕ, ДЛИНА-1, ЭЛ));

еnd if;

еnd funсtion;

Тогда для добавления элемента ДАННЫИ необходимо записать

ЧИСЛА:=ДОБ(ЧИСЛА, КОЛИЧЕСТВО, ДАННЫИ);

КОЛИЧЕСТВО:=КОЛИЧЕСТВО+1;

Программа удаления элемента:

funtion

УД (СТАРЫИ: СПИСОК; ДЛИНА: natural;

ЭЛ: ЭЛЕМЕНТ) геturn(НОВЫИ: СПИСОК) is

begin

if (ДЛИНА=О) then -- список не изменится,

НОВЫИ:=СТАРЫИ; -- так как он пуст

elsif (СТАРЫИ. ПЕРВЫИ=ЭЛ) then -- первый = ЭЛ

НОВЫИ:=СТАРЫИ. ПРОДОЛЖЕНИЕ; -- удаляем его

else -- удаляем элемент из продолжения списка

НОВЫИ:=СПИСОК(СТАРЫИ. ПЕРВЫИ,

УД(СТАРЫИ. ПРОДОЛЖЕНИЕ, ДЛИНА-1, ЭЛ));

еnd if;

еnd funcion;

Тогда для удаления элемента ДАННЫЙ необходимо записать

if ЕСТЬ(ЧИСЛА, КОЛИЧЕСТВО, ДАННЫИ) then

ЧИСЛА:=УД(ЧИСЛА, КОЛИЧЕСТВО, ДАННЫИ);

КОЛИЧЕСТВО:=КОЛИЧЕСТВО-1;

end if;

Программа поиска:

funcion ЕСТЬ (СТАРЫИ: СПИСОК; ДЛИНА: natural;

ЭЛ: ЭЛЕМЕНТ) геturn(НАЛИЧИЕ: Ьооlеаn) is

Ьеgin

if (ДЛИНА=О) then -- список пуст

НАЛИЧИЕ:=false;

elsif (СТАРЫИ. ПЕРВЫИ=ЭЛ) then -- ЭЛ уже есть

НАЛИЧИЕ:=true;

else -- элемент ЭЛ может быть лишь в продолжении

НАЛИЧИЕ:=ЕСТЬ(СТАРЫИ. ПРОДОЛЖЕНИЕ,

ДЛИНА-1, ЭЛ);

end if;

end function;

Тогда для поиска элемента ДАННЫИ необходимо записать

ПРИЗНАК: Ьооlеаn;

.......

ПРИЗНАК:=ЕСТЬ(ЧИСЛА, КОЛИЧЕСТВО, ДАННЫИ);

Все приведенные функции вызывают сами себя. Такие функции называются рекурсивными. Использование здесь рекурсивных функций не случай~ю: о~ю отражает рекурсивный характер обрабатываемых объектов данных типа СПИСОК. Вообще, рекурсивно определяемые типы данных наиболее естественно обрабатывать рекурсивными программами.

Описанная реализация списка и действий с ним неудобна потому, что приходится использовать дополнительную переменную КОЛИЧЕСТВО и, кроме том, список может содержать одинаковые элементы, что не всегда целесообразно.

П р и м е р 2. 18. Реализация линейного списка с

использованием косвенной рекурсии:

type СПИСОК is union

НЕПУСТОИ_СПИСОК;

(null);

end union;

type НЕПУСТОИ_СПИСОК is

record

ПЕРВЫИ: ЭЛЕМЕНТ;

ПРОДОЛЖЕНИЕ: СПИСОК;

end record;

Здесь тип СПИСОК представляет собой либо НЕПУСТОИ_СПИСОК, либо анонимный перечислимый тип с единственным значением, которое далее будет обозначать пустой список. Таким образом, можно считать, что переменные типа СПИСОК состоят из конечного числа элементов, причем конец списка идентифицируется значением NULL. В приведенном описании используется косвенная рекурсия: список определяется как непустой или пустой список, а непустой список состоит из некоторого элемента и списка-продолжения.

В этом случае программы для добавления, удаления и поиска элемента имеют вид

function ДОБ (СТАРЫИ: СПИСОК; ЭЛ: ЭЛЕМЕНТ)

return(НОВЫИ: СПИСОК) is

begin

if (СТАРЫИ=NULL) оr (СТАРЫИ. ПЕРВЫИ>ЭЛ) then

НОВЫИ:=НЕПУСТОИ_СПИСОК(ЭЛ, СТАРЫИ);

elsif (СТАРЫИ. ПЕРВЫИ=ЭЛ) then

НОВЫИ:=СТАРЫИ;

else

НОВЫИ:=НЕПУСТОИ_СПИСОК(СТАРЫИ. ПЕРВЫИ,

ДОБ(СТАРЫИ. ПРОДОЛЖЕНИЕ, ЭЛ));

end if;

end function;

function УД(СТАРЫИ: СПИСОК; ЭЛ: ЭЛЕМЕНТ)

return(НОВЫИ: СПИСОК) is

begin

if (СТАРЫИ=NULL) оr (СТАРЫИ. ПЕРВЫИ>ЭЛ) then

НОВЫИ:=СТАРЫИ;

elsif (СТАРЫИ. ПЕРВЫИ=ЭЛ) then

НОВЫИ:=СТАРЫИ. ПРОДОЛЖЕНИЕ;

else

НОВЫИ:=НЕПУСТОИ_СПИСОК(СТАРЫИ. ПЕРВЫИ,

УД(СТАРЫИ. ПРОДОЛЖЕНИЕ, ЭЛ));

end if;

end function;

function ЕСТЬ(СТАРЫИ: СПИСОК; ЭЛ: ЭЛЕМЕНТ)

return(НАЛИЧИЕ: Ьооlеаn) is

begin

if (СТАРЫИ=NULL) оr (СТАРЫИ. ПЕРВЫИ>ЭЛ) then

НАЛИЧИЕ:= false;

elsif (СТАРЫИ. ПЕРВЫИ=ЭЛ) then

НАЛИЧИЕ:= true;

else

НАЛИЧИЕ:= ЕСТЬ(СТАРЫИ. ПРОДОЛЖЕНИЕ, ЭЛ);

end if;

end function;

Тогда для добавления, удаления и поиска элемента ДАННЫИ

необходимо записать

ЧИСЛА:=ДОБАВИТЬ(ЧИСЛА, ДАННЫИ);

ЧИСЛА:=УДАЛИТЬ(ЧИСЛА, ДАННЫИ);

ПРИЗНАК:=ЕСТЬ(ЧИСЛА, ДАПНЫИ);

В начале значения ЧИСЛА есть NULL.

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