I: integer;

р: mark

End;

Очевидно, что ссылочная переменная, указывающая на данные такого типа, должна иметь тот же тип mark:

Туре

mark = ^dyn;

В ситуации, когда для описания типа mark привлекается понятие dyn, а при описании типа dyn используется mark, условились сначала описывать тип ссылочной переменной, а затем уже тип компонента:

Туре

mark = ^dyn;

dyn = record

I: integer;

P: mark;

End;

В дополнение к описанным ссылочным типам в Турбо Паскале имеется особый стандартный ссылочный тип, который позволяет не конкретизировать свой базовый тип. Этот тип обозначается идентификатором pointer и считается совместимым со всеми ссылочными типами. Описание ссылочной переменной будет иметь вид Var PR: pointer;. Значения типа pointer называют нетипизированными указателями. Для работы с нетипизированными указателями используется ряд специальных функций.

Функция Addr(X) возвращает результат типа pointer, в котором содержится адрес аргумента. Здесь X - любой объект программы (имя любой переменной, процедуры, функции). Возвращаемый адрес совместим с указателем любого типа. Аналогичный результат возвращает операция взятия адреса @.

Процедура GetMem(P, Size) резервирует за нетипизированным указателем фрагмент динамической памяти требуемого размера. За одно обращение к процедуре можно зарезервировать не более 65 521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память нефрагментирован-на, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.

Процедура FreeMem(P, Size) возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. Здесь Р - нетипизированный указатель, Size - длина в байтах освобождаемого фрагмента. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения.

С помощью ссылочных переменных можно организовать различные структуры динамических данных, классификация которых представлена на рис. 11.1.

Рис. 11.1. Классификация динамических структур данных

Определим основные компоненты указанной классификации.

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

Кольцевые списки - структура, аналогичная линейным спискам, но имеющая дополнительную связь между последним и первым элементом списка.

Очередь - частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.

Стек - частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.

Деревья ~ это динамические данные иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами).

Пирамидой (упорядоченным списком) называется дерево, в котором значения вершин (узлов) всегда возрастают или убывают при переходе на следующий уровень.

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

Каждый элемент списка представляет собой запись из нескольких полей: полей данных (Data) и поля ссылки (Link). Поле ссылки предназначено для организации связанного списка таких объектов и предполагает, что очередной объект списка посредством данного указателя связывается с последующим объектом. Поле ссылки последнего объекта содержит пустой указатель nil. Указатель на первый объект и на весь список содержится в некоторой переменной List. Описание списка с полем данных целого типа может быть следующим:

Туре

TDat = integer;

TLink = ^Element; Element = record

Data: TDat;

Link: Tlink

End;

Var

List: Tlink;

Создание очередного объекта определенного типа Element выполняется процедурой New(List).

После того как очередной динамический объект создан, следует поместить его в список. Динамический объект может быть помещен в начало, конец, между любыми соседними элементами созданного списка, аналогично удален из списка, над ним могут производиться действия в соответствии с заданным алгоритмом.