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

    Рассмотрим алгоритм вставки звена перед звеном, на которое указывает ссылка Res. Опишем его с помощью схем "до и после" Д.Кнута:

1. Создаем элемент:

       q = new(node);
       (*q).elem = Элем;
   

   
   Рис.1. Создание элемента

2. "Настраиваем" его указатели:

       (*q).sled = (*(*Res).pred).sled;
       (*q).pred = (*Res).pred;
   

   
   Рис.2. "Настройка" указателей созданного элемента

3. "Настраиваем" указатели элементов списка на вставляемый элемент:

       (*(*Res).pred).sled = q;
       (*Res).pred = q;
   

   
   Рис.3. "Настройка" указателей элементов списка на созданный элемент

4. В итоге получим:

   
   Рис.4. Итоговый результат

    Оформим алгоритм помещения звена в список в виде функции:

void InsBefore (int el, node **nsp, node **ksp, 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;
}

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

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