Структуры и алгоритмы обработки данных

       

Циклические списки


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

Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей.

Рис.1.3. Однонаправленный циклический список

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

В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка.

Рис.1.4. Двунаправленный циклический список

Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент. Рассмотрим пример программы, которая осуществляет следующие операции с двунаправленным циклическим списком:

добавление (справа и слева от текущего);

удаление (справа и слева от текущего);

поиск;



вывод списка.

program;

type element = record

               data:string;

               last, next: pointer;

     end;

var

      i,n: integer;

      point: pointer;

      current, pnt, pnt2: ^element;

      s:string;

begin

new(current);

current^.data:=-first-;

current^.next:=current

current^.last:=current;

repeat

        writeln(-1 v сделать текущим-);


        writeln(-2 v список элементов-);

        writeln(-3 v добавить справа-);

        writeln(-4 v добавить слева-);

        writeln(-5 v удалить текущий-);

        writeln(-6 v удалить справа от текущего-);

         writeln(-7 v удалить слева от текущего-);

         writeln(-0 v выход-);

         writeln(-текущий элемент: -, current^.data);

         readln(n);

         if n=1 then

{Выбор нового текущего элемента}

         begin

                  writeln(--); readln(s);

                  pnt:=current; point:=current;

                  repeat

                          if pnt^.data=s then current:=pnt;

                          pnt:=pnt^.next;

                 until pnt=point;

         end;

         if n=2 then

{Вывод всех элементов}

         begin

                 pnt:=curent; i:=1



                 repeat

                           writeln(i, - v -, pnt^.data);

                           pnt:=pnt^.next; i:=i+1;

                 until pnt=current;

        end;

        if n=3 then

{ Добавление нового элемента справа от текущего}

        begin

                 writeln(-элемент-); readln(s);

                 new(pnt);

                 pnt^.data:=s;

                 pnt^.last:=current;

                 pnt^.next:=current^.next;

                 pnt2:=current^.next;

                 pnt2^.last:=pnt;

                 current^.next:=pnt;

        end;

        if n=4 then

{Добавление нового элемента слева от текущего}

        begin

                 writeln(-элемент-); readln(s);



                 new(pnt);

                 pnt^.data:=s;

                 pnt^.last:=current^.last;

                 pnt^.next:=current;

                 pnt2:=current^.last;

                 pnt2^.next:=pnt;

        end;

        if n=5 and not(current^.next=current) then

        begin

{Удаление текущего элемента}

                  pnt:=current^.last;

                  pnt2^.next:=current^next;

                  pnt2^.last:=current^.last;

                  pnt2:=current^next;

                  dispose(current);

                  current:=pnt2;

        end;

        if n=6 and not(current^.next=current) then

{ Удаление элемента справа от текущего}

        begin

                  pnt:=current^.next;



                  current^.next:=pnt^next;

                  pnt2:=pnt^.next;

                  pnt2^.last:=current;

                  dispose(pnt);

        end;

        if n=7 and not(current^.next=current)then

{Удаление элемента слева от текущего}

        begin

                  pnt:=current^.last;

                  current^.last:=pnt^.last;

                  pnt2:=pnt^.last;

                  pnt2^.next:=current;

                  dispose(pnt);

        end;

until n=0;

end.

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




Содержание раздела