Динамические переменные

Динамические переменные отличаются тем, что они создаются по команде, а не в момент их описания. Это позволяет динамически управлять использованием памяти.

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

Type

< имя ссылочного типа> =^< имя типа>;

или в разделе переменных указать:

Var

< имя ссылочного типа> =^< имя типа>;

в качестве < имени типа> можно указывать любой тип, переменные которого располагаются в памяти. Например:

Type TMas=array[1..20] of Integer;

PMas=^TMas;

PString=^String;

Var A, B: PMas;

S, S2: PString;

X: ^Real;

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

New(< ссылочная переменная>);

где < ссылочная переменная> - переменная ссылочного типа. Создаваемый объект занимает в памяти столько байт, сколько заняла бы переменная базового типа для ссылочного типа. Например, по команде

New(A);

в памяти образуется массив из 20 элементов типа Integer (смотреть предыдущий пример), а его местоположение в памяти помещается в ссылочную переменную A:

Аналогичным образом, по команде:

New(X);

в памяти образуется переменная типа Real, а её адрес помещается в переменную X:

Адрес объекта может быть помещён в другую переменную того же ссылочного типа с помощью оператора присвоения, например, после операторов

Var A, B: PMas;

Begin

New(A);

B: =A;

в памяти будет создан массив из двадцати элементов, а затем адрес его местоположения в памяти копируется из переменной A в переменную B:

Обращение к объекту, расположенному в памяти, осуществляется через любую ссылочную переменную, содержащую адрес этого объекта. Например, к переменной типа Real, чей адрес хранится в ссылочной переменной X, можно обратиться, указав в вычисляемом выражении X^. Занести в эту переменную число 3 можно с помощью оператора

X ^: =3;

Занести число 5 в 3-й элемент массива, чей адрес хранится в переменной A, можно оператором

A^[3]: =5;

Удаление объекта из памяти осуществляется процедурой

Dispose(< ссылочная переменная>);

Например, удалить после использования одномерный массив, адрес которого находится в переменной A, можно с помощью оператора

Dispose(A);

При невнимательной работе с динамическими переменными можно допустить ошибки:

Ошибка 1

Var A, B: ^Real;

Begin

New(A);

A^: =3;

B: =A;

Dispose(A);

Writeln(B^);

В приведённом фрагменте программы первым оператором создаётся в памяти динамическая переменная, и её адрес помещается в переменную A. Вторым оператором - в динамическую переменную заносится число 3(см. рис. 1а). Адрес расположения

Рис. 1

этой динамической переменной третьим оператором копируется в ссылочную переменную B (см. рис. 1б). Четвёртым оператором динамическая переменная из памяти уничтожается (см. рис. 1в). Сбой вызовет пятый оператор, в котором осуществляется обращение к динамической переменной.

Ошибка 2

Var A, B: ^Real;

Begin

New(A);

New(B);

A^: =3;

B^: =5;

A: =B;

В этом фрагменте программы первыми четырьмя операторами создаются две динамические переменные типа Real, их адреса заносятся в переменные A и B соответственно, а затем первая динамическая переменная получает значение 3, а вторая- значение 5 (см. рис. 2а).

Рис. 2

Пятым оператором адрес второй динамической переменной копируется из ссылочной переменной B в A. Таким образом, доступ к первой динамической переменной потерян, и далее в программе к ней нельзя будет обратиться или удалить, поскольку её адреса нет ни в одной ссылочной переменной (см. рис. 2б). Эта динамическая переменная будет удалена по окончании выполнения программы.

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

Var A: ^Real;

Begin

A: =nil;

… … …

If A=Nil then Begin

New(A);

… … …

end;

… … … … … …

If not (A=nil) then Dispose(A);

Списки

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

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

Для решения этой задачи создадим свой тип:

Type

PEl=^TEl;

TEl=Record

Inf: Integer;

Pr: PEl;

End;

Опишем необходимые переменные:

Var A, B: PEl;

K: Integer;

Следующие операторы позволят создать список (слева строки пронумерованы):

{1} A: =nil;

{2} Readln(K);

{3} If not(K=0) then

{4} Begin

{5} New(A);

{6} A^.Inf: =K;

{7} B: =A;

{8} Readln(K);

{9} While not(K=0) do

{10} Begin

{11} New(B^.Pr);

{12} B: =B^.Pr;

{13} B^.Inf: =K;

{14} Readln(K);

{15} end;

{16} B^.Pr: =nil;

{17}end;

В первой строке в переменную A заносится значение nil, а затем второй строкой считывается первое вводимое число. В третьей строке проверяется, является ли число в переменой K нулём. Если K не равно нулю, то пятой строкой создаётся динамическая переменная типа TEl и её адрес заносится в переменную A. В строке шесть заполняется поле Inf динамической переменной (см. рис. 3а), а затем, в строке семь, адрес динамического объекта копируется из переменной A в переменную B. (см. рис. 3б).

Далее, для обработки всех остальных чисел организуется цикл с предусловием (строки 9-15), проверяющий перед созданием очередного элемента списка, чтобы очередное число не было нулём. Для запуска этого цикла считывается очередное число оператором Readln(K) (строка 8). Если очередное введённое число не нуль, то в этом случае:

создаётся новый динамический объект типа TEl, и его адрес заносится в поле предыдущего динамического элемента (строка 11, рис. 3в);

адрес нового элемента помещается в переменную B (строка 12), а затем заполняется поле Inf этого элемента (строка 13, рис. 3г);

