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

Рассмотрим алгоритм удаления звена справа. Пусть уже построен дек на базе двунаправленного списка без заглавного звена:

Рис.1. "Начальная" позиция

Приступим к пошаговому выполнению алгоритма:

Сохраним адрес удаляемого элемента и "настроим" указатель конца дека:
```
    q = kd; 
    kd = (*kd).pred;
    (*kd).sled = NULL;
```
Рис.2. "Настройка" указателей
Возвратим память в кучу:
```
    delete q;
```
Рис.3. Возврат памяти в кучу

Запишем функцию на языке C++, реализующую рассмотренный алгоритм:

void DelRight (node **nd, node **kd,int *el)
// Удаление звена из дека справа с помещением элемента 
//   удаляемого звена в переменную el.
// *nd - указатель на начало дека.
// *kd - указатель на конец дека.
{
  node *q;
  if ((**kd).pred!=NULL)
  { q = *kd; *el =(*q).elem; *kd = (**kd).pred; (**kd).sled = NULL; delete  q;}
  else
  { // В деке находится один элемент.
    q = *kd; *el =(*q).elem; *nd = *kd = NULL; 
    delete q; cout<<"Дек пуст!\n";}
}

Приведем обобщающий пример. Построение дека, вставка и удаление элементов из дека.

#include<iostream.h>
struct node
{
  int elem;
  node *sled;
  node *pred;
};

class Spisok
{
  private:
    node *nd;//Указатель на начало дека.
    node *kd;//Указатель на конец  дека.
    int klad;//Информационное поле удаленного элемента.
  public:
    void BuiltDeck ();
    void VyvodDeck ();
    void InsLeft (int);
    void InsRight (int);
    void DelLeft ();
    void DelRight ();
    int Get_Klad () {return klad;}
    void Ochistka();
};

void main ()
{
  Spisok A;
  int el;

  A.BuiltDeck ();
  A.VyvodDeck ();
  cout<<"Введите элемент звена, вставляемого справа: ";
  cin>>el; A.InsRight (el); A.VyvodDeck ();
  cout<<"Введите элемент звена, вставляемого слева: ";
  cin>>el; A.InsLeft (el); A.VyvodDeck ();
  cout<<"Удалим звено справа: \n";
  A.DelRight (); A.VyvodDeck ();
  cout<<"Был удален элемент: "<<A.Get_Klad()<<endl;
  cout<<"Удалим звено слева: \n";
  A.DelLeft (); A.VyvodDeck ();
  cout<<"Был удален элемент: "<<A.Get_Klad()<<endl;
  A.Ochistka();
}

void Spisok::BuiltDeck ()
// Построение дека на базе двунаправленного
// списка с заглавным звеном.
// nd - указатель на начало дека,
// *kd - указатель на конец дека.
{
  node *q;
  node *z;
  int  el;

  nd = new(node);
  z = nd;
  (*nd).pred = (*nd).sled = NULL;
  cout<<"Введите последовательность: \n";
  cin>>el;
  while  (el!=0)
  { (*z).sled = new (node);
    (*((*z).sled)).pred = z;
    z = (*z).sled; (*z).sled = NULL;
    (*z).elem = el; cin>>el;}
    if  ((*nd).sled!=NULL)
      { q = nd; nd = (*nd).sled; (*nd).pred = NULL;
        kd = z; delete q; }
    else 
      { delete nd; nd = kd = NULL; }
}

void Spisok::VyvodDeck ()
// Вывод содержимого дека.
// nd - указатель на начало дека.
{
  node *z;

  z = nd; cout<<"Содержимое дека: ";
  if  (z!=NULL)
    while  (z!=NULL)
     { cout<<(*z).elem<<" "; z = (*z).sled; }
  else  cout<<"он пуст!\n";
  cout<<endl;
}
void Spisok::InsLeft (int el)
// Добавление звена, содержащего элемент el, в дек слева.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  q = new(node);
  (*q).elem = el;
  if  (nd==NULL)
    { nd = q; (*q).sled = (*q).pred = NULL; kd = q; }
  else
    { (*q).sled = nd; (*q).pred = NULL;
      (*nd).pred = q; nd = q; }
}

void Spisok::InsRight (int el)
// Добавление звена, содержащего элемент el, в дек справа.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  q = new(node);
  (*q).elem = el;
  if  (kd==NULL)
    { nd = q; (*q).sled = (*q).pred = NULL; kd = q; }
  else
    { (*q).sled = NULL; (*q).pred = kd;
      (*kd).sled = q; kd = q; }
}

void Spisok::DelLeft ()
// Удаление звена из дека слева с помещением
// элемента удаляемого звена в переменную klad.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  if  ((*nd).sled!=NULL)
    { q = nd; klad =(*q).elem;
      nd = (*nd).sled; (*nd).pred = NULL; delete q;}
  else
    { // В деке находится один элемент.
      q = nd; klad =(*q).elem;
      nd = kd = NULL; delete q;cout<<"Дек пуст!\n"; }
}

void Spisok::DelRight ()
// Удаление звена из дека справа с помещением
// элемента удаляемого звена в переменную klad.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  if  ((*kd).pred!=NULL)
    { q = kd; klad =(*q).elem;
      kd = (*kd).pred; (*kd).sled = NULL; delete q; }
  else
    {// В деке находится один элемент.
     q = kd; klad =(*q).elem;
     nd = kd = NULL; delete q; cout<<"Дек пуст!\n"; }
}

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

  q = nd;
  q1 = (*q).sled;
  while (q1!=NULL)
    { delete q; q = q1; q1 = (*q).sled;}
  delete q;
  nd = kd = NULL;
}

Текст этой программы можно взять здесь.

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

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