Шаг 25.
Кольцевые однонаправленные списки с включеным заглавным звеном

    На этом шаге мы рассмотрим формирование кольцевого однонаправленного списка с включенным заглавным звеном..

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


    Замечание.
    Кольцевой список не имеет первого и последнего элемента.

Кольцевые однонаправленные списки с включенным заглавным звеном

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


Рис.1. Однонаправленный кольцевой список с включенным заглавным звеном

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


Рис.2. Пустой кольцевой список с включенным заглавным звеном

    Проведем процедуру построения кольцевого однонаправленного списка с включенным заглавным звеном:

 Procedure Create_Ring (var pBegin: PtrRec);
    Var pAux : PtrRec;
          el : TypeElement;
    Begin
         New (pBegin);
         pAux := pBegin;
         pAux^.pNext := Nil;
         Write ('Введите последовательность... ');
         Write ('Признак окончания ввода - 0');
         ReadLn (el);
         While el <> 0 do	{формируем список}
              Begin
                 New (pAux^.pNext);
                 pAux := pAux^.pNext;
                 pAux^.Element := el;
                 pAux^.pNext := Nil;
                 ReadLn (el);
              End;
         pAux^.pNext := pBegin;	{Замкнем кольцо на заглавное звено} 
    WriteLn;
 End;

    На следующем шаге мы поговорим о просмотре однонаправленного списка с включенным заглавным звеном.




Предыдущий шаг Содержание Следующий шаг