#include <stdlib.h>
#include <iostream>
using namespace std;
struct Node //Структура являющаяся звеном списка
{
int x; //Значение x будет передаваться в список
Node *Next,*Prev; //Указатели на адреса следующего и предыдущего элементов списка
};
class List //Создаем тип данных Список
{
Node *Head,*Tail; //Указатели на адреса начала списка и его конца
public:
List():Head(NULL),Tail(NULL){}; //Инициализируем адреса как пустые
~List(); //Деструктор
void Show(); //Функция отображения списка на экране
void Add(int x); //Функция добавления элементов в список
void Swap();//sortirovka
};
List::~List() //Деструктор
{
while (Head) //Пока по адресу на начало списка что-то есть
{
Tail=Head->Next; //Резервная копия адреса следующего звена списка
delete Head; //Очистка памяти от первого звена
Head=Tail; //Смена адреса начала на адрес следующего элемента
}
}
void List::Add(int x)
{
Node *temp=new Node; //Выделение памяти под новый элемент структуры
temp->Next=NULL; //Указываем, что изначально по следующему адресу пусто
temp->x=x;//Записываем значение в структуру
if (Head!=NULL) //Если список не пуст
{
temp->Prev=Tail; //Указываем адрес на предыдущий элемент в соотв. поле
Tail->Next=temp; //Указываем адрес следующего за хвостом элемента
Tail=temp; //Меняем адрес хвоста
}
else //Если список пустой
{
temp->Prev=NULL; //Предыдущий элемент указывает в пустоту
Head=Tail=temp; //Голова=Хвост=тот элемент, что сейчас добавили
}
}
void List::Show()
{
//ВЫВОДИМ СПИСОК С КОНЦА
Node *temp=Tail;
//Временный указатель на адрес последнего элемента
while (temp!=NULL) //Пока не встретится пустое значение
{
cout<<temp->x<<" "; //Выводить значение на экран
temp=temp->Prev; //Указываем, что нужен адрес предыдущего элемента
}
cout<<"\n";
}
void List::Swap() //меняем min с max
{
Node *min = Head, *max = Head, *cur = Head; //head element
//Поиск минимального и максимального узла
while(cur != Tail)
{
cur = cur->Next;
if(cur->x < min->x)
{
min = cur;
}
if(cur->x > max->x)
{
max = cur;
}
}
Node *beforeMin = min->Prev;
Node *afterMin = min->Next;
Node *beforeMax = min->Prev;
Node *afterMax = max->Next;
//выбор адресов элементов
beforeMin->Next = max;
afterMin->Prev = max;
beforeMax->Next = min;
afterMax->Prev = min;
min->Prev = beforeMax;
min->Next = afterMax;
max->Prev = beforeMin;
max->Next = afterMin;
//Проверка головы и хвоста
if(min == Head) Head = max;
if(min == Tail) Tail = max;
if(max == Head) Head = min;
if(max == Tail) Tail = min;
}
int main ()
{
List lst; //Объявляем переменную, тип которой есть список
for (int i = 0, n = rand()%11 + 10; i < n; ++i)
{
lst.Add(rand()%101-50);
}
lst.Show(); //Отображаем список на экране
lst.Swap(); //Отображаем поменяный список на экране
return 0;
}
