Кольцевой список
Если последний элемент линейного списка связать с первым посредством указателя 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 элементов. Указатель списка стоит на первом включенном в список элементе.
Вторая часть задачи – удаление step-того элемента, считая от первого. Алгоритм прост: отсчитывается заданное количество элементов, требуемый элемент удаляется, указатель на список переносится на следующий за удаленным элемент. Когда в списке останется только один элемент, его поля 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;