INF1010 - Tabelas de Dispersão

Entrega: até sábado, dia 12/10, à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 as seguintes estruturas para representar a tabela:

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

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

Ou seja, o Mapa é uma struct contendo um campo com o tamanho inicial, o número de entradas ocupadas 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 em sala (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. Posições livres na tabela possuem o campo chave também igual a -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 dado. 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.

   Para ""liberar" a compilação da função redimensiona, remova do arquivo mapa.c as linhas

   #if 0
   #endif
   

4. (2,5 pontos) Implemente a função de busca.
5. (1,5 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.