Шаг 33.
Двунаправленные кольцевые списки

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

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

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

    Мы приведем два варианта структуры кольцевых двунаправленных списков.

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

    Взгляните на приведенную ниже схему:


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

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


Рис.2. Пустой кольцевой двунаправленный список

    Проще всего построить кольцевой двунаправленный список с удаленным заглавным звеном с использованием алгоритма построения двунаправленного списка с заглавным звеном и последующего "замыкания" кольца. Это реализовано в приведенной ниже функции: 

void BuiltRing (node **nsp)
// Построение двунаправленного кольцевого списка nsp 
//  с удаленным заглавным звеном.
// *nsp - указатель на заглавное звено списка.
{
  node *r;
  int el;
  // Построим заглавное звено будущего кольцевого списка.
  *nsp = new(node);
  r = *nsp; (**nsp).pred = NULL; (**nsp).sled = NULL;
  cout<<"Вводите элементы звеньев списка: \n";
  cin>>el;
  while (el!=0)
    { (*r).sled = new(node); (*((*r).sled)).pred = r; 
       r = (*r).sled; (*r).sled = NULL; (*r).elem = el; 
      cin>>el; }
  // Образуем кольцевой список с удаленным заглавным звеном.
  if ((**nsp).sled!=NULL)
    {(*((**nsp).sled)).pred = r; (*r).sled = (**nsp).sled;}
  else  cout<<"Кольцевой список пуст!\n";
}

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

void VyvodLeftRight (node **nsp)
// Вывод содержимого двунаправленного кольцевого списка 
// с удаленным заглавным звеном "по часовой стрелке".
// *nsp - указатель на заглавное звено списка.
{
  node *r;

  cout<<"Кольцевой список: ";
  if ((**nsp).sled!=NULL)
    { cout<<(*((**nsp).sled)).elem)<<" ";
       r = (*((**nsp).sled)).sled; 
      while (r!=(**nsp).sled) 
        { cout<<(*r).elem)<<" "; r = (*r).sled; } 
      cout<<endl;}
  else cout<<"пуст!";
}

    Пример. Построение двунаправленного кольца с удаленным заглавным звеном, вывод содержимого кольцевого списка, вставка звена, удаление звена. 
#include<iostream.h>
struct node
{
  int elem;
  node *sled;
  node *pred;
};

class Spisok
{
  private:
    node *nsp;
  public:
    Spisok() {nsp=NULL;}
    void BuiltRing ();
    void VyvodLeftRight ();
    void VyvodRightLeft ();
    void InsAfter (node*,int);
    void InsBefore (node*,int);
    void Delete (node*);
    void DelAfter (node*);
    node *SearchRing (int);
    void Ochistka();
};

void main ()
{
  Spisok A;
  node *Res;
  int el,el1;

  A.BuiltRing ();
  cout<<"Содержимое кольца 'по часовой стрелке': \n";
  A.VyvodLeftRight ();
  cout<<"Содержимое кольца'против часовой стрелки': \n";
  A.VyvodRightLeft ();
  cout<<"Введите элемент звена, после которого ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"Введите элемент вставляемого звена: ";
  cin>>el1;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    {A.InsAfter (Res,el1); A.VyvodLeftRight ();}
  else  cout<<"Звена с таким элементом в списке нет!\n";
  cout<<"Введите элемент звена, перед которым ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"Введите элемент вставляемого звена: ";
  cin>>el1;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    { A.InsBefore (Res,el1); A.VyvodLeftRight (); }
  else  cout<<"Звена с таким элементом в списке нет!\n";

  cout<<"Введите элемент звена, который ";
  cout<<"надо удалить: ";
  cin>>el;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    { A.Delete (Res); A.VyvodLeftRight (); }
  else  cout<<"Звена с таким элементом в списке нет!\n";

  cout<<"Введите элемент звена, после которого ";
  cout<<"осуществляется удаление: ";
  cin>>el;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    { A.DelAfter (Res); A.VyvodLeftRight (); }
  else  cout<<"Звена с таким элементом в списке нет!\n";
  A.Ochistka();
}

void Spisok::BuiltRing ()
// Построение двунаправленного кольцевого списка nsp
//          с удаленным заглавным звеном.
// nsp - указатель на заглавное звено списка.
{
  node *r;
  int el;
  //Построим заглавное звено кольцевого списка.
  nsp = new(node);
  r = nsp; (*nsp).pred = NULL; (*nsp).sled = NULL;
  cout<<"Вводите элементы списка: \n";
  cin>>el;
  while  (el!=0)
  {
    (*r).sled = new (node);
    (*((*r).sled)).pred = r; r = (*r).sled;
    (*r).sled = NULL; (*r).elem = el;
    cin>>el;
  }
  //А теперь - образуем кольцевой список!
  if  ((*nsp).sled!=NULL)
    { (*((*nsp).sled)).pred = r; (*r).sled = (*nsp).sled; }
  else
    cout<<"Кольцевой список пуст!\n";
}

