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

                               │           │

                               │   ╔═════╗ │

                               │   ║ D1  ║ │

                               │   ║═════║ │

                               └──>║ NIL ║<┘

                                   ╚═════╝

 

 

                     ╔═════╗       ╔═════╗       ╔═════╗

  pTop:=pAux;        ║  *──║───┐   ║     ║   ┌───║──*  ║

                     ╚═════╝   │   ║═════║<──┘   ╚═════╝

                     pTop     └──>║ *──║─┐      pAux

                                   ╚═════╝ │

                                           │

                                   ╔═════╗ │

                                   ║ D1  ║ │

                                   ║═════║ │

                                   ║ NIL ║<┘

                                   ╚═════╝

 

                     ╔═════╗       ╔═════╗

  pTop^.D:=D2;       ║  *──║───┐   ║ D2  ║

                     ╚═════╝   │   ║═════║

                      pTop     └──>║  *──║─┐

                                   ╚═════╝ │

                                           │

                                   ╔═════╗ │

                                   ║ D1  ║ │

                                   ║═════║ │

                                   ║ NIL ║<┘

                                   ╚═════╝

 

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

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

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

                     ╔═════╗       ╔═════╗

                     ║  *──║───┐   ║ D3  ║

                     ╚═════╝   │   ║═════║

                      pTop     └──>║  *--║─┐

                                   ╚═════╝ │

                                           │

                                   ╔═════╗ │

                                   ║ D2  ║ │

                                   ║═════║ │

                                 ┌─║──*  ║<┘

                                 │ ╚═════╝

                                 │

                                 │ ╔═════╗

                                 │ ║ D1  ║

                                 │ ║═════║

                                 └>║ NIL ║

                                   ╚═════╝

 

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

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

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

 

                         ╔═════╗       ╔═════╗

  D3:=pTop^.D;           ║  *──║───┐   ║ D3  ║

  pTop:=pTop^.pNext;     ╚═════╝   │   ║═════║

                          pTop     │   ║     ║

                                   │   ╚═════╝

                                   │

                                   │   ╔═════╗

                                   │   ║ D2  ║

                                   │   ║═════║

                                   └──>║  *──║─┐

                                       ╚═════╝ │

                                               │

                                       ╔═════╗ │

                                       ║ D1  ║ │

                                       ║═════║ │

                                       ║ NIL ║<┘

                                       ╚═════╝

 

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

 

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

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

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

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

символов 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);          ║  *──║───┐   ║     ║       ║     ║

                       ╚═════╝   │   ║═════║       ╚═════╝

                       pBegin    └──>║     ║         pEnd

                                     ╚═════╝

 

 

                       ╔═════╗       ╔═════╗       ╔═════╗

pBegin^.pNext:=NIL;   ║  *──║───┐   ║     ║       ║     ║

                       ╚═════╝   │   ║═════║       ╚═════╝

                       pBegin    └──>║ NIL ║         pEnd

                                     ╚═════╝

 

 

                       ╔═════╗       ╔═════╗       ╔═════╗

pBegin^.D:=D1;        ║  *──║───┐   ║ D1  ║       ║     ║

                       ╚═════╝   │   ║═════║       ╚═════╝

                       pBegin    └──>║ NIL ║         pEnd

                                     ╚═════╝

 

 

                       ╔═════╗       ╔═════╗       ╔═════╗

pEnd:=pBegin;         ║  *──║───┐   ║ D1  ║   ┌───║──*  ║

                       ╚═════╝   │   ║═════║   │   ╚═════╝

                       pBegin    └──>║ NIL ║<──┘     pEnd

                                     ╚═════╝

 

 

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

 

New(pAux);

   

╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║   ┌───║──*  ║       ║     ║   ┌───║──*  ║

╚═════╝   │   ║═════║   │   ╚═════╝       ║═════║   │   ╚═════╝

pBegin    └──>║ NIL ║<──┘    pEnd         ║     ║<──┘     pAux

              ╚═════╝                     ╚═════╝

 

pAux^.pNext:=NIL;

   

╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║   ┌───║──*  ║       ║     ║   ┌───║──*  ║

╚═════╝   │   ║═════║   │   ╚═════╝       ║═════║   │   ╚═════╝

