Skip to main content
simplificados os métodos do exemplo
Fonte Link
arfneto
  • 2,5mil
  • 1
  • 8
  • 12
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->ant  = nullptr;
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
                tamanho += 1;
                return;
            }
            else
            {  // insere no meio
                p->ant->prox = novo;
                novo->ant    = p->ant;
                novo->prox   = p;
                tamanho += 1;}
              tamanho += return;1;
            }return;
        }
        else
        {
            // no fim da lista?
            if (p->prox == nullptr)
            {
                p->prox = novo;
                novo->ant    = p;
                novo->prox   = nullptr;
                fim          = novo;
                tamanho += 1;
                return;
            }
            else
            {
                // ainda na busca, avanca
                p = p->prox;
            }
        };  // if()
    };  // while()
    return;
};
#include <iostream>
using namespace std;
#include "Lista.h"
int main(void)
{
    Lista uma;
    cout << uma; // vazia
    // insere os impares de 1 a 19
    cout << uma;
    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;
}
#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, 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->ant  = nullptr;
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
                tamanho += 1;
                return;
            }
            else
            {  // insere no meio
                p->ant->prox = novo;
                novo->ant    = p->ant;
                novo->prox   = p;
                tamanho += 1;}
              tamanho += return;1;
            }return;
        }
        else
        {
            // no fim da lista?
            if (p->prox == nullptr)
            {
                p->prox = novo;
                novo->ant    = p;
                novo->prox   = nullptr;
                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

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->ant  = nullptr;
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
                tamanho += 1;
                return;
            }
            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;
                novo->prox   = nullptr;
                fim          = novo;
                tamanho += 1;
                return;
            }
            else
            {
                // ainda na busca, avanca
                p = p->prox;
            }
        };  // if()
    };  // while()
    return;
};
#include <iostream>
using namespace std;
#include "Lista.h"
int main(void)
{
    Lista uma;
    // insere os impares de 1 a 19
    cout << uma;
    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;
}
#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->ant  = nullptr;
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
                tamanho += 1;
                return;
            }
            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;
                novo->prox   = nullptr;
                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.

O programa todo tem então esses 3 arquivos que mostrei apenas.

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;
};
#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;
}
#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

Fonte Link
arfneto
  • 2,5mil
  • 1
  • 8
  • 12

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->ant  = nullptr;
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
                tamanho += 1;
                return;
            }
            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;
                novo->prox   = nullptr;
                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;
    // insere os impares de 1 a 19
    cout << uma;
    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->ant  = nullptr;
                novo->prox = ini;
                ini->ant   = novo;
                ini        = novo;
                tamanho += 1;
                return;
            }
            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;
                novo->prox   = nullptr;
                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.

O programa todo tem então esses 3 arquivos que mostrei apenas.