Ссылочные типы в ТП

Стеки

1. Определение и описание стека

   Для моделирования различных процессов часто используются линейные списки, в которых включение, исключение или просмотр элементов всегда начинается с первого или последнего звеньев. Такие списки имеют специальные названия.
   Стек – однонаправленный список, в котором все включения и удаления выполняются с конца списка.
   Детская пирамидка, железнодорожный тупик хорошо демонстрируют работу стека.
   Стек – это структура данных, которая организована по принципу «LIFO» (last in – first out, т.е. последний элемент, помещенный в стек, первым удаляется из стека)

   

   В стеке с помощью некоторой ссылки s доступно единственное последнее звено, которое называется вершиной стека.
   Поскольку в стеке доступна только его вершина, необходимость в заглавном звене отпадает. Роль указателя на стек, как на единый объект, выполняет ссылка на его вершину.

   Стек можно описать в программе так:

   Type te=тип инф.части; {тип элементов стека}
   Ss=^zveno; {ссылка на звено}
   Zveno=record {звено}
   Inf: te; {информационная часть}
   Sled:ss {ссылочная часть}
   End;
   Stek=ss;
   Var s:stek; {Ссылка на вершину стека}

2. Основные операции над стеком

   1. Начальная установка стека
      В начале работы стек пуст, т.е. значением указателя s стека является пустая ссылка. Это устанавливается оператором: s:=nil;

      Функция проверки пустоты стека

      Логическая функция pust, проверяющая пустоту стека, может быть определена как значение логического выражения: st=nil; (st – указатель стека – аргумент функции).

      function pust(var st:stek):boolean;

      begin

      pust:=(st=nil)

      end;

      Включение звена в стек

      Процедура добавления звена в стек должна иметь два параметра: имя стека и имя элемента, добавляемого в стек. Процедура создает новое звено и делает его вершиной стека:

      procedure vstek(var st:stek; x:te);

      var g:ss;

      begin

      new(g);

      g^.inf:=x;

      g^.sled:=st;

      st:=g

      end;

      Удаление звена

      Процедура удаления звена из стека сначала проверяет, является ли стек пустым, и в этом случае печатает соответствующее сообщение. Если же стек не пуст, процедура удаляет его вершину, присваивая выходному параметру х значение удаляемого элемента, ссылка на следующее звено становится вершиной стека:

      procedure izsteka(var st:stek; x:te);

      var g:ss;

      begin

      if st=nil then writeln('stek pust') else

      begin

      g:=st;x:=g^.inf;

      st:=st^.sled;

      dispose(g);

      end;

      end;

3. Пример программы

   В строке символов f записана без ошибок формула, определяемая следующим образом:

   1. Любая арабская цифра является формулой.
   2. Формулами являются выражения вида: m(формула, формула) или р(формула, формула), где m(a,b)=abs(a-b)mod 10, p(a,b)=(a+b)mod 10.
   3. Других формул нет.

   Составить программу, вычисляющую значение формулы: (например, m(9,p(p(5,9),m(2,6)))=m(9,p(4,4))=1)

   Для решения задачи воспользуемся следующими идеями:

   1. Образуем множество символов mn=['0'..'9','m','p'];
   2. Организуем последовательную обработку символов с формулы f по правилу: если с- элемент множества mn, поместим его в стек, иначе, если с=’)‘ , возьмем из стека три последних элемента, выполним операцию (последний из этих трех элементов m или р) и ее результат поместим в стек. Символы ‘(‘ и ‘,’ игнорируются.
   3. После окончания обработки прочитываем ответ из стека.
   program formula;
   uses crt;
   const mn: set of char=['0'..'9','m','p'];
   type
   te=char;
   ss=^zveno;
   zveno=record
   inf:te;
   sled:ss
   end;
   stek=ss;
   var s:stek; f,fst:string[100];
   c,op,x,y:char; x1,y1,k1,i,k:integer;

   function pust(var st:stek):boolean;
   begin
   pust:=st=nil
   end;

   procedure vstek(var st:stek; x:te);
   var g:ss;
   begin
   new(g);
   g^.inf:=x;
   g^.sled:=st;
   st:=g
   end;

   procedure izsteka(var st:stek; var x:te);
   var g:ss;
   begin
   if st=nil then writeln('stek pust') else
   begin
   g:=st;x:=g^.inf;
   st:=st^.sled;
   dispose(g);
   end;
   end;

   BEGIN clrscr; writeln('input formula');
   read(f); s:=nil;
   for i:=1 to length(f) do
   begin
   if f[i] in mn then vstek(s,f[i]) else
   if f[i]=')' then
   begin
   izsteka(s,y); izsteka(s,x); izsteka(s,op);
   val(y,y1,k1); val(x,x1,k1);
   case op of
   'm': k:=abs(x1-y1) mod 10;
   'p': k:=(x1+y1) mod 10;
   end;
   str(k,fst); vstek(s,fst[1]);
   end;
   end;
   izsteka(s,c); writeln('=',c);
   readkey;
   END.

Назад

Далее