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

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

Воспользуемся схемами "до и после":

Определяем местоположение следующего за удаляемым элемента.
```
    q = (*Res).sled;
```
Рис.1. Сохранение адреса следующего элемента
Определяем, не является ли удаляемое звено последним. В зависимости от этого реализация алгоритма будет различной.
```
    if (q!=NULL)
    {//Если удаляемое звено не является последним, то ...
      (*Res).elem = (*q).elem;
      (*Res).sled = (*q).sled;
```
Рис.2. "Переписываем" следующий элемент в удаляемый
Последняя тонкость: присоединение "кусочка" heap-области к списку свободной памяти:
```
      delete q;
```
Рис.3. Возврат памяти в кучу
```
    }
```
Теперь рассмотрим ситуацию, когда удаляемое звено является последним звеном списка:

Рис.4. Удаляемый элемент - последний

Найдем указатель на предпоследнее звено линейного списка с помощью двух вспомогательных указателей q1 и q2, перемещающихся по списку "параллельно друг другу", причем указатель q2 "опережает" указатель q1 на один шаг.
```
    q1 = phead; q2 = (*q1).sled; //Инициализация указателей.
    while (q2!=Res)
    { q1 = q2; q2 = (*q2).sled;}
```
После выполнения цикла while, мы получим следующую ситуацию:

Рис.5. Положение указателей
Приступим к удалению:
```
    (*q1).sled = NULL; q2 = NULL; delete  (Res);
```
Рис.6. После удаления

Приведем текст функции удаления:

void YDALE1 (node **phead, node **Res)
//Удаление звена, на которое указывает ссылка *Res 
//из однонаправленного списка с заглавным звеном. 
//*phead - указатель на заглавное звено списка.  
{
  node *q,*q1,*q2;
  q = (**Res).sled;
  if (q!=NULL)
  { (**Res).elem = (*q).elem; (**Res).sled = (*q).sled;delete q; }
  else
  { q1 = *phead; q2 = (*q1).sled; //Инициализация указателей.
     while (q2!=*Res) 
        { q1 = q2; q2 = (*q2).sled; } 
    (*q1).sled = NULL; q2 = NULL; delete *Res;
  }
}

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

#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 YDALE ();
     void YDALE1();
     void OCHISTKA();
 };

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

  A.POSTROENIE ();
  A.VYVOD ();
  cout<<"\nВведите элемент звена, после которого ";
  cout<<"осуществляется удаление:\n";
  cin>>el;
  Res_Zn=A.POISK (el);
  if  (Res_Zn!=NULL && (*Res_Zn).sled!=NULL)
    {A.YDALE (); A.VYVOD ();}
  else  cout<<"Звена с заданным элементом в списке нет!";
  cout<<"\nВведите удаляемый элемент звена:\n";
  cin>>el;
  Res_Zn=A.POISK (el);
  if  (A.POISK (el)!=NULL)
  {
    A.YDALE1 (); A.VYVOD (); cout<<endl;
  }
  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; (*t).sled = NULL;
    cin>>el;
  }
}

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

  t = phead; t = (*t).sled;
  cout<<"Список: ";
  while  (t!=NULL)
  {
	 cout<<(*t).elem <<" ";
    t = (*t).sled;
  }
}

 node *Spisok::POISK (int el)
//Поиск звена с элементом el в списке, заданном указателем phead.
//В случае успешного поиска в Res находится адрес искомого звена  
//списка. В противном случае Res содержит NULL.
{
  node *t;

  Res = NULL; t = phead; t = (*t).sled;
  while  (t!=NULL && Res==NULL)
    if  ((*t).elem==el)  Res = t;
    else  t = (*t).sled;
  return Res;
}

void Spisok::YDALE ()
//Удаление звена, расположенного после звена,
//на которое указывает ссылка Res. 
{
  node *q;
  q = (*Res).sled;
  if  (q!=NULL)
  {
    //Если звено, после которого нужно удалять,
    //не является последним, то:
    (*Res).sled = (*(*Res).sled).sled; delete q;
  }
  else
    cout<<"Звено с заданным элементом - последнее!\n";
}

void Spisok::YDALE1 ()
//Удаление звена, на которое указывает ссылка Res.
{
  node *q,*q1,*q2;

  q = (*Res).sled;
  if  (q!=NULL)
  {
    (*Res).elem = (*q).elem; (*Res).sled = (*q).sled;
    delete q;
  }
  else
  {
     q1 = phead; q2 = (*q1).sled;
    while  (q2!=Res)
    {
        q1 = q2; q2 = (*q2).sled;
    }
    (*q1).sled = NULL; q2 = NULL; delete Res;
  }
}

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

  q = phead;
  q1 = (*q).sled; // Указатель q1 "опережает" указатель q.
  while (q1!=NULL)
  { q = q1; q1 = (*q1).sled; delete q;}
}

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

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

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