Tabelas Hash - Exemplo em C

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}