29/04

#include <stdio.h>
#include <stdlib.h>


struct point {
 int x;
 int y;
 struct point *next;
};
void SortList(struct point **list)
{
if (*list) //Проверяем, если список не пуст, существует хотя бы один элемент, то выполняем
//сортировку
{//Сортировать мы будем методом вставки. Так как он очень удобен для реализации на списках.
//Основная идея, сортировки заключается в том, мы будем строить новый список из существующих
//элементов, следующим образом. Из текущего списка, каждый раз будем брать элемент (берем из
//головы так, как это самая простая операция).
//Разрываем связь между выбранным элементом, тем самым исключая его из текущего списка.
//Обязательно, все поля, отвечающие за хранения адресов (это общий случай), с помощью
//которых устанавливалась связь между элементами очищается. Теперь элемент становится
//самостоятельным.
//Этот элемент нужно добавить в новый список, не нарушая порядка в нем.
//Далее, этот элемент вставляется в новый список. С этой целью нужно найти нужную позицию в
//новом списке, и вставить этот элемент. Т.е.
//В этой задаче, воспользуемся операцией - добавление элемента после заданного (только без
//создания нового элемента).
//Т.е. в новом упорядоченном списке, нужно будет найти позицию, после которой добавим
//элемент, не нарушая порядка в нем.
//Рассмотрим случаи, которые могут возникнуть.
//1. Список может быть пустым - в этом случае инициализируем newList
//2. Значение элемента меньше, чем значение в голове списка, следовательно, в этом случае добавляем
//элемент в голову.
//3. Общая ситуация, в которой ищем нужную позицию.
//Запишем код.
struct point *newList = NULL, *elem = NULL;
// Берем первый элемент и добавляем его в пустой список
elem = *list;//Устанавлиывем указатель на головной элемент списка.
*list = (*list)->next;// Переходим на следующий элемент.
elem->next = NULL; // Сообщаем элементу, что у него нет последующего. Другими словами, разрушили
//связь, сделали его самостоятельным.
// Добавляем в новый список. Так как эта операция выполняется только один раз, следовательно мы ее
//выполняем вне цикла.
newList = elem;
//Организуем общий цикл, в котором будем брать очередной элемент из текущего списка
//Андреева Валентина Валерьевна, ИПМКН, 2020
// и добавлять этот элемент в новый список не нарушая порядка.
while (*list)
{
elem = *list;//Устанавливем указатель на головной элемент списка.
*list = (*list)->next;// Переходим на следующий элемент.
elem->next = NULL;// Сообщаем элементу, что у него нет последующего.
//Проверяем, может элемент нужно добавлять в голову нового списка.
if (elem->x < newList->x)
{ //Добавляем элемент в голову.
elem->next = newList;
newList = elem;
}
else
{
struct point *ptrIx = newList;
// В этом цикле указатель остановим на элементе, после которого добавим элемент
//(Проверьте, все ли верно?)
for (; ptrIx->next && ptrIx->next->x < elem->x; ptrIx = ptrIx->next);
//Добавляем элемент
elem->next = ptrIx->next;
ptrIx->next = elem;
}
}
*list = newList;
}
}



  void Sort( struct point **List )
{
    struct point *newList = NULL;
    struct point *Con = *List;
    while (Con)
    {
        struct point *elem = NULL;
        elem=Con;
        Con = Con->next;

        if ( newList == NULL || elem->x < newList->x )
        {
            elem->next = newList;
            newList = elem;
        }
        else
        {
            struct point *PtrIx = newList;
            while ( PtrIx->next != NULL && !( elem->x < PtrIx->next->x) )
            {
                  PtrIx = PtrIx->next;
            }

            elem->next = PtrIx->next;
            PtrIx->next = elem;
        }
    }
}





struct point * addToHead(struct point **list, int x,int y)
{
struct point *PtrIx = (struct point*) malloc(sizeof(struct point));
if (PtrIx)
{
PtrIx->x = x;
PtrIx->y = y;
PtrIx->next = NULL;
if (*list == NULL)
*list = PtrIx;
else
{
PtrIx->next = *list;
*list = PtrIx;
}
return PtrIx;
}
return NULL;
}




int main()
{
    struct point *head = NULL;// Переменная для хранения головы списка
    struct point *ptrIx = NULL;//Объявили рабочую переменную
    addToHead(&head, 4, 1);
    addToHead(&head, 3, 5);
    addToHead(&head, 1, 3);
    addToHead(&head, 9, 4);
    addToHead(&head, 7, 8);
    addToHead(&head, 0, 6);
    addToHead(&head, -1, 2);
    //SortList(&head);
    Sort(&head);
    ptrIx = head;
    while (ptrIx) {
        printf("point(%d,%d)\n", ptrIx->x, ptrIx->y);
        ptrIx = ptrIx->next;
    }
}