PUCRS
Faculdade de Informática
Programação para Engenharia II
Trabalho
II - 2008/I
Caminhos entre
Cidades
Data de Entrega:
01/07/2008
O objetivo deste
trabalho é criar um programa que informe os caminhos
possíveis entre duas cidades escolhidas pelo
usuário.
Ao iniciar, o programa deve
ler um arquivo que define cada caminho possível entre duas
cidades quaisquer. Por exemplo:
SaoBorja SaoLuizGonzaga
SaoBorja Santiago
SaoLuizGonzaga CerroLargo
CerroLargo SantaRosa
SaoLuizGonzaga SantaRosa
SantaRosa Girua
CerroLargo Girua
CerroLargo SantoAngelo
Girua SantoAngelo
SantaRosa TresDeMaio
TresDeMaio Horizontina
TresDeMaio TresPassos
TresDeMaio SantoAugusto
TresPassos SantoAugusto
SantoAgusto Ijui
SaoLuizGonzaga Ijui
Ijui Panambi
Panambi PalmeiraDasMissoes
TresDeMaio PalmeiraDasMissoes
PalmeiraDasMissoes FredericoWestphalen
FredericoWestphalen Sarandi
Sarandi Carazinho
Panambi Carazinho
Carazinho PassoFundo
Sarandi PassoFundo
Panambi CruzAlta
Ijui CruzAlta
CruzAlta JulioDeCastilhos
Carazinho Soledade
PassoFundo Soledade
Soledade SantaCruzDoSul
JulioDeCastilhos SantaMaria
SantaMaria SantaCruzDoSul
SantaMaria SaoPedroDoSul
SaoPedroDoSul SaoFranciscoDeAssis
SaoFranciscoDeAssis Santiago
Estas
informações foram extraídas a partir
do mapa do Estado (veja
abaixo). Posteriormente será fornecido um arquivo mais
extenso.
Após a leitura, o programa deve exibir ao usuário
uma lista em
ordem alfabética de todas as cidades existentes
no arquivo, sem repetição.
A seguir, o programa deve perguntar ao usuário a cidade de
origem e a
de destino e mostrar pelo menos um dos caminhos existentes entre elas.
O caminho solicitado pode não ser 'direto', ou seja, o
programa
deve mostrar as cidades por onde se deve passar para ir da cidade
origem até a destino.
Deve ser implementada uma
classe para representar a estrutura de
dados, e que permita a realização de consultas
sobre ela. Uma forma
simples
de implementar isso é através de uma matriz
bidimensional, onde as
linhas representam as cidades de origem e as colunas representam as
cidades de destino.
Onde houver um caminho entre uma cidade e outra, deve-se colocar uma
marca (ex: um número diferente de zero, ou um boolean) na
célula
correspondente
da matriz. Dessa forma, para saber se existe um caminho entre uma
cidade A e uma cidade B, basta localizar a
intersecção delas na matriz
e verificar se
a marca está presente.
Por exemplo, imaginando uma
matriz com 4 cidades:
|
Carazinho |
CruzAlta |
Ijui |
Panambi |
Carazinho |
|
|
X |
|
CruzAlta |
|
|
|
X |
Ijui |
|
X |
|
|
Panambi |
|
|
X |
|
A classe que representa a
estrutura de dados deve ter métodos para:
- Incluir um par de cidades: recebe os nomes da cidade de
origem e da cidade de destino, atualiza a matriz.
- Consultar se existe uma ligação entre
duas
cidades: recebe os nomes da cidade de origem e da cidade de
destino e retorna um valor informado se existe ou
não.
Programa deve ter ainda duas outras classes:
- uma que permita pesquisar um caminho, dados os
nomes de
uma cidade de origem e de uma cidade de destino. Este caminho deve ser
impresso na tela.
- uma que mantenha uma lista com os nomes das cidades e
permita imprimi estes nomes em ordem alfabética.
Veja dicas de implementação nesta página.
O trabalho
deverá consistir de um
único arquivo .cpp.
Esse arquivo deverá ser enviado para o email do
professor até o dia 01/07/2008.
Não serão aceitas entregas fora do prazo.
Cópia
de trabalhos caracteriza fraude escolar e nesse caso, todos os
envolvidos terão a sua nota anulada.
O trabalho, que deverá
ser desenvolvido individualmente, deverá ser
apresentado no dia 01/07/2008 durante o horário da
aula.