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 quinto exercício-programa (EP) é treinar (mais) Recursão, (mais) Registros e structs, (mais) Alocação dinâmica de memória, (mais) Listas encadeadas (listas circulares duplamente encadeadas com cabeça), Ordenação (Mergesort (Quicksort opcional)), um pouco de Busca de palavras em um texto, mais um pouco de Tabelas de símbolos implementadas através de uma Tabela de dispersão (= hash table, opcional).
Este EP é uma adaptação, feita pelo professor José Coelho de Pina, do EP5 de MAC0122 em 2005 de autoria do professor José Augusto Ramos Soares e do EP5 de MAC0122 em 2012 de autoria do professor Carlos Hitoshi Morimoto.
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 é formado por:
Seu programa irá ler as notas dos filmes de arquivos. Esses arquivos são disponibilizados e 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:
0000000233 419191 8.7 Cidade de Deus (2002)
7000000.00 231 1.5 Xuxa Abracadabra (2003)
A primeira linha indica que 419191 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 0000000233
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 231 votos,
fica a seu critério confiar ou não nessa nota.
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. Rodar o programa executável fornecido pode ajudar a entender o EP5.
Inicialmente o programa apresenta a seguinte lista de opções ao usuário e pede que digite uma das opções:
prompt> ./imdb MAC0121 2019 - EP5 The Internet Movie Database (Nov 16 2019, 16:35:45) [GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on Mac OS X ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao:
A leitura de dados pode ser feita várias vezes. A lista atual de filmes mantida pelo programa contém a união de todos os filmes nos arquivos lidos. Se utilizarmos a opção 'C' para carregar um arquivo de dados os eventuais filmes duplicados não serão inseridos na lista atual de filmes. Já, se utilizarmos a opção 'c', os eventuais filmes duplicados serão inseridos na lista de filmes.
Pergunta ao usuário o nome de um arquivo de filmes no formato do IMDB descrito anteriormente e carrega esse arquivo e armazena os dados dos filmes em uma lista.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: C carregueLista: Digite o nome do arquivo: 03-filmes.list carregueLista: Nome do arquivo de entrada: '03-filmes.list' -------------------------------------------------------------------------------- carregueFilme: relatorio da leitura do arquivo '03-filmes.list' no. linhas = 3 no. linhas ignoradas = 0 no. erros em votos ou nota = 0 no. erros no ano = 0 no. anos ignorados = 0 no. filmes repetidos = 0 no. filmes inseridos na lista = 3 no. filmes na lista = 3 carregueFilmes: leitura concluida -------------------------------------------------------------------------------- (0.000375 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- "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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First Television Comedy Team (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- mostreListaFilmes: 3 (de 3) filme(s) exibido(s) (0.0001 segundos)
Neste caso é pedido o nome do arquivo em que a lista atual de filmes deve ser gravada.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: g graveLista: digite o nome do arquivo: meus-3-filmes-preferidos.list AVISO: leiaString: string lido 'meus-3-filmes-preferidos.list' tem 29 caracteres AVISO: graveLista: nome do arquivo de saida: 'meus-3-filmes-preferidos.list' AVISO: graveLista: lista gravada no arquivo (0.000337 segundos)
Pergunta ao usuário informações sobre o novo filme, e o insere na lista.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: i Digite o nome do filme: Thor: The Dark World AVISO: leiaString: string lido 'Thor: The Dark World' tem 20 caracteres Digite o ano: 2013 Digite a nota: 7.2 Digite o numero de votos: 271146 Digite a distribuicao: 0..0004211 AVISO: leiaString: string lido '0..0004211' tem 10 caracteres -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] Filme inserido na lista de filmes (0.000491 segundos)
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 sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] -------------------------------------------------------------------------------- "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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First Television Comedy Team (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- mostreListaFilmes: 4 (de 4) filme(s) exibido(s) (0.000214 segundos)
Pergunta ao usuário uma parte ("string") que supostamente faz parte do nome do filme que está sendo procurado. Em seguida, o programa exibe filmes que contém a "string" como parte do seu nome, 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 sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: p Digite parte do nome do filme a ser procurado: thor AVISO: leiaString: string lido 'thor' tem 4 caracteres -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] Esse e' o filme procurado? [s/n/x] (x para sair): s (0.000234 segundos)
A implementação desta opção é facultativa.
Cria uma tabela de símbolos (= symbol table) das palavras que aparecem no nomes do filmes. Na tabela de símbolos, cada palavra que aparece no nome de algum filme faz o papel das chave enquanto que a lista dos filmes que contém a palavra fará o papel do valor. A tabela de símbolos deverá ser implementada através de uma tabela de dispersão (= hash table) em que as colisões são resolvidas por meio de listas encadeadas (= separate chaining).
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: h AVISO: hashFilmes: tabela de dispersao (hash) criada (0.000894 segundos)
A implementação desta opção é facultativa.
Pergunta ao usuário uma parte ou palavras ("string") que supostamente fazem parte do nome do filme que está sendo procurado. Em seguida, o programa exibe filmes que contém as palavras em seu nome, um filme de cada vez, até que o usuário confirme que encontrou o filme, ou que não haja mais filmes contendo aquelas palavras ou "string".
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: P Digite um parte do nome do filme a ser procurado: thor AVISO: leiaString: string lido 'thor' tem 4 caracteres -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] Esse eh o filme procurado? [s/n/x] (x para sair): s (0.000206 segundos)
A implementação desta opção é facultativa.
Mostra a tabela de símbolos exibindo os códigos de disperção (= hash codes) e a lista de chaves (= lista de palavras) que têm aquele código de dispersão.
======================================================================
(c) carregar um arquivo de dados sem eliminar repeticoes
(C) carregar um arquivo de dados eliminando repeticoes
(g) gravar a lista atual em um arquivo
(p) procurar a nota de um filme
(h) criar a TS com as palavras em nomes de filmes (opcional)
(P) procurar na TS a nota de um filme (opcional)
(M) mostrar a TS (opcional)
(L) limpar a TS (opcional)
(i) inserir um filme
(r) remover um filme
(o) ordenar a lista de filmes por nota (mergeSort)
(O) ordenar a lista de filmes por nome (mergeSort)
(q) ordenar a lista de filmes por nota (quickSort, opcional)
(Q) ordenar a lista de filmes por nome (quickSort, opcional)
(m) mostrar todos os filmes
(<) mostrar N filmes com nota _menor_ que X e pelo menos V votos
(>) mostrar N filmes com nota _maior_ que X e pelo menos V votos
(l) limpar a lista de filmes
(x) sair do programa
Digite uma opcao: M
. . . . . . . . . . . . . . . . . . . . . . .
Tabela de simbolos: { codigo: lista de chaves }
{ 126: 'Living' }
{ 451: 'Peppiatt' }
{ 1795: 'Part' }
{ 2634: 'Revenge' }
{ 3695: 'Day' }
{ 4174: 'Dawn' }
{ 5197: 'Dead' }
{ 6158: 'A' }
{ 7987: 'Thor' }
Continuar? [s/n]: s
{ 18995: 'Presents' }
{ 23194: 'les' }
{ 26214: 's' }
{ 26302: 'Return' }
{ 29156: 'Attack' }
{ 31354: 'ou' }
{ 32227: 'Alsaciens' }
{ 33681: 'First' }
{ 33943: 'Team' }
{ 34985: '3' }
Continuar? [s/n]: s
{ 36251: 'Evil' }
{ 36481: 'of' }
{ 37620: 'Mathilde' }
{ 37971: 'Mutant' }
{ 38449: 'Comedy' }
{ 40685: 'Dark' }
{ 41407: 'Tribute' }
{ 41520: 'The' }
{ 43110: 'Subhumanoid' }
{ 44587: 'Flesh' }
Continuar? [s/n]: s
{ 44886: 'Terror' }
{ 46269: 'to' }
{ 46965: 'World' }
{ 47559: 'Adrienne' }
{ 49043: 'Canada' }
{ 49295: 'Zombified' }
{ 51185: 'Clarkson' }
{ 51840: 'deux' }
{ 53204: 'Son' }
{ 54526: 'Television' }
Continuar? [s/n]: s
{ 56000: 'Eating' }
{ 57657: 'Hellbound' }
{ 64418: 'Aylesworth' }
{ 64600: 'Bride' }
{ 64799: 'Night' }
Continuar? [s/n]: s
(0.000811 segundos)
A implementação desta opção é facultativa.
Remove todas as palavras que estão na tabela de símbolos. Após a execução desta opção a tabela de símbolos estará vazia.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: L TS foi limpa (0.000187 segundos)
Ordena a lista de filmes em ordem decrescente de nota utilizando o Mergesort. Para isto, você deverá escrever no seu programa uma versão do Mergesort para listas circulares duplamente encadeadas com cabeça. Vixe! Baita nome! Ver a especificação mais adiante.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: o Lista de filmes ordenada por nota (3.8e-05 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First Television Comedy Team (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] -------------------------------------------------------------------------------- "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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- mostreListaFilmes: 4 (de 4) filme(s) exibido(s) (9.9e-05 segundos)
Ordena a lista de filmes em ordem (lexicográfica) crescente de nome utilizando o Mergesort. Para isto, você deverá escrever no seu programa uma versão do Mergesort para listas circulares duplamente encadeadas com cabeça. Vixe! baita nome! Ver a especificação mais adiante.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: O Lista de filmes ordenada por nome (4e-05 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- "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 Television Comedy Team (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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] -------------------------------------------------------------------------------- mostreListaFilmes: 4 (de 4) filme(s) exibido(s) (9.7e-05 segundos)
A implementação desta opção é facultativa.
Ordena a lista de filmes em ordem decrescente de nota utilizando o Quicksort. Para isto, você deverá escrever no seu programa uma versão do Quicksort para listas circulares duplamente encadeadas com cabeça. Vixe! Baita nome! Ver a especificação mais adiante.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: q Lista de filmes ordenada por nota (3.8e-05 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- Adrienne Clarkson Presents: A Tribute to Peppiatt & Aylesworth: Canada's First Television Comedy Team (ano 1996): nota 8.7 6 votos distribuicao [.....3...6] -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] -------------------------------------------------------------------------------- "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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- mostreListaFilmes: 4 (de 4) filme(s) exibido(s) (9.7e-05 segundos)
A implementação desta opção é facultativa.
Ordena a lista de filmes em ordem (lexicográfica) crescente de nome utilizando o Quicksort. Para isto, você deverá escrever no seu programa uma versão do Quicksort para listas circulares duplamente encadeadas com cabeça. Vixe! baita nome! Ver a especificação mais adiante.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: Q Lista de filmes ordenada por nome (3.4e-05 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- "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 Television Comedy Team (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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] -------------------------------------------------------------------------------- mostreListaFilmes: 4 (de 4) filme(s) exibido(s) (0.000128 segundos)
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 sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: r Digite parte do nome do filme a ser procurado: thor AVISO: leiaString: string lido 'thor' tem 4 caracteres -------------------------------------------------------------------------------- Thor: The Dark World (ano 2013): nota 7.2 271146 votos distribuicao [0..0004211] Esse e' o filme procurado? [s/n/x] (x para sair): s Filme removido (0.000235 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m -------------------------------------------------------------------------------- "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 Television Comedy Team (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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (ano 2005): nota 2.8 5 votos distribuicao [8........2] -------------------------------------------------------------------------------- mostreListaFilmes: 3 (de 3) filme(s) exibido(s) (0.000105 segundos)
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 por nota.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: < Qual o numero de filmes a serem 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 Revenge of the Terror of the Attack of the Evil, Mutant, Hellbound, Flesh-Eating Subhumanoid Zombified Living Dead, Part 3 (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. (0.000333 segundos)
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 por nota.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: > 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 Television Comedy Team (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. (0.000322 segundos)
Nesta opção a lista é "limpa" e toda área alocada por ela é devolvida ao sistema.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: l Lista de filmes foi limpa (2.8e-05 segundos) ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: m AVISO: mostreListaFilmes: lista de filmes vazia (4.8e-05 segundos)
Termina a execução do programa.
====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao: x (2e-06 segundos)
Os dados de cada filme devem ser armazenados em uma lista duplamente encadeada circular com cabeça tendo a seguinte estrutura.
Copiado do arquivo filmes.h#define TAM_DIST 10 /*----------------------------------------------------------*/ /* Estrutura Basica de uma Lista de Filmes */ /* Uma lista de filmes será uma lista __duplamente ligada__ */ /* __com cabeca__ de objetos do tipo Filme */ typedef struct celFilme Filme; struct celFilme { /* campos referentes a infos sobre o filme */ char dist[TAM_DIST+1]; /* distribuicao de notas do filme */ /* +1 para o '\0' */ int votos; /* numero de votos */ float nota; /* nota do filme */ char *nome; /* nome do filme */ int ano; /* ano do filme */ /* celula de uma lista duplamente ligada */ Filme *prox; /* ponteiro para o proximo filme */ Filme *ant; /* ponteiro para o filme anterior */ }; typedef struct listaFilmes ListaFilmes; struct listaFilmes { int nFilmes; /* no. de filmes na lista */ Filme *cab; /* ponteiro para a celula cabeca da lista de filmes */ };
Os nomes dos filmes devem ser lidos com no máximo TAM_STR (util.h) caracteres.
Suponha que lst é um objeto do tipo ListaFilmes.
Assim, a célula cabeça é lst->cab.
A primeira célula da lista é lst->cab->prox e a última é lst->cab->ant.
Quando a lista lst está vazia, temos que
ou, equivalentemente,lst->cab->prox == lst->cab && lst->cab->ant == lst->cab
lst->nFilmes == 0
O programa utilizará uma tabela de símbolos que tem como chaves as palavras que ocorrem nos nomes dos filmes e como itens filmes cujo título que contém as palavras.
A tabela de símbolos será implementada através de uma tabela de dispersão. O código será uma adaptação para este EP de uma implementação de Donald E. Knuth e das estruturas de dados de Robert Sedgewick contidas nas notas de aula de Paulo Feofiloff. A interface dessa implementação se encontra em st.h e a correspondente implementação em st.c.
Copiado do arquivo st.h/*----------------------------------------------------------*/ /* estrutura para a lista de ponteiros para filmes */ typedef struct ptrFilmes ListaPtrFilmes; struct ptrFilmes { /* ponteiro para um filme na lista de filmes */ Filme *ptrFlm; /* ponteiro para o proximo ponteir de filme na lista */ ListaPtrFilmes *proxPtr; }; /*-----------------------------------------------------------*/ /* prototipos das funcoes que manipulam a tabela de simbolos */ void initST(); ListaPtrFilmes * getFilmeST(String palavra); void putFilmeST(String palavra, Filme *flm); void showST(); void freeST();
A função hash() que calcula o código de dispersão (= hash code) de cada palavra deverá ser definida no arquivo st.c. As colisões serão resolvidas através de separate chaining: para cada código de dispersão ou índice h da tabela, há uma lista encadeada que armazena palavras (chaves) em nomes de filmes que a função de dispersão leva em h. A célula que representa cada palavra/chave possui um ponteiro iniListaPtr para a lista ligada dos (ponteiros para os) filmes que possuem a chave no seu nome.
Copiado do arquivo st.c/*-----------------------------------------------------------*/ /* Tamanho da Tabela de Dispersao * * 65521 e o maior primo menor que 2^16 = 65536 Observacao: * para este EP talvez o tamanho da tabela pudesse ser * menor, 65521 talvez seja um exagero... * * No EP M eh uma constante, mas podia ser uma variavel. */ #define M 65521 /*-----------------------------------------------------------*/ /* funcao que calcula o codigo de dispersao (hash code) de * cada chave/palavra. */ static int hash(String palavra); /*----------------------------------------------------------*/ /* Estrutura Basica da Tabela de Simbolos: * * definicao de uma celula/no' da lista de colisoes */ typedef struct celST CelST; struct celST { /* ponteiro para uma palavra que ocorre no titulo de algum filme */ String palavra; /* ponteiro para lista de ponteiros para filmes que possuem a * palavra em seu titulo */ ListaPtrFilmes *iniListaPtr; /* ponteiro para a proxima celula na tabela de dispersao */ CelST *proxST; }; /*-----------------------------------------------------------*/ /* ponteiros para as M listas de colisoes: para cada h em * [0..M-1], hashHead[h] e um ponteiro para o inicio da lista * encadeada de celulas do tipo CelST que contem as palavras cujo * valor da funcao de hash e' h. */ static CelST *hashHead[M]; /* numero de chaves na tabela de simbolos */ static long nChaves = 0;
O arquivo principal com os dados para este EP é imdb-ratings.list que foi copiado de http://www.imdb.com/interfaces. O arquivo imdb-ratings-limpo.list foi criado pelo executável removendo-se os filmes duplicados de imdb-ratings.list.
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), e
2002).
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)
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 com esses problemas,
pois a função para a leitura desse arquivo (carregueListaFilmes)
é totalmente fornecida a você no já famoso esqueleto,
em iofilmes.c.
Aqui estão listados os protótipos das funções fornecidas ou parcialmente fornecidas e que você utilizará em algum dos trechos de código que deverá escrever. O comportamento das funções está descrito nos comentários que precedem as funções nos arquivos do esqueleto.
No módulo main.c temos as funções
A função main() está parcialmente feita.int main(int argc, char *argv[]); static char leiaOpcao();
No módulo iofilmes.c temos as funções
Atenção, a função carregueListaFilmes() só funcionará após as funções contemFilme() e insereFilme() tiverem sido feitas.void carregueListaFilmes(ListaFilmes *lst); void graveListaFilmes(ListaFilmes *lst); void mostreFilme(Filme *flm);
No módulo filmes.c temos as funções
Filme * crieFilme(char *dist, int votos, float nota, char *nome, int ano);
Finalmente, no módulo util.c temos as funções
int strCmp(const char *s1, const char *s2); int leiaString(char s[], int size); void * mallocSafe(size_t n);
Aqui estão listados os protótipos das funções que você deverá escrever.
O comportamento das funções está descrito nos comentários que precedem
as funções nos arquivos do esqueleto ou ainda no meio
da função, como no caso das funções main() no main.c.
Você (sempre!) pode escrever mais funções auxiliares se achar necessário.
Utilize as funções da biblioteca do C que desejar.
Em main.c, parte do corpo da função
int main(int argc, char *argv[])
No módulo iofilmes.c encontramos as funções:
void mostreListaFilmes(ListaFilmes *lst); void mostrePioresFilmes(ListaFilmes *lst); void mostreMelhoresFilmes(ListaFilmes *lst);
No módulo filmes.c temos as funções:
Atenção, a função carregueListaFilmes() (iofilmes.c) só funcionará após as funções contemFilme() e insereFilme() tiverem sido feitas.ListaFilmes * crieListaFilmes(); Filme * crieFilme(char *dist, int votos, float nota, char *nome, int ano); void libereListaFilmes(ListaFilmes *lst); void libereFilme(Filme *flm); Bool contemFilme(ListaFilmes *lst, Filme *flm); void insiraFilme(ListaFilmes *lst, Filme *flm); void removaFilme(ListaFilmes *lst, Filme *flm); void mergeSortFilmes(ListaFilmes *lst, Criterio criterio); void quickSortFilmes(ListaFilmes *lst, Criterio criterio); /* opcional */ void hashFilmes(ListaFilmes *lst); /* opcional */
No módulo util.c:
Bool achePalavra(unsigned char *pal, int tPal, unsigned char *texto, int tTex)
No módulo st.c, todas as função são opcionais:
void initST(); ListaPtrFilmes * getFilmeST(String palavra); void putFilmeST(String palavra, Filme *flm); void showST(); void freeST(); static int hash(String palavra);
Aqui temos uma visão geral dos arquivos que compõem o EP. Você deverá depositar na página de MAC0121 apenas um arquivo zip ou tar.gz contendo todos os arquivos com extensão .h e .c do seu EP5.
Este exercício-programa é formado por 10 arquivos.
O diretório com o esqueleto do EP contém, além desses 10 arquivos, um Makefile para
gerar o executável imdb do EP e .zip
com todos os arquivos do EP.
Mais precisamente, os arquivos no diretório com o esqueleto são
prompt/esqueleto> ls -l total 100 -rw-r--r--@ 1 cris 19297 Nov 14 13:16 00-esqueleto.zip -rw-r--r--@ 1 cris 578 Nov 14 13:16 Makefile -rw-r--r--@ 1 cris 9128 Nov 14 13:16 filmes.c -rw-r--r--@ 1 cris 2089 Nov 14 13:16 filmes.h -rw-r--r--@ 1 cris 12821 Nov 14 13:16 iofilmes.c -rw-r--r--@ 1 cris 641 Nov 14 13:16 iofilmes.h -rw-r--r--@ 1 cris 8163 Nov 14 13:16 main.c -rw-r--r--@ 1 cris 1863 Nov 14 13:16 main.h -rw-r--r--@ 1 cris 7717 Nov 17 21:26 st.c -rw-r--r--@ 1 cris 1298 Nov 14 13:16 st.h -rw-r--r--@ 1 cris 6111 Nov 14 13:16 util.c -rw-r--r--@ 1 cris 1196 Nov 14 13:16 util.hPara compilar o programa e gerar o executável basta, na linha de comando, digitar make. Faça isto assim que baixar o esqueleto e você verá as seguintes mensagens e um executável de nome pitao será gerado.
prompt/esqueleto> make
gcc -g -Wall -g -O0 -ansi -pedantic -Wno-unused-result -c main.c
gcc -g -Wall -g -O0 -ansi -pedantic -Wno-unused-result -c util.c
gcc -g -Wall -g -O0 -ansi -pedantic -Wno-unused-result -c iofilmes.c
gcc -g -Wall -g -O0 -ansi -pedantic -Wno-unused-result -c filmes.c
gcc -g -Wall -g -O0 -ansi -pedantic -Wno-unused-result -c st.c
st.c:127:1: warning: unused function 'hash' [-Wunused-function]
hash(String palavra)
^
st.c:106:15: warning: unused variable 'hashHead' [-Wunused-variable]
static CelST *hashHead[M];
^
st.c:109:12: warning: unused variable 'nChaves' [-Wunused-variable]
static int nChaves = 0;
^
3 warnings generated.
gcc main.o util.o iofilmes.o filmes.o st.o -o imdb
Note que, apesar de no esqueleto o corpo das funções que
deverão ser feitas estar vazio, o EP compila
sem erros de sintaxe e com apenas 3 avisos
devido a definições que foram feitas em st.c mas não foram utilizadas.
No entanto, se você executar o programa imediatamente, ele não fará grandes coisas :-(.
AVISO: crieListaFilmes em filmes.c: Vixe! Ainda nao fiz essa funcao ... MAC0121 2019 - EP5 The Internet Movie Database (Nov 16 2019, 23:43:07) [GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.1)] on Mac OS X ====================================================================== (c) carregar um arquivo de dados sem eliminar repeticoes (C) carregar um arquivo de dados eliminando repeticoes (g) gravar a lista atual em um arquivo (p) procurar a nota de um filme (h) criar a TS com as palavras em nomes de filmes (opcional) (P) procurar na TS a nota de um filme (opcional) (M) mostrar a TS (opcional) (L) limpar a TS (opcional) (i) inserir um filme (r) remover um filme (o) ordenar a lista de filmes por nota (mergeSort) (O) ordenar a lista de filmes por nome (mergeSort) (q) ordenar a lista de filmes por nota (quickSort, opcional) (Q) ordenar a lista de filmes por nome (quickSort, opcional) (m) mostrar todos os filmes (<) mostrar N filmes com nota _menor_ que X e pelo menos V votos (>) mostrar N filmes com nota _maior_ que X e pelo menos V votos (l) limpar a lista de filmes (x) sair do programa Digite uma opcao:
Agora, passamos a descrição dos arquivos.
prompt> make gcc -Wall -O2 -ansi -pedantic -Wno-unused-result -c main.c gcc -Wall -O2 -ansi -pedantic -Wno-unused-result -c util.c gcc -Wall -O2 -ansi -pedantic -Wno-unused-result -c iofilmes.c gcc -Wall -O2 -ansi -pedantic -Wno-unused-result -c filmes.c gcc -Wall -O2 -ansi -pedantic -Wno-unused-result -c st.c gcc main.o util.o iofilmes.o filmes.o st.o -o imdb
Arquivos de entrada no formato do IMDB, com extensão .list, podem ser
obtidos deste diretório. Inclusive o arquivo
ratings com as notas de mais de 570 mil filmes.
O executável gasta um tempo razoável para carregar essa lista de
filmes eliminando os filmes repetidos (opção 'C').
Recomendamos que você não use os arquivos imdb-ratings.list
para testar o seu programa durante a fase de desenvolvimento.
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 permita, os compartilhe conosco via fórum.
O arquivo imdb-ratings.list contém muitos filmes que consideramos repetidos.
O arquivo imdb-ratings-limpo.list é uma versão "sem
repetições" que pode ser carregada rapidamente com a opção 'c'.