Algoritmos e Estruturas de Dados [LEEC] (2024/2025)

Lista de exercícios

Prática 08 (05/mai/2025)

Exercícios com dicionários.

Exercício 14 [J]: Capitais do mundo

Escreva um programa que informe sobre quais as capitais de diversos países. Use a nossa metodologia, o que significa que se deverá criar um TAD Mundo para representar base de dados que guardam correspondências entre países e capitais.

No início, o programa conhece apenas um pequeno número de países. Mas vai aprendendo: Nos casos em que não conhece a resposta, pede ao utilizador a resposta certa!

Das representações indicadas a seguir, qual é a que simplifica mais a implementação do TAD Mundo e porquê?

vetor
lista
sequência
dicionário
fila
pilha

Deverá montar no seu IDE um projeto com estes elementos:

MainMundo.c - falta só fazer o comando de listagem.
Mundo.h - já feito.
Mundo.c - para completar.
biblioteca.zip - pasta da biblioteca.

O programa suporta quatro comandos: C, L, ?, T. Observe este exemplo de execução:

> ?
Menu:
  C - capital
  L - lista ordenada
  ? - menu
  T - terminar
> l
Portugal -> Lisboa
Espanha -> Madrid
Franca -> Paris
> c Portugal
Portugal -> Lisboa
> c Espanha
Espanha -> Madrid
> c Italia
Nao conheço a capital de Italia. Por favor, ensine-me: Roma
Obrigado!
> l
Portugal -> Lisboa
Espanha -> Madrid
Franca -> Paris
Italia -> Roma
> c Italia
Italia -> Roma
> t
Volte sempre!

Exercício 15 [E]: Parque de Estacionamento usando TAD Dicionario

Resolva novamente o problema do Parque de Estacionamento, mas agora usando internamente um dicionário, em vez dum vetor normal ou duma sequência. [Use como ponto de partida, uma cópia da sua solução baseada em vetor ou sequência. Também pode espreitar o TAD Turma reimplementado usando um dicionário na aula teórica 07.]

A solução mais natural e mais prática usa um dicionário, visto os tickets serem identificados por uma chave (a matrícula).

Usar um dicionário ajuda imenso a implementar o Parque de forma mais simples. Contudo, não trata o seguinte aspeto: a listagem dos tickets precisa de ser feita por ordem de chegada - não compete aos dicionários tratar disso...

Resolva este problema da ordenação da seguinte forma:

Na implementação do TAD Ticket, associe um número de ordem a cada ticket. Os tickets passam a ter um campo inteiro novo chamado ordem. O valor desse campo é atribuído automaticamente, sempre que se cria um ticket novo (a função criaTicket não precisa de nenhum argumento novo). A sucessão de valores 0, 1, 2, 3, etc. é atribuída a sucessivos tickets.
Defina a operação de comparação de tickets (comparaTicket) com base no campo ordem.
No TAD Parque, acrescente uma nova função pública iteradorOrdemDeChegadaParque que produz um iterador que percorre os tickets por ordem de chegada. A implementação consiste numa chamada à função iteradorOrdenadoDicionario.
Não é estritamente necessário, mas pode aproveitar para acrescentar um nova função pública iteradorOrdemMatriculaParque que produz um iterador que percorre as matrículas por ordem alfabética. A implementação consiste numa chamada à função iteradorOrdenadoChavesDicionario.
Finalmente, altere a função cmdListaCarros do programa principal, para ela passar a usar o iterador dos tickets.