запрашивается очередное число, и в случае, если оно равно нулю, цикл останавливается.

Таким образом, после остановки цикла адрес последнего объекта будет храниться в переменной B (рис. 4а).

Рис. 4

Оператором B^.Pr: =nil; (строка 16) заполняется поле Pr последнего элемента (рис. 4б). Список сформирован.

Следует отметить, что если первое число равно нулю, то список не будет создан и в переменной A останется значение nil. Если же второе число равно нулю, то будет создан один элемент списка; цикл, расположенный в строках 9-15, не начнётся, и оператором в строке 16 поле Pr этого элемента заполнится значением nil.

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

Далее приведём фрагмент программы, выводящей элементы списка на экран в том порядке, в каком они были введены.

{1} B: =A;

{2} While not (B=nil) do

{3} Begin

{4} Write(B^.Inf);

{5} B: =B^.Pr;

{6} end;

Поскольку адрес первого элемента списка хранится в переменной A и значение этой переменной менять не следует, используем переменную B. Первой строкой в B помещается адрес первого элемента списка. Если список не создан, то есть A=nil, следовательно, и в B занесётся nil, значит цикл, расположенный в строках 2-6, не начнётся. В противном случае на экран выведется значение поля Inf первого элемента списка (строка 4), а затем в B заносится адрес следующего элемента. Если такового нет, то в B попадёт nil и цикл остановится, иначе операторы внутри цикла (строки 4-5) повторятся ещё раз.

По окончании список необходимо из памяти удалить. Это можно сделать следующим образом:

{1} While not (A=nil) do

{2} Begin

{3} B: =A;

{4} A: =A^.Pr;

{5} Dispose(B);

{6} end;

Удаление списка будет происходить поэлементно. При очередном повторении операторов цикла адрес первого элемента помещается в B (строка 4, рис. 5а), затем в A помещается адрес следующего элемента (или, если такового нет) (строка 4, рис. 5б) и удаляется первый элемент (строка 6, рис. 5в).

Рис. 5

Заметим, что цикл не начнётся, если список не был создан, то есть A=nil.

При работе со списками зачастую приходится вставлять элемент в список или, наоборот, удалять элемент из списка. Ниже приведём фрагмент программы, осуществляющий вставку элемента в список N-ным по порядку(N> 0), если число N превышает количество элементов списка, то новый элемент добавляется в конец списка. Для описания этого фрагмента потребуется ещё одна переменная C типа PEl.

{1} Readln(I);

{2} If N=1 then

{3} Begin

{4} New(C);

{5} C^.Inf: =I;

{6} C^.Pr: =A;

{7} A: =C;

{8} end

{9} else

{10} Begin

{11} B: =A;

{12} While not(B^.Pr=nil) and (N> 2) do

{13} B: =B^.Pr;

{14} New(C);

{15} C^.Inf: =I;

{16} C^.Pr: =B^.Pr;

{17} B^.Pr: =C;

{18} end;

Первой строкой в этом фрагменте запрашивается числовое значение для нового элемента. Если необходимо вставить первый элемент (это проверяется во второй строке), то после создания нового элемента в памяти (строка 4) и заполнения поля Inf (строка 5, рис. 6а), необходимо в поле Pr нового элемента

занести адрес первого элемента списка (строка 6, рис. 6б), а затем в ссылочную переменную A занести адрес нового элемента (строка 7, рис. 6в).

В противном случае в переменную B необходимо занести адрес элемента, после которого необходимо вставить элемент (на рис. 7а приведён пример для N=3). Это достигается фрагментом, расположенным в строках 11-13. Следует отметить, что

Рис. 7

если число N превышает количество элементов, то цикл остановится по окончании списка, то есть в B занесётся адрес последнего элемента. В строках 14 и 15 создаётся новый элемент списка и заполняется информированное поле (рис. 7б). Следующим оператором (строка 16) адрес элемента с номером N заносится в поле Pr нового элемента (рис. 7в). Последняя команда – адрес нового элемента заносится в поле Pr элемента с номером N-1 (строка 17, рис. 7г).

Алгоритм удаления из списка элемента с номером N, N> 0, также разбивается на две части: N=1 и N> 1.

{1} If N=1 then

{2} Begin

{3} C: =A;

{4} A: =A^.Pr;

{5} Dispose(A);

{6} end

{7} else

{8} Begin

{9} B: =A;

{10} While not(B^.Pr=nil) and (N> 2) do

{11} B: =B^.Pr;

{12} If not(B^.Pr=nil) then

{13} Begin

{14} C: =B^.Pr;

{15} B^.Pr: =C^.Pr;

{16} Dispose(C);

{17} end;

{18} end;

Если N=1 (строка 1), то в C заносится адрес первого элемента (строка 3), затем в A заносится адрес второго элемента (строка 4, рис. 8а) и удаляется первый элемент (строка 5, рис. 8б).

Рис.8

Если же N> 1, то перед удалением, как и при вставке элемента, в переменную B необходимо занести адрес элемента с номером N-1 (строки 9-11). Если число N больше, чем количество элементов в списке (оператор в строке 12), то операция удаления не будет выполнена. В противном случае в переменную C заносится адрес удаляемого элемента (строка 14, рис. 9а) в поле Pr элемента N-1 заносится адрес элемента N+1 (строка 15, рис. 9б), а затем удаляется элемент N (строка 16, рис. 9в).

Рис. 9

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