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

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

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

Глобальным переменным программы память отводиться в начале ее выполнения; эти переменные существуют в течение всего периода работы программы. Распределение памяти во всех этих случаях производиться полностью автоматически. Переменные, память под которые распределяется описанным способом, называются статическими. Под эту категорию попадают все переменные, описанные в Pascal - программе и обозначенные идентификаторами.

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

Необходимость в динамических структурах данных обычно возникает в следующих случаях:

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

2. В процессе работы программы нежен массив или список или иная структура, размер которой изменяется в пределах и трудно предсказуем.

3. Когда размер данных, обрабатываемых в программе, превышает 64К (сегмент данных).

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

Естественным средством доступа к статическим переменным являются идентификаторы этих переменных (так как статическая переменная всегда описана в некотором блоке).

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

На принципе обращения к динамическим переменным посредством указателей (ссылок) на них и основаны все соответствующие средства языка Pascal.

Указатели

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

В ТР можно объявить указатель и не связывать его при этом с каким-либо конкретным типом данных. Для этого служит стандартный тип POINTER:

Var

PP:pointer;

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

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

Адреса задаются сегментом и смещением.

Сегмент - участок памяти, имеющий длину 64К и начинающийся с физического адреса кратного 16 (0, 16, 32, 64…)

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

Фрагмент памяти в 16 байт называется параграфом.

Все ссылочные переменные имеют одинаковый размер, равный 4 байтам, и содержат адрес расположения в памяти конкретных значений переменных базового типа.

Для того, чтобы присвоить переменной ссылочного типа некоторое значение, необходимо воспользоваться унарной операцией взятия адреса объекта, которая обозначается знаком '@' (амперсант).

Например:

В ТР можно передавать значения только между указателями, связанными с одним и тем же типом данных. Это ограничение не распространяется на безтиповые указатели.

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

Например:

Для того, чтобы указатель "никуда не указывал", ему присваивается значение NIL:

P1:=NIL;

NIL - предопределенная константа типа Pointer, соответствующая адресу 0000:0000. Это значение можно присваивать любому указателю.

Над значениями ссылочных типов допускаются две операции сравнения на равенство '=' и неравенство '<>'.

Эти операции проверяют, ссылаются ли два указателя на одно и то же место в памяти.

If P3<>NIL then …

If P1=P2 then …

Типизированные константы - указатели

Единственным значением типизированной константы - указателя может быть только NIL, например:

Const

PR:^real=NIL;

Доступ к переменной по указателю

Для доступа к переменной (статической) имеются две возможности:

Одна - обращение к переменной по имени, то есть через идентификатор;

Вторая - воспользоваться адресом переменной, который содержится в указателе.

Например:

I:=I+2;

P1:=@I;

Для реализации второго, косвенного доступа к переменной через указатель на нее используется конструкция, называемая разыменованием.

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

Запись P1^ означает, "переменная, на которую ссылается P1".

Еще раз:

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

- А чтобы указать, что речь идет не об адресе, а о самих данных, за указателем ставится значок '^'.

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

I:=I+2; и P1^:=P1^+2; полностью эквивалентны.

Разыменование имеет тип, совпадающий с базовым типом переменной - указателя; то есть конструкция P1^ считается переменной целого типа.

Разыменование допускается для любых ссылочных типов.

В случае "указателя на указатель" возможно многократное разыменование.

Например:

Считается разыменование некорректным, если значение указателя равно NIL.

В этом случае нет переменной, на которую ссылается указатель.

Недопустимо:

P1:=NIL;

P1^:=2;