Tabelas Hash - Exemplo em C
De Aulas
Links relacionados: DAS5102 Fundamentos da Estrutura da Informação
contato.h
1#ifndef CONTATO_H_INCLUDED
2#define CONTATO_H_INCLUDED
3
4typedef struct contato Contato;
5
6Contato* contato_criar(int codigo, char nome[], char telefone[], char email[]);
7
8int contato_getCodigo(Contato *c);
9char* contato_getNome(Contato *c);
10char* contato_getTelefone(Contato *c);
11char* contato_getEmail(Contato *c);
12
13void contato_setCodigo(Contato *c, int codigo);
14void contato_setNome(Contato *c, char nome[]);
15void contato_setTelefone(Contato *c, char telefone[]);
16void contato_setEmail(Contato *c, char email[]);
17
18void contato_destruir(Contato *c);
19
20#endif // CONTATO_H_INCLUDED
contato.c
1#include "contato.h"
2#include "string.h"
3#include <stdlib.h>
4
5struct contato
6{
7 int codigo;
8 char nome[255];
9 char telefone[30];
10 char email[50];
11};
12
13Contato* contato_criar(int codigo, char nome[], char telefone[], char email[])
14{
15 Contato *c = (Contato*) malloc (sizeof(Contato));
16 c->codigo = codigo;
17 strcpy(c->nome, nome);
18 strcpy(c->telefone, telefone);
19 strcpy(c->email, email);
20 return c;
21}
22
23int contato_getCodigo(Contato *c)
24{
25 return c->codigo;
26}
27
28char* contato_getNome(Contato *c)
29{
30 return c->nome;
31}
32
33char* contato_getTelefone(Contato *c)
34{
35 return c->telefone;
36}
37
38char* contato_getEmail(Contato *c)
39{
40 return c->email;
41}
42
43void contato_setCodigo(Contato *c, int codigo)
44{
45 c->codigo = codigo;
46}
47
48void contato_setNome(Contato *c, char nome[])
49{
50 strcpy(c->nome, nome);
51}
52
53void contato_setTelefone(Contato *c, char telefone[])
54{
55 strcpy(c->telefone, telefone);
56}
57
58void contato_setEmail(Contato *c, char email[])
59{
60 strcpy(c->email, email);
61}
62
63void contato_destruir(Contato *c)
64{
65 free(c);
66 c = NULL;
67}
lista.h
1#ifndef LISTA_H_INCLUDED
2#define LISTA_H_INCLUDED
3
4typedef struct lista Lista;
5
6Lista* lista_criar();
7void lista_inserirInicio(Lista* l, int codigo, void *item);
8void lista_inserirFim(Lista* l, int codigo, void *item);
9void lista_inserir(Lista* l, int codigo, void *item, int posicao);
10void* lista_buscar(Lista* l, int posicao);
11void* lista_buscarCodigo(Lista* l, int codigo);
12void lista_excluir(Lista* l, int posicao);
13int lista_tamanho(Lista* l);
14void lista_destruir(Lista* l);
15
16#endif // LISTA_H_INCLUDED
lista.c
1#include "lista.h"
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6typedef struct no No;
7
8struct no
9{
10 int codigo;
11 void* item;
12 No* proximo;
13};
14
15struct lista
16{
17 int tamanho;
18 No* inicio;
19 No* fim;
20};
21
22Lista* lista_criar()
23{
24 Lista* l = malloc(sizeof(Lista));
25 l->tamanho = 0;
26 l->inicio = NULL;
27 l->fim = NULL;
28 return l;
29}
30
31void lista_inserirInicio(Lista* l, int codigo, void* item)
32{
33 No* n = malloc (sizeof(No));
34 n->codigo = codigo;
35 n->item = item;
36 if (l->tamanho == 0)
37 {
38 n->proximo = NULL;
39 l->inicio = n;
40 l->fim = n;
41 l->tamanho++;
42 return;
43 }
44 n->proximo = l->inicio;
45 l->inicio = n;
46 l->tamanho++;
47}
48
49void lista_inserirFim(Lista* l, int codigo, void *item)
50{
51 if(l->tamanho == 0)
52 {
53 lista_inserirInicio(l, codigo, item);
54 return;
55 }
56 No* n = malloc(sizeof(No));
57 n->codigo = codigo;
58 n->item = item;
59 n->proximo = NULL;
60 l->fim->proximo = n;
61 l->fim = n;
62 l->tamanho++;
63}
64
65void lista_inserir(Lista* l, int codigo, void *item, int posicao)
66{
67 if (posicao <= 0)
68 {
69 lista_inserirInicio(l, codigo, item);
70 return;
71 }
72 if (posicao >= l->tamanho)
73 {
74 lista_inserirFim(l, codigo, item);
75 return;
76 }
77 int i;
78 No* local = l->inicio;
79 for (i = 0; i < posicao - 1; i++)
80 {
81 local = local->proximo;
82 }
83 No* n = malloc(sizeof(No));
84 n->codigo = codigo;
85 n->item = item;
86 n->proximo = local->proximo;
87 local->proximo = n;
88 l->tamanho++;
89}
90
91void* lista_buscar(Lista* l, int posicao)
92{
93 if (l->tamanho == 0)
94 {
95 return ""; // Lista vazia
96 }
97 if ((posicao < 0) || (posicao >= l->tamanho))
98 {
99 return ""; // fora da area de abrangencia
100 }
101 No* local = l->inicio;
102 int i;
103 for (i = 0; i < posicao; i++)
104 {
105 local = local->proximo;
106 }
107 return local->item;
108}
109
110void* lista_buscarCodigo(Lista* l, int codigo)
111{
112 No* local = l->inicio;
113 while (local != NULL)
114 {
115 if (local->codigo == codigo)
116 {
117 return local->item;
118 }
119 local = local->proximo;
120 }
121 return NULL;
122}
123
124void lista_excluir(Lista* l, int posicao)
125{
126 if (l->tamanho == 0)
127 {
128 return;
129 }
130 if (l->tamanho == 1)
131 {
132 free(l->inicio);
133 l->tamanho = 0;
134 l->inicio = NULL;
135 l->fim = NULL;
136 }
137 if (posicao == 0)
138 {
139 No* aux = l->inicio;
140 l->inicio = aux->proximo;
141 free(aux);
142 l->tamanho--;
143 return;
144 }
145 No* local = l->inicio;
146 int i = 0;
147 for (i = 0; i < posicao - 1; i++)
148 {
149 local = local->proximo;
150 }
151 No* aux = local->proximo;
152 local->proximo = aux->proximo;
153 free(aux->item);
154 free(aux);
155 if (local->proximo == NULL)
156 {
157 l->fim = local;
158 }
159 l->tamanho--;
160}
161
162int lista_tamanho(Lista* l)
163{
164 return l->tamanho;
165}
166
167void lista_destruir(Lista* l)
168{
169 if (l->tamanho == 0)
170 {
171 return;
172 }
173 while (l->inicio != NULL)
174 {
175 No* aux = l->inicio;
176 l->inicio = l->inicio->proximo;
177 free(aux->item);
178 free(aux);
179 }
180 l->tamanho = 0;
181 free(l);
182 l = NULL;
183}
hash.h
1#ifndef HASH_H_INCLUDED
2#define HASH_H_INCLUDED
3
4typedef struct hash Hash;
5
6Hash* hash_criar();
7void hash_destruir(Hash* h);
8void* hash_buscar(Hash* h, int codigo);
9void hash_inserir(Hash* h, int codigo, void *item);
10
11#endif // HASH_H_INCLUDED
hash.c
1#include "hash.h"
2#include "lista.h"
3#include <stdlib.h>
4#include <stdio.h>
5
6#define OPERADOR 4
7
8struct hash
9{
10 Lista* vet[OPERADOR];
11};
12
13Hash* hash_criar()
14{
15 int i;
16 Hash* h = malloc(sizeof(Hash));
17 for (i = 0; i < OPERADOR; i++)
18 {
19 h->vet[i] = lista_criar();
20 }
21 return h;
22}
23
24void hash_inserir(Hash* h, int codigo, void *item)
25{
26 int chave = (codigo % OPERADOR);
27 lista_inserirInicio(h->vet[chave], codigo, item);
28}
29
30void* hash_buscar(Hash* h, int codigo)
31{
32 return lista_buscarCodigo(h->vet[codigo % OPERADOR], codigo);
33}
34
35void hash_destruir(Hash* h)
36{
37 int i;
38 for (i = 0; i < OPERADOR; i++)
39 {
40 lista_destruir(h->vet[i]);
41 }
42 free(h);
43 h = NULL;
44}
main.c
1#include <stdio.h>
2#include <stdlib.h>
3#include "hash.h"
4#include "contato.h"
5
6int main()
7{
8 Hash* h = hash_criar();
9 hash_inserir(h, 2, contato_criar(2, "Saulo", "99990000", "saulopz@gmail.com"));
10 hash_inserir(h, 6, contato_criar(6, "Joao", "99009900", "joao@gmail.com"));
11 hash_inserir(h, 13, contato_criar(13, "Marta", "99778877", "marta@gmail.com"));
12 hash_inserir(h, 12, contato_criar(12, "Roberta", "87872222", "roberta@gmail.com"));
13 hash_inserir(h, 7, contato_criar(7, "Marta", "77887777", "marta@gmail.com"));
14 int i;
15 for (i = 0; i < 20; i++)
16 {
17 Contato *c = (Contato*)hash_buscar(h, i);
18 if (c != NULL)
19 {
20 printf("%d - %d: %s - %s\n", i % 4, i, contato_getNome(c), contato_getEmail(c));
21 }
22 }
23 hash_destruir(h);
24 return 0;
25}
