// laba_spiski.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
using namespace std;

struct list
{
    int Data;
    struct list* next;
    struct list* prev;
};

list* head = NULL; //корень списка


struct list * init(int a)
{
    struct list* lst;
    lst = (struct list*)malloc(sizeof(struct list));
    lst->field = a;
    lst->next = NULL;
    lst->prev = NULL;
    return(lst);
}

struct list * additem(list *lst, int a)
{
    struct list *temp, *p;
    temp = (struct list*)malloc(sizeof(list));
    p = lst->next;
    lst->next = temp;
    temp->field = a;
    temp->next = p;
    temp->prev = lst;
    if (p != NULL)
        p->prev = temp;
    return(temp);
}

struct list* deleteitem(list* lst)
{
    struct list* prev, * next;
    prev = lst->prev;
    next = lst->next;
    if (prev == NULL) // это корень
    {
        if (next != NULL)
            next->prev = NULL;
        prev = next;
    }
    else
    {
        prev->next = lst->next;
        if (next != NULL)
            next->prev = lst->prev;
    }
    free(lst);
    return(prev);
}

struct list * deletehead(list *root)
{
    struct list* temp;
    temp = root->next;
    if (temp != NULL)
       temp->prev = NULL;
    free(root);
    return(temp);
}

struct list * deleteList(list *root)
{
    struct list* prev = root;

    while (root!=NULL)
    {
        root = deletehead(root);
    }
    return(NULL);
}

struct list* outList(struct list *root)
{
    struct list* p;
    p = root;
    if (p == NULL)
    {
        cout << "Список пуст";
    }
    else
    {
        do {
            printf("%d ", p->field);
            p = p->next;
        } while (p != NULL);
    }

    return(NULL);
}

struct list* swap(struct list* root, struct list* l1, struct list* l2)
{
        struct list* left1, * left2, * right1, * right2;
        left1 = l1->prev;
        right1 = l1->next;
        left2 = l2->prev;
        right2 = l2->next;

        if (l2 == right1)
        {
            l2->next = l1;
            l2->prev = left1;
            l1->next = right2;
            l1->prev = l2;
            if (right2 != NULL)
                right2->prev = l1;
            if (l1 != root)
                left1->next = l2;
        }
        else  if (l1 == right2)
        {
            l1->next = l2;
            l1->prev = left2;
            l2->next = right1;
            l2->prev = l1;
            if (right1 != NULL)
                right1->prev = l2;
            if (l2 != head)
                left2->next = l1;
        }
        else
        {
            if (l1 != root)
                left1->next = l2;
            l2->next = right1;
            if (l2 != root)
                left2->next = l1;
            l1->next = right2;
            l2->prev = left1;
            if (right2 != NULL)
                right2->prev = l1;
            l1->prev = left2;
            if (right1 != NULL)
                right1->prev = l2;
        }
        if (l1 == root)
            return(l2);
        if (l2 == root)
            return(l1);
        return(root);

}

struct list* swapTo1(struct list* head1,struct list* l2)
{
    struct list* left1, * left2, * right1, * right2;
    left1 = head1->prev;
    right1 = head1->next;

    left2 = l2->prev;
    right2 = l2->next;

    if (l2 == right1)
    {
        l2->next = head1;
        l2->prev = NULL;

        head1->next = right2;
        head1->prev = l2;

        if (right2 != NULL)
            right2->prev = head1;
    }
    else
    {
        l2->next = right1;
        l2->prev = NULL;
        if (right1 != NULL)
            right1->prev = l2;

        head1->next = right2;
        if (right2 != NULL)
            right2->prev = head1;
        head1->prev = left2;
        if (left2 != NULL)
            left2->next = head1;
    }
    return(l2); //возвращаем новый корень
}