void Spisok::VyvodLeftRight ()
// Вывод содержимого двунаправленного кольцевого списка
// с удаленным заглавным звеном "по часовой стрелке".
// nsp - указатель на заглавное звено списка.
{
  node *r;

  cout<<"Кольцевой список: ";
  if  ((*nsp).sled!=NULL)
  {
    cout<<(*((*nsp).sled)).elem<<" ";
    r = (*((*nsp).sled)).sled;
    while  (r!=(*nsp).sled)
      { cout<<(*r).elem<<" "; r = (*r).sled; }
    cout<<endl;
  }
  else cout<<"пуст!";
}

void Spisok::VyvodRightLeft ()
// Вывод содержимого двунаправленного кольцевого списка
// с удаленным заглавным звеном "против часовой стрелки".
// nsp - указатель на заглавное звено списка.
{
  node *r;

  cout<<"Кольцевой список: ";
  if  ((*nsp).sled!=NULL)
  {
    cout<<(*((*((*nsp).sled)).pred)).elem<<" ";
    r = (*((*((*nsp).sled)).pred)).pred;
    while  (r!=(*((*nsp).sled)).pred)
      { cout<<(*r).elem<<" "; r = (*r).pred; }
    cout<<endl;
  }
  else cout<<"пуст!";
}

node *Spisok::SearchRing (int el)
// Поиск элемента el в кольцевом двунаправленном списке
//             с удаленным заглавным звеном.
// nsp - указатель на заглавное звено списка.
{
  node   *q;
  node   *p;
  node *Res;

  Res = NULL; p = nsp;
  if  ((*((*p).sled)).elem==el) Res = (*p).sled;
  else
  {
    q = (*((*p).sled)).sled;
    while  (q!=(*p).sled && Res==NULL)
      if  ((*q).elem==el) Res = q;
      else  q = (*q).sled;
  }
  return Res;
}

void Spisok::InsAfter (node *Res,int el)
// Вставление в кольцевой двунаправленный список звена
// с информационным полем el после  звена, на  которое
// указывает ссылка Res.
{
  node *q;

  q = new(node);
  (*q).elem = el; (*q).sled = (*Res).sled;
  (*q).pred = (*(*Res).sled).pred;
  (*(*Res).sled).pred = q; (*Res).sled = q;
}

void Spisok::InsBefore (node *Res,int el)
// Вставка в кольцевой двунаправленный список звена
// с информационным полем el перед звеном, на  которое
// указывает ссылка Res.
// nsp - указатель на заглавное звено списка.
{
  node *q;

  q = new(node);
  (*q).elem = el;
  (*q).sled = (*(*Res).pred).sled; (*q).pred = (*Res).pred;
  (*(*Res).pred).sled = q; (*Res).pred = q;
  if  (Res==(*nsp).sled) (*nsp).sled = q;
}

void Spisok::Delete (node *Res)
// Удаление из кольцевого двунаправленного списка
// звена, на которое указывает ссылка Res.
// nsp - указатель на заглавное звено списка.
{
  if  ((*Res).sled==Res)
    { (*nsp).sled = NULL; delete Res; }
  else
  {
    (*(*Res).sled).pred = (*Res).pred;
    (*(*Res).pred).sled = (*Res).sled;
    if  ((*nsp).sled==Res)
      // Удаляем "первое" звено кольца.
      (*nsp).sled = (*Res).sled;
    delete Res;
  }
}

void Spisok::DelAfter (node *Res)
// Удаление из кольцевого двунаправленного списка звена,
// расположенного  после  звена, на  которое  указывает
// ссылка Res.
// nsp - указатель на заглавное звено списка.
{
  node *q;

  if  ((*Res).sled==Res)
    { (*nsp).sled = NULL; delete Res;}
  else
  {
    q = (*Res).sled;
    (*(*(*Res).sled).sled).pred = (*(*Res).sled).pred;
    (*Res).sled = (*(*Res).sled).sled;
    if  ((*(*nsp).sled).pred==Res)
      // Удаляем "последнее" звено кольца.
      (*nsp).sled = (*Res).sled;
    delete q;
  }
}

void Spisok::Ochistka()
{
  node *q,*q1;

  q = (*((*nsp).sled)).sled;
  q1 = (*q).sled;
  while (q1!=(*((*nsp).sled)).sled)
    { delete q; q=q1; q1=(*q1).sled; }
  delete q;
  delete nsp;
}
Текст этой программы можно взять здесь.

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


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

    Мы будем называть подобную структуру кольцевым двунаправленным списком с включенным заглавным звеном.

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


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

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

    Этого недостатка лишен первый способ организации списка, но в этом случае труднее реализуется добавление звена в конец списка.

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




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