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

37.   Д И Н А М И Ч Е С К И Е    С Т Р У К Т У Р Ы

Д А Н Н Ы Х

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

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

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

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

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

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

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

Рекомендуемые материалы

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

дач.

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

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

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

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

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

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

де:

                               г=====¬

                               ¦  D  ¦

                               ¦=====¦

                               ¦  p  ¦

                               L=====-

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

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

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

   type

    Pointer = ^Comp;

    Comp = record

            D:T;

            pNext:Pointer

8. Емкостные датчики - лекция, которая пользуется популярностью у тех, кто читал эту лекцию.

         end;

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

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

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

компоненты.