LISTAS

Lista simplesmente ligada

Desenvolvimento de funções para a estrutura de dados do tipo lista simplesmente ligada com utilização de estruturas de repetição.

Fonte: Shutterstock.

Deseja ouvir este material?

Áudio disponível no material digital.

Sem medo de errar

Você foi incumbido de desenvolver mais duas funções para a estrutura de dados do tipo lista simplesmente ligada, a saber, “posicao_menor” e “existe”. Em cada uma delas, você precisará percorrer a lista ligada. Para isso, nós vimos que podemos usar a estrutura de repetição for. Isso será útil para a função “posicao_menor”, pois temos que percorrer todos os elementos da lista para descobrir qual é a posição do menor elemento, ou seja, nós sabemos a priori quantas iterações serão realizadas.

Já para a função “existe”, nós podemos usar a estrutura de repetição while, uma vez que não sabemos quantas iterações teremos que fazer para encontrar o elemento desejado, se é que ele existe.

Uma possível solução para cada função requisitada é apresentada a seguir:

bool existe(struct Lista* li, int item) {
  assert(li != NULL);
  struct No* aux = li->inicio;
  while(aux != NULL) {
   if (aux->info == item) {
     return true;
   }
   aux = aux->proximo;
  }
  return false;
}

int posicao_menor(struct Lista* li) {
  assert(li != NULL);
  struct No* aux = li->inicio;
  int pos_menor = 0, menor = aux->info;
  for(int i = 0; i < li->tamanho; i++) {
   if (aux->info < menor) {
     pos_menor = i;
     menor = aux->info; 
   }
   aux = aux->proximo;
  }
  return pos_menor;
}

Para demonstrar o funcionamento da função “posicao_menor”, foi pedido a você que imprimisse o nome do inimigo que está mais próximo do jogador em determinado momento (cabe lembrar que você trabalha em uma empresa desenvolvedora de jogos digitais). Considerando que os inimigos, bem como sua distância do jogador, estão armazenados em um vetor, uma possível solução para esse problema é o seguinte:

int main() {
  struct Inimigo i1, i2, i3;
  i1.nome = "Vampiro";
  i1.distanciaDoJogador = 10;
  
  i2.nome = "Morcego Assassino";
  i2.distanciaDoJogador = 2;

  i3.nome = "Zoombie";
  i3.distanciaDoJogador = 3;
  
  struct Inimigo inimigos[3] = {i1, i2, i3};

  struct Lista* lista_distancias = criar(); 
  inserir(lista_distancias, 0, i1.distanciaDoJogador); 
  inserir(lista_distancias, 0, i2.distanciaDoJogador);  
  inserir(lista_distancias, 0, i3.distanciaDoJogador);  

  int posicaoMenor = posicao_menor(lista_distancias);
  
  printf("Inimigo mais próximo: %s\n", inimigos[posicaoMenor].nome);  

  return 0;
} 

Avançando na prática

Ordenar lista

Na situação-problema anterior, nós implementamos a função “posicao_menor”, que retorna a posição do menor elemento da lista. Utilize essa função, juntamente com as já existentes na lista simplesmente ligada, para implementar a função “ordernar(li)”, que ordena a lista “li” em ordem crescente. Por exemplo, dada a lista [3, 2, 1, 4, 5], após a execução da função “ordenar”, a lista ficará assim: [1, 2, 3, 4, 5].

void ordenar(struct Lista* li) {
  assert(li != NULL);
  struct Lista* lista_aux = criar();
  int i = 0, pos_menor, elemento;
  while(vazia(li) == false) {
   pos_menor = posicao_menor(li);
   elemento = remover(li, pos_menor);
   inserir(lista_aux, i, elemento);
   i++;
  }
  i = 0;
  while(vazia(lista_aux) == false) {
   elemento = remover(lista_aux, 0);
   inserir(li, i, elemento);
   i++; 
  }
  liberar(lista_aux);
}