-2

Preciso inserir valores inteiros numa lista simplesmente encadeada de forma que eles fiquem ordenados de forma crescente independente da ordem que foram inseridos.

Exemplo: se eu inserir os valores 5, 1, 3
eles devem ser organizados na lista como 1, 3, 5;

De acordo com o exercicio proposto pelo meu professor, a função obrigatoriamente deve ser void, recebendo como parametro apenas o valor que vai ser inserido no nó.
O codigo que desenvolvi foi o seguinte, a função responsavel por inserir em ordem crescente é a 'void ListaEncad::inserirCrescente(int val)' porem não consigo identificar aonde estou errando e o que eu deveria fazer para conseguir ordenar de forma crescente.

#include "listaEncad.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstddef>

ListaEncad::ListaEncad()
{
    this->primeiro = NULL;
}
ListaEncad::~ListaEncad()
{
    No *p = primeiro;
    while (p != NULL)
    {
        No *t = p->getProx();
        delete p;
        p = t;
    }
}
void ListaEncad::imprime()
{
    No *p = primeiro;
    while (p != NULL)
    {
        printf("%i ", p->getInfo());
        p = p->getProx();
    }
}
void ListaEncad::inserirCrescente(int val)
{
    No *novo = new No();
    No *anterior = NULL;
    No *p = primeiro;

    while (p != NULL && p->getInfo() < val)
    {
        anterior = p;
        p = p->getProx();
    }
    if (anterior == NULL)
    {
        novo->setProx(p);
        p = novo;
    }
    else
    {
        novo->setProx(anterior->getProx());
        anterior->setProx(novo);
    }
}

listaEncad.h

#include "no.h"
class ListaEncad
{
public:
    ListaEncad();
    ~ListaEncad();
    void imprime();
    void inserirCrescente(int val);

private:
    No *primeiro;
};

no.h

class No
{
private:
    int info;
    No *prox;

public:
    No();
    ~No();
    int getInfo();
    No *getProx();
    void setInfo(int n);
    void setProx(No *p);
};

no.cpp

#include <iostream>
#include "no.h"

No::No()
{
}
No::~No()
{
}
int No::getInfo()
{
    return info;
}
No *No::getProx()
{
    return prox;
}
void No::setInfo(int info)
{
    this->info = info;
}
void No::setProx(No *p)
{
    this->prox = p;
}

Minha classe main

#include <iostream>
#include <stdio.h>
#include "listaEncad.h"
using namespace std;

int main()
{
    ListaEncad lista;
    int n, val;
    printf("Informe o tamanho da lista: ");
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        printf("Insira o %iº valor: ", i);
        cin >> val;
        lista.inserirCrescente(val);
    }
    lista.imprime();
    return 0;
}
7
  • É difícil imaginar um professor que sugira uma função que insere numa lista e não passa o endereço da lista como parâmetro. Para fazer isso tem que ter a lista global, o que é uma bobagem. De todo modo poste um programa completo. Onde está o .h da lista? Uma lista não é um nó. Um nó não é uma lista nem o dado da lista. Não programe assim: só vai ter mais trabalho. Para inserir numa ordem apenas use uma função de comparação para determinar o local de inserção, como faz por exemplo o sort() em C++
    – arfneto
    16/10/2021 às 14:12
  • Boa tarde @arfneto, fiz a edição na postagem com os demais códigos. 16/10/2021 às 18:20
  • E onde estaria main()? Os includes do usuário em geral devem vir depois dos includes do sistema. Os "" depois dos <> porque podem depender deles
    – arfneto
    16/10/2021 às 18:57
  • É muito mais complicado usar listas com ponteiros para um lado só. Precisa mesmo fazer assim? É mais complicado, a toa. Mantenha o tamanho atualizado dentro da lista
    – arfneto
    16/10/2021 às 19:00
  • Como o No é private na lista não há razão para ser uma classe separada e com getters e setters. Só atrapalha.
    – arfneto
    16/10/2021 às 19:04

1 Resposta 1

-1
void ListaEncad::inserirCrescente(int val)
{
    No *novo = new No();
    No *anterior = NULL;
    No *p = primeiro;

    while (p != NULL && p->getInfo() < val)
    {
        anterior = p;
        p = p->getProx();
    }
    if (anterior == NULL)
    {
        novo->setProx(p);
        p = novo;
    }
    else
    {
        novo->setProx(anterior->getProx());
        anterior->setProx(novo);
    }
}

Acho que não precisava de uma classe para No porque No só é usado dentro da lista e foi declarado private. Por essa razão também pode ser trabalho a toa declarar getters e setters para uma classe que é interna à implementação.

Veja esse exemplo para Lista.h:

#pragma once
class Lista
{
private:
    struct No
    {
        int info;
        No* ant;
        No* prox;
        No() = delete;
        No(int v) : info(v), ant(nullptr), prox(nullptr){};
        ~No(){};
    };
    No*    ini; // inicio E fim da lista
    No*    fim;
    size_t tamanho; // questao pratica

   public:
    Lista();
    ~Lista();
    void insere(const int);
    size_t size();
    bool vazia();
    friend std::ostream& operator<<(std::ostream& out, Lista& c);
};

