DAS5102 - Tabela Hash

Links Relacionados: DAS5102 Fundamentos da Estrutura da Informação

Roteiro

Observe o código abaixo:

 1#include <stdio.h>
 2 
 3#define TAMHASH 113
 4 
 5struct registro
 6{
 7    int prio;
 8    char nome[30];
 9    struct registro *prox;
10};
11 
12struct registro *tabela[TAMHASH];
13 
14int hash( char *n)
15{
16    int i, h;
17    for( i=0, h=1; n[i]!='\0'; ++i)
18    {
19        h = (h * n[i]) % TAMHASH;
20    }
21    printf("Funcao hash de <%s> deu <%d>\n", n, h);
22    return h;
23}
24 
25void insere( int p, char *n)
26{
27    struct registro *novo;
28    int h;
29 
30    if( (novo = (struct registro *) malloc( sizeof(struct registro))) == NULL )
31    {
32        printf("Erro na alocacao\n");
33        exit(1);
34    }
35 
36    novo->prio = p;
37    strcpy( novo->nome, n);
38 
39    h = hash(n);
40 
41    novo->prox = tabela[h];
42    tabela[h] = novo;
43}
44 
45struct registro * consulta( char *n)
46{
47    int h;
48    struct registro *x;
49 
50    h = hash(n);
51    x = tabela[h];
52    while( x != NULL  &&  strcmp( n, x->nome) != 0 )
53    {
54        x = x->prox;
55    }
56    return x;
57}
58
59int main( int argc, char *argv[])
60{
61    int i;
62    struct registro *p;
63 
64    for(i=0; i<TAMHASH; ++i)
65    {
66        tabela[i] = NULL;
67    }
68 
69    insere( 5, "5555");
70    insere( 5, "55555");
71    insere( 8, "8888");
72    insere( 7, "7777");
73    insere( 3, "3333");
74    insere( 9, "9999");
75    insere( 89, "8889");
76    insere( 98, "9998");
77 
78    p = consulta("5555");
79 
80    if( p == NULL )
81    {
82        printf("Nao encontrou 5555!\n");
83    }
84    else
85    {
86        printf("Encontrou 5555 com prioridade %d!\n", p->prio);
87    }
88}

1. Implemente a tabela hash como apresentada em aula (arquivos .h e .c).

2. Implemente um programa principal que faça várias inserções e consultas a esta tabela.

3. Na aula tinha funções para: Criar, inserir e consultar. Contudo, não eram genéricas, mas especificas para "alunos" cujo campo chave era o nome. Modifique-as para que fiquem genéricas, podendo receber qualquer tipo.