UNIVERSIDADE
FEDERAL DE MINAS GERAIS
INSTITUTO
DE CIÊNCIAS EXATAS
DEPARTAMENTO
DE CIÊNCIA DA COMPUTAÇÃO
ALGORITMOS
E ESTRUTURAS DE DADOS II
Prof.
Raquel O. Prates 24
de abril de 2006
Data de entrega: 09 de maio de 2006
Penalidade por atraso: 10% por dia de atraso
Objetivo do trabalho: O objetivo deste trabalho é
permitir aos alunos colocar em prática o conceito de lista encadeada vista na
sala de aula e sua manipulação. Além disso, permite uma prática inicial sobre a
parte de ordenação.
Descrição do trabalho:
Você foi contratado para implementar um sistema
de controle de compras eletrônicas de uma livraria. Para que um cliente possa
fazer compras, ele deve fornecer ao sistema seu login e senha. Na sua conta, o cliente
pode definir diferentes carrinhos de compra, para organizar melhor suas compras e fazer as
compras. Para cada carrinho o cliente deve dar um nome, e uma descrição (e.g.
nome: AEDS2; descrição: livros de algoritmos e estruturas de dados relacionados;
outro carrinho poderia ser: nome: LITERATURA; descrição: livros que eu gostaria
de ler). O cliente escolhe a partir da lista de livros disponíveis (cada livro
tem título, autor e preço), aqueles que deseja comprar e os adiciona a um de
seus carrinhos de compras, dizendo quantas unidades deseja do livro. Os livros
são colocados no carrinho na ordem em que foram selecionados pelo cliente.
A qualquer momento o cliente pode tirar um
livro de um carrinho, ou trocar um livro de um carrinho para outro. O cliente
deve poder listar os livros (dados completos e quantidade de cada um) que estão
em um carrinho (nome e descrição); ou listar tudo (todos os livros de todos os
carrinhos). Quando estiver satisfeito o cliente pode finalizar suas compras de
um carrinho, neste momento, o sistema lista todos os livros deste carrinho com
os seus respectivos preços, lhe informa o valor total das compras, solicita o
nome do cartão a ser debitado (apenas nome) e solicita a confirmação do
cliente. Caso o cliente confirme, a compra é efetuada, e o carrinho esvaziado.
Caso contrário, ele volta (com seu carrinho) para as compras. Como muitas vezes
o cliente acaba não podendo comprar tudo o que gostaria de uma só vez, ele pode
pedir uma ordenação (crescente ou descrescente) por preço dos produtos
selecionados, os livros são então ordenados no carrinho e então a lista
ordenada é mostrada ao cliente.
A qualquer momento o cliente pode escolher
deixar de ser cliente e remover seus dados do cadastro da livraria.
Considerações sobre o
trabalho:
Para simplificar o trabalho, não é preciso
fazer o cadastro do cliente ou verificação do seu login ou senha. Considere que
qualquer login e senha fornecidos são válidos. Os alunos podem considerar que existe um número máximo de 10 carrinhos disponíveis
por cliente. No entanto, o número de livros a serem comprados não é limitado.
Assim, os alunos podem usar um vetor
para representar os carrinhos do cliente, mas DEVEM usar lista encadeada (usando alocação dinâmica de memória –
apontadores) para representar os produtos no carrinho de cada cliente.
Além disso, considerem que o estoque de livros
é ilimitado, ou seja, sempre tem livros para atender aos pedidos dos clientes.
Os dados sobre os livros devem ser armzenados
em um único lugar, e não devem ser repetidos em cada carrinho. Para evitar esta
repetição, crie um vetor contendo a informação dos livros (i.e. a lista de
livros) e armazene no carrinho desejado (em relação ao livro) apenas um
indentificador do livro (e.g. o índice do livro no vetor).
Para ordenar os livros no carrinho de um
cliente, os alunos devem implementar o algoritmo de ordenação de seleção para a lista encadeada de produtos.
A interface do sistema pode ser simples
(textual), mas deve sempre deixar claro para o cliente o que ele pode fazer a
cada momento. Vale ressaltar que não é razoável esperar que os clientes saibam
os livros disponíveis na livraria no momento da compra, então os usuários podem
ver a qualquer momento durante a compra a lista de livros disponíveis.
O aluno deve se preocupar com a qualidade do
código sendo gerado, assim, o programa deve estar dividido em subrotinas,
deve-se usar constantes sempre que apropriado, selecionar nomes mnemônicos para
variáveis, o programa não deve fazer uso
de variáveis globais ou de comandos GOTO.
O trabalho deve ser feito individualmente.
Linguagem de programação:
Os alunos podem utilizar PASCAL ou C.
O que deve ser entregue:
Cada aluno deverá entregar o código do
programa, o programa executável e a documentação. A documentação do programa
deve apresentar:
3. Estudo
de Complexidade: estudo da ordem de complexidade do tempo de execução dos
procedimentos implementados e do programa como um todo (notação O).
4.
Conclusão: comentários gerais sobre o trabalho e as principais dificuldades
encontradas em sua implementação.
5.
Bibliografia: bibliografia que porventura tenha sido utilizada para o
desenvolvimento do trabalho, incluindo sites da Internet se for o caso
Será
marcada uma entrevista do aluno com um dos monitores para apresentar o
trabalho.
Exemplo de tabela de livros a ser utilizada:
Podem usar
esta tabela ou outra qualquer, no entanto, para teste do algoritmos é
importante que a tabela tenha pelo menos 2 livros de mesmo preço.
|
Título |
Autor |
Preço (R$) |
|
Projeto
de Algoritmos |
Nívio
Ziviani |
76,50 |
|
Design de
Interação |
Jenny
Preece |
67,80 |
|
Data
Structure and Algorithms |
Alfred
Aho |
123,00 |
|
Semiotic
Engineering for HCI |
Clarisse
de Souza |
80,00 |
|
Algoritmos
e Estruturas de Dados |
Ângelo
Guimarães |
40,00 |
|
Cálculo
Numérico |
Leônidas
Barroso |
55,00 |
|
Introdução
à Computação Móvel |
Geraldo
Mateus |
40,00 |
|
Modern
Information Retrieval |
Berthier
Ribeiro |
55,00 |
|
Sistemas
de Comércio Eletrônico |
Wagner
Meira |
40,00 |
|
Introdução
à Ciência da Computação |
Ângelo
Guimarães |
45,00 |
|
Alice no
País das Maravilhas |
Lewis
Carroll |
30,90 |
|
A Arte da
Política – A História que Vivi |
Fernando
Henrique Cardoso |
70,00 |
|
As Intermitências
da Morte |
José
Saramago |
35,00 |
|
A Bagagem
do Viajante |
José
Saramago |
35,00 |
|
O Nome da
Rosa |
Umberto
Eco |
55,00 |
|
Vidas
Secas |
Graciliano
Ramos |
27,90 |
|
Grande
Sertão Veredas |
João
Guimarães Rosa |
28,00 |
|
Capitães
de Areia |
Jorge
Amado |
30,90 |
|
O Retorno
do Chef Sem Mistérios |
Jamie
Oliver |
69,00 |
|
1000
Receitas da Culinária Brasileira |
Regina
Reis |
49,00 |
|
Le Cordon
Bleu – Todas as Técnicas da Culinária |
Jeni
Wright |
220,00 |
|
O que
Einstein Disse a seu Cozinheiro |
Robert L.
Wolke |
41,00 |
|
Guia dos
Vinhos Brasileiros |
Eduardo
Viotti |
55,00 |
|
Saladas:
Celeiro |
Maria
Rosa Herz |
90,00 |