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

End.

Begin

End.

Begin

End.

Begin

End. End.

Interface Interface

End. End.

Implementation Implementation

Interface Interface

End. End.

Interface Interface

End.

End.

Interface Interface

Взаимное использование модулей

Модули могут обращаться друг к другу косвенно или рекурсивно.

При косвенном использовании модулей один из них использует другой:

Unit A; Unit B;

Uses B; .....

Пусть в головной программе используется только модуль A:

Uses CRT, A;

В этом случае нет необходимости указывать и модуль B:

Uses CRT, A, B;

При рекурсивном использовании модулей они взаимно обращаются друг к другу:

Unit A; Unit B;

Uses B; Uses A;

....... .......

Если какой-нибудь из них подключить к программе:

Uses CRT, A;

то будет зафиксирована ошибка:

Error 68: Circular Unit Reference (A)

Взаимное использование возможно, если модули подключить из раздела реализации:

Unit A; Unit B;

....... .......

Uses B; Uses A;

....... .......

Особенности выполнения инициирующих разделов

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

Unit A; Unit B;

Const x = 1; Const x = 2; x - глобальная

Implementation Implementation переменная

подключены к программе:

Program Primer;

Uses WinCRT, A, B;

ClrScr;

WriteLn('x=', x);

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

x=2

Последним подключен модуль B, в котором глобальная x = 2.

Изменим порядок подключения:

Program Primer;

Uses WinCRT, B, A;

ClrScr;

WriteLn('x=', x);

В этом случае на экране появится:

x=1

так как в модуле A глобальная x = 1.

Если в программе необходим доступ ко всем переменным, в том числе и одноименным, из интерфейсов всех модулей, то указываются их составные имена, похожие на имена полей записей:

Program Primer;

Uses WinCRT, A, B;

ClrScr;

WriteLn('A.x=', A.x);

WriteLn('B.x=', B.x);

На экран будет выведено:

A.x=1

B.x=2

Ссылки и динамические переменные

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

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

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

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

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

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

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

Ссылки (указатели) можно описать в программе двумя способами.

При первом способе в разделе определения типов Type указывается имя типа ссылки, ставятся знаки = и ^ (карат), указывается тип переменных, к которому будет относиться эта ссылка:

Type TPntint = ^Integer;

TPntchar = ^Char;

TPntReal = ^Real;

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

Var a, b:TPntint;

x, y: TPntchar;

s, r: TPntReal;

При втором способе переменные ссылочного типа можно вводить обычным путем, с помощью их описания в разделе Var:

Var a, b:^Integer;

x, y: ^Char;

s, r: ^Real;

Переменные a, b, x, y, s, r будут хранить адреса ячеек памяти, где находятся значения одноименных динамических переменных. В порядке исключения такие переменные не описываются в разделе Var, а производятся в программе с помощью оператора New:

New(a);

New(b);

……

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

Таким образом, оператор New играет для динамической переменной ту же роль, что и описание для статической.

В Паскале для работы с динамическими переменными введено понятие переменной с указателем – это переменная ссылочного типа, за которой следует символ ^ : x^, y^, a^. Стрелка после имени переменной ссылочного типа говорит о том, что речь идет не о значении данной переменной (адресе ячейки памяти), а о значении одноименной динамической переменной, то есть переменной, на которую указывает эта переменная ссылочного типа.

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

New(a);

New(b);

WriteLn(a^, ‘ ‘, b^); на экран будет выведено содержание ячеек
памяти, адреса которых содержатся в

переменных a и b

WriteLn(a, ‘ ‘, b); ошибка! Нельзя выводить на экран адреса

ячеек памяти (Error 64)

a^ := 3;

b^ := 5;

WriteLn(a^, ‘ ‘, b^); на экран будет выведено: 3 5

a := b; переменная a содержит адрес той же ячейки, что и переменная b – они указывают на одну и ту же ячейку памяти

WriteLn(a^, ‘ ‘, b^); на экран будет выведено: 5 5

b := Nil; ссылка b никуда не указывает

WriteLn(a^, ‘ ‘, b^); ошибка! Значение b^ не определено!

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

ссылки динамические переменные

New(a);

Определены адреса a и b динамических переменных a^ и b^, но сами их значения пока не заданы, поэтому на экран будут выведены значения, оставшиеся в ячейках памяти с указанными адресами после решения предыдущей задачи.

a^ := 3;

a := b;

WriteLn(a^, ‘ ‘, b^);

Указателю a присвоено новое значение – значение адреса ячейки памяти, хранившееся в указателе b. Поэтому сейчас оба указателя хранят один и тот же адрес – адрес b. Они указывают на одну и ту же динамическую переменную b^. Адрес же динамической переменной a^ утерян, поэтому ее значение становится недоступным. Значит, на экран будут выведены два одинаковых числа, являющиеся текущими значениями переменных a^ и b^: 5 и 5.

b := Nil;

1. вместо описания самих динамических переменных в программе дается описание ссылок на них (статических переменных ссылочного типа), поставленных в соответствие одноименным динамическим переменным,

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

3. значение динамической переменной задается с помощью переменной с указателем,

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

Над значениями переменных ссылочного типа – адресами динамических переменных – в Паскале кроме операции присваивания определены две операции сравнения: = и <>.

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

Если в процессе выполнения программы динамический объект, созданный оператором, например New(a), становится ненужным, то его можно уничтожить оператором Dispose(a). При этом динамический объект, на который указывает ссылочная переменная a , уничтожается, занимаемое им место в памяти освобождается, а значение переменной a становится неопределенным. Оператор Dispose уничтожает только сам динамический объект, но не указатель на него:

New(a);