0

Надо удалить наибольший элемент из первых 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;
}
1
  • 1
    Пробежаться по этим "первым элементам", запоминая значение и индекс, найти максимальный, а потом его по индексу и грохнуть...
    – Akina
    29 мая 2018 в 10:11

2 ответа 2

2

Делаем одну переменную, указывающую на предыдущий узел списка. Сначала он 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++ я думаю вам не в лом.

0
1
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; чтобы явно выразить о своем намерении не менять состояние обьекта.

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

1
  • Понял, принял. Спасибо)
    – MiT
    30 мая 2018 в 11:44

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.