Действия над ссылками

Var

p1,p3:^Integer;

р2:^Real;

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

New(p1); New(p2)

В Паскале можно передавать значения только между указателями, связанными с одним и тем же типом данных. Например:

р 1:= p 3.

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

p 1^:=3; p 2^:=3.14;

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

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

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

dispose (p1);

dispose (p2);

В результате выполнения оператора процедуры вида dispose (p) динамический объект, на который указывает ссылочная переменная р, прекращает свое существование, занимаемое им место в памяти считается свободным, а значение переменной р становится неопределенным. Т.е. уничтожается только сам динамический объект, но не указатель на него.

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

Const

p:^Real=NIL;

Begin

…………

if p = NIL then

new(p);

…………

dispose(p);

p:=NIL;

End.

Никакие другие операции сравнения над указателями не разрешены.

Начальное значение указателя может быть произвольным.

Итак, значением ссылочного типа является ссылка на объект определенного типа:

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

Связь указателя с объектом схематически можно изобразить так

p

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

После введения в употребление ссылочной переменной в разделе описаний, она не ссылается ни на какой программный объект и даже не имеет в качестве своего значения пустой ссылки Nil. Таким образом, описание

var v: ^T

лишь вводит в употребление статическую переменную v ссылочного типа (по этому описанию транслятор только отводит место в памяти, необходимое для размещения ссылки), но не вводит в употребление никакого программного объекта типа Т, на который будет указывать значение этой ссылочной переменной v. Это описание говорит лишь о том, что значениями переменной v могут быть ссылки на такие объекты. Для порождения же самого динамического объекта служит стандартная процедура с именем NEW (новый), обращение к которой производится с помощью оператора процедуры. В этом операторе процедуры задается один фактический параметр — ссылочная переменная, сопоставленная порождаемому динамическому объекту, например NEW (p). В результате выполнения оператора процедуры такого вида порождается новый объект типа, указанного в описании той ссылочной переменной, которая задана в качестве фактического параметра, и в качестве значения этой ссылочной переменной присваивается ссылка на этот вновь порожденный объект, при этом порожденному динамическому объекту не присваивается какого-либо значения, так что для динамического объекта процедура NEW играет ту же роль, что и описание для статического объекта.

Действия над ссылками

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

Присваивание. Для присваивания значения ссылочной переменной v, как обычно, используется оператор присваивания

v: = e

где е – ссылочное выражение, которое задает ссылочное значение того же типа, что и переменная v.

При этом в качестве ссылочного выражения может использоваться:

– пустая ссылка nil;

– ссылочная переменная;

– ссылочная функция (т.е. функция, значением которой является ссылка).

Пусть в программе имеется описание ссылочных переменных:

р,d: ^integer

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

p ^:=3; d ^:=58; р: = d; d: = nil;

Для наглядности получаемые при этом результаты представим в виде схем на рис. 1

Рис. 1.

Обратите внимание, что в данном примере после выполнения оператора присваивания р: = d на динамический объект со значением 3 не указывает ни одна ссылка, т.е. он стал недоступным для программы. С другой стороны, в результате выполнения этого же оператора присваивания не образуется какой-либо новый динамический объект со значением 58, а переменная р будет ссылаться на тот же уже существующий динамический объект, на который ссылается и переменная d.

Рассмотрим возможные комбинации операторов присваивания, в которых участвуют ссылочные переменные р и d, определенные выше, и соответствующие переменные с указателем p ^ и d^, а самое главное, проследим, как изменяются соответствующие ссылки и значения динамических объектов. Пусть аналогично предыдущему примеру выполняются операторы p ^:=3; d ^:=58. В результате будем иметь:

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

Если же вместо оператора p:= d выполнить оператор p ^:= q ^, то получим следующие результаты:

Примеры неправильного использования ссылочных переменных и переменных с указателем в операторах присваивания (учитывая ранее приведенные описания):

p:= d ^ (в левой части оператора присваивания фигурирует переменная ссылочного типа, а в правой части – переменная с указателем типа integer)

p ^:=’a’ (в левой части – переменная с указателем типа integer, а в правой части – символьная константа ‘a’)

p ^:= nil (в левой части – переменная с указателем типа integer, а в правой части – значение ссылочного типа)

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

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

Уничтожение динамических объектов.

Если обратить внимание на рис. 1, то станет понятной ситуация, когда от созданных динамических объектов хотелось бы избавиться. На этом рисунке изображена ситуация, когда в результате выполнения операторов присваивания на динамический объект типа integer с значением 3не указывает ни одна ссылочная переменная. А это означает, что этот объект (и его значение) стал недоступен программе, хотя он и продолжает занимать отведенное для него место в памяти. Если в процессе выполнения программы некоторый динамический объект, созданный в результате выполнения оператора процедуры new, становится ненужным, то его можно уничтожить (отказаться от выделенного для него места в памяти) с помощью стандартной процедуры с именем dispose. В результате выполнения оператора процедуры вида dispose(p) динамический объект, на который указывает ссылочная переменная р, прекращает свое существование, занимаемое им место в памяти считается свободным, а значение переменной р становится неопределенным. Внимание! Процедурой dispose уничтожается только сам динамический объект, но не указатель на него.

