Вопрос 7) Циклические списки

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

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

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

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

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

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

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

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

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

В качестве примера использования циклического списка рассмотрим задачу выбора из N претендентов на приз одного. Для решения этой задачи выстраиваем всех претендентов в круг и убираем каждого М-го человека, постепенно сужая круг. Надо найти человека, который останется последним (и получит приз, если организаторы к тому времени не передумают), или, по-другому, найти порядок отсеивания претендентов. На основе циклического списка нетрудно составить программу, которая читает значения N и M, и затем распечатывает порядок отсеивания.

Сначала создается список с ключами от 1 до N. Затем программа проходит по этому циклическому списку, пропуская M–1 элементом и уничтожая следующий после них узел до тех пор, пока в списке не останется один единственный элемент.

В delphi будет выгледеть примерно так:

Record = link

Inf:integer;

Next:^link;

End;

В программе

Var

Beg,elem link;

I:integer;

Begin

New(beg); // создание списка из 10 элементов

Beg^.next:=nil;

Beg^.inf:=1;

Elem:=beg;

For i:=2 to 10 do

Begin

New(elem^.next);

Elem:=elem^.next;

Elem^.next:=beg;

Elem^.inf:=I;

End;

Elem:=beg; // вывод списка

Writeln(elem^.inf);

Elem:=elem^.next;

While(elem <> beg) do

Begin

Writeln(elem^.inf);

Elem:=elem^.next;

End;

End;

В СИ ++

Struct list{

Int inf;

Struct List *next;

};

void main()

{

List *beg,*elem;

Beg=NULL;

Elem=NULL;

Beg = new list; // создание списка из 10 элементов

Beg->inf=1;

Beg->next=NULL;

Elem=beg;

Fore(int i=2;i<=10;i++)

{

Elem->next = new list;

Elem=elem->next;

Elem->next=beg;

Elem->inf=I;

}

Elem=beg;

Cout<<elem->inf<<endl;

Elem=elem->next;

While(elem != beg)

{

Cout<<elem->inf<<endl;

Elem=elem->next;

}

}