Departamento de Ciência da
Computação - IME - USP
Listas encadeadas são as estruturas de dados mais importantes do universo
[nada como exagerar um pouco para chamar atenção].
Paulo Feofiloff
O objetivo desse segundo exercício-programa (EP) é treinar (mais) Recursão, (mais) Registros e structs, (mais) Alocação dinâmica de memória, (mais) Listas encadeadas, Ordenação (algoritmo Quicksort) e um pouco de Busca de palavras em um texto.
Quem assina TV a cabo tem várias opções para assistir filmes. Porém, poucos são os filmes que realmente valem a pena serem vistos. As sinopses oferecidos pelas empresas pouco ajudam.
Pois bem, seus problemas acabaram. Neste EP vamos fazer um programa que imprime notas para filmes usando informações disponíveis na Internet!
Para isso vamos implementar um programa que lê de um (ou mais) arquivo(s) informações sobre filmes e permite fazer operações como consulta, ordenação, inserção e remoção de filmes, etc.
Um esqueleto para você utilizar como ponto de partida para o EP5 está disponível aqui.
Essencialmente, o esqueleto tem a funções de entrada e saída do EP5, inclusive uma função de nome
leString que pode ser usada para ler cadeias de caracteres como, por exemplo, nomes de filmes.
Seu programa irá ler as notas dos filmes de arquivos. Esses arquivos estão no formato utilizado pela The Internet Movie Database (IMDB). O IMDB coleta essas informações a partir da participação de vários espectadores que se dispuseram a dar notas aos filmes.
Como exemplo, mostramos duas linhas do arquivo:
0000000133 279506 8.7 Cidade de Deus (2002)
700000.000 201 1.8 Xuxa Abracadabra (2003)
A primeira linha indica que 279506 pessoas votaram no
filme, a média das notas foi 8,7,
o nome do filme é
Cidade de Deus e o ano do filme é 2002.
Cada nota de um votante é um inteiro de 1 até
10.
O string 0000000133
indica a distribuição de votos.
Cada caractere representa a porcentagem de votos para cada possível
nota, de acordo com a seguinte descrição.
"." nenhum voto "3" 30-39% dos votos "7" 70-79% dos votos
"0" 1-9% dos votos "4" 40-49% dos votos "8" 80-89% dos votos
"1" 10-19% dos votos "5" 50-59% dos votos "9" 90-99% dos votos
"2" 20-29% dos votos "6" 60-69% dos votos "*" 100% dos votos
Portanto, no caso de Cidade de Deus, entre 30 a
39% dos votos foram 10, enquanto que entre
70 a 79% dos votos da Xuxa foram
1. Mas como o filme da Xuxa recebeu apenas 201 votos,
fica a seu critério confiar ou não nessa nota.
O arquivo com os dados de entrada tem, além dos dados a serem lidos,
várias linhas com comentários que devem ser ignorados.
As linhas que devem ser lidas começam com 6 espaços em branco (' ') seguidos de um dígito ('0'..'9') ou do caractere ponto
('.').
Cada linha com uma avaliação de um filme contém, na ordem,
6 espaços em branco,
10 caracteres representando a distribuição dos votos do filme (por exemplo, 0000000133),
279506),
8.7),
Cidade de Deus),
2002).
Para complicar um pouco a vida, às vezes a linha termina com outro par
de parênteses com uma das palavras: mini, TV
ou V, ou com comentários entre chaves (caracteres '{' e '}'). Essa parte deve ser ignorada.
Outro problema: às vezes o ano é desconhecido e é representado por "????", como mostra o exemplo abaixo.
2000001002 107 4.3 "Gigolos" (????)
Vocês não precisam se preocupar muito com isto, já que a função para a leitura desse
arquivo é totalmente fornecida a você no já famoso esqueleto.c.
Os dados de cada filme devem ser armazenados em uma lista duplamente encadeada tendo a seguinte estrutura.
#define TAMNOME 80
typedef struct filme {
char dist[11];
int votos;
float nota;
char nome[TAMNOME+1];
int ano;
struct filme *prox; /* ponteiro para a proxima celula */
struct filme *ant; /* ponteiro para a celula anterior */
} Filme;
typedef struct lista {
Filme *ini; /* ponteiro para a primeira celula da lista de filmes */
Filme *fim; /* ponteiro para a ultima celula da lista de filmes */
} Lista;
Os nomes dos filmes devem ser lidos com no máximo 80
caracteres. Nomes mais longos serão truncados.
Para manter ponteiros para o início e o fim
da lista, usamos uma estrutura do tipo Lista.
Podem aparecer filmes duplicados no arquivo de entrada. Por exemplo, a seguinte entrada aparece duplicada.
0000000124 72392 8.8 Casablanca (1942)
0000000124 72392 8.8 Casablanca (1942)
Somente uma entrada para cada filme deve ser inserida na lista pela função de leitura.
Para isto considerarmos que dois filmes são iguais se eles têm a mesma nota, nome e ano.
Assim, devemos observar que os seguintes filmes são diferentes.
0000000124 72392 8.8 Casablanca (1942)
4....0..03 11 5.5 Casablanca (1961)
1.000.0015 36 4.9 Casablanca (2002)
0.0.021210 60 7.0 Casablanca 50th Anniversary Special: You Must Remember This (1992) (V)
0000212000 71 5.6 Casablanca Driver (2004)
2121000000 84 3.4 Casablanca Express (1989)
3...11.1.2 8 5.4 Casablanca revisitada (1992)
...021310. 25 5.9 Casablanca, Casablanca (1985)
2..111..02 13 5.2 Casablanca, nid d'espions (1963)
.1...133.1 9 6.3 Casablancais, Les (1999)
00.1023000 55 6.2 Cirkus Casablanca (1981)
4.....1..4 7 5.3 Juego sucio en Casablanca (1985)
0000012211 802 7.0 Night in Casablanca, A (1946)
Nos exemplos, tudo que aparece em vermelho foi digitado pelo usuário. A descrição abaixo serve apenas para você formar uma ideia do comportamento do programa. Para entender melhor, rode o programa executável.
Inicialmente o programa apresenta a seguinte lista de opções ao usuário e pede que digite uma das opções:
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao:
A leitura de dados pode ser feita várias vezes. A lista de filmes deve conter os filmes de todos os arquivos lidos, sem duplicação.
Pergunta ao usuário o nome de uma arquivo de filmes no formato do IMDB descrito anteriormente e carrega esse arquivo e armazena os dados os filmes em uma lista.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: c Digite o nome do arquivo: 03-filmes.list Nome do arquivo de entrada: 03-filmes.list ====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First T (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- Night of the Day of the Dawn of the Son of the Bride of the Return of the Reveng (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- "Alsaciens - ou les deux Mathilde, Les" (ano 1996): nota 4.7 19 votos distribuicao [1..0..2103] -------------------------------------------------------------------------------- Total de filmes: 3
Neste caso é pedido o nome do arquivo em que a lista atual de filmes deve ser gravada.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: g Digite o nome do arquivo: meus-3-filmes-preferidos.txt Nome do arquivo de saida: meus-3-filmes-preferidos.txt
Pergunta ao usuário informações sobre o novo filme, e o insere na lista.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: i Digite o nome do filme: The Avengers Digite o ano: 2012 Digite a nota: 8.4 Digite o numero de votos: 393892 Digite a distribuicao: 0..0000124 Filme inserido: -------------------------------------------------------------------------------- The Avengers (ano 2012): nota 8.4 393892 votos distribuicao [0..0000124]
Imprime na tela do computador a lista corrente de filmes. Atenção, essa opção será muuiiittooo útil durante o desenvolvimento do seu programa.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First T (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- Night of the Day of the Dawn of the Son of the Bride of the Return of the Reveng (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- "Alsaciens - ou les deux Mathilde, Les" (ano 1996): nota 4.7 19 votos distribuicao [1..0..2103] -------------------------------------------------------------------------------- The Avengers (ano 2012): nota 8.4 393892 votos distribuicao [0..0000124] -------------------------------------------------------------------------------- Total de filmes: 4
Ordena a lista filmes em ordem de nota. Para isto, você deverá escrever no seu programa uma versão do Quicksort para listas encadeadas.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: o ====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First T (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- The Avengers (ano 2012): nota 8.4 393892 votos distribuicao [0..0000124] -------------------------------------------------------------------------------- "Alsaciens - ou les deux Mathilde, Les" (ano 1996): nota 4.7 19 votos distribuicao [1..0..2103] -------------------------------------------------------------------------------- Night of the Day of the Dawn of the Son of the Bride of the Return of the Reveng (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Total de filmes: 4
Pergunta ao usuário uma parte do nome ("string"), e exibe um filme de cada vez até que o usuário confirme que encontrou o filme, ou que não haja mais filmes contendo aquela "string".
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: p Digite parte do nome a ser procurado: Avengers -------------------------------------------------------------------------------- The Avengers (ano 2012): nota 8.4 393892 votos distribuicao [0..0000124] Esse eh o filme procurado? [s/n]: s
Faz a procura de um filme e, após a confirmação do usuário, remove o filme da lista.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: r Digite parte do nome a ser procurado: Avengers -------------------------------------------------------------------------------- The Avengers (ano 2012): nota 8.4 393892 votos distribuicao [0..0000124] Esse eh o filme procurado? [s/n]: s ====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First T (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- "Alsaciens - ou les deux Mathilde, Les" (ano 1996): nota 4.7 19 votos distribuicao [1..0..2103] -------------------------------------------------------------------------------- Night of the Day of the Dawn of the Son of the Bride of the Return of the Reveng (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Total de filmes: 3
Pergunta ao usuário uma nota máxima X, uma quantidade N, de filmes e um número V de votos e exibe na tela os N melhores filmes com nota menor ou igual X e com pelo menos V votos. Essa opção só deve ser utilizada quando a lista estiver ordenada.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: t Qual o numero de filmes a ser mostrado: 3 Qual a nota maxima: 4.6 Qual o numero minimo de votos: 3 -------------------------------------------------------------------------------- Night of the Day of the Dawn of the Son of the Bride of the Return of the Reveng (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Esses sao os 1 melhores filmes com nota menor que 4.6 e pelo menos 3 votos.
Pergunta ao usuário uma nota mínima X, uma quantidade N de filmes e um número V de votos e exibe na tela os N piores filmes com nota maior ou igual a X e com pelo menos V votos. Essa opção só deve ser utilizada quando a lista estiver ordenada.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: u Qual o numero de filmes a ser mostrado: 3 Qual a nota minima: 4.5 Qual o numero minimo de votos: 4 -------------------------------------------------------------------------------- "Alsaciens - ou les deux Mathilde, Les" (ano 1996): nota 4.7 19 votos distribuicao [1..0..2103] -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First T (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- Esses sao os 2 piores filmes com nota maior que 4.5 e pelo menos 4 votos.
Termina a execução do programa.
====================================================================== (c) Carregar um arquivo de dados (g) Gravar a lista atual em um arquivo (i) Inserir um filme (m) Mostrar todos os filmes (o) Ordenar a lista de filmes (p) Procurar a nota de um filme (r) Remover um filme (t) Mostrar N filmes com nota menor que X e pelo menos V votos (u) Mostrar N filmes com nota maior que X e pelo menos V votos (x) Sair do programa Digite uma opcao: x Mensagem dos nossos patrocinadores: Would you *______really* want to get on a non-stop flight? -- George Carlin
Arquivos de entrada no formato do IMDB, com extensão .list, podem ser
obtidos deste diretório. Inclusive o arquivo
imdb-ratings.list com as notas de mais de 380 mil filmes.
O executável gasta um tempo razoável para carregar essa lista de
filmes. Recomendamos que você não use o arquivo
imdb-ratings.list
para testar o seu programa. Os demais arquivos .list
fornecidos podem ajudar você durante o desenvolvimento, mas
recomendamos que você monte outros arquivos para teste (contendo os seus
filmes favoritos, ou desfavoritos, ou com nomes iguais ou bizarros etc). Caso o tamanho
dos arquivos permitir, compartilhe eles conosco via fórum.
Os arquivos ep5.exe e
ep5-linux são exemplos de executáveis
fornecidos para o Windows e Linux. Muitas dúvidas de como deve ser o
comportamento do programa em algumas situações podem ser resolvidas
experimentando esses programas.
O arquivo esqueleto.c
inclui, entre outras, funções para fazer a leitura do arquivo e construção da
lista duplamente encadeada Você pode utilizar o que quiser do
arquivo esqueleto.c.
Você pode modificar o que quiser, apenas os protótipos das funções
pedidas a seguir não podem ser modificados e precisam ser,
obrigatoriamente, utilizadas no seu programa.
Além da função main, você deve implementar as três funções descritas a seguir.
A função
int achaFilme(Lista *lista, Filme *f);recebe um ponteiro
lista de uma lista de filmes e um ponteito f para um filme.
A função devolve TRUE se o filme está na lista e devolve FALSE em caso contrário.
Para isto considerarmos que dois filmes são iguais se eles têm a mesma nota, nome e ano.
O ponteito lista contém o endereço de
para uma célula do tipo Lista que contém os endereços
ini e fim do início e fim de uma
lista duplamente encadeada de filmes.
A função achaFilme precisa ser implementada para que a função insereFilme passe
a funcionar corretamente.
A opção (o) permite a ordenação da lista de filmes, que ao final deve ficar em ordem decrescentes de notas. Para a ordenação você deve implementar o algoritmo Quicksort adaptado para listas encadeadas. O protótipo da função deve ser o seguinte:
void quickSort(Lista *lista);
A opção (p) e (r) permitem a procura de um filme usando parte do nome. Para isso, seu programa deve perguntar ao usuário a parte do nome a ser procurada e, como é possível encontrar vários filmes contendo uma certa palavra, o usuário deve confirmar se o filme foi achado ou não. Rode o executável para entender melhor esse procedimento.
Para achar um filme com nome contendo o "string" definido pelo
usuário, você deve implementar a função achaPalavra com o
seguinte protótipo:
int achaPalavra(unsigned char *pal, int tPal, unsigned char *texto, int codeexto);que recebe um string
pal com tamanho tPal, e outro
string texto com tamanho codeexto. A função deve
devolver TRUE caso a sequência pal occorra em
texto, e FALSE em caso contrário.
As opções (t) e (u) podem ser utilizadas para mostrar o
N
melhores ou piores filmes em relação a uma nota X
e com pelo menos V votos. Por
exemplo, para um filme entrar na lista dos 250 melhores filmes do
IMDB, além de uma boa nota, ele precisa receber pelo menos
25.000 votos.
Você pode definir o protótipo
que desejar para essas funções, desde que o seu comportamento seja
compatível com o do executável. Recomendamos que ela seja baseada na
função mostraLista contida no esqueleto.