Considere uma lista simplesmente 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á! O enunciado pede pra gente trabalhar com uma lista simplesmente encadeada circular, que é um tipo de estrutura de dados usada em programação para armazenar elementos de forma sequencial. A gente precisa implementar um programa que tenha várias funções como inserir elementos no começo ou no final, remover elementos específicos e imprimir a lista. Para resolver isso, vamos precisar entender como funciona uma lista encadeada circular e como manipular seus nós (elementos) em diferentes situações.
Passo 2
Primeiro, vamos entender o que é uma lista simplesmente encadeada circular. Imagina que você tem vários nós, cada um com um valor e um ponteiro que aponta pro próximo nó. Na lista circular, o último nó aponta de volta pro primeiro, formando um círculo. Isso ajuda a navegar pela lista de forma contínua sem chegar num fim. Cada nó tem a seguinte estrutura:
typedef struct Nodo {
int dado;
struct Nodo *prox;
} Nodo;
Aqui,
dado
armazena o valor e prox
aponta pro próximo nó.Passo 3
Vamos começar implementando a função a) Inserção no início da lista. A ideia é criar um novo nó e colocá-lo antes do primeiro nó atual. Se a lista estiver vazia, o novo nó aponta pra ele mesmo. Caso contrário, a gente percorre a lista até chegar no último nó para atualizar o ponteiro dele.
void inserirInicio(Nodo **ultimo, int valor) {
Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
novo->dado = valor;
if (*ultimo == NULL) {
*ultimo = novo;
novo->prox = novo;
} else {
novo->prox = (*ultimo)->prox;
(*ultimo)->prox = novo;
}
}
Passo 4
Agora, vamos para a função b) Remoção do primeiro elemento da lista. Aqui, a gente precisa remover o nó que está logo após o nó
ultimo
, que é o primeiro da lista. Se tiver só um nó, a lista fica vazia. Senão, apontamos o prox
do ultimo
pro próximo do nó removido e liberamos a memória.void removerInicio(Nodo **ultimo) {
if (*ultimo == NULL) {
printf("Lista vazia!\n");
return;
}
Nodo *temp = (*ultimo)->prox;
if (*ultimo == temp) {
*ultimo = NULL;
} else {
(*ultimo)->prox = temp->prox;
}
free(temp);
}
Passo 5
Vamos implementar a função c) Inserção na última posição da lista. Isso é parecido com a inserção no início, mas a gente insere e atualiza o ponteiro
ultimo
para o novo nó. Se a lista estiver vazia, é o mesmo que inserir no início.void inserirFinal(Nodo **ultimo, int valor) {
Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
novo->dado = valor;
if (*ultimo == NULL) {
*ultimo = novo;
novo->prox = novo;
} else {
novo->prox = (*ultimo)->prox;
(*ultimo)->prox = novo;
*ultimo = novo;
}
}
Passo 6
Agora, vamos para a função d) Remoção do último elemento da lista. Precisamos encontrar o nó que aponta pro
ultimo
, atualizar seu prox
para o primeiro, e então liberar o antigo ultimo
. Se tiver só um nó, a lista fica vazia.void removerFinal(Nodo **ultimo) {
if (*ultimo == NULL) {
printf("Lista vazia!\n");
return;
}
Nodo *temp = (*ultimo)->prox;
if (*ultimo == temp) {
free(*ultimo);
*ultimo = NULL;
} else {
while (temp->prox != *ultimo)
temp = temp->prox;
temp->prox = (*ultimo)->prox;
free(*ultimo);
*ultimo = temp;
}
}
Passo 7
Vamos implementar a função e) Remoção de uma chave informada. Aqui, a gente procura pelo nó que contém o valor especificado e o remove da lista. Se a lista estiver vazia ou a chave não for encontrada, mostramos uma mensagem. Precisamos cuidar de atualizar os ponteiros corretamente para não quebrar a lista.
void removerChave(Nodo **ultimo, int chave) {
if (*ultimo == NULL) {
printf("Lista vazia!\n");
return;
}
Nodo *temp = (*ultimo)->prox, *prev = *ultimo;
do {
if (temp->dado == chave) {
if (temp == *ultimo) {
if (temp->prox == *ultimo) {
*ultimo = NULL;
} else {
prev->prox = temp->prox;
*ultimo = prev;
}
} else {
prev->prox = temp->prox;
}
free(temp);
return;
}
prev = temp;
temp = temp->prox;
} while (temp != (*ultimo)->prox);
printf("Chave %d não encontrada na lista.\n", chave);
}
Passo 8
Por fim, vamos criar a função f) Impressão da lista. A gente percorre a lista começando do primeiro elemento e vai imprimindo cada valor até voltar ao inicio, garantindo que a gente não entra em um loop infinito.
void imprimirLista(Nodo *ultimo) {
if (ultimo == NULL) {
printf("Lista vazia!\n");
return;
}
Nodo *temp = ultimo->prox;
do {
printf("%d -> ", temp->dado);
temp = temp->prox;
} while (temp != ultimo->prox);
printf("(retorna ao início)\n");
}
Resposta
Pronto! Agora você tem todas as funções implementadas para manipular uma lista simplesmente encadeada circular. Você pode testar adicionando, removendo e imprimindo elementos para ver como a lista se comporta.