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

    Вначале рассмотрим алгоритм вставки звена после звена, на которое указывает ссылка Res. Пусть ссылка Res указывает на звено, после которого будет производиться вставка нового звена. Изобразим это схематически:

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

    Проверим, является ли звено, на которое указывает ссылка Res, последним в списке. Это осуществляется путем анализа значения операции отношения (*Res).sled!=NULL.

    Пусть звено, на которое указывает Res, не является последним.

1. В heap-области резервируем место для нового динамического объекта, а в информационное поле этого объекта помещаем значение информационного поля звена, которое желательно вставить в двунаправленный список:

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

   
   Рис.2. Вставляемый элемент

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

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

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

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

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

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

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

   
   Рис.5. Результат вставки элемента

    Если элемент, после которого размещается новый элемент, окажется последним в двунаправленном списке, тогда алгоритм изменится следующим образом:

1. Создадим новый элемент и заполним его поля:

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

   
   Рис.6. Вставляемый элемент

2. Осуществим "настройку" указателей:

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

   
   Рис.7. "Настройка" указателей

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

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

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

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