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 comostruct
mas DENTRO deLista
. Parece mais conveniente assim. E como éprivate
não é visível fora da classe. Como criar umNo
sem valor não está previsto no seu código, o construtor padrão foi invalidado e só pode criar umNo
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 destd::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