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

Хотя структура в виде линейного списка является весьма полезной, у нее имеется ряд недостатков. Сейчас мы рассмотрим другие методы организации списков и использование их с целью устранения этих недостатков.

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

Предположим теперь, что в структуре линейного списка было сделано изменение, при котором поле sled последнего элемента содержит указатель "назад" или на заглавное звено, или на элемент, следующий за заглавным звеном.

Под кольцевым (циклическим) списком понимается список, в котором указатель из некоторой ячейки направлен на такое место в списке, откуда данная ячейка может быть достигнута снова [1]. Очевидно, что теперь мы можем из любого звена списка, "перемещаясь" по указателям достичь любого другого звена.

Кольцевым списком (кольцом) на базе линейного однонаправленного списка называется линейный список, в котором указатель из некоторого звена направлен на такое звено в списке, из которого данное звено может быть достигнуто вновь.

Опишем два способа представления однонаправленного кольцевого списка с заглавным звеном:

Рис.1. Кольцо с удаленным заглавным звеном

Такой кольцевой список будем называть кольцевым списком с удаленным заглавным звеном.

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

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

Рис.3. Кольцо с включенным заглавным звеном

А этот кольцевой список назовем кольцевым списком с включенным заглавным звеном.

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

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

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

Сказанное легко формализуется:

void POSTROENIE (node **phead)
//Построение кольцевого списка с заглавным звеном.
//*phead - указатель на заглавное звено.
{
  int el;
  struct node *t;
  // Вначале сформируем заглавное звено.
  *phead = new (node);
  t = *phead; (*t).sled = NULL;
  cout<<"Вводите элементы кольца: "; cin>>el;
  while (el!=0)
  { (*t).sled = new (node); t = (*t).sled; (*t).elem = el; 
    cin>>el;
  }
  (*t).sled = (*(*phead)).sled;
}

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

void VYVOD (node **phead)
//Вывод содержимого кольцевого списка с удаленным 
// заглавным звеном. 
//*phead - указатель на заглавное звено.
{
  struct node *t;
  t = (**phead).sled; cout<< "Кольцо: ";
  if (t!=NULL)
  { cout<<(*t).elem; t = (*t).sled; 
     while (t!=(**phead).sled) 
      { 
        cout<<(*t).elem; 
        t = (*t).sled; }
      }
  else cout<<"пусто!\n";
}

⁽¹⁾Фостер Дж. Обработка списков. - М.: Мир, 1974. - 72 с.

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

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