Удалить все эл-ты двусвязного списка, находящиеся между его минимальным и максимальным эл-тами

[natatttt]

Помогите, пожалуйста
Требуется удалить все эл-ты двусвязного списка, находящиеся между его минимальным и максимальным эл-тами. Информационную часть в операционной системе не перемещать. В конце освободить всю динамическую память.

Минимальный и максимальный эл-ты я нашла, а вот удаление (void del_between()) не очень понимаю как реализовать

#include <iostream>
#include <Windows.h>
#include <stdio.h>
#include <io.h>
#include <iomanip>
using namespace std;
 
struct TNode
{
    int inf; //информационная часть
    TNode* left; //адресная часть
    TNode* right; //адресная часть
};
 
struct list //работа со списком
{
    TNode* front = nullptr; // Указатель на начало очереди
    TNode* back = nullptr; // Указатель на конец очереди
 
    // Проверка наличия элементов в очереди
    bool empty() 
    {
        if (front) return false;
        else return true;
    }
 
    // Добавление элемента в очередь
    void push(int inf) 
    {
        TNode* spt = new TNode;
        spt->inf = inf;
        spt->right = nullptr;
        if (!front) 
        {
            spt->left = nullptr;
            front = back = spt;
            return;
        }
        back->right = spt;
        spt->left = back;
        back = spt;
    }
 
    // Удаление элемента из очереди
    void pop() 
    {
        TNode* spt = front;
        front = front->right;
        delete spt;
        if (!front) back = nullptr;
        else front->left = nullptr;
    }
 
    // Вывод очереди
    void print() 
    {
        TNode * spt = front;
        while (spt != nullptr) 
        {
            cout << spt->inf << " ";
            spt = spt->right;
        }
    }
 
    //поиск минимального эл-та
    TNode* search_min()
    {
        TNode* min = front;
        TNode* spt = front;
        while (spt != nullptr)
        {
            if (spt->inf < min->inf) min = spt;
            spt = spt->right;
        }
        return min;
    }
 
    //поиск максимального эл-та
    TNode* search_max()
    {
        TNode* max = front;
        TNode* spt = front;
        while (spt != nullptr)
        {
            if (spt->inf > max->inf) max = spt;
            spt = spt->right;
        }
        return max;
    }
 
    void del_between()
    {
        TNode* min = search_min();
        TNode* max = search_max();
        TNode* spt = front;
 
 
 
    }
};
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    list s;
    int n;
    cout << "Введите кол-во эл-тов списка: ";
    cin >> n;
    cout << "___________________________________" << endl;
    int k;
    for (int i = 0; i < n; i++)
    {
        cout << "Введите " << i + 1 << " эл-т списка : ";
        cin >> k;
        s.push(k);
    }
    cout << "___________________________________" << endl;
    cout << "Введенные эл-ты списка: " << endl;
    s.print();
    cout << endl;
    cout << "___________________________________" << endl;
    TNode* min = s.search_min();
    cout << "Минимальный эл-т списка: " << min->inf << endl;
    TNode* max = s.search_max();
    cout << "Максимальный эл-т списка: " << max->inf << endl;
    cout << "___________________________________" << endl;
    s.del_between();
    cout << endl;
    cout << "Cписок после удаления эл-тов: " << endl;
    s.print();
    cout << endl;
    while (!s.empty()) s.pop();
    return 0;
}

[maks1331]

Если оставаться в рамках текущей реализации, то я бы добавил счетчик позиции для min и max, чтобы понимать, left или right указатель изменять у соответствующих TNodes.

Как вариант, можно добавить два приватных члена класса к list. Не забывая очищать их после обрезания и проверять перед обрезанием, на случай, если обрезать нечего.

void del_between()
{
    TNode* min = search_min();
    TNode* max = search_max();

    if (min_pos == max_pos) {
    	std::cout << "Пустая область между min и max" << std::endl;
    	return;
    }

    if (min_pos > max_pos) {
    	TNode* temp = min;
    	min = max;
    	max = temp;
    }

    TNode* saveToFree;
    while (min->right != max) {
    	saveToFree = min->right;
    	min->right = min->right->right;
    	free(saveToFree);
    }

    min_pos = 0;
    max_pos = 0;
}

А так, я бы оставил один метод del_between_min_max и отказался от дополнительных членов класса.

Так же стоит указать, что код ищет только первые минимум и максимум.
И на сладкое, я бы написал функцию для тестирования, простейший unit test, типо такого:

#include <vector>

bool UnitTest(const std::vector<int>& input, const std::vector<int>& output)
{
    list s;
    for (const auto value : input) {
        s.push(value);
    }
    s.del_between();

    TNode* node = s.front;
    for (const auto value : output) {
        if (node == nullptr) {
            std::cout << "Тест провален, итоговый список короче, чем ожидалось" << std::endl;
            return false;
        }
        if (node->inf != value) {
            std::cout << "Тест провален, значение списка: " << node->inf << " не равно ожидаемому: " << value << std::endl;
            return false;
        }
        node = node->right;
    }

    if (node != nullptr) {
        std::cout << "Тест провален, итоговый список длиннее, чем ожидалось" << std::endl;
        return false;
    }

    std::cout << "Тест пройден" << std::endl;
    return true;
};

if (!UnitTest({ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }, { 1, 5, 1, 2, 3, 4, 5 })
    || !UnitTest({ 1, 2, 3, 4, 5, 0, 1, 2, 3, -1, 4, 5 }, { 1, 2, 3, 4, 5, -1, 4, 5 })
    || !UnitTest({ 5, 4, 3, 2, 1, 5, 4, 3, 2, 1 }, { 5, 1, 5, 4, 3, 2, 1 })
    || !UnitTest({ 5, 4, -1, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1 }, { 5, 4, -1, 6, 5, 4, 3, 2, 1 })
    || !UnitTest({ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }) 
    || !UnitTest({ 0 }, { 0 })
    || !UnitTest({ 0, 1 }, { 0, 1 }) 
    || !UnitTest({ 1, 0 }, { 1, 0 })) {

    return -1;
}

[natatttt]

А что делает функция free(saveToFree)?
я не очень понимаю

[BDA]

Думаю, free приблудилась из C, делайте delete. Еще стоит добавить проверку front в функции pop, а не лезть сразу по указателю front->right, т.к. список может быть пуст.

[natatttt]

У меня еще иногда высвечивается исключение в строке

min->right = min->right->right;

"Вызвано исключение: нарушение доступа для чтения.
min->right было nullptr."

[BDA]

Сообщение от natatttt

иногда высвечивается исключение

Почему-то пролетаете мимо максимума до конца списка. Как выставляете min_pos в search_min и max_pos в search_max?
А еще в del_between после цикла нужно сделать max->left = min, чтобы сохранить двусвязность списка.