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

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


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

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

В разделе типов описываем ссылку на звено 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.

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











Назад