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

                     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.   Л И Н Е Й Н Ы Е   С П И С К И

   

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

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

нент.

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

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

ся оттуда.

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

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

ненты, он может занимать как отдельное поле записи, так и быть частью

поля записи.

   Основные отличия связного списка от стека и очереди следующие:

   -для чтения доступна любая компонента списка;

   -новые компоненты можно добавлять в любое место списка;

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

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

   -начальное формирование списка (запись первой компоненты);

   -добавление компоненты в конец списка;

   -чтение компоненты с заданным ключом;

   -вставка компоненты в заданное место списка (обычно  после  компо-

ненты с заданным ключом);

   -исключение компоненты с заданным ключом из списка.

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

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

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

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

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

   type

    PComp= ^Comp;

    Comp= record

           D:T;

           pNext:PComp

          end;

   var

    pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

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

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

   Начальное формирование списка, добавление компонент в конец списка

выполняется так же, как и при формировании очереди.

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

¦  *--¦-¬   ¦ D1  ¦    ¦ D2  ¦       ¦ DN1 ¦    ¦ DN  ¦  --¦--*  ¦

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

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

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

                                                                                                                                                                                                                                                               

   Для чтения  и вставки компоненты по ключу необходимо выполнить по-

иск компоненты с заданным ключом:

   

  pCKey:=pBegin;

  while (pCKey<>NIL) and (Key<>pCKey^.D) DO

   pCKey:=pCKey^.pNext;

  

Здесь Key - ключ, тип которого совпадает с типом данных компоненты.

   После выполнения  этих операторов указатель pСKey будет определять

компоненту с заданным ключом или такая компонента не будет найдена.

   Пусть pCKey определяет компоненту с заданным ключом. Вставка новой

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

   

 New(pAux);               г===¬

 pAux^.D:= DK1;        ---¦-* ¦

                       ¦  L===-

                       ¦  pCKey

                       ¦

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

¦ *-¦--¬  ¦D1 ¦      ¦Key¦     ¦KK1¦      ¦DN ¦  ---¦-* ¦

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

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

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

                                                                                                                                                                                                                                                               

   

                                           г===¬     г===¬

                                           ¦DK1¦  ---¦-* ¦

                                           ¦===¦  ¦  L===-

                                           ¦   ¦<--   pAux

                                           L===-

   

 pAux^.pNext:=pCKey^.pNext;

 pCKey^.pNext:=pAux;

                                        

                          г===¬

                       ---¦-* ¦

                       ¦  L===-

                       ¦  pCKey

                       ¦

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

¦ *-¦--¬  ¦D1 ¦      ¦Key¦     ¦KK1¦      ¦DN ¦  ---¦-* ¦

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

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

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

                       ¦         ^

                       ¦         ¦          г===¬     г===¬

                       ¦         ¦          ¦DK1¦  ---¦-* ¦

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

                       L------------------->¦-* ¦<--   pAux

                                            L===-

   

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

нужной компоненты помнить адрес предшествующей:

  pCKey:=pBegin;

  while (pCKey<>NIL) and (Key<>pCKey^.D) do

   begin

    pPreComp:=pCKey;

    pCKey:=pCKey^.pNext

   end;

   

Здесь указатель pCKey определяет компоненту с заданным ключом, указа-

тель pPreComp содержит адрес предидущей компоненты.

   

   Удаление компоненты с ключом Key выполняется оператором:

 pPreComp^.pNext:=pCKey^.pNext;

   

                    pPreComp   pCKey

                     г===¬     г===¬

                     ¦ * ¦     ¦ * ¦

                     L===-     L===-

                       ¦         ¦

                       ¦         ¦

                       ¦         ¦

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

¦ *-¦--¬  ¦D1 ¦      ¦KK1¦     ¦Key¦    ¦KK2¦      ¦DN ¦  ---¦-* ¦

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

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

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

                           ¦              ^

                           ¦              ¦

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

                                                                                                                                                                                                                                                               

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

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

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

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

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

 Program LISTLINKED;

  uses Crt;

  type

   Alfa= String[10];

   PComp= ^Comp;

   Comp= record

          sD:Alfa;

          pNext:PComp

         end;

  var

   pBegin, pEnd, pAux, pCKey, pPreComp: PComp;

   sC, sKey: Alfa;

   bCond: Boolean;

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

   begin

    New(pBegin);

    pBegin^.pNext:=NIL;

    pBegin^.sD:=sC;

    pEnd:=pBegin

   end;

  Procedure AddLL(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 Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp;

                 var bCond: Boolean);

   begin

    pCKey:=pBegin;

    while (pCKey <> NIL) and (sKey <> pCKey^.D) do

     begin

      pPreComp:=pCKey;

      pCKey:=pCKey^.pNext

     end;

    if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE

                                             else bCond:=TRUE

   end;

  Procedure InsComp(var sKey,sC: Alfa);

   var pAux:PComp;

   begin

    Find(sKey,pBegin,pCKey,pPreComp,bCond);

    New(pAux);

    pAux^.sD:=sC;

    pAux^.pNext:=pCKey^.pNext;

    pCKey^.pNext:=pAux

   end;

  Procedure DelComp(var sKey: Alfa; var pBegin: PComp);

   begin

    Find(sKey,pBegin,pCKey,pPreComp,bCond);

    pPreComp^.pNext:=pCKey^.pNext

   end;

  begin

   ClrScr;

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

   readln(sC);

   CreateLL(pBegin,pEnd,sC);

   repeat

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

    readln(sC);

    AddLL(pEnd,sC)

   until sC='END';

   writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****');

   pAux:=pBegin;

   repeat

    writeln(pAux^.sD);

    pAux:=pAux^.pNext;

   until pAux=NIL;

   writeln;

   writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ');

   readln(sKey);

   writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ');

   readln(sC);

   InsComp(sKey,sC);

   writeln;

   writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ');

   readln(sKey);

   DelComp(sKey,pBegin);

   writeln;

   writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****');

    pAux:=pBegin;

    repeat

     writeln(pAux^.sD);

     pAux:=pAux^.pNext;

    until pAux=NIL

  end.