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

Построим теперь алгоритм для удаления звена, стоящего после звена, на которое указывает ссылка Res. Пусть удаляемое звено не является последним, то есть (*(*Res).sled).sled!=NULL. Изобразим этот факт на схеме "до":

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

Исключим звено из списка, "перенастроив" указатели предыдущего и последующего звеньев, а также сохраним адрес удаляемого звена:
```
    q = (*Res).sled;
    (*(*(*Res).sled).sled).pred = Res;
    (*Res).sled = (*(*Res).sled).sled;
```
Рис.2. "Перенастройка" указателей
Осталось только удалить звено, на которое указывает q, из heap-области:
```
    delete q;
```

Если же удаляемый элемент является последним в двунаправленном списке,

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

то алгоритм становится тривиальным:

"Настроим" указатели предпоследнего элемента и конца списка:
```
    q = (*Res).sled; (*Res).sled = NULL; ksp = (*ksp).pred;
```
Рис.4. "Настройка" указателей
Теперь удалим из кучи звено, на которое указывает q:
```
    delete q; 
```
Рис.5. Возврат памяти в кучу

Функция для удаления звена, стоящего после звена, на которое указывает ссылка Res, имеет вид:

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

  if ((*Res).sled==NULL) 
    cout<<"Вы хотите удалить звено за последним звеном!\n";
  else 
    if ((*(*Res).sled).sled!=NULL) 
      { 
        q = (*Res).sled; 
        (*(*(*Res).sled).sled).pred = Res;
        (*Res).sled = (*(*Res).sled).sled; 
        delete q;
      } 
    else 
      {   q = (*Res).sled; (*Res).sled = NULL; 
          *ksp = (**ksp).pred; delete q; }
}

Приведем пример программы, иллюстрирующей применение рассмотренных функций.

Пример: построение двунаправленного списка. Помещение звена в двунаправленный список. Удаление звена из двунаправленного списка. Очистка двунаправленного списка.

#include<iostream.h>
struct node
{
  int elem;
  node *sled;
  node *pred;
};
class Spisok
{
  private:
    node *nsp,*ksp;
  public:
    Spisok() {nsp=ksp=NULL;}
    void Postroenie ();
    void VyvodForward ();
    void VyvodBack ();
    void Ochistka ();
    void InsAfter (int,node*);
    void InsBefore (int,node*);
    void Delete (node*);
    void DelAfter (node*);
    node *PoiskForward (int);
    node *PoiskBack (int);
};
void main ()
{
  Spisok A;
  node *Res;
  int el,el1;
      
  A.Postroenie ();
  A.VyvodForward (); A.VyvodBack ();
      
  cout<<"Введите элемент звена, после которого ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"Введите элемент вставляемого звена: ";
  cin>>el1;
  Res=A.PoiskForward (el);
  if  (Res!=NULL)
    {
      A.InsAfter (el1,Res);
      A.VyvodForward (); A.VyvodBack ();
    }
  else  cout<<"Звена с заданным элементом в списке нет!\n";

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

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

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

  A.Ochistka ();
}

void Spisok::Postroenie ()
//Построение двунаправленного списка с заглавным звеном:
// nsp - указатель на начало списка,
// ksp - указатель на конец списка.
{
  node *rsp;
  int el;

  nsp = new(node);
  rsp = nsp;
  (*nsp).pred = NULL; (*nsp).sled = NULL;
  cout<<"Вводите последовательность:\n";
  cin>>el;
  while  (el!=0)
  {
    (*rsp).sled = new(node);
    (*((*rsp).sled)).pred = rsp; rsp = (*rsp).sled;
    (*rsp).sled = NULL; (*rsp).elem = el;
    cin>>el;
  }
  ksp = rsp;
}

void Spisok::VyvodForward ()
//Вывод содержимого двунаправленного списка от его начала.
// nsp - указатель на начало списка, ksp - указатель на конец списка.
{
  node *rsp;
  rsp = (*nsp).sled;
  cout<<"Двунаправленный список содержит: ";
  while  (rsp!=NULL)
  {
    cout<<(*rsp).elem<<" "; rsp = (*rsp).sled;
  }
  cout<<endl;
}

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

  rsp = ksp;
  cout<<"Двунаправленный список в обратном порядке: ";
  while  ((*rsp).pred!=NULL)
  {
    cout<<(*rsp).elem<<" "; rsp = (*rsp).pred;
  }
  cout<<endl;
}

node *Spisok::PoiskForward (int el)
//Функция возвращает указатель на найденный элемент el
//двунаправленного списка, заданного указателями  nsp
// и ksp, или NULL, если элемент в списке не найден.
{
  node   *q;
  node *Res;
  
  Res = NULL; q = (*nsp).sled;
  while  (q!=NULL && Res==NULL)
    if  ((*q).elem==el) Res = q;
    else  q = (*q).sled;
  return Res;
}

node *Spisok::PoiskBack (int el)
//Функция возвращает указатель на найденный элемент el
//двунаправленного списка, заданного указателями  nsp
// и ksp, или NULL, если элемент в списке не найден.
{
  node   *q;
  node *Res;

  Res = NULL; q = ksp;
  while  (q!=NULL && Res==NULL)
    if  ((*q).elem==el) Res = q;
    else  q = (*q).pred;
  return Res;
}

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

  q = new(node);
  (*q).elem = el;
  if  ((*Res).sled!=NULL)
  {
    (*q).sled = (*Res).sled;
    (*q).pred = (*(*Res).sled).pred;
    (*(*Res).sled).pred = q; (*Res).sled = q;
  }
  else
  {
    (*q).sled = NULL;
    (*q).pred = Res; ksp = q; (*Res).sled = q;
  }
}

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

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

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

  if  ((*Res).sled==NULL) cout<<"Указано последнее звено!\n";
  else
    if  ((*(*Res).sled).sled!=NULL)
    {
      q = (*Res).sled;
      (*(*(*Res).sled).sled).pred = Res;
      (*Res).sled = (*(*Res).sled).sled;
      delete q;
    }
    else
    {
      q = (*Res).sled; (*Res).sled = NULL;
      ksp = (*ksp).pred; delete q; }
}

void Spisok::Ochistka ()
//Удаление двунаправленного списка из памяти.
// nsp - указатель на заглавное звено списка,
// ksp - указатель на последнее звено списка.
{
  node *q,*q1;

  q  = nsp; q1 = (*q).sled;
  while  (q1!=NULL)
  {
    q = q1; q1 = (*q1).sled; delete q;
  }
  delete nsp; nsp = ksp = NULL;
}

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

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

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