Universidade Federal da Bahia
Departamento de Ciência da Computação
MATA40 - Algoritmos e Estruturas de Dados I
Prof.: Flávio M. Assis Silva
7 de outubro de 2008
Manipulação de Listas
1
Descrição Geral do Trabalho
Neste trabalho o aluno deve fazer um programa que mantém informações sobre vendas de uma montadora de carros. O programa deve manter o número
de vendas para combinações de modelos de carros, cor e cidade onde o carro
foi vendido. Para isto, o programa deve obedecer aos itens abaixo:
• os modelos de carros devem ser mantidos em uma lista encadeada simples (cada item da lista mantém o nome de um modelo - p.e., gol, golf,
santana, etc.);
• as cores de carros devem ser mantidas em uma lista encadeada simples
(cada item da lista contém o nome de uma cor - p.e., azul, cinza chumbo,
cinza quasar, etc.);
• as cidades devem ser mantidas em uma lista encadeada simples (cada
item da lista contém o nome de uma cidade);
• cada quantidade de vendas de um determinado carro, de uma determinada cor, em uma determinada cidade deve ser armazenada como um
valor inteiro alocado dinamicamente;
• para atender às consultas (descritas a seguir), os itens informando quantidades de vendas devem formar listas encadeadas para cada uma das
dimensões (modelo de carro, cor e cidade), como indicado em sala de
aula.
1
2
Formato de Entrada
O programa deve ler da entrada padrão. A entrada consistirá de uma
seqüência de informações sobre vendas de carros, seguida por uma seqüência
de operações.
A seqüência de informações sobre vendas terá o seguinte formato. A
primeira linha terá um número inteiro, indicando uma quantidade de nomes
de modelos de carros. Representemos este número por m. Haverá em seguida
m linhas, cada uma com o nome de um modelo de carro (todos distintos entre
si).
Em seguida, haverá uma linha com outro número inteiro. Este número
indicará uma quantidade de cores. Representemos este número por c. Haverá
em seguida c linhas, cada uma com o nome de uma cor (todos distintos entre
si).
Em seguida, haverá uma linha com outro número inteiro. Este número
indicará uma quantidade de nomes de cidades. Representemos este número
por t. Haverá em seguida t linhas, cada uma com o nome de uma cidade
(todos distintos entre si).
Em seguida, haverá uma linha com mais um número inteiro. Representemos este número por v. Haverá em seguida v linhas, cada uma com o seguinte
formato: um nome de modelo de carro, seguido por um espaço, seguido pelo
nome de uma cor, seguido por um espaço, seguido pelo nome de uma cidade,
seguido por um espaço, seguido por um número inteiro. Esta linha indica o
número de vendas (último número na linha) de carros do modelo, da cor e
na cidade indicados.
Não haverá, nesta seção, mais de uma linha com os mesmos valores para
os três itens (modelo, cor e cidade), tomados em conjunto.
Assuma que um nome, seja de modelo de carro, cor ou cidade, é uma
seqüência de letras, de, no máximo, tamanho 20. Assuma que todos os
valores inteiros desta seção são maiores que zero.
Em seguida, haverá uma seqüência de operações. Cada operação pode ser
de um dos tipos definidos abaixo. A seqüência termina com uma operação
do tipo término de seqüência de operações. Os formatos das operações são:
1. consulta quantidade de carros vendidos: esta operação consistirá
de uma linha, contendo a letra ’m’, seguida de um espaço, seguido do
nome de um modelo de carro. Esta operação retorna o número de carros
do modelo indicado vendidos, independentemente de cor e cidade.
2. consulta quantidade de carros de uma determinada cor vendidos: esta operação consistirá de uma linha, contendo a letra ’c’,
2
seguida de um espaço, seguido do nome de uma cor. Esta operação retorna o número de carros vendidos da cor indicada, independentemente
de modelo e cidade.
3. consulta quantidade de carros vendidos em uma determinada
cidade: esta operação consistirá de uma linha, contendo a letra ’t’,
seguida de um espaço, seguido do nome de uma cidade. Esta operação
retorna o número de carros vendidos na cidade indicada, independentemente de modelo e cor.
4. consulta quantidade de carro por modelo e cidade: esta operação
consistirá de uma linha, contendo a letra ’s’, seguida de um espaço, seguido do nome de um modelo de carro, seguido de um espaço, seguido
do nome de uma cidade. Esta operação retorna o número de carros do
modelo indicado vendidos na cidade indicada (independentemente da
cor).
5. consulta quantidade de carro por modelo e cor: esta operação
consistirá de uma linha, contendo a letra ’u’, seguida de um espaço,
seguido do nome de um modelo de carro, seguido de um espaço, seguido do nome de uma cor. Esta operação retorna o número de carros
vendidos do modelo e cor indicados (independentemente da cidade).
6. consulta quantidade de carro por modelo, cor e cidade: esta
operação consistirá de uma linha contendo a letra ’v’, seguida de um
espaço, seguido do nome de um modelo de carro, seguido de um espaço,
seguido do nome de uma cor, seguido de um espaço, seguido pelo nome
de uma cidade. Esta operação retorna o número de carros vendidos do
modelo e cor e na cidade indicados.
7. remove informação sobre venda: esta operação consistirá de uma
linha contendo a letra ’r’, seguida de um espaço, seguido do nome de
um modelo de carro, seguido de um espaço, seguido do nome de uma
cor, seguido de um espaço, seguido pelo nome de uma cidade. Esta
operação remove a célula que indica o número de carros vendidos do
modelo, cor e cidade indicados. As listas de nomes de modelos de
carros, cores e cidades não são alteradas.
8. lista nomes de modelos de carros: esta operação consistirá de
uma linha contendo a letra ’l’, seguida de um espaço, seguido da letra
’m’. Esta operação lista os nomes dos modelos de carros mantidos pelo
programa (lidos na primeira parte da entrada).
3
9. lista nomes de cores: esta operação consistirá de uma linha contendo
a letra ’l’, seguida de um espaço, seguido da letra ’c’. Esta operação
lista os nomes de cores mantidos pelo programa (lidos na primeira parte
da entrada).
10. lista nomes de cidades: esta operação consistirá de uma linha contendo a letra ’l’, seguida de um espaço, seguido da letra ’t’. Esta
operação lista os nomes de cidades mantidos pelo programa (lidos na
primeira parte da entrada).
11. término de seqüência de operações: esta operação consistirá de
uma linha contendo a letra ’e’.
Somente ocorrerão letras minúsculas na entrada. Não serão usados acentos.
3
Formato de Saı́da
O programa deve gerar sua saı́da na saı́da padrão.
As operações de consulta retornarão um valor inteiro. As saı́das destas
operações devem ser uma em cada linha.
As operações de remoção e de término de seqüência de operações não
geram saı́da.
As operações de listagem devem apresentar cada item da lista em uma
linha separada.
Todas as letras na saı́da devem ser minúsculas.
Importante: O programa não deve gerar nenhum caractere na saı́da que
não siga o formato descrito nesta seção.
4
Observações
• trabalho individual
• data de entrega: 3 de novembro
• a entrega do trabalho será feita através da web, como indicado em sala
de aula
• o aluno deve usar apenas os seguintes compiladores (os trabalhos somente serão compilados neles):
4
– Pascal: FreePascal
– C: gcc ou djgpp
– C++: g++ ou djgpp
– Java: JDK mais recente
Erros de compilação gerados pelos compiladores acima serão
considerados erros do trabalho. Em outras palavras, somente
serão aceitos trabalhos compilados nos compiladores acima.
5