Лабораторная работа № 5 Указатели
До сих пор мы встречались с переменными, для каждой из которых отводилась неизменная на все время выполнения программы ячейка памяти. Такие переменные Н. Вирт назвал статическими. В целях более эффективного распоряжения памятью были разработаны динамические переменные и указатели (ссылки) Применение указателей и динамических переменных позволяет создавать гибкие вычислительные структуры и существенно расширяет объем используемой памяти.
Динамическая переменная не указывается явно в описаниях переменных и у нее нет имени. Для доступа к динамическим переменным предназначены переменные специального типа данных, называемые указателями (или ссылками).
Указатель – это переменная, значением которой является адрес динамической переменной. Имя указателя составляется по общим правилам идентификации, принятым в Delphi. Если указатель связывается с динамической переменной определенного типа, то он называется типизированным. Для описания типизированного указателя используется значок ^, который помещается перед соответствующим типом динамической переменной. Как правило, динамические переменные имеют тип запись, так как должны содержать, помимо значения (числового или текстового), указатели на другие динамические переменные связанной структуры. В операторной части программы динамические переменные обозначаются именем указателя с значком ^, помещенным после имени. Описание указателя обычно имеет следующую форму:
type <тип указателя>=^<тип динамической переменной>;
<тип динамической переменной>=record
<имя поля данных>:<тип данных>;
. . . . . . . . . . .
<имя поля указателя>:<тип указателя>:
. . . . . . . . . . .
end;
var <имя указателя>:<тип указателя>;
<имя указателя>:^<тип динамической переменной>;
Например:
type pn=^dp;
dp=record
i:integer;
p:pn
end;
var p1:^integer;
p2:^real;
p3:pn;
Приведенное описание предполагает использование указателя p1, содержащего адрес динамической переменной целого типа, указателя p2, указывающего на переменную действительного типа, и указателя p3, указывающего на переменную типа запись. В операторной части программы соответствующие переменные будут обозначены как p1^, p2^ и p3^.
В Delphi можно объявлять указатель и не связывать его при этом с каким-либо конкретным типом данных. Для этого служит стандартный тип pointer, например:
var p:pointer;
Указатели такого рода называются не типизированными. Поскольку не типизированные указатели не связаны с конкретным типом, с их помощью удобно динамически размещать данные, структура и тип которых меняются в ходе работы программы.
Указателю может быть присвоено "пустое" значение адреса, обозначаемое служебным словом nil. Оператор присваивания p1:=nil; означает, что указатель p1 не ссылается ни на одну динамическую переменную.
Для создания динамических переменных предназначается процедура new(r), где r – типизированный указатель. В результате выполнения этой процедуры в свободной памяти (обозначаемой термином "куча") выделяется ячейка, соответствующая описанию динамической переменной, а в значение указателя заносится адрес выделенной ячейки памяти. После этого в поля динамической переменной могут вводиться требуемые значения.
Для "стирания" динамических переменных используется процедура dispose(r), в результате выполнения которой указатель приобретает значение nil, а участок памяти очищается (выделенная ячейка памяти возвращается в "кучу").
Связи между элементами в более или менее сложных вычислительных структурах обычно иллюстрируются схемами. Каждый объект изображается прямоугольником, разделенным на части, соответствующие полям записи. Рядом приводится обозначение переменной. Ссылки изображаются стрелками. Значения данных записываются в части прямоугольников, отведенных под поля данных.
Вначале рассмотрим графическое изображение элементарных операций. Описание указателей и динамических переменных (здесь и далее) выглядит следующим образом:
type pn=^dp;
dp=record
i:integer;
p:pn
end;
var k, j, n:integer;
q, r, s:pn;
Пусть в памяти машины уже размещены две цепочки динамических переменных r^ r^.p^
r 15 25
q 20 30
q^ q^.p^
После выполнения оператора q:=r; указатель q ссылается на ту же переменную, что и r.
r 15 25
r^
q q^
После выполнения оператора q^:=r^; (из исходного состояния) на место переменной со значением 20 засылается переменная со значением 15, ссылающаяся на переменную с значением 25.
r 15 25
q 15
После выполнения оператора q^.i:=r^.i; (из исходного состояния) на место целого значения 20 заслано значение 15, а поле указателя не изменилось.
r 15 25
q 15 30
После выполнения оператора q^.p:=r^.p (из исходного состояния) на место ссылки на переменную с значением 30 засылается ссылка на переменную с значением 25, а поле целого значения не изменилось.
r 15 25
q 20
Указатели можно сравнивать посредством операций = и <>. Логическое выражение q=r имеет значение true в случае а), а в случаях б) и в) – false, так как в этих случаях указатели .q и r указывают на разные динамические переменные, имеющие, правда, равные значения.
Построим список из трех элементов, содержащих целые числа 5, 12 и 8. Значением указателя r в процессе построения всегда будет ссылка на первый элемент уже построенной части списка. Указатель q будет использоваться для выделения с помощью new места в памяти под размещение новых элементов списка. Выполнение оператора r:=nil; приводит к созданию пустого списка. После выполнения операторов:
new(q); q^.i:=8; q^.p:=r; r:=q;
получают список, состоящий из одного элемента, содержащего число 8 в части для данных. Ссылка на этот элемент является значением указателей r и q.
r 8 nil
r^, q^
q
Выполнение операторов new(q); q^.i:=12; q^.p:=r; r:=q; приводит к тому, что в начало этого списка добавляется новый элемент, содержащий число 12.
r 12 8 nil
r^ r^.p^
q q^ q^.p^
После выполнения операторов new(q); q^.i:=5; q^.p:=r; r:=q; добавляющих в начало списка элемент, содержащий число 5, построение списка завершается.
r 5 12 8 nil
r^ r^p^ r^.p^.p^
q q^ q^p^ q^.p^.p^
Значением указателей r и q является ссылка на первый элемент списка. Значение nil поля p элемента, содержащего число 8, является признаком того, что этот элемент последний в списке. Значением переменной r^.p^.i. является целое число 12; значением r^.p^.p – ссылка на третий элемент списка.
Рассмотренный способ построения списка заключается в создании пустого списка и в повторяющемся выполнении ряда однотипных шагов, добавляющих в начало построения списка новые элементы. Это означает, что в общем случае для построения списка можно использовать оператор цикла.
Если значением указателя q является адрес некоторого элемента списка, то оператор q:=q^.p; дает адрес очередного элемента или nil. Пользуясь таким способом перехода от одного элемента к другому, можно просматривать весь список или его часть.
Для включения в имеющийся список нового элемента необходимо вначале указателем q указать элемент списка, после которого должен размещаться новый элемент, а затем выполнить последовательность операторов new(s); s^.i:=j; s^.p:=q^.p; q^.p:=s;. Здесь s – вспомогательный указатель, j – значение нового элемента.
Для исключения из списка элемента, следующего за тем, на который ссылается указатель q, необходимо выполнить последовательность операторов s:=q^p; q^.p:=q^.p^.p; s^.p:=nil;