Var Pr:preco;
Выделение памяти
В результате выполнения процедур New и Getmem в ячейки переменных-указателей записываются адреса, по которым будут располагаться данные соответствующих типов, и выделяется память по указанным адресам для хранения объектов, на которые ссылаются указатели:
New(x); New(y); New(B); New(R); New(Pa); New(Pr);
Getmem (p, sizeof(real)); Getmem(q, sizeof(A));
Разыменование (занесение значений)
x^ := 10; y^ := 20; B^:=255; R^:=1.125;
for i:=1 to 5 do Pa^[i] := sqr(i);
Pr^.c := `$`; Pr^.n := 1000;
Копирование значений
x^ := y^;
R^ := B^;
Копирование адресов
x:=y;
Пусть в тексте программы имеется: var k:real; … k := 625.5;
Тогда присвоение адреса переменной k указателям r и p будет выглядеть следующим образом: r:=@k; p:=@k;
Высвобождение памяти
Dispose(y); Dispose(x);
Freemem (p,sizeof(p));
Dispose(Pa); Dispose(Pr);
13.5.7. Задание «нулевого» значения
new(x);
x := nil;
14. Использование указателей для организации связанных динамических структур
Чаще всего указатели используют для ссылки на записи, чем достигается значительная экономия памяти. В такие записи включаются информационные поля для хранения интересующих пользователя данных (любого типа, который может быть полем записи) и обязательно хотя бы одно поле-указатель на следующую запись. Наличие поля-адреса позволяет образовывать связанные списки – структуру, в которой отдельные записи связаны последовательно друг с другом посредством поля-указателя.
14.1. Списки
Линейный список – связанный список, в котором имеется адрес точки входа в список (обозначим его HEAD), а последний элемент указывает на Nil. В любую точку списка разрешается добавлять элемент (ы) и исключать любой элемент. Обе операции производятся с помощью перенастройки указателей и, соответственно, выделения памяти и занесения в нее значения (в случае вставки элемента в список) или высвобождения памяти (в случае удаления из списка).
П р и м е р линейного односвязного списка представлен на рис. 14.1.
Рис. 14.1. Список в динамической памяти
Таким образом, все указатели списка, кроме первого (HEAD), размещаются в динамической памяти. Поскольку каждый элемент списка состоит из разнотипных частей - хранимой информации в виде информационных полей и указателя, то естественно представить в Паскале такой элемент типом Record. Для указателя на вход в список необходимо описать переменную соответствующего типа.
П р и м е р описания списка
Type psp = ^tsp;
tsp = Record
… {Поля любых типов}
…
next : psp
end;
14.1.1. Алгоритмы работы со списками
1. Построение списка сводится к последовательному добавлению элементов в первоначально пустой список. На пустой список указывает (head = nil). Пусть требуется создать список слов, вводимых с клавиатуры. Последнее слово в списке – «end».
Type
psp = ^tsp;
tsp = Record
wd:string; {В нашем примере информационное по
ле имеет тип string}
next : psp
end;
Var
head,p:psp;
sl:string;
begin
new(p);
head:=p;
p^.next:=nil;
readln(sl);
p^.wd:=sl;
while sl<>'end'
do begin
readln(sl);
new(q);
q^.wd := sl;
p^.next := q;
q^.next := nil;
p := q
end;
end;
2. Просмотр и печать списка. Пусть требуется написать процедуру Print_Spisok печати элементов списка, созданного в алгоритме 1.
Procedure Print_spisok;
begin
p:= head;
while p <> nil
do begin
writeln((p^.wd);
p := p^.next
end
end;
3. Поиск элемента в списке. Определить, есть ли в списке (алгоритм I) слово «begin» и если есть, то сколько раз встречается. К описанию алгоритма 1 добавим: var k : integer;
…
begin
p := head;
while p <> nil
do begin
if p^.wd = ‘begin’
then inc(k);
p := p^.next
end;
if k=0
then writeln(‘Такого элемента нет’)
else writeln(‘Слово’,sl,’ встречается ‘,k,’ раз’)
end;
4. Удаление первого элемента списка. Необходимо: 1) передвинуть указатель head на следующий элемент; 2) освободить память; 3) освободить память, занятую удаляемым элементом.
begin
p := head;
head := p^.next;
dispose(p);
Print_Spisok
end;
5. Удаление последнего элемента списка. К разделу описаний алгоритма 1 добавим вспомогательную переменную q типа psp.
begin
p := head;
q := p^.next;
while q^.next <> nil
do begin
p := q;
q := q^.next
end;
dispose(p);
p^.next := nil;
Print_Spisok
end;
6. Вставка элемента в список. Пусть необходимо вставить в список (алгоритм 1) новый элемент sl_new перед первым вхождением элемента sl_old, если sl_old входит в список. Добавим к разделу описаний алгоритма I описание переменных sl_new,sl_old : string; и fl:Boolean.
begin
write('Введите искомое слово ');
readln(sl_old);
write('Введите новое слово ');
readln(sl_new);
fl:=false;
p:=head;
while (p<> nil) and not fl
do if p^.wd=sl_old
then fl:=true
else p:=p^.next;
if fl
then begin {Вставка элемента}
new(q);
q^.wd:=sl_old;
q^.next:=p^.next;
p^.wd:=sl_new;
p^.next:=q
end;
Print_Spisok;
end;