Кольцевой список

Если последний элемент линейного списка связать с первым посредством указателя Next, то получится кольцевойодносвязный список, как показано на рис. 9.10.

Рис. 9.10. Односвязный кольцевой список

Для создания двусвязного кольцевогосписка необходимо связать последний элемент с первым как по указателю Next, так и по указателю Pred. Двусвязный кольцевой список показан на рис. 9.11.

Рис. 9.11. Двусвязный кольцевой список

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

В качестве примера использования двусвязного кольцевого списка решим следующую задачу. Дети стали в круг, взявшись за руки. Начав отсчет от первого, каждый i-тый выходит из круга, а круг смыкается. Кто останется?

Первая часть задачи — создание списка. Процедура Insert2 вставляет элемент в двусвязный список.

Листинг 9.8. Процедура Insert2 вставляет элемент в двусвязный список

procedure Insert2(var r: PNode; e: TInfo);

// вставка элемента в двусвязный список

var t: PNode;

begin

if r=Nil then begin // список пуст, создание первого элемента

new(r);

with r^ do begin

Info:=e;

Next:=r; Pred:=r; // ссылки замыкаем на себя

end;

end

else begin

new(t);

with t^ do begin

Info:=e; Next:=r^.Next; Pred:=r;

end;

r^.Next^.Pred:=t; r^.Next:=t;

end

end;

Вызвав эту процедуру K раз, получим список, содержащий K элементов. Указатель списка стоит на первом включенном в список элементе.

Вторая часть задачи – удаление i-того элемента, считая от первого. Алгоритм прост: отсчитывается заданное количество элементов, требуемый элемент удаляется, указатель на список переносится на следующий за удаленным элемент. Когда в списке останется только один элемент, его поля Pred и Next будут указывать на него самого. Функция CountDel реализует этот алгоритм.

Листинг 9.9. Удаление элемента

function CountDel (var p: PNode; step: integer): PNode;

var r,t: PNode;

i : integer;

begin

r:=p;

repeat

for i:=1 to step do r:=r^.Next;

t:=r^.Pred; // этот элемент будем удалять

t^.Pred^.Next:=r; r^.Pred:=t^.Pred; // замыкаем круг

dispose(t)

until r=r^.Next;

Result:=r;

end;