Примеры задач
Стеки и очереди
Сформировать файл из натуральных чисел. Разработать процедуру перестановки первого и последнего элементов списка, построенного из элементов файла. Методика решения
В разделе типов описываем ссылку на звено 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.