Desenvolvimento de Lista Encadeada Dinâmica Genérica

Publicado por Danilo Renato da Silva em 08/10/2014

[ Hits: 12.085 ]

Blog: http://widgetscomcafe.blogspot.com/

0 0

Denuncie Favoritos Indicar Impressora

Desenvolvimento de Lista Encadeada Dinâmica Genérica

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

Outras dicas deste autor

Sobrecarga de Operadores em C++

Leitura recomendada

Ter computador é o suficiente para Inclusão Digital?

Monitorando rede com Zabbix

Sarg - Configurando recurso padrão para relatórios diários, semanais e mensais

Como instalar o Divulga (Resultado das Eleições 2014)

TexLive - Latex em qualquer lugar!

Comentários

Nenhum comentário foi encontrado.