11.3 Операции над указателями

Указатель может находиться в одном из трех состояний:

1. Указатель не инициализирован. Указатель можно инициализировать процедурой NEW, значением другого (инициализированного) указателя, или константой NIL.

2. Указатель инициализирован процедурой NEW. Можно использовать динамическую переменную q^, сам указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

3. Указатель инициализирован константой NIL. Можно указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

11.4 Пояснения с помощью картинки

Указатель q:^T описан в тексте программы на ТР. С помощью процедуры new(q) указатель q инициализируется. Диспетчер динамической памяти выделяет участок свободной памяти размером sizeof(T) в области динамической памяти (в куче) и адрес его начала присваивает переменной q. Теперь динамическая переменная q^ типа Т доступна для использования, однако, пока не инициализирована. Инициализировать ее можно, например, присваиванием q^:=t, где t – константа типа Т.

11.5 Динамическая цепочка

Зачем нужна динамическая переменная? Одиночная динамическая переменная не представляет никакого интереса. Интерес представляют различные структуры данных, созданные в области динамической памяти. Такие структуры создаются и развиваются на этапе выполнения программы, они могут быть адаптированы к текущим данным, объемы которых становятся известными лишь на этапе выполнения программы. Вернемся к задаче (*). Пользователь набирает на клавиатуре последовательность символов. Окончание набора фиксируется набором комбинации клавиш Ctrl+z, Enter. Для хранения введенных символов необходимо использовать структуру данных достаточного объема. Все статические структуры данных (структуры данных, созданные в статической памяти) имеют ограничения на количество вводимых символов. Попробуем организовать хранение введенных с клавиатуры символов в динамической памяти. Для этого в программе опишем новый тип данных, представляющий собой запись, содержащую поле типа char для хранения введенного символа, и поле типа «указатель» на следующую запись:

PElem=^Elem;

Elem=Record

inf:char;

next:PElem

end

В начале работы программы создается пустая цепочка записей. После каждого ввода очередного символа создается новая запись и подсоединяется к цепочке. Пусть p – данное типа PElem, x:char, тогда

• p:=nil; {Создана пустая цепочка p}

• while not eof do

begin

readln(x);

new(q);

q^.inf:=x;

q^.next:=p;

p:=q;

end; {Создана цепочка записей, p – указатель на первую запись цепочки}

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

Задача: Распечатать третью запись цепочки, если она есть.

writeln(p^.next^.next^.inf) {а если её нет?!}

Задача: Распечатать k-ую запись цепочки.

q:=p;

i:=1;

while (q<>nil) and (i<k) do

begin

i:=i+1;

q:=q^.next;

end;

if q<>nil then writeln(q^.inf) else writeln(‘нет записи’);

Распечатать информационные части цепочки p.

Традиционное решение	Рекурсивное решение
Procedure prnchar(p:PElem); Var q:PElem; begin q=p; while p<>NIL do begin write(p^.inf); p=p^.next end end	Procedure prnchar(p:PElem); begin if p<>NIL then begin write(p^.inf); prnchar(p^.next) end end

Задача: Распечатать информацию, вводимую с клавиатуры, в прямом порядке.

Задача: «Перевернуть» файл (Указание – использовать цепочку)