É bem semelhante ao que escreveu, mas:

  • No foi declarado como struct mas DENTRO de Lista. Parece mais conveniente assim. E como é private não é visível fora da classe. Como criar um No sem valor não está previsto no seu código, o construtor padrão foi invalidado e só pode criar um No com o valor dentro. Mais simples. Veja no código exemplo abaixo.
  • Tem ponteiros para os dois lados assim é mais fácil seguir a lista para frente ou para trás sem declarar e salvar novos ponteiros
  • Tem o tamanho atualizado dentro da lista e isso ajuda muito porque é algo essencial a toda hora
  • ~Lista apaga todo mundo e assim libera a memória
  • << foi redefinido para a função de imprime(), o que é clássico em C++ e muito mais fácil de ler porque pode usar dentro de std::cout
  • inserirCrescente() é insere() apenas porque afinal só tem um critério de inserção mesmo.

Uma versão de insere()

Essa versão é um pouco mais comprida porque tem ponteiros para os dois lados. Pode apagar um deles e vai funcionar de modo similar.

void Lista::insere(const int val)
{
    No* novo      = new No(val);
    if (tamanho == 0)
    {
        ini = fim = novo;
        tamanho   = 1;
        return;
    };
    // busca a posicao
    No* p = ini;
    while (p != nullptr)
    {  // enquanto nao acabar a lista
        if (val < p->info)
        {  // vai inserir antes de p
            if (p->ant == nullptr)
            {   // insere no inicio
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
            }
            else
            {  // insere no meio
                p->ant->prox = novo;
                novo->ant    = p->ant;
                novo->prox   = p;
            }
            tamanho += 1;
            return;
        }
        else
        {   // no fim da lista?
            if (p->prox == nullptr)
            {
                p->prox = novo;
                novo->ant    = p;
                fim          = novo;
                tamanho += 1;
                return;
            }
            else // ainda na busca, avanca
                p = p->prox;
        };  // if()
    };  // while()
    return;
};

um programa de teste para essa classe

Esse programa cria uma Lista inserindo ímpares de 1 a 19 e depois pares de 20 a 2 e depois inteiros de 0 a -9 inclusive, para um total de 30 valores

#include <iostream>
using namespace std;
#include "Lista.h"
int main(void)
{
    Lista uma;
    cout << uma; // vazia
    // insere os impares de 1 a 19 
    for (int i = 1; i < 20; i += 2) uma.insere(i);
    // insere os pares de 20 a 2
    for (int i = 20; i > 1; i -= 2) uma.insere(i);
    // insere de 0 a -9
    for (int i = 0; i > -10; i -= 1) uma.insere(i);
    // devem ser 30 elementos
    cout << uma;
    return 0;
}

saída do exemplo

Lista vazia
Lista tem 30 elementos:
-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1,\
 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,\ 
 15, 16, 17, 18, 19, 20

Apaga: -9, -8, -7, -6, -5, -4, -3, -2, -1, 0,\
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,\
 15, 16, 17, 18, 19, 20

Lista.cpp

#include <iostream>
#include "Lista.h"

Lista::Lista() : tamanho(0), ini(nullptr), fim(nullptr){};

Lista::~Lista()
{   // apaga todo mundo
    std::cout << "Apaga: ";
    if (tamanho == 0) return; // vazia
    No* p    = ini;
    No* prox = p->prox;
    for (size_t i = 0; i < tamanho-1; i += 1)
    {   std::cout << p->info << ", ";
        delete p;
        p = prox, prox = p->prox;
    }
    std::cout << p->info << "\n";
    delete p;
}

void Lista::insere(const int val)
{
    No* novo      = new No(val);
    if (tamanho == 0)
    {
        ini = fim = novo;
        tamanho   = 1;
        return;
    };
    // busca a posicao
    No* p = ini;
    while (p != nullptr)
    {  // enquanto nao acabar a lista
        if (val < p->info)
        {  // vai inserir antes de p
            if (p->ant == nullptr)
            {   // insere no inicio
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
            }
            else
            {  // insere no meio
                p->ant->prox = novo;
                novo->ant    = p->ant;
                novo->prox   = p;
            }
            tamanho += 1;
            return;
        }
        else
        {   // no fim da lista?
            if (p->prox == nullptr)
            {
                p->prox = novo;
                novo->ant    = p;
                fim          = novo;
                tamanho += 1;
                return;
            }
            else // ainda na busca, avanca
                p = p->prox;
        };  // if()
    };  // while()
    return;
};

size_t Lista::size() { return tamanho; }

bool Lista::vazia() { return tamanho == 0; };

std::ostream& operator<<(std::ostream& out, Lista& L)
{
    if (L.vazia())
    {
        out << "Lista vazia\n";
        return out;
    }
    std::cout << "Lista tem " << L.tamanho << " elementos:\n";
    Lista::No* p = L.ini;  // inicio
    for (size_t i = 0; i < L.tamanho - 1; i += 1)
    {
        out << p->info << ", ";
        p = p->prox;
    };
    out << p->info << "\n\n";
    return out;
}

A memória é liberada ao final e deixei uns cout para o teste, mas pode ser exagero: é só para ilustrar o funcionamento.

O programa todo tem então esses 3 arquivos que mostrei apenas: List.h Lista.cpp e main.cpp

3
  • Muito obrigado ! 16/10/2021 às 21:45
  • Então uma resposta que inclui uma discussão do problema com o código original, mais um programa de teste comentado e com a execução do exemplo e uma descrição das classes, e aceita como resposta pelo autor da pergunta. é marcada como pouco útil por um usuário que prefere não se identificar? Muito útil a atitude
    – arfneto
    19/10/2021 às 4:02
  • Sinceramente, queria saber o que a comunidade do StackOverflow ganha fazendo isso... Sou novo por aqui e praticamente toda pergunta nova que vejo tem alguém pra "negativar" a pergunta e a resposta sem nenhum motivo aparente... Sacanagem viu... 23/10/2021 às 18:49

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .