Реферат: Основные понятия алгоритмического языка

  pTop^.pNext:=NIL;  ¦  *--¦---¬   ¦     ¦

                     L=====-   ¦   ¦=====¦

                      pTop     L-->¦ NIL ¦

                                   L=====-

                     г=====¬       г=====¬

  pTop^.D:=D1;       ¦  *--¦---¬   ¦ D1  ¦

                     L=====-   ¦   ¦=====¦

                      pTop     L-->¦ NIL ¦

                                   L=====-

    Последний оператор или группа операторов записывает  содержимое

поля данных первой компоненты.

    Добавление компоненты в стек призводится с использованием вспо-

могательного указателя:

   

                     г=====¬       г=====¬       г=====¬

  New(pAux);         ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦

                     L=====-   ¦   ¦=====¦   ¦   L=====-

                      pTop     ¦   ¦     ¦<---    pAux

                               ¦   L=====-

                               ¦

                               ¦   г=====¬

                               ¦   ¦ D1  ¦

                               ¦   ¦=====¦

                               L-->¦ NIL ¦

                                   L=====-

                     г=====¬       г=====¬       г=====¬

  pAux^.pNext:=pTop; ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦

                     L=====-   ¦   ¦=====¦<---   L=====-

                      pTop     ¦   ¦  *--¦-¬      pAux

                               ¦   L=====- ¦

                               ¦           ¦

                               ¦   г=====¬ ¦

                               ¦   ¦ D1  ¦ ¦

                               ¦   ¦=====¦ ¦

                               L-->¦ NIL ¦<-

                                   L=====-

                     г=====¬       г=====¬       г=====¬

  pTop:=pAux;        ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦

                     L=====-   ¦   ¦=====¦<---   L=====-

                      pTop     L-->¦  *--¦-¬      pAux

                                   L=====- ¦

                                           ¦

                                   г=====¬ ¦

                                   ¦ D1  ¦ ¦

                                   ¦=====¦ ¦

                                   ¦ NIL ¦<-

                                   L=====-

                     г=====¬       г=====¬

  pTop^.D:=D2;       ¦  *--¦---¬   ¦ D2  ¦

                     L=====-   ¦   ¦=====¦

                      pTop     L-->¦  *--¦-¬

                                   L=====- ¦

                                           ¦

                                   г=====¬ ¦

                                   ¦ D1  ¦ ¦

                                   ¦=====¦ ¦

                                   ¦ NIL ¦<-

                                   L=====-

   Добавление последующих компонент производится аналогично.

   Рассмотрим процесс выборки компонент из стека. Пусть к моменту на-

чала выборки стек содержит три компоненты:

                     г=====¬       г=====¬

                     ¦  *--¦---¬   ¦ D3  ¦

                     L=====-   ¦   ¦=====¦

                      pTop     L-->¦  *--¦-¬

                                   L=====- ¦

                                           ¦

                                   г=====¬ ¦

                                   ¦ D2  ¦ ¦

                                   ¦=====¦ ¦

                                 --¦--*  ¦<-

                                 ¦ L=====-

                                 ¦

                                 ¦ г=====¬

                                 ¦ ¦ D1  ¦

                                 ¦ ¦=====¦

                                 L>¦ NIL ¦

                                   L=====-

   Первый оператор или группа операторов осуществляет  чтение  данных

из компоненты - вершины стека. Второй оператор изменяет значение ука-

зателя вершины стека:

                         г=====¬       г=====¬

  D3:=pTop^.D;           ¦  *--¦---¬   ¦ D3  ¦

  pTop:=pTop^.pNext;     L=====-   ¦   ¦=====¦

                          pTop     ¦   ¦     ¦

                                   ¦   L=====-

                                   ¦

                                   ¦   г=====¬

                                   ¦   ¦ D2  ¦

                                   ¦   ¦=====¦

                                   L-->¦  *--¦-¬

                                       L=====- ¦

                                               ¦

                                       г=====¬ ¦

                                       ¦ D1  ¦ ¦

                                       ¦=====¦ ¦

                                       ¦ NIL ¦<-

                                       L=====-

   Как видно из рисунка, при чтении компонента удаляется из стека.

   Пример. Составить программу,  которая формирует стек,  добавляет в

него произвольное количество компонент, а затем читает все компоненты

и выводит их на экран дисплея,  В качестве данных взять строку симво-

лов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка

символов END.

   

 Program STACK;

  uses Crt;

  type

   Alfa= String[10];

   PComp= ^Comp;

   Comp= Record

           sD: Alfa;

           pNext: PComp

          end;

  var

   pTop: PComp;

   sC: Alfa;

  Procedure CreateStack(var pTop: PComp; var sC: Alfa);

   begin

    New(pTop);

    pTop^.pNext:=NIL;

    pTop^.sD:=sC

   end;

  Procedure AddComp(var pTop: PComp; var sC: Alfa);

   var pAux: PComp;

   begin

    NEW(pAux);

    pAux^.pNext:=pTop;

    pTop:=pAux;

    pTop^.sD:=sC

   end;

  Procedure DelComp(var pTop: PComp; var sC:ALFA);

   begin

    sC:=pTop^.sD;

    pTop:=pTop^.pNext

   end;

  begin

   Clrscr;

   writeln('  ВВЕДИ СТРОКУ ');

   readln(sC);

   CreateStack(pTop,sC);

   repeat

    writeln('  ВВЕДИ СТРОКУ ');

    readln(sC);

    AddComp(pTop,sC)

   until sC='END';

   writeln('****** ВЫВОД  РЕЗУЛЬТАТОВ ******');

   repeat

    DelComp(pTop,sC);

    writeln(sC);

   until pTop = NIL

  end.

                                    

39.   О Ч Е Р Е Д И

   

   Очередью называется динамическая структура данных, добавление ком-

поненты в которую производится в один конец, а выборка осуществляется

с другого конца. Очередь работает по принципу:

        FIFO (First-In, First-Out) -

поступивший первым, обслуживается первым.

   Для формирования очереди и работы с ней необходимо иметь три пере-

менные типа указатель,  первая из которых определяет начало  очереди,

вторая - конец очереди, третья - вспомогательная.

   Описание компоненты очереди и переменных типа указатель дадим сле-

дующим образом:

   

  type

   PComp=^Comp;

   Comp=record

         D:T;

         pNext:PComp

        end;

  var

   pBegin, pEnd, pAux: PComp;

где pBegin - указатель начала очереди, pEnd - указатель конца  очере-

ди, pAux - вспомогательный указатель.

   Тип Т определяет тип данных компоненты очереди.

   Начальное формирование очереди выполняется следующими операторами:

                       г=====¬       г=====¬       г=====¬

 New(pBegin);          ¦  *--¦---¬   ¦     ¦       ¦     ¦

                       L=====-   ¦   ¦=====¦       L=====-

                       pBegin    L-->¦     ¦         pEnd

                                     L=====-

                       г=====¬       г=====¬       г=====¬

 pBegin^.pNext:=NIL;   ¦  *--¦---¬   ¦     ¦       ¦     ¦

                       L=====-   ¦   ¦=====¦       L=====-

                       pBegin    L-->¦ NIL ¦         pEnd

                                     L=====-

                       г=====¬       г=====¬       г=====¬

 pBegin^.D:=D1;        ¦  *--¦---¬   ¦ D1  ¦       ¦     ¦

                       L=====-   ¦   ¦=====¦       L=====-

                       pBegin    L-->¦ NIL ¦         pEnd

                                     L=====-

                       г=====¬       г=====¬       г=====¬

 pEnd:=pBegin;         ¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦

                       L=====-   ¦   ¦=====¦   ¦   L=====-

                       pBegin    L-->¦ NIL ¦<---     pEnd

                                     L=====-

   Добавление компоненты в очередь производится в конец очереди:

 New(pAux);

   

г=====¬       г=====¬       г=====¬       г=====¬       г=====¬

¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦       ¦     ¦   ----¦--*  ¦

L=====-   ¦   ¦=====¦   ¦   L=====-       ¦=====¦   ¦   L=====-

pBegin    L-->¦ NIL ¦<---    pEnd         ¦     ¦<---     pAux

              L=====-                     L=====-

 pAux^.pNext:=NIL;

   

г=====¬       г=====¬       г=====¬       г=====¬       г=====¬

¦  *--¦---¬   ¦ D1  ¦   ----¦--*  ¦       ¦     ¦   ----¦--*  ¦

L=====-   ¦   ¦=====¦   ¦   L=====-       ¦=====¦   ¦   L=====-

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12