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

Зачем нужна динамическая переменная? Одиночная динамическая переменная не представляет никакого интереса. Интерес представляют различные структуры данных, созданные в области динамической памяти. Такие структуры создаются и развиваются на этапе выполнения программы, они могут быть адаптированы к текущим данным, объемы которых становятся известными лишь на этапе выполнения программы. Вернемся к задаче (*). Пользователь набирает на клавиатуре последовательность символов. Окончание набора фиксируется набором комбинации клавиш 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); begin 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

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

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