Если вспомнить ситуацию, изображенную на рис. 1, то соответствующую ей последовательность операторов следовало бы модифицировать следующим образом (учитывая и процедуру new – создания динамических объектов):

var

p, d: ^ integers;

…………

new (p); new (d);

p ^:=3; d ^:=58;

dispose (р);

р: = d;

d:= nil;

Результаты выполнения отдельных этапов этого фрагмента изображены ниже.

Ошибка:

var

р,d: ^integer;

………………

new(р); р^:=3;

d:=р; dispose(p);

………………

После выполнения оператора присваивания d:=р обе ссылочные переменные указывают на один и тот же динамический объект с значением 3. В результате выполнения оператора dispose(p) динамический объект, на который указывает переменная р, будет уничтожен. Но к этому времени и указатель d ссылается на этот же динамический объект, так что получается конфликтная ситуация: после выполнения dispose(p) пользоваться значением динамического объекта, на который указывает переменная d нельзя, поскольку этого объекта уже нет.

Списки

Рассмотрим определения типов

type d = ^t;

t = record

……..

с: d;

……..

end;

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

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

Будем употреблять слова «ссылка на элемент списка» вместо слов «ссылка на место в памяти, отведенное для элемента списка». Каждый элемент списка, кроме последнего, содержит ссылку на следующий за ним элемент. Признаком того, что данный элемент является последним в списке, служит то, что поле типа d этого элемента равно nil. На каждый элемент списка, кроме первого, имеется ссылка только от одного элемента – предшествующего. Вместе с каждым списком рассматривается переменная, значением которой является ссылка на первый элемент списка. Если список не имеет ни одного элемента (такой список называется пустым), значение этой переменной должно равняться nil.

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

type ссылка = ^элем;

элем = record

инф: integer;

след: ссылка

end;

и.описание var p, q: ссылка. Построим список из трех элементов, содержащих числа 5, 12 и -8. Значением переменной р в процессе построения всегда будет ссылка на первый элемент уже построенной части списка. Переменная q будет использоваться для выделения с помощью new места в памяти под размещение новых элементов списка. Выполнение оператора р:= nil приводит к созданию пустого списка. После выполнения операторов

new (q); q^. инф:= - 8; q^. след:=p; p:=q

имеем список, состоящий из одного элемента, содержащего число -8 в информационной части. Ссылка на этот элемент является значением переменных р и q (cм. рис. 2, а). Выполнение операторов

new(q); q^.инф:= 12; q^.след:=р; p:=q

приводит к тому, что в начало этого списка добавляется новый элемент, содержащий число 12; значением переменных р и q является ссылка на первый элемент списка (см. рис. 2, б). После выполнения операторов

new(q); q^.инф:=5; q^.след:=p; p:=q

добавляющих в начало списка элемент, содержащий число 5, построение списка завершается (см. рис. 2, в). Значением переменных р и q является ссылка на первый

Рис. 2

элемент списка. Значение nil поля след элемента, содержащего число -8, является признаком того, что этот элемент – последний в списке. Значением переменной р^.след^.инф является целое число 12; значением р^.след^.след – ссылка на третий элемент списка.

Рассмотренный способ построения списка заключается в создании пустого списка и в повторяющемся выполнении ряда однотипных шагов, добавляющих в начало построенного списка новые элементы. Это означает, что в общем случае для построения списка можно использовать оператор цикла. Пусть, кроме переменных р и q типа ссылка, описаны переменные i и n типа integer и требуется построить список, элементы которого содержат квадраты чисел 1, 2,..., n. Для этого нужно выполнить последовательность операторов

p:=nil;

for i:= n downto 1 do

begin

new (q); q^.инф:=sqr(i);

q^.след:=p; p:=q

end

Отметим, что при n < 1 тело цикла не выполняется ни разу. Получающийся в этом случае результат (p = nil) является тем не менее вполне осмысленным – построен пустой список.

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

q:=p;

while q <> nil do

begin

write (q^.инф);

q:= q^.cлeд

end

По ходу выполнения цикла значением переменной q является поочередно ссылка на первый, второй, третий и т. д. элементы списка и, наконец, nil. Если список был пустым (было выполнено отношение p = nil), то тело цикла не выполнится ни разу и не будет выведено ни одного числа.

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

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

Замечание. В построенном списке числа последовательности следуют в обратном порядке.

Задание 2. Задана последовательность целых чисел, содержащая по крайней мере два отрицательных числа. Написать программу, в ходе выполнения которой выводятся числа этой последовательности, начиная с первого отрицательного и кончая последним отрицательным.

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

Дата добавления: 2015-07-12