Considere uma lista duplamente encadeada circular e implemente um programa que contém as seguintes funções:
a) Inserção no início da lista.
b) Remoção (free) do primeiro elemento da lista.
c) Inserção na última posição da lista.
d) Remoção (free) do último elemento da lista.
e) Remoção (free) de uma chave informada.
f) Impressão da lista.
a) Inserção no início da lista.
b) Remoção (free) do primeiro elemento da lista.
c) Inserção na última posição da lista.
d) Remoção (free) do último elemento da lista.
e) Remoção (free) de uma chave informada.
f) Impressão da lista.
Passo 1
Beleza, vamos lá! Você tem um exercício que pede para implementar várias funções em uma lista duplamente encadeada circular. Isso faz parte da matéria de Estruturas de Dados. Vamos precisar entender como funciona uma lista duplamente encadeada circular e como manipular seus elementos. As funções que vamos implementar são:
a) Inserção no início da lista.
b) Remoção do primeiro elemento da lista.
c) Inserção na última posição da lista.
d) Remoção do último elemento da lista.
e) Remoção de um elemento específico pela chave.
f) Impressão da lista.
Passo 2
Primeiro, vamos entender o que é uma lista duplamente encadeada circular. Basicamente, é uma estrutura onde cada elemento (ou nó) aponta para o próximo e para o anterior, formando um círculo. Isso significa que o último nó aponta de volta para o primeiro, e o primeiro aponta para o último. Ter essa estrutura permite inserções e remoções eficientes em ambas as extremidades.
Passo 3
Vamos começar definindo a estrutura do nó da lista. Em C, podemos fazer isso usando
struct
. Cada nó terá um valor, um ponteiro para o próximo nó e outro para o nó anterior.#include <stdio.h>
#include <stdlib.h>
// Definição do nó
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
Passo 4
Agora, precisamos de uma função para criar um novo nó. Essa função vai alocar memória para o nó, atribuir o valor e inicializar os ponteiros
next
e prev
apontando para ele mesmo, já que é circular.// Função para criar um novo nó
Node* criarNo(int valor) {
Node* novoNo = (Node*)malloc(sizeof(Node));
novoNo->data = valor;
novoNo->next = novoNo;
novoNo->prev = novoNo;
return novoNo;
}
Passo 5
Vamos implementar a função inserção no início da lista. Essa função adiciona um novo nó antes do nó cabeça da lista.
// Inserção no início
void inserirInicio(Node** head, int valor) {
Node* novoNo = criarNo(valor);
if (*head == NULL) {
*head = novoNo;
} else {
Node* ultimo = (*head)->prev;
novoNo->next = *head;
novoNo->prev = ultimo;
ultimo->next = novoNo;
(*head)->prev = novoNo;
*head = novoNo; // Atualiza o head para o novo nó
}
}
Explicação: Se a lista estiver vazia, o novo nó se torna o head e aponta para ele mesmo. Caso contrário, ajustamos os ponteiros para inserir o novo nó antes do head atual e atualizamos o head para o novo nó.
Passo 6
Agora, a função de remoção do primeiro elemento. Essa função remove o nó que está no início da lista.
// Remoção do primeiro elemento
void removerInicio(Node** head) {
if (*head == NULL) {
printf("A lista está vazia.\n");
return;
}
if ((*head)->next == *head) { // Apenas um nó na lista
free(*head);
*head = NULL;
} else {
Node* ultimo = (*head)->prev;
Node* temp = *head;
*head = (*head)->next;
ultimo->next = *head;
(*head)->prev = ultimo;
free(temp);
}
}
Explicação: Se a lista está vazia, informamos isso. Se há apenas um nó, liberamos a memória e definimos o head como
NULL
. Caso contrário, ajustamos os ponteiros do último nó e do novo head, e liberamos o nó antigo.Passo 7
Vamos para a função de inserção na última posição. Essa função adiciona um novo nó ao final da lista.
// Inserção no final
void inserirFinal(Node** head, int valor) {
Node* novoNo = criarNo(valor);
if (*head == NULL) {
*head = novoNo;
} else {
Node* ultimo = (*head)->prev;
ultimo->next = novoNo;
novoNo->prev = ultimo;
novoNo->next = *head;
(*head)->prev = novoNo;
}
}
Explicação: Se a lista estiver vazia, o novo nó se torna o head. Caso contrário, ajustamos os ponteiros do último nó e do novo nó para inseri-lo no final, mantendo a natureza circular.
Passo 8
Agora, a função de remoção do último elemento. Essa função remove o nó que está no final da lista.
// Remoção do último elemento
void removerFinal(Node** head) {
if (*head == NULL) {
printf("A lista está vazia.\n");
return;
}
if ((*head)->next == *head) { // Apenas um nó na lista
free(*head);
*head = NULL;
} else {
Node* ultimo = (*head)->prev;
Node* penultimo = ultimo->prev;
penultimo->next = *head;
(*head)->prev = penultimo;
free(ultimo);
}
}
Explicação: Similar à remoção do início, se há apenas um nó, liberamos a memória e definimos o head como
NULL
. Caso contrário, encontramos o penúltimo nó, ajustamos os ponteiros para excluir o último nó e liberamos sua memória.Passo 9
Vamos implementar a função de remoção de uma chave específica. Essa função busca um nó com o valor informado e o remove da lista.
// Remoção de uma chave específica
void removerChave(Node** head, int chave) {
if (*head == NULL) {
printf("A lista está vazia.\n");
return;
}
Node* atual = *head;
Node* temp = NULL;
// Percorre a lista procurando a chave
do {
if (atual->data == chave) {
temp = atual;
break;
}
atual = atual->next;
} while (atual != *head);
if (temp == NULL) {
printf("Elemento %d não encontrado na lista.\n", chave);
return;
}
if (temp->next == temp) { // Apenas um nó na lista
free(temp);
*head = NULL;
} else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
if (temp == *head) { // Se for o head, atualiza
*head = temp->next;
}
free(temp);
}
}
Explicação: Percorremos a lista procurando pelo valor (
chave
). Se encontrado, ajustamos os ponteiros dos nós vizinhos para excluir o nó encontrado. Se o nó a ser removido for o head, atualizamos o head para o próximo nó. Se a chave não for encontrada, informamos o usuário.Passo 10
Por fim, a função de impressão da lista. Essa função percorre a lista e imprime os valores de cada nó.
// Impressão da lista
void imprimirLista(Node* head) {
if (head == NULL) {
printf("A lista está vazia.\n");
return;
}
Node* atual = head;
printf("Lista: ");
do {
printf("%d ", atual->data);
atual = atual->next;
} while (atual != head);
printf("\n");
}
Explicação: Se a lista estiver vazia, informamos isso. Caso contrário, percorremos a lista a partir do head, imprimindo cada valor até retornarmos ao head, garantindo que percorremos todo o círculo.
Resposta
Prontinho! Agora você tem todas as funções implementadas para manipular uma lista duplamente encadeada circular. Não esqueça de criar um menu ou funções de teste para verificar se tudo está funcionando conforme esperado. Boa programação!