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

   Структурированные типы данных,  такие, как массивы, множества, за-

писи, представляют   собой статические структуры,  так как их размеры

неизменны в течение всего времени выполнения программы.

   Часто требуется, чтобы структуры данных меняли свои размеры в ходе

решения задачи.   Такие структуры данных называются динамическими,  к

ним относятся стеки,  очереди, списки, деревья и другие. Описание ди-

намических структур  с помощью массивов,  записей и файлов приводит к

неэкономному использованию памяти ЭВМ и увеличивает время решения за-

дач.

   Каждая компонента любой динамической структуры представляет  собой

запись, содержащую   по крайней мере два поля:  одно поле типа указа-

тель, а  второе - для размещения данных.  В общем случае запись может

содержать не   один,  а несколько укзателей и несколько полей данных.

Поле данных может быть переменной,  массивом, множеством или записью.

   Для дальнейшего рассмотрения представим отдельную компоненту в ви-

де:

                               ЙННННН»

                               є  D  є

                               єНННННє

                               є  p  є

                               ИНННННј

где поле p - указатель;

    поле D - данные.

   Описание этой компоненты дадим следующим образом:

   type

    Pointer = ^Comp;

    Comp = record

            D:T;

            pNext:Pointer

         end;

здесь T - тип данных.

   Рассмотрим основные правила  работы  с  динамическими  структурами

данных типа стек, очередь и список, базируясь на приведенное описание

компоненты.