Home > Tecnologia > Informática > Programação > C++ > Listas ligadas simples em C++ (Parte II)

Listas ligadas simples em C++ (Parte II)

Na primeira parte deste artigo, vimos a definição de listas ligadas simples e métodos de inserção de nós. Agora vamos ver métodos de remoção.

Remoção à cabeça

Listas ligadas simples em C++ (Parte II)

Na figura acima, podemos ver que, se pretendemos remover o primeiro nó de uma lista (remoção à cabeça), o processo é muito simples. Precisamos de aceder a este nó, que está a ser apontado pela cabeça, obter o apontador para o segundo nó e copiá-lo para a cabeça. Desta forma, a cabeça passará a apontar para o segundo nó, o qual passará então a ser o primeiro nó. Por fim, libertamos o primeiro nó da memória. Já iremos ver o código mais à frente, o qual contemplará esta situação.

Remoção a meio da lista e à cauda

Listas ligadas simples em C++ (Parte II)

Para removermos um nó no meio da lista, temos que procurá-lo a partir do nó anterior. Isto porque, iremos precisar de ter acesso ao nó anterior para poder copiar o apontador do nó seguinte, do nó que pretendemos remover, para o nó anterior. Desta forma, fazemos o apontador do nó seguinte, do nó anterior ao que queremos eliminar, apontar para o nó que está a seguir a este (seta verde). Feita esta operação, poderemos libertar da memória o nó que queremos remover.

A remoção à cauda pode ser feita exactamente pelo mesmo processo, pois, nesse caso, o apontador do nó seguinte, do nó que queremos remover, está a apontar para NULL. Ao copiar este apontador para o nó anterior, estamos a torná-lo o novo último nó!

Vamos ver o código em C++, que vai procurar um nó com um determinado valor para o remover:

    int v = valor_a_remover;
    bool removeu = false;
    no = cabeca;
    if (no->valor==v) {
        cabeca = no->seguinte;
        free(no);
        removeu = true;
    }
    else {
        while (no->seguinte!=NULL) {
            No *remover = no->seguinte;
            if (remover->valor==v) {
                no->seguinte = remover->seguinte;
                free(remover);
                removeu = true;
                break;
            }
            no = no->seguinte;
        }
    }
    if (!removeu) {
        cout << "O valor não foi encontrado!" << endl;
    }

Podemos ver, na linha 1, que declaramos uma variável inteira “v” com o valor que pretendemos remover. Na linha 4, testamos se o valor está no nó apontado pela cabeça (primeiro nó). Caso esteja, estamos perante uma remoção à cabeça! Então, na linha 5 alteramos a cabeça para apontar para o nó seguinte (segundo nó) e a seguir libertamos da memória o nó que queremos remover. Caso contrário, teremos que procurar o nó anterior ao que queremos eliminar num ciclo “while” (linha 10). Em cada iteração do ciclo, obtemos a referência ao nó seguinte (linha 11) para testar se é o que queremos remover (linha 12). Quando encontrarmos o nó que queremos remover, copiamos o seu apontador do nó seguinte para o nó anterior (linha 13) e, em seguida, libertamos o nó a remover da memória (linha 14). O código testa ainda se o valor a remover foi encontrado e exibe uma mensagem caso não o encontre.

Note que, neste código, não testámos se a lista estava vazia. Mas tal processo deve ser feito, como poderá ver mais abaixo, no código completo.



Outro aspecto importante, é que devemos sempre libertar da memória todos os nós que estejam ainda alocados, quando o programa termina. Uma forma de o fazer é implementando um método recursivo que vai até ao final da lista e começa a remover os nós do último ao primeiro:

void liberta_lista(No *n) {
    if (n!=NULL) {
        liberta_lista(n->seguinte);
        cout << "A libertar a nó com o valor: " << n->valor << endl;
        free(n);
    }
    else {
        return;
    }
}