void Z1(struct list *root)
{
    struct list* p = root;
    struct list* min;

    cout << "\n Задача 1 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);
    p = head1;
    min = p;
    //ищем миним элемент
    do {
        if (min->field > p->field)
            min = p;
        p = p->next;
    } while (p != NULL);
    //переставим его первым
    head1= swapTo1(head1,min);
    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z2(struct list* root)
{
    struct list* head1, * head2, * el1, * el2;
    struct list* p = root;
    head1 = NULL;
    head2 = NULL;
    el1 = NULL;
    el2 = NULL;
    cout << "\n Задача 2 \n";
    //разбиваем исходный список на 2
    do {
        if (p->field >= 0)
        {
            if (head1 == NULL)
            {
                el1 = init(p->field);
                head1 = el1;
            }
            else el1 = additem(el1, p->field);
        }
        else
        {
            if (head2 == NULL)
            {
                el2 = init(p->field);
                head2 = el2;
            }
            else el2 = additem(el2, p->field);
        }
        p = p->next;
    } while (p != NULL);
    cout << "\n Выводим список с положительнымии елементами \n";
    outList(head1);
    cout << "\n Выводим список с положительнымии елементами \n";
    outList(head2);
    //удалим список
    deleteList(head1);
    deleteList(head2);
}

void Z3(struct list* root)
{
    cout << "\n Задача 3 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    struct list* p = root;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);


    //ищем миним и макс элементы
    p = head1;
    struct list* min = p;
    struct list* max = p;
    int pos_min = 0, pos_max = 0, i = 0;
    do {
        if (min->field > p->field)
        {
            min = p;
            pos_min = i;
        }

        if (max->field < p->field)
        {
            max = p;
            pos_max = i;
        }

        p = p->next;
        i++;
    } while (p != NULL);

    //удаляем лишние элементы
    //получим элемент отсчета
    int j = 0;
    if (pos_min < pos_max)
    {
        p = min;
        j = pos_max;
    }
    else
    {
        p = max;
        j = pos_min;
    }
    //удаление
    i = 0;
    do {
        if ((p != min) && (p != max) && (i < j))
            p = deleteitem(p);

        p = p->next;
        i++;
    } while (((p != NULL) || (p == min) || (p == max)) && (i < j));

    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z4(struct list* root)
{
    cout << "\n Задача 4 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    struct list* p = root;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);


    //ищем макс элемент
    p = head1;
    struct list* max = p;
    do {
        if (max->field < p->field)
            max = p;
        p = p->next;
    } while (p != NULL);

    //переходим к макс элементу
    p = head1;
    do {
        if (max == p)
            break;

        p = p->next;
    } while (p != NULL);

    //Переносим элементы во 2 список
    struct list* head2 = NULL;
    p = p->next;
    if (p != NULL)
    {
        el = NULL;
        do {
            if (head2 == NULL)
            {
                el = init(p->field);
                head2 = el;
            }
            else el = additem(el, p->field);
            p = p->next;
        } while (p != NULL);
    }

    //выводим список на экран
    outList(head2);
    //
    deleteList(head2);
}

void Z5(struct list* root)
{
    struct list* p = root;
    int pos=0;

    cout << "\n Задача 5 \n";
    cout << "Введите число позиций для сдвига. \n";
    cin >> pos;
    cout << "\n";

    //сделаем копию списка, чтобы не испортить исходный для посл заданий
    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);

    //зацикливаем список
    //el  -  последний элем списка
    head1->prev = el;
    el->next = head1;

    //сместим элементы списка по кольцу на pos позиций
    int i;
    p = head1;
    //
    for (i = 0; i < pos; i++)
        p = p->next;
    //определим новый корень списка
    head1 = p;
    p->prev->next = NULL;
    head1->prev = NULL;

    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z6(struct list* root)
{
    struct list* p = root;

    cout << "\n Задача 6 \n";

    //сделаем копию списка, чтобы не испортить исходный для посл заданий
    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);
    p = head1;

    //удалим все отрицательные эл-ты
    do {
        if (p->field < 0)
            p = deleteitem(p);

        p = p->next;
    } while (p != NULL);

    cout << "\n Выводим список\n";
    outList(head1);
    //удалим список
    deleteList(head1);
 }

void Z7(struct list* root)
{
    cout << "\n Задача 7 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    struct list* p = root;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);


    //ищем миним и макс элементы
    p = head1;
    struct list* min = p;
    struct list* max = p;
    int pos_min = 0, pos_max = 0, i = 0;
    do {
        if (min->field > p->field)
        {
            min = p;
            pos_min = i;
        }

        if (max->field < p->field)
        {
            max = p;
            pos_max = i;
        }

        p = p->next;
        i++;
    } while (p != NULL);

    //удаляем лишние элементы
    //получим элемент отсчета
    int j = 0;
    if (pos_min < pos_max)
    {
        p = min;
        j = pos_max;
    }
    else
    {
        p = max;
        j = pos_min;
    }
    //создаем новый список
    struct list* head2 = NULL;
    el = NULL;

    i = 0;
    do {
        if ((p != min) && (p != max) && (i < j))
        {
            if (head2 == NULL)
            {
                el = init(p->field);
                head2 = el;
            }
            else el = additem(el, p->field);
        }
        p = p->next;
        i++;
    } while (((p != NULL) || (p == min) || (p == max)) && (i < j));
    //превращаем список в кольцо
    head2->prev = el;
    el->next = head2;

    //выводим исходный список, чтобы показать что он не изменился
    outList(head1);
    cout << "\n";
    //выводим список-кольцо на экран (делаем 3 оборота чтобы показать замкнутость списка)
    p = head2;
    if (p == NULL)
    {
        cout << "Список пуст";
    }
    else
    {
        i = 0;
        do {
            printf("%d ", p->field);

            if (p == head2)
                i++;

            p = p->next;
        } while ((p != NULL)&&(i<3));
    }
    //
    deleteList(head1);
    //перед удалением списка-кольца - разомкнем его
    head2->prev = NULL;
    el->next = NULL;
    deleteList(head2);
}

void Z8(struct list* root)
{
    struct list* p = root;

    cout << "\n Задача 8 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);
    p = head1->next;
    // удалим первый элемент
    deleteitem(head1);
    head1 = p;
    // удалим последний элемент
    el= deleteitem(el);
    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z9(struct list* root)
{
    struct list* p = root;
    struct list* min;

    cout << "\n Задача 1 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);
    p = head1;
    min = p;
    //ищем миним элемент
    do {
        if (min->field > p->field)
            min = p;
        p = p->next;
    } while (p != NULL);
    //удаление
    if (min->prev == NULL)
        head1 = deleteitem(min);
    else if (min->next == NULL)
            deleteitem(min);
         else
         {
            if (min->prev->prev==NULL)
                head1=deleteitem(min->next);
            else
                deleteitem(min->next);
            deleteitem(min->prev);
         }
    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z11(struct list* root)
{
    struct list* p = root;

    cout << "\n Задача 11 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);
    p = head1;

    struct list* p1 = p->next;
    //ищем миним элемент
    do {
        p1 = p->next;
        bool b = false;
        while (p1 != NULL)
        {
            if (p1->field == p->field)
            {
                p1 = deleteitem(p1);
                b = true;
            }
            p1 = p1->next;
        }
        p1 = p;
        p = p->next;

        if (b)
        {
            if (p1->prev == NULL)
                head1 = deleteitem(p1);
            else
                deleteitem(p1);
        }

    } while (p != NULL);

    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z12(struct list* root)
{
    cout << "\n Задача 12 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    struct list* p = root;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);


    //ищем миним и макс элементы
    p = head1;
    struct list* min = p;
    struct list* max = p;
    int pos_min = 0, pos_max = 0, i = 0;
    do {
        if (min->field > p->field)
        {
            min = p;
            pos_min = i;
        }

        if (max->field < p->field)
        {
            max = p;
            pos_max = i;
        }

        p = p->next;
        i++;
    } while (p != NULL);

    //меняем их местами
    head1=swap(head1,min, max);
    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}


void Z13(struct list* root)
{
    struct list* p = root;
    int pos = 0;

    cout << "\n Задача 13 \n";

    //сделаем копию списка, чтобы не испортить исходный для посл заданий
    struct list* head1 = NULL;
    struct list* el = NULL;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);

    //закольцуем список
    //el  -  последний элем списка
    head1->prev = el;
    el->next = head1;

    //становимся в конерь на старт
    el = head1;
    pos = 1;
    while (pos!=0)
    {
        p = head1;
        //выводим список на экран
        cout << "СПИСОК \n";
        do {
            if (p == el)
            {
                printf("%c", "*");
                printf("%d ", p->field);
            }
            else
                printf("%d ", p->field);
            p = p->next;
        } while (p != head1);

        cout << "\n Введите число позиций для сдвига. (0 - прекратить) \n";
        cin >> pos;
        cout << "\n";

        int i;

        if (pos > 0)
        {
            for (i = 0; i < pos; i++)
                el = el->next;
        }
        else
        {
            for (i = pos; i <0; i++)
                el = el->prev;
        }
    }

    //возвращаемся в обычный список из кольца
    head1->prev->next = NULL;
    head1->prev= NULL;

    //выводим список на экран
    cout << "Исходный список \n";
    outList(head1);
    //
    deleteList(head1);
}

void Z14(struct list* root)
{
    cout << "\n Задача 14 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    struct list* p = root;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);


    //ищем макс элемент
    p = head1;
    struct list* max = p;
    do {
        if (max->field < p->field)
            max = p;

        p = p->next;
    } while (p != NULL);

    //меняем  местами max и корень
    head1 = swap(head1, head1, max);
    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

void Z15(struct list* root)
{
    cout << "\n Задача 15 \n";
    //сделаем копию списка, чтобы не испортить исходный для посл заданий

    struct list* head1 = NULL;
    struct list* el = NULL;
    struct list* p = root;
    do {
        if (head1 == NULL)
        {
            el = init(p->field);
            head1 = el;
        }
        else el = additem(el, p->field);
        p = p->next;
    } while (p != NULL);


    //ищем последний элемент
    p = head1;
    struct list* p1 = p;
    do {
         p1 = p;
         p = p->next;
    } while (p != NULL);

    //меняем  местами max и корень
    head1 = swap(head1, head1, p1);
    //выводим список на экран
    outList(head1);
    //
    deleteList(head1);
}

int main()
{
    setlocale(LC_ALL, "Russian");

    //создадим новый список
    cout << "Введите элементы списка. (Для прекращения введите 55) \n";
    int el;
    list *elem=NULL; //содержит текущий элемент списка

    do
    {
        cin >> el;
        if ((el >= -50) && (el <= 50))
        {
            if (head == NULL)
            {
                elem = init(el);
                head = elem;
            }
            else elem=additem(elem, el);
        }
    } while (el != 55);

    //задание - 1
    //Z1(head);
    //задание - 2
   // Z2(head);
    //задание - 3
   // Z3(head);
    //задание - 4
   // Z4(head);
    //задание - 5
   // Z5(head);
    //задание - 6
   //  Z6(head);
    //задание - 7
   //  Z7(head);
    //задание - 8
   //  Z8(head);
    //задание - 9
   //  Z9(head);
    //задание - 10
   //  Z3(head);
    //задание - 11
    // Z11(head);
    //задание - 12
    //Z12(head);
    //задание - 13
    //Z13(head);
    //задание - 14
   // Z14(head);
    //задание - 15
   // Z15(head);
   //удалим список
    deleteList(head);

}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.