Esta dica tem por objetivo, demostrar a construção de uma lista encadeada dinâmica genérica em
C++, utilizando o recurso de templates da linguagem.
Introdução
Listas encadeadas dinâmicas, são estruturas de dados formadas por um conjunto de "nós" que são constituídos pelo dado a ser armazenado (um inteiro, um caractere, etc) e por um ponteiro apontando para o próximo nó na memória, formando assim, uma "corrente" de nós interligados.
A vantagem deste tipo de lista em relação às estruturas estáticas (como vetores com tamanhos previamente definidos), é que estas listas têm seus nós alocados dinamicamente, em tempo de execução, podendo expandir-se dependendo da necessidade da aplicação, ou seja, o tamanho destas listas é variável, dependendo da memória disponível no sistema. Desta forma, é necessário que se tome um certo cuidado para que a aplicação não "estoure" a memória do sistema no decorrer da execução da mesma.
Para que nossa lista possa operar com diferentes tipos de dados, sem que tenhamos que definir uma classe diferente para cada tipo, faremos uso do recurso de templates da linguagem
C++, que possibilita a construção de classes que operam com tipos genéricos de dados.
Desta forma, no momento de instanciar nossa lista, poderemos fazer algo como:
- Lista<int> lista = new Lista<int>() → para inteiros;
- Lista<char> lista = new Lista<char>() → para caracteres, etc.
Implementação
Nossa lista terá as seguintes funcionalidades:
- Inserção no início da lista.
- Inserção no final da lista.
- Inserção dos elementos em ordem crescente.
- Retornar elemento em determinada posição.
- Verificação de existência de determinado elemento.
- Mostrar os elementos presentes na lista.
- Limpar a lista.
A implementação trata, basicamente, de uma classe
C++ utilizando o recurso de templates, para que possamos declarar listas de diversos tipos de dados, não necessitando reescrever a classe para cada um dos tipos desejados.
A classe terá métodos que atenderão às necessidades descritas na lista acima.
Código fonte
#include <iostream>
using namespace std;
//Declaração da classe utilizando o recurso de templates
template <class T>
class Lista
{
private:
//Declaração da struct 'nó'
//T é um tipo genérico que será definido no momento de instanciar um objeto do tipo Lista
//prox é um ponteiro para o próximo elemento da lista
struct no
{
T x;
struct no *prox;
};
//O nó que sera instanciado no momento de inserção na lista
no *novo;
//O nó inicial da lista
no *lista;
public:
//Construtor da classe
Lista()
{
//Instanciamos o nó inicial da lista
lista = new no;
lista->prox = NULL;
}
//Método para inserção no início da lista
void InsereInicio(T x)
{
novo = new no;
novo->x = x;
novo->prox = lista->prox;
lista->prox = novo;
}
//Método para inserção no final da lista
void InsereFim(T x)
{
novo = new no;
novo->x = x;
novo->prox = NULL;
//Utilizamos um nó auxiliar para não corrompermos a lista original ao percorrê-la
no* aux = lista;
while(aux->prox)
{
aux = aux->prox;
}
aux->prox = novo;
}
//Método para inserção dos elementos em ordem crescente
void InsereOrdem(T x)
{
no *novo = new no;
no *aux;
novo->x = x;
if(lista->prox != NULL)
{
if(x < lista->prox->x)
{
novo->prox = lista->prox;
lista->prox = novo;
}
else
{
aux = lista;
while(aux->prox)
{
if(x < aux->prox->x)
{
novo->prox = aux->prox;
aux->prox = novo;
return;
}
aux = aux->prox;
}
novo->prox = NULL;
aux->prox = novo;
}
}
else
{
lista->prox = novo;
novo->prox = NULL;
}
}
//Método que verifica se determinado elemento existe na lista
bool existe(T x)
{
no* aux = lista;
while(aux->prox)
{
if(aux->prox->x == x)
return true;
aux = aux->prox;
}
return false;
}
//Método para retornar um elemento em determinada posição na lista (começando em 0)
T get(int indice)
{
no* aux = lista;
int i = 0;
while(i <= indice && aux->prox)
{
aux = aux->prox;
i++;
}
return aux->x;
}
//Método para limpar a lista
void limpa()
{
lista->prox = NULL;
}
//Método para mostrar os elementos presentes na lista
void mostra()
{
cout << endl;
if(lista->prox == NULL)
{
cout << "Lista vazia";
return;
}
no* aux = lista;
while(aux->prox)
{
cout << aux->prox->x << " ";
aux = aux->prox;
}
}
};
// EXEMPLOS DE UTILIZAÇÃO
int main()
{
//Lista de inteiros
Lista<int>* intLista = new Lista<int>();
int vetor[] = {3,40,6,8,4,1,100,2};
for(int i = 0; i < 8; i++)
{
intLista->InsereOrdem(vetor[i]);
}
intLista->mostra();
int x = intLista->get(2);
cout << "\n" << x ;
intLista->limpa();
delete[] intLista;
//Lista de caracteres
Lista<char>* charLista = new Lista<char>();
for(int i = 65; i < 91; i++)
{
charLista->InsereFim((char)i);
}
charLista->mostra();
charLista->limpa();
charLista->mostra();
delete[] charLista;
return 0;
}
Nenhum comentário foi encontrado.