Desafio 1: Implemente o TAD Listas duplamente ligadas de inteiros. Deve ter as operações abaixo: (2 V):
c. Remover nó
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:
- A lista está vazia: Não há o que remover.
- O nó a ser removido é o primeiro: Precisamos atualizar o ponteiro do primeiro nó.
- O nó a ser removido é o último: Atualizamos o ponteiro do último nó.
- 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.
- Se o nó a ser removido não for o primeiro, atualizamos o ponteiro
- 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.