Antes de terminar o programa, evocamos este método passando a cabeça como argumento!

    liberta_lista(cabeca);

Vejamos agora o programa completo:

#include <iostream>
#include <stdlib.h>

using namespace std;

struct No {
    int valor;
    No *seguinte;
};

void liberta_lista(No *n) {
    if (n!=NULL) {
        liberta_lista(n->seguinte);
        cout << "A libertar o nó com o valor: " << n->valor << endl;
        free(n);
    }
    else {
        return;
    }
}

int main() {
    
    No *cabeca = NULL;
    No *no = NULL;
    char menu = ' ';
    
    while (menu!='0') {
        
        cout << "1 - Inserir valor à cabeça" << endl;
        cout << "2 - Inserir valor no fim" << endl;
        cout << "3 - Listar valores dos nós" << endl;
        cout << "4 - Remover nó de valor x" << endl;
        cout << "0 - Sair do programa" << endl;
        cin >> menu;
        
        switch (menu) {
            case '0':
                break;
            case '1':
                char valor_para_cabeca[6];
                cout << "Introduza um novo valor para o inicio da lista: ";
                cin >> valor_para_cabeca;
                no = (No*) malloc(sizeof(No));
                no->valor=atoi(valor_para_cabeca);
                if (cabeca==NULL) {
                    no->seguinte = NULL;
                }
                else {
                    no->seguinte = cabeca;
                }
                cabeca = no;
                break;
            case '2':
                char valor_para_fim[6];
                cout << "Introduza um novo valor para o fim da lista: ";
                cin >> valor_para_fim;
                no = (No*) malloc(sizeof(No));
                no->valor=atoi(valor_para_fim);
                no->seguinte = NULL;
                if (cabeca==NULL) {
                    cabeca = no;
                }
                else {
                    No *procura_ultimo = cabeca;
                    while (procura_ultimo->seguinte!=NULL) {
                        procura_ultimo = procura_ultimo->seguinte;
                    }
                    procura_ultimo->seguinte = no;
                }
                break;
            case '3':
                if (cabeca==NULL) {
                    cout << "A lista está vazia!" << endl;
                }
                else {
                    no = cabeca;
                    while (no!=NULL) {
                        cout << "Valor: " << no->valor << endl;
                        no = no->seguinte;
                    }
                }
                break;
            case '4':
                if (cabeca==NULL) {
                    cout << "A lista está vazia!" << endl;
                }
                else {
                    char valor_remover[6];
                    cout << "Introduza o valor a remover: ";
                    cin >> valor_remover;
                    int v = atoi(valor_remover);
                    bool removeu = false;
                    no = cabeca;
                    if (no->valor==v) {
                        cabeca = no->seguinte;
                        free(no);
                        removeu = true;
                    }
                    else {
                        while (no->seguinte!=NULL) {
                            No *remover = no->seguinte;
                            if (remover->valor==v) {
                                no->seguinte = remover->seguinte;
                                free(remover);
                                removeu = true;
                                break;
                            }
                            no = no->seguinte;
                        }
                    }
                    if (!removeu) {
                        cout << "O valor não foi encontrado!" << endl;
                    }
                }
                break;
            default:
                printf("Opção inválida!");
                break;
        }
        
    }
    
    liberta_lista(cabeca);
    
    return 0;
    
}



Na terceira parte deste artigo iremos implementar esta lista em classes.

Listas ligadas simples em C++ (Parte III)

Este artigo foi escrito de acordo com a antiga grafia.

About Carlos Santos

Frequência em mestrado de Engenharia Electrotécnica e de Computadores. Programador freelancer: Websites, Aplicações Web (JAVA e PHP), J2SE/J2EE, C/C++ e Android. Explicador e formador em informática, matemática e electrotecnia. Formação presencial ou remota através de Skype e Team Viewer. Interesses: Música, áudio, vídeo, ciência, astronomia e mitologia.

Leave a Reply

Your email address will not be published and it is optional.