Implemente o TAD Listas circulares simples usando a linguagem
, com menu iterativo. Deve ter as operações abaixo: Inicializar lista; Inserir nó numa posição específica e Remover nó.
Passo 1
Beleza, vamos lá! O exercício pede para a gente implementar um TAD (Tipo Abstrato de Dados) de listas circulares simples na linguagem C. Isso significa que vamos criar uma estrutura que representa uma lista onde o último elemento aponta de volta para o primeiro, formando um círculo. Precisamos criar um menu interativo que permita ao usuário:
- Inicializar a lista: Começar com uma lista vazia.
- Inserir um nó numa posição específica: Adicionar um novo elemento em um lugar escolhido dentro da lista.
- Remover um nó: Tirar um elemento da lista.
Para resolver isso, vamos precisar entender como funcionam as listas circulares, como criar estruturas em C para representá-las e como implementar as funções para as operações mencionadas. Vamos também precisar saber como fazer um menu interativo no C para que o usuário possa escolher as opções.
Passo 2
Primeiro, vamos entender o que é uma lista circular simples. Em uma lista simplesmente ligada, cada elemento (ou nó) aponta para o próximo. Na lista circular, o último nó aponta de volta para o primeiro, criando um ciclo. Isso é útil quando queremos que a lista não tenha um fim definido e possamos percorrê-la continuamente.
Para representar isso em C, geralmente usamos uma estrutura para o nó que contém os dados e um ponteiro para o próximo nó. Vamos definir isso:
typedef struct No {
int dados;
struct No *proximo;
} No;
Aqui,
No
é a estrutura que representa cada elemento da lista. Ele contém um campo dados
para armazenar o valor e um ponteiro proximo
que aponta para o próximo nó da lista.Passo 3
Agora, precisamos de uma forma de gerenciar a lista circular. Vamos usar um ponteiro que aponta para o último nó da lista. Por que o último? Porque, em uma lista circular, o último nó aponta para o primeiro, então ter um ponteiro para ele facilita inserir ou remover elementos.
Vamos declarar um ponteiro para o último nó:
No *ultimo = NULL;
Inicialmente, a lista está vazia, então
ultimo
é NULL
.Passo 4
Vamos criar uma função para inicializar a lista. Na verdade, já fizemos isso ao declarar
ultimo
como NULL
. Mas podemos criar uma função que reseta a lista, caso já tenha elementos:void inicializarLista() {
ultimo = NULL;
printf("Lista inicializada!\n");
}
Essa função simplesmente define
ultimo
como NULL
e informa ao usuário que a lista foi inicializada.Passo 5
Agora, vamos para a função de inserir um nó em uma posição específica. Precisamos permitir que o usuário escolha em qual posição quer adicionar um novo elemento. Vamos precisar:
- Criar um novo nó.
- Se a lista estiver vazia, o novo nó aponta para si mesmo.
- Se não estiver vazia, navegar até a posição desejada e ajustar os ponteiros.
Vamos implementar isso:
void inserirNo(int valor, int posicao) {
No *novo = (No*)malloc(sizeof(No));
novo->dados = valor;
if (ultimo == NULL) {
// Lista vazia: novo nó aponta para si mesmo
novo->proximo = novo;
ultimo = novo;
} else {
No *temp = ultimo->proximo; // Primeiro nó
// Navega até a posição anterior
for(int i = 1; i < posicao - 1 && temp->proximo != ultimo->proximo; i++) {
temp = temp->proximo;
}
novo->proximo = temp->proximo;
temp->proximo = novo;
if(temp == ultimo) {
ultimo = novo;
}
}
printf("Nó inserido na posição %d!\n", posicao);
}
Aqui, alocamos memória para um novo nó, definimos seu valor e verificamos se a lista está vazia. Se estiver, o nó aponta para si mesmo. Caso contrário, navegamos até a posição desejada e ajustamos os ponteiros para inserir o novo nó. Se inserirmos no final, atualizamos o ponteiro
ultimo
.Passo 6
Agora, vamos implementar a função de remover um nó. Precisamos permitir que o usuário escolha qual nó remover. Para isso, vamos:
- Verificar se a lista está vazia.
- Navegar até o nó anterior ao que queremos remover.
- Ajustar os ponteiros para excluir o nó.
- Liberar a memória do nó removido.
Vamos ao código:
void removerNo(int posicao) {
if(ultimo == NULL) {
printf("Lista vazia! Nada para remover.\n");
return;
}
No *temp = ultimo->proximo; // Primeiro nó
if(posicao == 1) {
if(ultimo == temp) {
// Apenas um nó na lista
ultimo = NULL;
} else {
ultimo->proximo = temp->proximo;
}
free(temp);
printf("Nó na posição 1 removido!\n");
return;
}
// Navega até o nó anterior ao que queremos remover
for(int i = 1; i < posicao - 1 && temp->proximo != ultimo->proximo; i++) {
temp = temp->proximo;
}
No *remover = temp->proximo;
if(remover == ultimo->proximo) {
printf("Posição inválida!\n");
return;
}
temp->proximo = remover->proximo;
if(remover == ultimo) {
ultimo = temp;
}
free(remover);
printf("Nó na posição %d removido!\n", posicao);
}
Esse código verifica se a lista está vazia, depois navega até a posição anterior à que queremos remover. Se for o primeiro nó, atualizamos
ultimo->proximo
. Se for o último, atualizamos o ponteiro ultimo
. Finalmente, liberamos a memória do nó removido.Passo 7
Por fim, vamos criar o menu interativo para o usuário escolher as opções. Vamos usar um loop
while
que continua até o usuário decidir sair. Dentro do loop, apresentamos as opções e chamamos as funções correspondentes:int main() {
int escolha, valor, posicao;
while(1) {
printf("\nMenu:\n");
printf("1. Inicializar lista\n");
printf("2. Inserir nó\n");
printf("3. Remover nó\n");
printf("4. Sair\n");
printf("Escolha uma opção: ");
scanf("%d", &escolha);
switch(escolha) {
case 1:
inicializarLista();
break;
case 2:
printf("Digite o valor a inserir: ");
scanf("%d", &valor);
printf("Digite a posição para inserir: ");
scanf("%d", &posicao);
inserirNo(valor, posicao);
break;
case 3:
printf("Digite a posição para remover: ");
scanf("%d", &posicao);
removerNo(posicao);
break;
case 4:
printf("Saindo...\n");
exit(0);
default:
printf("Opção inválida! Tente novamente.\n");
}
}
return 0;
}
Nesse trecho, apresentamos as opções ao usuário e, conforme a escolha, chamamos a função adequada. O loop continua até que o usuário escolha sair.
Resposta
Pronto! Agora você tem uma implementação básica de um TAD de listas circulares simples em C, com um menu interativo que permite inicializar a lista, inserir nós em posições específicas e remover nós conforme necessário. Testa o programa para ver como funciona e faz os ajustes que precisar!