не работает функция Max и Min в двусвязном списке

Рейтинг: -1Ответов: 1Опубликовано: 17.05.2023

У меня программа работы со списками. Добавляет, печатает, находит Max, а Min пишет 0 и не меняет. Может кто-то поможет мне исправить. Похожую делала в односвязном, работает, а в двусвязном нет. То есть не работает следующая функция: Поменять местами элементы, которые стоят перед Min и после Max, если хотя бы один из них не является крайним, то просто поменять местами Max и Min. Подскажите, как можно исправить работу функции Max и Min.

#include <iostream>
#include <Windows.h> 
 
using namespace std;
 
 
struct node
{
    int elem; 
    node* next; 
    node* prev; 
};
 
struct lists 
{
private: 
    node* end; 
    int quanity; 
public: 
    node* head; 
    lists() 
    {
        head = end = new node();
        quanity = 0;
    }
 
    int count() 
    {
        return quanity;
    }
 
    node* find(int el)
    {
        node* curr = head->next; 
        while (curr != nullptr)  
        {
            if (curr->elem == el)
            {
                return curr;
            }
            curr = curr->next;
        }
        return nullptr;
    }
    node* find(int el, node*& aft)
    {
        node* curr = head->next;
        aft = head;
        while (curr != nullptr)
        {
            if (curr->elem == el)
            {
                return curr;
            }
            aft = curr;
            curr = curr->next;
        }
        return nullptr;
    }
 
    void push_back(int el)
    {
        node* curr = new node();
        curr->elem = el;
        end->next = curr;
        end = curr;
        quanity++;
    }
 
    void push_forward(int el)
    {
        node* curr = new node();
        curr->elem = el;
        curr->next = head->next;
        head->next = curr;
        if (end == head)
        {
            end = curr;
        }
        quanity++;
    }
 
 
    void print() const
    {
        if (head->next == nullptr)
        {
            cout << "Список пуст" << endl;
            return;
        }
        node* current = head->next;
        while (current != nullptr)
        {
            cout << current->elem << " ";
            current = current->next;
        }
        cout << endl;
    }
 
    void clear()
    {
        node* current = head->next;
        while (current != nullptr)
        {
            node* next = current->next;
            delete current;
            current = next;
        }
        head->next = nullptr;
        end->next = nullptr;
        end = head;
        quanity = 0;
        cout << "Список очищен" << endl;
    }
};
// Функция для поиска Min и Max элементов в двусвязном списке
void findMinMax(node* head, int& min, int& max)
{
    node* current = head;
    min = head->elem;
    max = head->elem;
 
    while (current != nullptr)
    {
        if (current->elem < min)
        {
            min = current->elem;
        }
        if (current->elem > max)
        {
            max = current->elem;
        }
        current = current->next;
    }
    cout << "Min = " << min << endl;
    cout << "Max = " << max << endl;
}
// Функция для обмена значениями двух элементов в двусвязном списке
void swapValues(node* el1, node* el2)
{
    int temp = el1->elem;
    el1->elem = el2->elem;
    el2->elem = temp;
}
 
// Функция для обмена элементами перед Min и после Max элементов двусвязного списка
void swapElementList_2(node* head)
{
    if (head == nullptr)
    {
        return;
    }
    node* current = head;
    node* prevMin = nullptr;
    node* minNode = nullptr;
    node* maxNode = nullptr;
    int min, max;
 
    cout << "head->elem" << head->elem << endl;
    findMinMax(head, min, max);
    while (current != nullptr)
    {
        if (current->elem <= min)
        {
            minNode = current;
        }
        if (current->elem >= max)
        {
            maxNode = current;
        }
        if (current->prev != nullptr && current->prev->elem == min)
        {
            prevMin = current->prev;
        }
 
        current = current->next;
    }
 
    bool isMinEdge = (minNode == head || minNode->next == nullptr);
    bool isMaxEdge = (maxNode == head || maxNode->next == nullptr);
    // Обменивакм значениями элементы перед Min и после Max
    if (isMinEdge && isMaxEdge)
    {
        // Если и Min, и Max элементы крайние, просто меняем их местами
        swapValues(minNode, maxNode);
    }
    else if (isMinEdge)
    {
        // Если только Min элемент крайний, меняем местами его и следующий за Max
        swapValues(minNode, maxNode->next);
    }
    else if (isMaxEdge)
    {
        // Если только Max элемент крайний, меняем местами предыдущий Min и Max элементы
        swapValues(prevMin, maxNode);
    }
    else
    {
        // Если ни Min, ни Max элементы не являются крайними, меняем местами элемент перед Min и элемент после Max
        swapValues(prevMin, maxNode->next);
    }
}
 
void printList_2(node* head)
{
    node* current = head;
    while (current != nullptr)
    {
        cout << current->elem << " ";
        current = current->next;
    }
    cout << endl;
}
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    lists myList;
    int el, el2;
    int c;
    int choice;
    int ch;
    while (true)
    {
        cout << "Введите команду" << endl;
        cout << "1 - работа с двусвязным списком " << endl;
        cout << "2 - выйти" << endl;
        cin >> ch;
        if (ch == 2)
        {
            exit(0);
            break;
        }
        if (ch == 1)
        {
            while (true)
            {
                cout << "Выберите цифру меню: " << endl;
                cout << "1 - добавить элемент в конец" << endl;//
                cout << "2 - добавить элемент в начало" << endl;
                cout << "3 - показать список" << endl;
                cout << "4 - очистить список" << endl;
                cout << "5 - Функция Min_Max" << endl;
                cout << "6 - назад" << endl;
                cin >> c;
                if (c == 6)
                {
                    break;
                }
                switch (c)
                {
                case 1:
                    cout << "Введите элемент: ";
                    cin >> el;
                    myList.push_back(el);
                    cout << "Элемент добавлен в конец списка" << endl;
                    break;
                case 2:
                    cout << "Введите элемент: ";
                    cin >> el;
                    myList.push_forward(el);
                    cout << "Элемент добавлен в начало списка" << endl;
                    break;
                case 3:
                    myList.print();
                    break;
                case 4:
                {
                    myList.clear();
                    break;
                }
                case 5:
                {
                    cout << "Двусвязный список до изменения: ";
                    myList.print();
                    cout << "myList.head->elem: " << myList.head->elem << endl;
                    swapElementList_2(myList.head);
                    cout << "Двусвязный список после изменения: ";
                    myList.print();
                    break;
                }
                case 6:
                    break;
                default://Если введено число не соответствующее номеру (case), то выдает ошибку 
                    cout << "Некорректный ввод. Попробуйте еще раз." << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

вот что выходит введите сюда описание изображения

Ответы

▲ 0

Многовато у вас ошибок для работы со списком, которую вы уже однажды выполняли:

  • в списке на 1 элемент больше
  • в функции swapElementList_2() у вас находится только минимум, максимум не ищется, а в качестве максимума всегда получается последний элемент
  • печать списка идет без первого элемента, а поиск включая первый элемент - служебный и в findMinMax() и в swapElementList_2()

В итоге - первый ноль - это минимум и он меняется с последним элементом - 2. Визуально кажется что двойка пропала, а ноль появился.
Такое впечатление, что код не вы писали. Вам нужно было просто повторить код из findMinMax(), а это не сделано.
Чтобы не делать двойную работу лучше, чтобы функция findMinMax() возвращала не значения, а указатели на элементы списка.

void findMinMax(node* head, int& *min, int& *max)

Реализация с head = end = nullptr на мой взгляд проще, чем реализация с с одним фиктивным узлом, определяющим начало списка.