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

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

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

Рис.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 сделать текущим’);

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

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

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

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

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

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

writeln(‘0 выход’);

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, ‘ ‘, 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.

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