Добавил:
oih07968
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:lab3 / Task3
.cpp#include <iostream>
#include <string>
#include <iomanip>
#include <Windows.h>
using namespace std;
#if defined(max)
#undef max
#endif
struct List
{
int number = 0;
List* next = nullptr;
List* prev = nullptr;
};
template <typename T>
void get_value(T& value);
List* push(int number, List* last);
void output(List* stk);
List* list_sort(List* first, bool dir);
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
List* first = nullptr; // для сортируемого списка
List* last = nullptr;
List* afirst = nullptr; // для несортируемого списка
List* alast = nullptr;
int n;
cout << "Введите количество чисел:" << endl;
get_value(n);
srand((unsigned int)time(NULL));
for (int i = 0; i < n; i++)
{
int randnum = rand() % 100; // записываем случайное число
last = push(randnum, last); // добавляем в списки
alast = push(randnum, alast);
if (first == nullptr) first = last; // если не заданы - задаем
if (afirst == nullptr) afirst = alast;
}
bool dir;
cout << "Введите направление сортировки (1 - прямая, 0 - обратная):" << endl;
get_value(dir); // получаем направление сортировки
first = list_sort(first, dir); // сортируем
output(first); // выводим полученный список
bool archive;
cout << "Хотите увидеть изначальный список? (1 - да, 0 - нет)" << endl;
get_value(archive);
if(archive) output(afirst); // если ответ положительный выводим несортированный список
system("pause");
return 0;
}
template <typename T>
void get_value(T& value)
{ // ввод данных
cin >> value;
while (cin.fail())
{
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cout << "Некорректный ввод! Попробуйте снова: ";
cin >> value;
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
List* push(int number, List* last)
{ // добавляет значения в список
List* item = new List;
item->number = number;
item->next = nullptr;
item->prev = last;
if (last != nullptr) last->next = item;
return item;
}
void output(List* stk)
{ // выводит список
if (stk == nullptr) cout << "Список пуст!";
while (stk != nullptr)
{
cout << stk->number << " ";
stk = stk->next;
}
cout << endl;
}
List* list_sort(List* first, bool dir)
{ // сортирует список
if (first == nullptr || first->next == nullptr) return first;
// если есть что сортировать
List* i = first; // вспомогательный указатель
while (i != nullptr)
{
int min = i->number; // записываем текущий элемент как минимальный
List* min_value = i;
List* j = i->next;
while (j != nullptr)
{
int cur = j->number;
if ((dir && cur < min) || (!dir && cur > min))
{ // находим наименьший элемент и записываем в переменную
min = cur;
min_value = j;
}
j = j->next; // переходим к следующему элементу
}
if (min_value != i)
{ // если значение минимального изменилось меняем местами
List* flip_next = i->next;
List* flip_prev = i->prev;
if (i->next == min_value)
{ // если у текущего элемента следующий тот, с кем обмен (соседи)
flip_next = i;
min_value->prev = min_value;
}
i->next = min_value->next;
i->prev = min_value->prev;
if (i->next != nullptr) (i->next)->prev = i;
if (i->prev != nullptr) (i->prev)->next = i;
// если предыдущий элемент существует, то устанавливаем значение указателя next у предыдущего элемента на текущий
min_value->next = flip_next;
min_value->prev = flip_prev;
if (min_value->next != nullptr) (min_value->next)->prev = min_value;
if (min_value->prev != nullptr) (min_value->prev)->next = min_value;
if (min_value->prev == nullptr) first = min_value;
}
i = min_value->next; // переходим к следующему элементу
}
return first;
}