22. Ссылки (POINTER)

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

Данные могут быть организованы и другим образом. Их можно хранить в некоторой области памяти, не обозначая именем переменной, а используя ссылку на эту область. Аналогично тому, как иногда "обозначают" зрителя: "человек с 5-го ряда, 3-го места". Как мы увидим ниже, такой вид доступа позволяет динамически захватывать и освобождать память в процессе работы блока программы. Поэтому и сами переменные, которые могут создаваться и ликвидироваться по мере надобности, называют динамическими.

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

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

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

Чтобы проиллюстрировать преимущества динамических переменных, продолжим аналогию с очередью пациентов.

Пусть один из пациентов покидает очередь. Этот процесс не требует перемещения в пространстве остальных пациентов: просто стоящий за ушедшим теперь запоминает другого человека. То есть исключение элемента'из цепочки данных сводится к изменению одной единственной ссылки и не требует перемещения остальных элементов, как это имело бы место для массива. На рис. 5 показывается исключение элемента цепочки.

Рис. 5

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

С помощью ссылок легко вставить новую компоненту в цепочку данных. Для этого достаточно изменить две ссылки (см. рис. 6).

Рис. 6

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

Обращение к динамической переменной происходит посредством ссылочной переменной, которая содержит адрес соответствующей динамической переменной.

Под ссылочную переменную транслятор отводит место в памяти машины; эта переменная имеет имя и явно упоминается в программе. Ссылочные переменные образуют новый тип данных - "ссылки" (указатели).

Динамические переменные, как правило, имеют тип "запись" (RECORD), так как должны содержать, помимо значения (целого, вещественного и т. п.), ссылку на другую динамическую переменную связанной структуры.

Пример. Пусть в памяти машины имеется динамическая переменная, содержащая поле целого значения 2 и поле ссылки (указатель) на другую компоненту связанной структуры (цепочки): Адрес данной переменной (ссылка) содержится в ссылочной переменной R. ссылочной переменной через POINT, а тип динамической переменной через СТ. Тогда этот факт описывается следующим образом:

Говорят, что "тип POINT указывает (ссылается) на компоненты типа СТ" или "тип POINT связан с типом СТ".

Ссылочную переменную R можно описать двумя способами:

Переменная R указывает на компоненты типа СТ.

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

Например, компоненты, содержащие числа 5,10,15,8, должны иметь еще информацию о том, где находится предыдущий элемент, так как это не массив и компоненты размещаются необязательно подряд.

Опишем тип таких данных, обозначив его СТ. Очевидно, этот тип есть "запись" с двумя полями: полем целого значения (I) и полем ссылки (Р)

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

Опишем этот тип:

Как мы видим, возник порочный круг: для описания типа POINT привлекается понятие СТ, а при описании типа СТ необходимо использовать POINT.

Условились в этом случае сначала описывать тип ссылочной переменной, а затем уже тип компоненты:

Правила языка паскаль только при описании ссылок допускают использование идентификатора (СТ) до его описания; во всех остальных случаях, прежде чем упомянуть идентификатор, необходимо описать его тип. Рассмотрим схему образования цепочки динамических данных, содержащих числа 5,10.

Машине необходимо произвести следующие действия:

1. Найти и зарезервировать место в памяти для компоненты:

2. Заслать ссылку на эту компоненту (адрес) в ссылочную переменную

3. Присвоить полю I значение

4. Присвоить некоторой ссылочной переменной Q значение R (скопировать):

5. Найти и зарезервировать место в памяти для новой компоненты:

6. Заслать в

7. Заслать в поле I значение 10:

8. Заслать в поле Р значение Q:

Последовательность подобных действий создает цепочку динамических переменных.