Desafio 1: Implemente o TAD Listas duplamente ligadas de inteiros. Deve ter as operações abaixo: (2 V):
c. Remover nó

Passo 1

Beleza, vamos lá! O desafio aqui é implementar o Tipo Abstrato de Dados (TAD) para Listas Duplamente Ligadas de inteiros, focando na operação de remover um nó. Isso faz parte da estrutura de dados chamada listas ligadas, onde cada elemento aponta tanto para o próximo quanto para o anterior, facilitando a inserção e remoção de elementos. Para resolver isso, vamos precisar entender como funcionam os nós dessas listas e como ajustar os ponteiros ao remover um nó específico.

Passo 2

Primeiro, precisamos definir como é um nó em uma lista duplamente ligada. Cada nó tem três partes: o valor (um inteiro, no nosso caso), um ponteiro para o nó anterior e outro para o próximo nó. Em código, isso pode ser representado assim:
\begin{verbatim}
typedef struct No {
    int valor;
    struct No* anterior;
    struct No* proximo;
} No;
\end{verbatim}

Passo 3

Agora, vamos criar a estrutura da lista que vai armazenar esses nós. A lista deve ter um ponteiro para o primeiro nó e outro para o último, facilitando operações como inserção e remoção. Veja como fica:
\begin{verbatim}
typedef struct ListaDuplamenteLigada {
    No* primeiro;
    No* ultimo;
} ListaDuplamenteLigada;
\end{verbatim}

Passo 4

Para implementar a função de remover um nó, precisamos considerar alguns casos:
  1. A lista está vazia: Não há o que remover.
  2. O nó a ser removido é o primeiro: Precisamos atualizar o ponteiro do primeiro nó.
  3. O nó a ser removido é o último: Atualizamos o ponteiro do último nó.
  4. O nó está no meio da lista: Ajustamos os ponteiros dos nós anterior e próximo para pular o nó removido.

Passo 5

Vamos agora implementar a função removerNo. Ela receberá a lista e o valor a ser removido. A função irá procurar o nó com o valor especificado e ajustar os ponteiros conforme necessário.
\begin{verbatim}
void removerNo(ListaDuplamenteLigada* lista, int valor) {
    if (lista->primeiro == NULL) {
        printf("Lista vazia. Nada para remover.\n");
        return;
    }

    No* atual = lista->primeiro;

    while (atual != NULL && atual->valor != valor) {
        atual = atual->proximo;
    }

    if (atual == NULL) {
        printf("Valor %d não encontrado na lista.\n", valor);
        return;
    }

    if (atual->anterior != NULL) {
        atual->anterior->proximo = atual->proximo;
    } else {
        lista->primeiro = atual->proximo;
    }

    if (atual->proximo != NULL) {
        atual->proximo->anterior = atual->anterior;
    } else {
        lista->ultimo = atual->anterior;
    }

    free(atual);
    printf("Valor %d removido com sucesso.\n", valor);
}
\end{verbatim}

Passo 6

Vamos explicar o que cada parte da função faz:
  • Verificação se a lista está vazia: Se o primeiro nó for NULL, significa que a lista não tem elementos.
  • Busca pelo nó com o valor: Percorremos a lista até encontrar o nó com o valor desejado ou chegar ao fim.
  • Caso o nó não seja encontrado: Informamos que o valor não está na lista.
  • Ajuste dos ponteiros:
    • Se o nó a ser removido não for o primeiro, atualizamos o ponteiro proximo do nó anterior.
    • Se for o primeiro, atualizamos o ponteiro primeiro da lista.
    • Se o nó a ser removido não for o último, atualizamos o ponteiro anterior do nó seguinte.
    • Se for o último, atualizamos o ponteiro ultimo da lista.
  • Liberação da memória: Usamos free para liberar a memória ocupada pelo nó removido.
  • Mensagem de sucesso: Informamos que a remoção foi realizada.

Resposta

Pronto! Implementamos a função removerNo para uma lista duplamente ligada de inteiros, considerando todos os casos possíveis e ajustando os ponteiros de forma adequada. Agora, ao chamar essa função passando a lista e o valor que deseja remover, o nó correspondente será removido corretamente da estrutura.

Exercícios relacionados