Funcoes Tabela Hash.pdf

Prévia do material em texto

Tabela Hash - Func¸o˜es
Tratamento de Colisa˜o - Listas Encadeadas
Disciplina de Algoritmos e Estruturas de Dados I
Curso de Engenharia de Computac¸a˜o
Professor: Silvio Luiz Bragatto Boss
1) Tipo de Dado Abstrato para Tabela Hash
✞
1
2 typedef struct NoTag{
3 int valor; // valor a ser inserido
4 struct NoTag *prox; // ponteiro para o proximo no
5 }no;
✝ ✆
2) Func¸a˜o Main
✞
1
2 void main(void)
3 {
4 no Hash[MAX];
5 int hash ,num ,opcao;
6
7 Inicializa(Hash);
8
9 do
10 {
11 printf("\n1 - Insere elemento na Tabela Hash ");
12 printf("\n2 - Remove elemento na Tabela Hash ");
13 printf("\n3 - Exibe elementos da Tabela Hash ");
14 printf("\n4 - Encerrar Programa ");
15 printf("\nInsira sua opcao ");
16 scanf("%d",&opcao);
17
18 switch(opcao){
19 case 1:
20 printf("Insira um elemento ");
21 scanf("%d",&num);
22 Inserir(Hash , num , num%MAX);
23 break;
24 case 2:
25 printf("Insira um elemento ");
26 scanf("%d",&num);
27 Remover(Hash , num , num%MAX);
28 break;
29 case 3:
30 Imprime(Hash);
31 break;
32 case 4:
33 break;
34 default:
35 printf ("\n Digito nao valido");
36 break;
37 }
38 }while (opcao!= 4);
39
40 }
✝ ✆
3) Func¸a˜o que Inicializa a Tabela Hash
✞
1
2 void Inicializa(no vetHash [])
3 {
4 int i;
5 for (i=0; i<MAX; i++)
6 {
1
7 vetHash[i].prox = NULL;
8 vetHash[i].valor = i;
9 }
10 }
✝ ✆
4) Func¸a˜o que Insere um Elemento na Tabela Hash
✞
1
2 void Inserir(no vetHash[], int valor , int chave)
3 {
4
5 no *aux ,*p;
6
7 aux = ( no *) malloc ( sizeof ( no ) );
8 aux ->valor = valor;
9
10 if(vetHash[chave].prox == NULL)
11 {
12 printf("o numero %d nao se encontra em colisao\n",valor);
13 aux ->prox=NULL;
14 vetHash[chave].prox = aux;
15 }
16 else{// quando entra nesse else , ja esta em colisao
17 printf("o numero %d se encontra em colisao\n",valor);
18 p=vetHash[chave].prox;
19 while(p->prox!=NULL)
20 p=p->prox;
21 p->prox=aux;
22 aux ->prox=NULL;
23 }
24
25 }
✝ ✆
5) Func¸a˜o que Remove um Elemento da Tabela Hash
✞
1
2 void Remover(no vetHash[], int valor , int chave)
3 {
4 no *p,*aux;
5 int verifica =0;
6
7 p=vetHash[chave].prox;
8 if(p == NULL || (p->prox == NULL && p->valor != valor))
9 {
10 printf("Elemento nao encontrado na tabela hash ");
11 }
12 else{
13 if(p->prox == NULL && p->valor == valor)
14 {
15 printf("O numero excluido nao se encontra em colisao\n");
16 vetHash[chave].prox = NULL;
17 free(p);
18 }
19 else{
20 aux = &vetHash[chave];
21 while(p != NULL)
22 {
23 if(p->valor == valor)
24 {
25 printf("O numero excluido se encontra em colisao\n");
26 aux ->prox = p->prox;
27 free(p);
28 verifica = 1;
29 break;
30 }
2
31 aux = p;
32 p = p->prox;
33 }
34 if(verifica == 0)
35 printf("Elemento nao encontrado na tabela hash ");
36 }
37 }
38 }
✝ ✆
6) Func¸a˜o que Exibe os elementos da Tabela Hash
✞
1
2 void Imprime(no vetHash [])
3 {
4
5 int i;
6 no *p;
7
8 for(i=0; i<MAX; i++)
9 {
10
11 if(vetHash[i].prox != NULL)
12 {
13 printf("\nPosicao %d da Tabela Hash\n",vetHash[i].valor);
14 p = vetHash[i].prox;
15 while(p!=NULL)
16 {
17 printf("%d ", p->valor);
18 p=p->prox;
19 }
20 }
21 else
22 printf("\nPosicao %d vazia da Tabela Hash\n",vetHash[i].valor);
23 }
24
25
26 }
✝ ✆
3