Hash

Universidade Federal da Grande Dourados Faculdade de Ciˆncias Exatas e Tecnologia e Bacharelado em Sistemas de Informa¸˜o ca Estruturas de Dados II Trabalho Pr´tico II a
Professor: M.Sc. Rodrigo Porf´ da Silva Sacchi ırio 5 de junho de 2011
Este trabalho consiste no desenvolvimento de uma aplica¸˜o de dicion´rio, utilizando Tabela Hash ca a com tratamento de colis˜es por encadeamento. O trabalho pode ser desenvolvido em C, C++ ou Java. Os o elementos a serem inseridos sempre ser˜o n´meros inteiros. Pelo menos trˆs classes (ou arquivos .h, no a u e caso de C e C++) devem ser implementadas: • Uma classe com m´todos e atributos static para implementa¸˜o de duas fun¸˜es hash, uma para o e ca co m´todo da divis˜o e outra para o m´todo da multiplica¸˜o: e a e ca – M´todo da divis˜o: Utilizaremos um tamanho igual a 211 para a tabela hash e a fun¸˜o h(x) e a ca = k mod 211; – M´todo da multiplica¸˜o: Utilizaremos um tamanho igual a 512 para a tabela hash e a fun¸˜o e ca ca √ h(x) = m * (k * A mod 1) , onde A = ( 5 − 1); • Uma classe para representar uma tabela hash com tratamento de colis˜es por encadeamento, com o todos os atributos e m´todos necess´rios. Podem utilizar tipos existentes do Java e C++, como e a o LinkedList e STL (Standard Template Library), respectivamente, para implementar cada lista encadeada. – Construtor passando como parˆmetro o tamanho da tabela hash; a – M´todos getter e setter para manipular atributos da classe; e – Inser¸˜o de um elemento na tabela hash; ca – Remo¸˜o de um elemento na tabela hash; ca – Busca de um elemento na tabela hash; – Impress˜o da tabela hash; a • Uma classe deve ser implementada com um menu para testar os m´todos da classe que representa e a tabela hash: – Escolha de qual fun¸˜o utilizar para inserir elementos na tabela hash; ca – Inser¸˜o de um elemento na tabela hash; ca – Remo¸˜o de um elemento na tabela hash; ca – Busca de um elemento na tabela hash; – Impress˜o da tabela hash; a Pode ser feito com at´ dois