INF1010 - Tabelas de Dispersão

entrega: até sexta, dia 17/5, às 23h

Neste laboratório, vamos implementar uma tabela de dispersão (ou hash) com a mesma interface mapa.h de sempre.

O esqueleto de implementação usa usar as seguintes estruturas para representar a tabela:

typedef struct {
  int chave;
  void* dados;
  int prox;
} ttabpos;

struct smapa {
  int tam;
  int ocupadas;
  ttabpos *tabpos;
};

Ou seja, a tabela é uma struct contendo um campo com o tamanho inicial e um ponteiro para a tabela propriamente dita. Sua implementação deve tratar conflitos através de encadeamento interno, de maneira semelhante ao que foi exposto na aula de segunda (esboçado nesses slides). Cada posição da tabela contém, além da chave e dos dados, um campo prox, apontando para o índice da tabela contendo a próxima chave mapeada para o mesmo valor de hash que a chave na posição atual. Se não houver essa "próxima" chave, o campo prox deve conter o valor -1.

Pegue o arquivo mapa.c que tem um esboço da implementação, e o arquivo de teste em teste.c.

1. (4 pontos) Implemente a função insere, inicialmente sem redimensionamento. O esqueleto de implementação está criando tabelas com 11 posições. A função insere deve seguir o seguinte algoritmo:
   1. Calcula pos fazendo o hash da chave modulo o tamanho da tabela
   2. Caso pos esteja livre, realiza inserção e retorna. Caso contrário, procura por poslivre, uma próxima posição livre na tabela.
   3. Caso a chave em pos tenha o mesmo valor de hash que a chave a inserir, estamos em um conflito primário: insere a nova chave em poslivre e encadeia poslivre na lista atual.
   4. Caso a chave em pos tenha valor diferente de hash que a chave a inserir, estamos em um conflito secundário: move a chave em pos para poslivre e corrige a lista encadeada referente aos conflitos deste outro valor de hash.
2. Teste sua implementação usando o programa de testes dados. A função de hash usada inicialmente gera conflitos para todos os números iguais módulo o tamanho da tabela (definido inicialmente como 11). Use isto para gerar conflitos propositalmente.
3. (2 pontos) Implemente o redimensionamento da tabela (função redimensiona, chamado quando a tabela atinge 75% de ocupação.
4. (2 pontos) Implemente a função de busca.
5. (2 pontos) Implemente a função de retirada. (Não há esqueleto ou teste para essa função!)

obs: Nesse laboratório não é necessário copiar os testes realizados para a área de comentários. Basta entregar o arquivo mapa.c e, caso tenha alterado os testes, entregue também seu arquivo teste.c.