Implemente o TAD Listas circulares simples usando a linguagem C, 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:
  1. Inicializar a lista: Começar com uma lista vazia.
  2. Inserir um nó numa posição específica: Adicionar um novo elemento em um lugar escolhido dentro da lista.
  3. 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:
  1. Criar um novo nó.
  2. Se a lista estiver vazia, o novo nó aponta para si mesmo.
  3. 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:
  1. Verificar se a lista está vazia.
  2. Navegar até o nó anterior ao que queremos remover.
  3. Ajustar os ponteiros para excluir o nó.
  4. 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!

Exercícios relacionados