Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 85 стр.

            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
    3) вставить current на найденное место.
    При удалении сохраняем адреса предыдущего и следующего элементов в
переменных help1 и help2 соответственно. Далее соединяем эти два узла.
Если следующего узла не существует, т.е. current был последним узлом,
L.tail устанавливается на help1.
    Для определения места вставки элемента, двигаемся от узла help1 к на-
чалу списка до тех пор, пока не встретим узел со значением, меньшим «встав-
ляемого», или пока не достигнем начала списка. Если current нужно вста-
вить на первое место, то связываем элементы current и help1 и меняем
начало списка (L.head=current). Если же позиция вставки current не
начальная, то сохраняем адрес элемента, перед которым нужно вставить
current, в переменную help3, и организуем связи с учетом вставки
current. Далее повторяем те же действия для следующего элемента, адрес
которого был сохранен в переменной help2.

   // определение функции сортировки списка методом вставок
   void SortList(TwoWayList& L)
   {
         Node* current,*help1,*help2,*help3;
         if(L.head==L.tail) return;
         current=L.head->next;
         bool f=true; // булева переменная, которая принимает
                      // значение true, если конец списка
                      // не достигнут, а иначе – false
         while(f)
         {
              if(current->prev->info > current->info)
              {
                   // значение элемента current меньше,
                   // чем значение последнего элемента в уже
                   // упорядоченной части списка

                     //извлекаем элемент current из списка
                     help2=current->next;
                     help1=current->prev;
                     help1->next=current->next;
                     // если элемент current был
                     // последним в списке
                     if(current==L.tail)
                     {
                           // переносим конец списка
                           // на предыдущий элемент

                                      85