Программирование

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

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

 

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

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

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

                      pTop     L-->¦     ¦

                                   L=====-

 

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

  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=====-

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

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

pBegin^.pNext:=pAux;

   

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

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

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

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

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

                 ¦                           ^

                 ¦                           ¦

                 L----------------------------

pEnd:=pAux;

 

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

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

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

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

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

                 ¦                           ^

                 ¦                           ¦

                 L----------------------------

 

pEnd^.D:=D2;

   

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

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

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

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

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

                                             

                                             

 

 

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

   

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

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

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

 

 

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

¦  *--¦---¬   ¦ D1  ¦       ¦ D2  ¦       ¦ D3  ¦   ----¦--*  ¦

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

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

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

 

 

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

 

 D1:=pBegin^.D;

pBegin:=pBegin^.pNext;

   

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

¦  *--¦---¬   ¦ D1  ¦       ¦ D2  ¦       ¦ D3  ¦   ----¦--*  ¦

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

pBegin    ¦   ¦     ¦   --->¦  *--¦------>¦  NIL ¦<---     pEnd

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

          ¦             ¦

          L--------------

   

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

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

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

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

строка символов 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.   Л И  Н Е Й Н Ы Е   С П  И С К И

   

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

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

нент.

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

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

ся оттуда.

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

число, либо  строка символов. Ключ располагается  в поле данных компо-