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

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

нент.

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

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

ся оттуда.

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

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

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

поля записи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   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є  ЪДєДД*  є

ИНННННј і   єНННННє    єНННННє       єНННННє    єНННННє  і ИНННННј

pBegin  АДД>є  *ДДєДДД>є  *ДДєД....Д>є*ДДєДДД>є NIL є<ДЩ   pEnd

            ИНННННј    ИНННННј       ИНННННј    ИНННННј

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

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

  pCKey:=pBegin;

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

   pCKey:=pCKey^.pNext;

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

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

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

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

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

 New(pAux);               ЙННН»

 pAux^.D:= DK1;        ЪДДєД* є

                       і  ИНННј

                       і  pCKey

                       і

ЙННН»     ЙННН»      ЙННН»     ЙННН»      ЙННН»     ЙННН»

є *ДєДДїєD1 є      єKeyє     єKK1є      єDN є  ЪДДєД* є

ИНННј  і  єНННє      єНННє     єНННє      єНННєі  ИНННј

pBegin АД>є *ДєД...Д>є *ДєДДДД>є *ДєД...Д>єNILє<ДЩ  pEnd

          ИНННј      ИНННј     ИНННј      ИНННј

                                           ЙННН»     ЙННН»

                                           єDK1єЪДДєД* є

                                           єНННєі  ИНННј

                                           є   є<ДЩ   pAux

                                           ИНННј

 pAux^.pNext:=pCKey^.pNext;

 pCKey^.pNext:=pAux;

                          ЙННН»

                       ЪДДєД* є

                       і  ИНННј

                       і  pCKey

                       і

ЙННН»     ЙННН»      ЙННН»     ЙННН»      ЙННН»     ЙННН»

є *ДєДДїєD1 є      єKeyє     єKK1є      єDN є  ЪДДєД* є

ИНННј  і  єНННє      єНННє     єНННє      єНННєі  ИНННј

pBegin АД>є *ДєД...Д>є * є     є *ДєД...Д>єNILє<ДЩ  pEnd

          ИНННј      ИНННј     ИНННј      ИНННј

                       і         ^

                       і         і          ЙННН»     ЙННН»

                       і         і          єDK1єЪДДє-* є

                       і         АДДДДДДДДДДєНННє  і  ИНННј

                       АДДДДДДДДДДДДДДДДДДД>єД* є<ДЩ   pAux

                                            ИНННј

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

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

  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

                     ЙННН»     ЙННН»

                     є * є     є * є

                     ИНННј     ИНННј

                       і         і

                       і         і

                       і         і

ЙННН»     ЙННН»      ЙННН»     ЙННН»    ЙННН»      ЙННН»     ЙННН»

є *ДєДДїєD1 є      єKK1є     єKeyє    єKK2є      єDN єЪДДєД* є

ИНННј  і  єНННє      єНННє     єНННє    єНННє      єНННє  і  ИНННј

pBegin АД>є *ДєД...Д>є *ДєДї   є *ДєДДД>є *ДєД...Д>єNILє<ДЩ   pEnd

          ИНННј      ИНННј і   ИНННј    ИНННј      ИНННј

                           і              ^

                           і              і

                           АДДДДДДДДДДДДДДЩ

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

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

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

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

клавиатуры дисплея, признак конца ввода - строка символов 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.