Шаг 13.
Кольцевые списки. Основные операции

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


    На этом шаге мы приведем лишь обобщающий пример. Приведем текст программы, осуществляющий включение звена в кольцо с удаленным заглавным звеном, а также удаление звена с заданным значением информационного поля из кольца с удаленным заглавным звеном.
#include<iostream.h>
struct node
{
  int elem;
  node *sled;
};
class Spisok {
  private:
    node *phead,*Res;
  public:
    Spisok () {phead=new(node);Res=NULL;}
    ~Spisok() {delete phead;}
    void POSTROENIE ();
    void VYVOD ();
    node *POISK (int);
    void InsAfter (int);
    void InsBefore (int);
    void Delete ();
    void DelAfter ();
    void OCHISTKA();
};

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

  A.POSTROENIE();
  A.VYVOD();
  cout<<"\nВведите элемент звена, после которого ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"\nВведите элемент вставляемого звена: ";
  cin>>el1;
  if  (A.POISK(el)!=NULL)
  { A.InsAfter (el1); A.VYVOD ();}
  else  cout<<"Звена с заданным элементом в кольце нет!";
  cout<<"\nВведите элемент звена, перед которым ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"Введите элемент вставляемого звена: ";
  cin>>el1;
  if  (A.POISK(el)!=NULL)
  {
    A.InsBefore(el1); A.VYVOD ();
  }
  else  cout<<"Звена с заданным элементом в кольце нет!";
  cout<<"\nВведите элемент удаляемого звена: ";
  cin>>el;
  if  (A.POISK(el)!=NULL)
  {
    A.Delete (); A.VYVOD ();
  }
  else  cout<<"Звена с заданным элементом в кольце нет!";
  cout<<"\nВведите элемент звена, ";
  cout<<"после которого нужно удалять: ";
  cin>>el;
  if  (A.POISK(el)!=NULL)
  {
    A.DelAfter (); A.VYVOD ();
  }
  else  cout<<" Звена с заданным элементом в кольце нет!";
  A.OCHISTKA();
}

void Spisok::POSTROENIE ()
//Построение кольцевого списка с удаленным заглавным звеном.
//phead - указатель на заглавное звено.
{
  node *t;
  int  el;

  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 Spisok::VYVOD ()
//Вывод содержимого кольцевого списка с удаленным заглавным звеном.
//phead - указатель на заглавное звено.
{
  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";
}

node *Spisok:: POISK (int el)
//Поиск элемента el в кольцевом списке phead.  
//Если элемент найден, то Res содержит указатель на звено,
//содержащее элемент el. В противном случае - NULL. 
{
  node *t;
  Res = NULL; t =(*phead).sled;
  while ((*t).sled!=(*phead).sled && Res==NULL)
  if  ((*t).elem==el) Res = t;
  else  t = (*t).sled;

  if  (Res==NULL && (*t).elem==el)
    Res = t;

  return Res;
}

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

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

void Spisok::InsBefore (int el)
//Включение звена с информационным полем el в кольцо
//перед звеном, на которое указывает ссылка Res. 
{
  node *q;
  q = new (node);
  (*q).elem = (*Res).elem; (*q).sled = (*Res).sled;
  (*Res).elem = el; (*Res).sled = q;
}

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

  if  ((*Res).sled!=(*phead).sled)
  {
    q = (*Res).sled;
    (*Res).elem = (*((*Res).sled)).elem;
    (*Res).sled = (*((*Res).sled)).sled;
    delete q;
  }
  else  if  ((*Res).sled==Res)
        {
           //В кольце единственное звено.
           q = (*phead).sled; (*phead).sled = NULL;
          delete q; cout<<"Кольцо пусто!";
        }
       else
       {
         //Удаляется "последнее" звено кольца.
         z = phead; q = (*phead).sled;
         while  (q!=Res)
           { z = q; q = (*q).sled; }
         (*z).sled = (*((*z).sled)).sled;
         delete q;
        }
}

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

  if  ((*Res).sled!=(*phead).sled)
  {
    //Ссылка Res не указывает на последнее звено. 
    q = (*Res).sled;
    (*Res).sled = (*((*Res).sled)).sled;
    delete q;
  }
  else  if  ((*Res).sled==Res)
          {
            //Удаляемое звено - единственное в кольце. 
            q = (*phead).sled; (*phead).sled = NULL;
            delete q; cout<<"Кольцо пусто!";
           }
          else
          {
            //Удаляемое звено - первое в кольце и не единственное.
            q = (*phead).sled;
           (*Res).sled = (*((*Res).sled)).sled;
           (*phead).sled  = (*Res).sled; delete q;
           }
}

void Spisok::OCHISTKA()
{
  node *q,*q1;// Рабочие указатели.
  q = phead;
  q1 = (*q).sled; // Указатель q1 "опережает" указатель q.
  do {
        q = q1;
        q1 = (*q1).sled;
        delete q;
       }
  while (q1!=(*phead).sled);
}
Текст этой программы можно взять здесь.

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




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