→ Пошук по сайту       Увійти / Зареєструватися
Знання Мова програмування Pascal

Линейные списки

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

Связный (линейный) список является структурой данных, в произвольно выбранное место которого могут включаться данные, а также изыматься оттуда.

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

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

  • для чтения доступна любая компонента списка;
  • новые компоненты можно добавлять в любое место списка;
  • при чтении компонента не удаляется из списка.

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

  • начальное формирование списка (запись первой компоненты);
  • добавление компоненты в конец списка;
  • чтение компоненты с заданным ключом;
  • вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);
  • исключение компоненты с заданным ключом из списка.

Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало списка, вторая - конец списка, остальные- вспомогательные.

Описание компоненты списка и переменных типа указатель дадим следующим образом:

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.
загрузка...
Сторінки, близькі за змістом