pBegin    └──>║ NIL ║<──┘    pEnd         ║ NIL ║<──┘     pAux

              ╚═════╝                     ╚═════╝

pBegin^.pNext:=pAux;

   

╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║   ┌───║──*  ║       ║     ║   ┌───║──*  ║

╚═════╝   │   ║═════║   │   ╚═════╝       ║═════║   │   ╚═════╝

pBegin    └──>║  *  ║<──┘    pEnd         ║ NIL ║<──┘     pAux

              ╚═════╝                     ╚═════╝

                 │                           ^

                 │                           │

                 └───────────────────────────┘

pEnd:=pAux;

 

╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║       ║  *──║───┐   ║     ║   ┌───║──*  ║

╚═════╝   │   ║═════║       ╚═════╝   │   ║═════║   │   ╚═════╝

pBegin    └──>║  *  ║        pEnd     └──>║ NIL ║<──┘     pAux

              ╚═════╝                     ╚═════╝

                 │                           ^

                 │                           │

                 └───────────────────────────┘

 

pEnd^.D:=D2;

   

╔═════╗       ╔═════╗                     ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║                     ║ D2  ║   ┌───║──*  ║

╚═════╝   │   ║═════║                     ║═════║   │   ╚═════╝

pBegin    └──>║ *──║────────────────────>║ NIL ║<──┘    pEnd

              ╚═════╝                     ╚═════╝

                                             

                                             

 

 

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

   

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

одновременно компонента исключается  из очереди.  Пусть в  памяти  ЭВМ

сформирована очередь, состоящая  из трех элементов:

 

 

╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║       ║ D2  ║       ║ D3  ║   ┌───║──*  ║

╚═════╝   │   ║═════║       ║═════║       ║═════║   │   ╚═════╝

pBegin    └──>║  *──║──────>║  *──║──────>║ NIL ║<──┘     pEnd

              ╚═════╝       ╚═════╝       ╚═════╝

                                                                                                                                                                                                                                                              

 

 

   Выборка компоненты выполняется  следующими операторами:

 

D1:=pBegin^.D;

pBegin:=pBegin^.pNext;

   

╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗       ╔═════╗

║  *──║───┐   ║ D1  ║       ║ D2  ║       ║ D3  ║   ┌───║──*  ║

╚═════╝   │   ║═════║       ║═════║       ║═════║   │   ╚═════╝

pBegin    │   ║     ║   ┌──>║  *──║──────>║  NIL ║<──┘     pEnd

          │   ╚═════╝   │   ╚═════╝       ╚═════╝

          │             │

          └─────────────┘

   

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

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

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

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

строка символов END.

 

  Program QUEUE;

  uses Crt;

  type

   Alfa= String[10];

   PComp= ^Comp;

   Comp= record

          sD:Alfa;

          pNext:PComp

         end;

  var

   pBegin, pEnd: PComp;

   sC: Alfa;

  Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);

   begin

    New(pBegin);

    pBegin^.pNext:=NIL;

    pBegin^.sD:=sC;

    pEnd:=pBegin

   end;

  Procedure AddQueue(var pEnd:PComp; var sC:Alfa);

   var pAux: PComp;

   begin

    New(pAux);

    pAux^.pNext:=NIL;

    pEnd^.pNext:=pAux;

    pEnd:=pAux;

    pEnd^.sD:=sC

   end;

  Procedure DelQueue(var pBegin: PComp; var sC: Alfa);

   begin

    sC:=pBegin^.sD;

    pBegin:=pBegin^.pNext

   end;

  begin

   Clrscr;

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

   readln(sC);

   CreateQueue(pBegin,pEnd,sC);

   repeat

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

    readln(sC);

    AddQueue(pEnd,sC)

   until sC='END';

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

   repeat

    DelQueue(pBegin,sC);

    writeln(sC);

   until pBegin=NIL

  end.

   

   

40.   Л И Н Е Й Н Ы  Е   С П И С К И

   

   В стеки или очереди  компоненты можно добавлять только  в  какой  -

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

нент.

   Связный (линейный) список является структурой данных, в произволь-

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

ся оттуда.

   Каждая компонента списка  определяется ключом.  Обычно  ключ -  либо