Удалить максимальное значение из простого списка

Question

Как я могу удалить максимальное значение из списка Просто подключенных?

Два из опробованных мной решений дают неправильные результаты.Пожалуйста, объясните мне, что я делаю не так.С кодом, если не сложно.

Стек:

struct Stack
{
    int info;
    Stack *next;
} *top;

Неправильное решение 1:

void delMaxValue(Stack **stck, int maxValue){
Stack *tmp = NULL;
do {
    if ((*stck)->info != maxValue) 
        tmp = *stck;
        cout << tmp->info << endl;
        tmp = tmp->next;
    *stck = (*stck)->next;
} while ((*stck)->next != NULL);
while (tmp != NULL)
{
    *stck = tmp;
    *stck = (*stck)->next;
    tmp = tmp->next;
}

Неправильное решение 2:

Stack* deleteMaxValue(Stack *begin) {
Stack *t = begin, *p = begin->next;
for (; p; p = p->next)
    if (p->info > t->info)  t = p;
p = begin;
if (p != t) {
    while (p->next != t)   p = p->next;
    p->next = t->next;
}
else
    begin = t->next;
delete t;
return begin;}

Answer 1

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

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

void stackRemoveMaxValue(Stack*& top) {
    if(top == nullptr) {
        return;
    }

    // Find max value.
    int maxValue = top->info;
    Stack* node = top->next;
    for(; node != nullptr; node = node->next) {
        if(maxValue < node->info) {
            maxValue = node->info;
        }
    }

    // Remove first node that contains maxValue.
    Stack* previous = nullptr;
    Stack* current = top;
    do {
        if(current->info != maxValue) {
            previous = current;
            current = current->next;
        } else {
            if(previous != nullptr) {
                previous->next = current->next;
            } else {
                top = current->next;
            }
            delete current;
            return;
        }
    } while(current != nullptr);
}

Answer 2

Надеюсь, это будет полезно.

#include <iostream>

struct LList
{
    int info;
    LList *next;

    //constructer
    LList(int info_) :info(info_) {
        next = nullptr;
    }
};
void removeMaxValue(LList *&root) {
    int max = 0;

    LList *temp = root;
    //Searching for max value
    while (temp!=nullptr)
    {
        if (temp->info > max)
            max = temp->info;

        temp = temp->next;
    }
    temp = root;
    //Find max value and remove
    while (temp->next->info != max)
        temp = temp->next;

    LList *maxNode = temp->next;

    temp->next = temp->next->next;

    delete maxNode;
}
void print(const LList *root)
{
    while (root!=nullptr)
    {
        std::cout << root->info << " ";
        root = root->next;
    }
    std::cout << std::endl;
}

int main() {

    LList *root = new LList(15);
    root->next= new LList(10);
    root->next->next= new LList(45);
    root->next->next->next = new LList(85);
    root->next->next->next->next = new LList(5);

    //before removing
    print(root);

    removeMaxValue(root);

    //After removing
    print(root);

    std::cin.get();
}

Answer 3

#include <cstdio>
#include <iostream>

struct Stack
{
    int info;
    Stack *next;
    // added just to easy initialization
    Stack(int _info, Stack *_next) : info(_info), next(_next) {}
} *top;

void delMaxValue(Stack *&head) 
{
    // first - find MaxValue in the list
    // as you can see, i save pointer to the previous element in the list
    Stack* max_prev = nullptr;
    Stack* max = head;
    for(Stack *i_prev = nullptr, *i = head; i; i_prev = i, i = i->next) {
         if (max->info < i->info) {
             max_prev = i_prev;
             max = i;
         }
    }
    // max has the maximum value and max_prev is the element before max in the list
    // now we remove max
    if (max_prev == nullptr) {
        // max has no prev, so max is the head of the list. We assign the new head
        head = max->next;
     } else {
        max_prev->next = max->next;
        max->next = NULL;
     }
}

void printStack(Stack *head) {
    std::cout << "Priting " << head << std::endl;
    for(Stack *i = head; i; i = i->next) {
        std::cout << i << " " << i->info << std::endl;
    }
}

int main()
{
    Stack *head = new Stack(1, new Stack(15, new Stack(10, nullptr)));
    printStack(head);
    delMaxValue(head);
    printStack(head);
    return 0;
}

Вы можете быть заинтересованы в списках макросов помощи от bsd, которые теперь доступны в glibc, newlib, openbsd и т. Д., См. здесь .

Answer 4

Ваше первое решение принимает максимальное значение в качестве параметра, а второе - нет.Я предполагаю, что у нас нет максимального значения, и мы вычислим его при обработке стека.

Основной подход должен быть в первую очередь думать о логике.

Шаг 1.) Нам нужно вытолкнуть все элементы, чтобы найти максимальный элемент в стеке.Также нам нужно хранить все значения, которые мы извлекли, в другом стеке (скажем, вспомогательный ).Теперь мы знаем о максимальном значении (скажем, MAX ).

Шаг 2.) Обратите внимание, что теперь у нас будет стек в обратном порядке.Извлеките все элементы из вспомогательного стека и, если значение не является максимальным, вставьте их в исходный стек.

Данные вначале,

Original Stack: 1->2->3->4->100->5->7->NULL
Auxiliary Stack: NULL

Данные после первого шага,

Original Stack: NULL 
Auxiliary Stack: 7->5->100->4->3->2->1->NULL 
MAX: 100

Наконец,

Original Stack: 1->2->3->4->5->7->NULL
Auxiliary Stack: NULL

Попробуйте написать код для этого.Оба ваших решения работают не так, как ожидалось.