Примеры задач

Стеки и очереди

Сформировать файл из натуральных чисел. Разработать процедуру перестановки первого и последнего элементов списка, построенного из элементов файла.

Методика решения

В разделе типов описываем ссылку на звено ss=^zveno, а затем само звено в виде записи, состоящей из информационной inf:integer и ссылочной next:ss частей.

Для реализации данной программы понадобятся следующие переменные:

l – ссылки на начало очереди (тип ss);

r – ссылка на конец очереди (тип ss);

c – натуральные числа (тип integer);

f – файловая переменная типа integer;

Описываем их в разделе переменных.

Для реализации данной программы будем использовать процедуру добавления звена в очередь (voch), процедуру удаления звена из очереди (izoch), процедуру перестановки первого и последнего элементов списка (zamena).

Процедура добавления звена в очередь

Эта процедура будет иметь входной параметр a –элемент, добавляемый в очередь.

Добавление нового звена к очереди происходит в конце очереди.

Создаём новое звено New(p), его информационную часть заносим a.

Ссылочную часть нового звена делаем пустой: p^.next:=nil;

Далее проверяем, если очередь не пуста (l<>nil), тогда ссылочную часть последнего звена очереди направляем на звено p, и указатель R переносим на это звено.

R^.next:=p; R:=p;

Если же очередь пуста, то ссылки l и R направляем на новое звено P. Новое звено будет и первым, и последним звеном очереди.

Процедура удаления звена из очереди

Эта процедура будет иметь входной параметр a –элемент, удаляемый из очереди.

Удаление элемента из очереди происходит с начала очереди Сначала проверяем, является ли ссылка l - ссылка на начало очереди пустой, если да, то выводим на экран сообщение о том, что очередь пуста.

Если же очередь не пуста, то удаляем ее первое звено, предварительно присвоив переменной a его информационную часть. Следующее звено делаем первым, направляя ссылку l на него.

Графически это выглядит следующим образом:

P:=L;

L:=L^.next;

Теперь звено g можно удалить dispose(g);

Процедура перестановки первого и последнего элементов списка

Эта процедура имеет одну локальную переменную Х типа integer. Этой переменной присваиваем информационную часть последнего звена очереди. Затем L^.inf заменим на r^.inf, а в первое звено заносим Х.

Раздел операторов

Делаем начальную установку очереди: l:=nil; r:=nil;

Связываем файловую переменную с файлом с помощью процедуры assign. Открываем файл для записи, вводим с клавиатуры натуральные числа c. Далее в цикле пока с<>0 считываем числа и записываем в файл.

Затем в цикле пока не конец файла считываем числа из файла и с помощью процедуры добавления звена в очередь (voch) заносим их в очередь.

С помощью процедуры перестановки первого и последнего элементов списка (zamena) меняем местами элементы очереди.

Далее, пока ссылка l – ссылка на начало очереди не пуста с помощью процедуры удаления звена из очереди (izoch) извлекаем элементы очереди и выводим их на экран.

Листинг программы

uses crt;

type

ss=^zveno;

zveno=record

inf:integer;

next:ss

end;

var l,r:ss; c:integer;

f:file of integer;

procedure voch (a:integer);

var p:ss;

begin

new(p); p^.inf:=a; p^.next:=nil;

if l<>nil then begin r^.next:=p; r:=p;end else begin l:=p; r:=p; end;

end;

procedure izoch(var a:integer);

var p:ss;

begin

if l=nil then writeln('ochered pusta') else

begin

p:=l; a:=p^.inf; l:=l^.next; dispose(p);

end;

end;

procedure zamena;

var x:integer;

Begin

x:=l^.inf; l^.inf:=r^.inf; r^.inf:=x;

end;

begin clrscr;

l:=nil; r:=nil;

assign(f,'file.dat');

rewrite(f);

writeln('Vvedite natyralnie chisla (konec vvoda-0)');

readln(c);

while c<>0 do

begin

write(f,c);

readln(c);

end;

close(f);

reset(f);

while not eof(f) do

begin

read(f,c);

voch(c);

end;

close(f);

writeln('rezyltat:');

zamena;

while l<>nil do

begin

izoch(c);

write(c:3);

end;

readkey;

end.

Запустить программу

Назад