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

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

поля записи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

   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.