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

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                       .
    bool Symmetry(TwoWayList& L)
    {
         Node *b=L.head, *e=L.tail;
         if(b==NULL) return false;

           // просмотр элементов с начала и с конца списка
           // до тех пор, пока значения соответствующих элементов
           // равны и не просмотрены все элементы списка
           while(b->info==e->info && b!=e && b->prev!=e)
           {
                 b=b->next;
                 e=e->prev;
             }

            // определение условия, по которому произошел
            // выход из цикла
            if(b->info!=e->info)
                // найдена несимметричная пара элементов
                 return false;
           // список симметричен
           return true;
    }

    Задача 3. Дан двусвязный список, содержащий целые числа. Отсортиро-
вать его методом вставок.
    Метод вставок применительно к массиву можно описать так. Пусть дан
массив a[0]…a[n]. Каждый элемент a[i] (i изменяется от 1 до n) вставляется на
подходящее место в уже упорядоченной совокупности a[0]…a[i-1]. Это место
определяется при обратном проходе по массиву от (i-1)-го элемента до эле-
мента с меньшим значением, чем a[i], или, если такого элемента не нашлось,
до начала массива.
    Если список пуст или состоит из одного элемента, сортировать его не
нужно. Для просмотра всех элементов списка, начиная со второго, создается
переменная current. Если current стоит на своем месте, т. е. предыдущий
элемент имеет меньшее значение информационного поля, то current либо
сдвигается на следующий узел, либо происходит выход из цикла, когда до-
стигнут конец списка.
    Если требуется изменить позицию элемента current, то выполняются
следующие действия:
    1) удалить current из списка, присоединив «хвост» списка к предыду-
щему элементу;
    2) определить его место в уже отсортированной части списка;

                                            84