Циклические списки
Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент.
Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей.
Рис.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.
В данном примере указатель на первый элемент списка отсутствует. Для предотвращения зацикливания при обходе списка во время поиска указатель на текущий элемент предварительно копируется и служит ограничителем.
