Listas ligadas simples em C++ (Parte III)

Na primeira parte e segunda parte deste artigo, vimos a definição de listas ligadas simples, métodos para inserir, remover e listar nós e um exemplo com uma lista de nós usando uma “struct” para definir cada nó. Agora, vamos implementar uma lista ligada simples com classes e com algumas abordagens um pouco diferentes, relativamente à gestão dos nós, das que vimos nos exemplos anteriores. No fim, poderá encontrar um link para fazer o download de todos os ficheiros com comentários. Nos troços de código aqui exemplificados, não estão contemplados os “include“.

Nesta implementação, os nós são inseridos de forma ordenada e não é permitida a duplicação de valores.

Vamos encontrar 3 classes:

• No (nó)
• Lista
• Iterador

A classe “No” é a mais simples e está reduzida apenas a um ficheiro de cabeçalho (em “No.h”). Vamos ver a definição da classe:

class No {
public:
    No(const int v = 0, No *no = NULL) : valor(v), seguinte(no) {}
    ~No() {}
    int valor;
    No *seguinte;
};

No construtor da classe (linha 3), podemos passar, como parâmetros, um valor para o nó e o apontador do próximo nó. Por omissão, o valor é zero e o apontador para o nó seguinte é NULL.

Vejamos agora a definição da classe “Lista” (em “Lista.h”):

class Lista {
private:
    No *cabeca;
public:
    Lista();
    ~Lista();
    bool vazia();
    bool insere(int);
    bool remove(int);
    void limpar();
    Iterador *obtemIterador();
};

Repare que fazemos aqui uma referência a uma classe “Iterador” que irá servir para listar os nós. Repare também que a cabeça está declarada como “private“, pelo que só poderemos aceder aos nós através do Iterador, como iremos ver mais à frente.

Temos nesta classe, os seguintes métodos e funções:

• vazia() – devolve “verdade” se a lista não tiver nós (lista vazia) ou “falso” se a lista tiver nós.
• insere(int) – Insere um nó, com um número inteiro, na lista de forma ordenada. Devolve “verdade” se o nó foi inserido com sucesso ou “falso” se o número já se encontra armazenado.
• remove(int) – Remove o nó que contem o número inteiro passado como parâmetro. Devolve “verdade” se o nó foi removido com sucesso ou “falso” se o valor não foi encontrado na lista ou esta estiver vazia.
• limpar() – Remove todos os nós da lista.
• obtemIterador() – Devolve um iterador para podermos aceder aos nós da lista, começando pelo nó apontado pela cabeça (primeiro nó).

Implementação da classe (em “Lista.cpp”):

Lista::Lista() {
    cabeca = new No();
}

Lista::~Lista() {
    if (!vazia()) {
        limpar();
    }
    delete cabeca;
}

bool Lista::vazia() {
    return (cabeca->seguinte==NULL);
}

bool Lista::insere(int v) {
    No *pesquisa = cabeca;
    while (pesquisa->seguinte!=NULL) {
        No *teste = pesquisa->seguinte;
        if (teste->valor==v) {
            return false;
        }
        else {
            if (teste->valor > v) {
                break;
            }
        }
        pesquisa = pesquisa->seguinte;
    }
    No *novo = new No(v, pesquisa->seguinte);
    pesquisa->seguinte = novo;
    return true;
}

bool Lista::remove(int v) {
    if (vazia()) {
        return false;
    }
    No *pesquisa = cabeca;
    while (pesquisa->seguinte!=NULL) {
        No *teste = pesquisa->seguinte;
        if (teste->valor==v) {
            pesquisa->seguinte = teste->seguinte;
            delete teste;
            return true;
        }
        pesquisa = pesquisa->seguinte;
    }
    return false;
}

void Lista::limpar() {
    while (cabeca->seguinte!=NULL) {
        No *remove = cabeca->seguinte;
        cabeca->seguinte = remove->seguinte;
        std::cout << "A apagar o nó com o valor: " << remove->valor << std::endl;
        delete remove;
    }
}

Iterador *Lista::obtemIterador() {
    Iterador *i = new Iterador(cabeca);
    return i;
}

Vejamos agora algumas considerações relevantes e algumas diferenças:

