MAC122 - Lista 1 - Listas ligadas e filas

1. Escreva uma função

      int conta (apont p, int x) 
   

   que devolve o número de vezes que o elemento x aparece na lista apontada por p. (Escreva uma versão iterativa e, se quiser, uma versão recursiva da função, para treinar recursão!)
2. Escreva uma função

      apont remove (apont p, int x) 
   

   que remove a primeira aparição de x na lista apontada por p e devolve o início da lista resultante.

   Reescreva a função de forma que ela remova todas as aparições de x na lista (e devolva a lista resultante).

3. Considere as convenções do exercício 2 da P1 e escreva uma função

      apont interseccao (apont p, apont q)
   

   que devolve o início de uma lista com a interseção dos conjuntos representados por p e q.
4. Escreva uma função

      apont ordena (apont p) 
   

   que recebe o apontador de uma lista ligada de inteiros e rearraja essa lista de forma que ela esteja ordenada, devolvendo o início da lista resultante. Não troque o conteúdo das células. Apenas atualize os apontadores para ordenar a lista (imagine que as informações guardadas em cada célula da lista são muitas e que seria muuuuito caro trocar o conteúdo de duas células).
5. Escreva uma função

      apont tira_repetição (apont p) 
   

   que remove todos os elementos repetidos da lista apontada por p, deixando apenas uma cópia de cada um; devolva o início da lista resultante.
6. Qual é a saída da seguinte seqüência de operações sobre uma fila:

      cria(10);
      insere(1);
      insere(2);
      printf("%d", retira());
      insere(3); 
      printf("%d", retira());
      printf("%d", retira());
      insere(4);
      insere(5);
      printf("%d", retira());
      printf("%d", retira());
   

   E das seguintes operações sobre uma fila dupla:

      cria(10);
      insere_esquerda(1);
      insere_direita(2);
      printf("%d", retira());
      insere_direita(3); 
      printf("%d", retira());
      printf("%d", retira());
      insere_direita(4);
      insere_esquerda(5);
      printf("%d", retira());
      printf("%d", retira());
   

7. Escreva o programa que resolve o problema do ratinho sem usar a interface de fila, mas usando um vetor (dois, na verdade) diretamente como uma fila, como é feito nas notas do Prof. Paulo sobre filas como o exercício 3 da P1.
8. Simule o algoritmo do problema do ratinho para a seguinte entrada:

      8 9 (tamanho do labirinto)
      -2 -2 -2 -2 -1 -2 -1 -1 -2 (-2 indica posição livre, -1 parede)
      -2 -2 -1 -2 -2 -2 -1 -2 -2
      -2 -2 -2 -1 -1 -2 -1 -2 -1
      -2 -1 -2 -2 -1 -2 -2 -2 -1
      -2 -1 -1 -2 -1 -2 -1 -2 -2
      -2 -2 -2 -2 -2 -2 -1 -1 -2
      -2 -2 -1 -2 -1 -2 -2 -1 -2
      -2 -1 -1 -2 -1 -1 -2 -2 -2
      1 1 (posição do rato)
      8 9 (posição do queijo)
   

   Mostre como fica a matriz no fim do programa e qual é a saída do programa para estes dados.
9. Modifique o algoritmo do problema do ratinho para que ele resolva a seguinte variante do problema: determinar se não existe caminho do queijo ao rato, se existe exatamente um caminho ou se existem dois ou mais caminhos do queijo ao rato.
10. Você consegue pensar em uma forma de alterar o algoritmo do problema do ratinho de forma a determinar quantos caminhos de comprimento mínimo existem do queijo ao rato?
11. Escreva um programa que recebe um labirinto, como no problema do ratinho, e a posição do rato, e imprime todas as posições do labirinto as quais o rato pode chegar.
12. Leia as notas de aula de filas. Entenda o problema e o algoritmo lá explicado. Modifique-o para que a saída seja a lista de cidades a que posso chegar a partir da cidade s.