Найти и удалить максимальный элемент в списке. (C++)

354

18 июня 2018, 20:10

Надо удалить наибольший элемент из первых n-элементов списка. Как-то не соображу как это сделать. Подскажите, пожалуйста, как это сделать.

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define List struct list
List
{
    int Dn;
    List* Nx;
};
class cList
{
protected:
    List* p;
public:
    cList() : p(NULL) {}
    ~cList();
    int Empty() { return p == NULL; }
    void AddHead(int D)
    {
        List* q = new(List);
        q->Dn = D;
        q->Nx = p;
        p = q;
    }
    void Display();
    void AddEnd(int D);
    long Len();
    void DelFirst()
    {
        List* q = p;
        p = p->Nx;
        delete(q);
    }
};
void cList::Display()
{
    List* t = p;
    if (p)
        while (t)
        {
            cout << t->Dn << " ";
            t = t->Nx;
        }
    else cout << "->|";
    cout << endl;
};
void cList::AddEnd(int D)
{
    List* q = new List;
    q->Dn = D;
    q->Nx = NULL;
    List* t = p;
    if (p)
    {
        while (t->Nx) t = t->Nx;
        t->Nx = q;
    }
    else p = q;
};
long cList::Len()
{
    if (p)
    {
        List* t = p;
        long i = 0;
        while (t)
        {
            t = t->Nx;
            i++;
        };
        return i;
    };
    return 0;
};
cList::~cList()
{
    while (!Empty()) DelFirst();
};
int main()
{
    cout << "Demo List" << endl;
    int A[12] = {23, 19, 14, 43, 17, 22, -31, 46, -7, 2, 64, 53};
    cList L1;
    cout << "The list is empty?:" << L1.Empty() << endl;
    L1.Display();
    cout << endl;
    for (int i = 0; i < 12; i++) L1.AddEnd(A[i]);
    L1.Display();
    cout << endl;
    cout << "Count Element = " << L1.Len() << endl;
    L1.~cList();
    system("pause");
    return 0;
}

Answer 1

Делаем одну переменную, указывающую на предыдущий узел списка. Сначала он nullptr, так как у начала списка предыдущего узла нет. Проходим список, проверяем кто больше в памяти. Если найдём конкурента, меняем указатель на ПРЕДЫДУЩИЙ узел. После прохода списка, у ПРЕДЫДУЩЕГО ссылку на следующего менять на следующий после максимального. Удаляем узел списка, где макс элемент найден.

АЛГОРИТМ УДАЛИТЬМАКСИМАЛЬНЫЙ:
ЕСЛИ p==nullptr ОШИБКА
List * ПРЕДЫДУЩИЙ = nullptr ;
int МАКСИМАЛЬНОЕЗНАЧЕНИЕ = p -> Dn ;
List * ИНДЕКССПИСКАПРЕДЫДУЩИЙ = p ;
List * ИНДЕКССПИСКА = p -> Nx ;
size_t СЧЁТЧИК = 1 ;
while ( ИНДЕКССПИСКА И СЧЁТЧИК < N ) {
  ЕСЛИ ИНДЕКССПИСКА -> Dn > МАКСИМАЛЬНОЕЗНАЧЕНИЕ ТО {
    ПРЕДЫДУЩИЙ := ИНДЕКССПИСКАПРЕДЫДУЩИЙ
    МАКСИМАЛЬНОЕЗНАЧЕНИЕ := ИНДЕКССПИСКА -> Dn ; }
  ИНДЕКССПИСКАПРЕДЫДУЩИЙ := ИНДЕКССПИСКА
  ИНДЕКССПИСКА := ИНДЕКССПИСКА -> Nx ;
  ++ СЧЁТЧИК ; }
ЕСЛИ ПРЕДЫДУЩИЙ == nullptr ТО DelFirst();
ИНАЧЕ {
  List * МАКСИМАЛЬНЫЙ := ПРЕДЫДУЩИЙ -> Nx ;
  ПРЕДЫДУЩИЙ -> Nx := МАКСИМАЛЬНЫЙ -> Nx ;
  delete МАКСИМАЛЬНЫЙ ; }

Перевести алгоритм на C++ я думаю вам не в лом.

Answer 2

void cList::delete_maxElement()
{
    if (!p) return;
    List* ptr = p, *prev = p;
    for (List* q = p; q; q = q->Nx) {
        if (q->Dn > ptr->Dn)
            ptr = q;
    }
    if (ptr == p) {
        DelFirst();
        return;
    }
    for (; prev->Nx != ptr; prev = prev->Nx);
    if (ptr->Nx)
        prev->Nx = ptr->Nx;
    else {
        prev->Nx = 0;
    }
    delete ptr;
}

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

Во вторых: ваши селекторы не придворены модификатором const, т.е. те функции, которые не меняют состояние обьекта ( они обычно обьвляются в классе последными как признак хорошего стилья), такие как void Display() const; чтобы явно выразить о своем намерении не менять состояние обьекта.

В третьих: не нужно вызвать деструктор класса явно, он и так вызывается, поэтому вызвать деструктор явно, означает вызвать его два раза...

Создание интернет-магазина спортивных товаров в ABCname

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

задача на вектор

Сережа и Дима играют в игруПеред игроками лежат в ряд n карточек,На каждой карточке написано число, причем все числа на карточках различны,Игроки...

233

c++

Что нужно сделать, чтобы при компиляции под x64_32 передать ссылку на функцию?

При вызове MessageSubscribe в hCallback передаётся часть кода функции main_loop, а не указательИзменение HPROC на void* ничего не меняет

184

c++

Можно ли хранить объекты разных классов (производных одного абстрактного класса) в одном массиве или списке?

Допустим имеется один абстрактный класс: Word - от него производим два класса: Noun и VerbТут сталкиваемся с вопросом: как хранить объекты этих классов?...

199

c++

Не создаётся QWidget без Qapplication

Когда я скомпилировал мой qt проект , он показал такую ошибкуПочему ??

190