• Repare que, no construtor da classe, definimos a cabeça como um nó que, por omissão, terá o seu valor a zero e o apontador para o nó seguinte a NULL (linha 2). Na implementação anterior (partes 1 e 2 deste artigo), a cabeça era definida como um apontador directo ao primeiro nó. Agora, será o apontador “seguinte” do “nó cabeça” que irá apontar para o primeiro nó. Desta forma, simplificamos os métodos de inserção e remoção de nós, pois não iremos precisar de testar se estas operações estão a ser feitas à cabeça ou não, uma vez que a cabeça será sempre vista como um hipotético “primeiro” nó, cujo valor será sempre ignorado.
• Um pormenor do destrutor da classe (linha 5), em vez de uma função recursiva, vamos usar um método diferente para limpar os nós da lista, como iremos ver em seguida. Como a cabeça foi declarada como um objecto da classe “No”, temos que a destruir como a instrução “delete” (linha 9).
• Para testar se a lista está vazia, já não o fazemos testando se a cabeça aponta para NULL, mas sim se o seu apontador “seguinte” é NULL (linha 13).
• Para inserir um novo nó, e como já foi referido, bastará implementar o código como se a inserção fosse feita em qualquer parte da lista. É testado se o valor já se encontra na lista (linha 20), retornando “falso” caso o valor seja encontrado, e procurando um nó cujo valor seja superior ao que se pretende inserir (linha 24), saindo do ciclo caso seja encontrado. No fim, na linha 30, o novo nó será inserido antes do nó que tem um valor maior do que o estamos a inserir ou à cauda, caso o novo valor seja o maior que existe na lista (o ciclo “while” termina sem terem sido encontrados valores superiores). Este processo de inserção é análogo ao que vimos na primeira parte deste artigo.
• A remoção de um nó é feita de forma análoga à remoção de um nó em qualquer parte da lista, ou à cauda, conforme vimos na segunda parte deste artigo, em que vamos testar sempre um nó à frente (linha 41).
• Para limpar a lista, em vez de usarmos um método recursivo, vamos fazendo sucessivas remoções à cabeça (a partir do apontador “seguinte” do “nó cabeça”) até esta ficar vazia (ciclo “while” na linha 53). O “cout” na linha 56, serve apenas para o leitor ter a noção dos nós que são removidos.
• Por fim, temos a função para obter o iterador da lista, que devolve um iterador iniciado com o “nó cabeça” (linha 62). Vamos ver esta classe já a seguir.

Definição da classe “Iterador” (em “Iterador.h”):

class Iterador {
private:
    No *no;
public:
    Iterador(No *no);
    ~Iterador();
    No *obterNo();
};

Aqui temos apenas a função “obterNo()” que devolve o nó que está a ser iterado.

Implementação da classe (em “Iterador.cpp”):

Iterador::Iterador(No *no) {
    this->no = no;
}

Iterador::~Iterador() {}

No *Iterador::obterNo() {
    if (no==NULL) {
        return NULL;
    }
    no = no->seguinte;
    return no;
}

Repare que, no construtor, copiamos o apontador recebido (que será a cabeça, caso estejamos a receber este iterador a partir da lista) para o objecto “no” local (linha 2).

Na função “obterNo()”, devemos testar se o iterador já chegou ao fim (linha 8), quando o “no” é NULL. Normalmente, pode-se implementar uma excepção para estes casos, mas aqui limitamos-nos a devolver NULL, o mesmo que acontece quando chegamos ao fim da lista. Na linha 11, avançamos sempre o iterador para o próximo nó antes de o devolver. Desta forma, quando este é criado e recebe o “nó cabeça”, irá devolver o primeiro nó e, quando chegar ao fim, irá devolver NULL. Podemos então usar este iterador, para listar todos os nós da lista, num ciclo até que este devolva NULL.

O exemplo que se segue, tirado do ficheiro “main.cpp”, ilustra este caso:

    Iterador *i = lista->obtemIterador();
    No *no;
    while ((no=i->obterNo())!=NULL) {
        cout << "Valor: " << no->valor << endl;
    }
    delete i;

Não vou abordar mais o código do ficheiro “main.cpp”, pois a sua implementação é bastante trivial, no que diz respeito ao uso da classe “Lista”.

Pode fazer o download do ficheiro “classe_lista.zip“ que contem todos os ficheiros das classes e o ficheiro “main.cpp” com comentários. A codificação de caracteres está em UTF-8 e os fins de linha em modo OS X / UNIX.

Observações:

• A implementação de listas, pilhas, filas e outras estruturas semelhantes, existe na biblioteca STL (Standard Template Library) do C++. Porém, para estudo, é sempre boa ideia começar pelas suas próprias implementações para melhor compreende o funcionamento destas estruturas.
• Este exemplo está limitado a valores inteiros. Uma lista pode ser implementada para ser usada de forma genérica com o uso de “templates“. Oportunamente, irei falar sobre classes com “templates“.

Este artigo foi escrito de acordo com a antiga grafia.