Trabalho 6 - Hash
Entrega: 2/12/2009
Implemente uma tabela de dispersao com encadeamento
externo.
Seu programa deve ler um numero, que indica o numero de palavras em um
texto a serem consideradas.
Em seguida, seu programa deve ler este numero de palavras do texto,
contanto quantas vezes a palavra apareceu no texto.
Apos as palavras do texto, o programa lera' uma lista de palavras (ate
fim de arquivo), que devem ser consultadas. Para cada uma delas,
diga quantas vezes ela apareceu no texto.
Faca isto, utilizando sua hash. Faca tambem utilizando o hash_map do
stl, e o map do stl. Compare os tempos de execucao de cada uma destas
estruturas, e do seu.
Utilize um parametro, para indicar que estrutura voce esta
utilizando:
hash -h -> utilize seu encadeamento externo
hash -m -> utilize map do stl
hash -hm -> utilize hash_map do stl.
Exemplo:
Entrada:
61
Em ciência da computação uma tabela de
dispersão também conhecida por tabela de espalhamento ou
tabela hash do inglês hash é uma estrutura de dados
especial que associa chaves de pesquisa a valores
Seu objetivo é a partir de uma chave simples fazer uma
busca rápida e obter o valor desejado
É algumas vezes traduzida como tabela de escrutínio
fonte wikipedia
tabela
hash
dados
jogo
de
uma
pedra
Saida:
# tempo de execucao: XXXXXXX (se possivel, marque o tempo de execucao)
tabela 4
hash 2
dados 1
jogo 0
de 6
uma 4
pedra 0