Desafio 2: Implemente o TAD Listas circulares simples. Deve ter as operações abaixo: (2 V)
f. Crie uma função que recebe uma lista circular simples de números inteiros e um número inteiro que represente o número K aleatório. Começando pelo primeiro elemento da lista deve ser contado até K. Todos os K nós devem ser removidos da lista até
sobrar um único número. Imprima os números a medida que forem sendo removidos.
f. Crie uma função que recebe uma lista circular simples de números inteiros e um número inteiro que represente o número K aleatório. Começando pelo primeiro elemento da lista deve ser contado até K. Todos os K nós devem ser removidos da lista até
sobrar um único número. Imprima os números a medida que forem sendo removidos.
Passo 1
Beleza, vamos entender o que a questão está pedindo. A gente precisa implementar um Tipo Abstrato de Dados (TAD) para Listas Circulares Simples. O foco aqui é criar uma função que recebe uma lista circular de números inteiros e um número K. A função vai contar até K a partir do primeiro elemento e remover cada K-ésimo nó da lista até restar apenas um número. Além disso, conforme removemos os nós, vamos imprimir os números retirados. Para isso, vamos precisar entender como funcionam as listas circulares e como manipular seus nós.
Passo 2
Primeiro, vamos definir como é uma Lista Circular Simples. É uma estrutura de dados onde cada elemento (ou nó) aponta para o próximo, e o último nó aponta de volta para o primeiro, formando um círculo. Isso é útil para problemas onde precisamos percorrer repetidamente a lista, como o nosso desafio.
Passo 3
Vamos começar implementando a estrutura básica da lista circular. Precisamos de uma classe para representar cada nó e outra para a lista em si. Cada nó vai ter um valor e um ponteiro para o próximo nó.
class No:
def __init__(self, valor):
self.valor = valor
self.proximo = None
class ListaCircular:
def __init__(self):
self.ultimo = None
Passo 4
Agora, vamos adicionar uma função para inserir elementos na lista. Como a lista é circular, sempre vamos manter uma referência para o último nó, que aponta para o primeiro.
def inserir(self, valor):
novo_no = No(valor)
if not self.ultimo:
self.ultimo = novo_no
self.ultimo.proximo = self.ultimo
else:
novo_no.proximo = self.ultimo.proximo
self.ultimo.proximo = novo_no
self.ultimo = novo_no
Passo 5
Com a lista pronta, vamos agora criar a função que remove os K-ésimos nós. A ideia é percorrer a lista, contando até K, remover o nó nessa posição e imprimir seu valor, repetindo o processo até sobrar apenas um nó.
def remover_k_esimo(self, K):
if not self.ultimo:
return
atual = self.ultimo.proximo # Começa no primeiro nó
anterior = self.ultimo
while atual != anterior:
# Contar até K
for _ in range(K - 1):
anterior = atual
atual = atual.proximo
# Remover o nó atual
print(atual.valor)
anterior.proximo = atual.proximo
atual = atual.proximo
# Imprimir o último nó
print(atual.valor)
Passo 6
Vamos testar nossa implementação. Vamos criar uma lista com alguns números e chamar a função com um valor de K. Por exemplo, se K = 3 e a lista tiver os números de 1 a 5, a ordem de remoção deve seguir a contagem até 3.
# Criando a lista
lista = ListaCircular()
for numero in range(1, 6):
lista.inserir(numero)
# Removendo os K-ésimos elementos
K = 3
lista.remover_k_esimo(K)
Resposta
Ao executar o código acima com K = 3 e lista de 1 a 5, a saída será:
3
1
5
2
4
Isso significa que os números foram removidos na ordem 3, 1, 5, 2 e, por fim, restou apenas o número 4.