Desafio 2: Implemente o TAD Listas circulares simples. Deve ter as operações abaixo: (2 V)
b. Inserir nó numa posição específica
b. Inserir nó numa posição específica
Passo 1
Beleza, vamos lá! O enunciado pede para a gente implementar o TAD (Tipo Abstrato de Dados) de Listas Circulares Simples, especificamente a operação de inserir um nó numa posição específica. Então, vamos trabalhar com estruturas de listas onde o último elemento aponta de volta para o primeiro, formando um ciclo. Para isso, vamos precisar entender como navegar na lista e ajustar os ponteiros para inserir o novo nó na posição que a gente quer.
Passo 2
Primeiro, vamos lembrar como é uma lista circular simples. Cada elemento (ou nó) tem dois componentes principais: o valor que ele guarda e um ponteiro para o próximo nó. O último nó sempre aponta para o primeiro, garantindo que a lista seja circular. Para inserir um novo nó numa posição específica, precisamos:
- Criar o novo nó com o valor que queremos.
- Navegar até a posição anterior onde queremos inserir o novo nó.
- Ajustar os ponteiros para que o novo nó seja ligado corretamente na lista.
Passo 3
Vamos detalhar cada um desses passos. Primeiro, criar o novo nó é bem direto: alocamos memória para ele, definimos o valor e inicialmente apontamos seu próximo para
NULL
. Depois, se a lista estiver vazia, ou seja, não tiver nenhum nó, o novo nó vai apontar para ele mesmo, já que é circular. Caso contrário, temos que encontrar a posição anterior onde vamos inserir o novo nó.Passo 4
Para navegar até a posição anterior, começamos no primeiro nó e avançamos pelos ponteiros até chegarmos na posição imediatamente antes da onde queremos inserir. É importante verificar se a posição desejada é válida, ou seja, não ultrapassa o tamanho da lista.
Passo 5
Depois de chegar na posição anterior, vamos ajustar os ponteiros. O próximo do nó anterior vai apontar para o novo nó, e o próximo do novo nó vai apontar para o nó que estava originalmente nessa posição. Dessa forma, mantemos a estrutura circular sem perder nenhum nó.
Passo 6
Vamos colocar isso tudo em código para ficar mais claro. Aqui está um exemplo em C:
#include <stdio.h>
#include <stdlib.h>
// Definição do nó
typedef struct Nodo {
int valor;
struct Nodo* proximo;
} Nodo;
// Função para inserir na posição específica
void inserir(Nodo** head, int valor, int pos) {
Nodo* novo = (Nodo*)malloc(sizeof(Nodo));
novo->valor = valor;
if (*head == NULL) {
// Lista vazia: novo nó aponta para si mesmo
novo->proximo = novo;
*head = novo;
} else if (pos == 1) {
// Inserir no início
Nodo* temp = *head;
while (temp->proximo != *head) {
temp = temp->proximo;
}
novo->proximo = *head;
temp->proximo = novo;
*head = novo;
} else {
// Inserir em posição específica
Nodo* temp = *head;
for (int i = 1; i < pos-1 && temp->proximo != *head; i++) {
temp = temp->proximo;
}
novo->proximo = temp->proximo;
temp->proximo = novo;
}
}
// Função para imprimir a lista
void imprimir(Nodo* head) {
if (head == NULL) return;
Nodo* temp = head;
do {
printf("%d ", temp->valor);
temp = temp->proximo;
} while (temp != head);
printf("\n");
}
int main() {
Nodo* head = NULL;
inserir(&head, 10, 1); // Inserir 10 na posição 1
inserir(&head, 20, 2); // Inserir 20 na posição 2
inserir(&head, 15, 2); // Inserir 15 na posição 2
imprimir(head); // Deve imprimir: 10 15 20
return 0;
}
Resposta
Seguindo os passos acima, conseguimos implementar a operação de inserir um nó numa posição específica em uma lista circular simples. No exemplo de código em C, a função
inserir
trata casos onde a lista está vazia, inserção no início e inserção em posições intermediárias, mantendo sempre a estrutura circular da lista. Quando executamos o programa, a lista resultante após as inserções será: 10 15 20
.