Tablas hash en C

Tablas hash en C

Vamos a ver una estructura de datos bastante útil en el desarrollo de aplicaciones en C. Hablo de las tablas hash. Estas estructuras de datos se usan habitualmente para realizar búsquedas e inserciones muy eficientes, así como un elevado almacenamiento de datos.

Un diccionario es el ejemplo más tipico que se puede construir usando tablas hash. Voy a dejar en éste artículo un ejemplo bastante sencillo de ésta estructura de datos, que podéis compartir desde  mi cuenta de github.

Cabecera de las funciones y procedimientos

Comenzamos, como siempre, por la declaración de las funciones y procedimientos que requeriremos en nuestra estructura de datos.

#ifndef HASH_XXX_TYPO
#define HASH_XXX_TYPO

typedef struct fich_disperso *disperso;

disperso hash_xxx_nuev(char *fich,int tam, int tam_cubeta,
							 char *(*devuelve_clave) (const void *a));
void hash_xxx_dest (disperso *tabla);
void hash_xxx_inserta(disperso tabla,struct hash_xxx_typo *dato,
				  char *(*devuelve_clave) (const void *a));
void hash_xxx_borrar(disperso tabla,struct hash_xxx_typo *dato,
				  char *(*devuelve_clave) (const void *a));
int hash_xxx_consulta(disperso tabla,struct hash_xxx_typo *dato,
				  char *(*devuelve_clave) (const void *a));
#endif

Implementación de la estructura de datos

El siguiente paso será implementar cada una de éstas funciones y procedimientos en C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "hash_xxx.h"
#include "arditipo.h"

#define MAXLETRAS 32

struct fich_disperso{

	char f[12];
	ardi_tipo cubeta;

};

struct registro0{
	int num_cubeta;
	int tam_cubeta;
};

/*******************************************************************/
/*			MODULO DE PRIMITIVAS PUBLICAS                */
/*******************************************************************/

int dispersion (char *clave, int tamano){

	int i, resultado;

	if (strlen(clave)<2){
		i=0;
		resultado=clave[i]% tamano;
	}
	for (resultado=clave[0], i=1; clave[i]!='\0'; i++)
		resultado=(resultado*MAXLETRAS+clave[i])% tamano;
	return(resultado);

}

/*****************************************************************/

int dispersion2 (char *clave, int tamano){

	int i, resultado;

	if (strlen(clave)<2){
		i=0;
		resultado=clave[i]% tamano;
	}
	for (i=strlen(clave),resultado=clave[i]; i!=0; i--)
		resultado=(resultado*MAXLETRAS+clave[i])% tamano;
	return(resultado);

}


/*******************************************************************/
/*										MODULO DE PRIMITIVAS PUBLICAS								 */
/*******************************************************************/

disperso hash_xxx_nuev(char *fich,int tam, int tam_cubeta,
							 char *(*devuelve_clave) (const void *a)){

	struct registro0 reg0;
	struct hash_xxx_typo dato;
	FILE *f;
	disperso t;
	int i;
	char clave[32];

	strcpy(devuelve_clave(&amp;dato),"");
	t=(disperso)malloc(sizeof(struct fich_disperso));
	if (!t){
		fprintf(stderr, "hash_xxx_nuev: No hay memoria.\n");
		exit(0);
	}
	strcpy(t->f,fich);
	if ((f = fopen(fich, "a+b"))== NULL){
		fprintf(stderr, "Hash_xxx_nuev: No se puede abrir el fichero.\n");
		exit(0);
	}
	reg0.num_cubeta=tam;
	reg0.tam_cubeta=tam_cubeta;
	fwrite(&amp;reg0, sizeof(struct registro0),1,f);
	for (i=0; i!=tam; i++){
		t->cubeta=ardi_tipo_const(tam_cubeta,dato);
		fseek(f,sizeof(struct registro0)+(sizeof(int)*3+
								sizeof(struct hash_xxx_typo)*reg0.tam_cubeta)*i,SEEK_SET);
		ardi_tipo_copiafich(t->cubeta,f);
	}
	fclose(f);
	return t;
}

/********************************************************************/

void hash_xxx_dest (disperso *tabla){

	if (remove((*tabla)->f)){
		fprintf(stderr,"Hash_xxx_dest: El fichero no se puede borrar.\n");
		exit(0);
	}
	ardi_tipo_dest(&amp;(*tabla)->cubeta);
	free(*tabla);
	*tabla=NULL;
}

/*******************************************************************/

void hash_xxx_inserta(disperso tabla,struct hash_xxx_typo *dato,
										 char *(*devuelve_clave) (const void *a)){

	FILE *f;
	int valor, intento=0,tam_cub;
	struct registro0 reg0;
	int i,j;
	struct hash_xxx_typo elem;


	if ((f = fopen(tabla->f, "r+b"))== NULL){
		fprintf(stderr, "Hash_xxx_inserta: No se puede abrir el fichero.\n");
		exit(0);
	}
	fread(&amp;reg0,sizeof(struct registro0),1,f);
	for (i=0; i<reg0.num_cubeta;i++){
		valor=dispersion(devuelve_clave(dato),reg0.num_cubeta)+intento
			 *(dispersion2(devuelve_clave(dato),reg0.num_cubeta)+1);
		fseek(f,sizeof(struct registro0)+(sizeof(int)*3+
								sizeof(struct hash_xxx_typo)*reg0.tam_cubeta)*valor,SEEK_SET);
		ardi_tipo_leefich(tabla->cubeta,f);
		tam_cub=ardi_tipo_tama(tabla->cubeta);
		if (tam_cub<reg0.tam_cubeta){
			for (j=0; j<reg0.tam_cubeta;j++){
				ardi_tipo_obti(tabla->cubeta,j,&amp;elem);
				if (!strcmp(devuelve_clave(&amp;elem),"")){
					ardi_tipo_asig(tabla->cubeta,j,*dato);
					j=reg0.tam_cubeta;
					i=reg0.num_cubeta;
				}
			}
			ardi_tipo_aumlogico(tabla->cubeta);
		}
		else
			intento++;
	}
	fseek(f,sizeof(struct registro0)+(sizeof(int)*3+
							sizeof(struct hash_xxx_typo)*reg0.tam_cubeta)*valor,SEEK_SET);
	ardi_tipo_copiafich(tabla->cubeta,f);
	fclose(f);
}

/**********************************************************************/

void hash_xxx_borrar(disperso tabla,struct hash_xxx_typo *dato,
												char *(*devuelve_clave) (const void *a)){

	FILE *f;
	int valor, intento=0;
	struct registro0 reg0;
	int i,j, encontrado=0;
	struct hash_xxx_typo elem;


	if ((f = fopen(tabla->f, "r+b"))== NULL){
		fprintf(stderr, "Hash_xxx_borrado: No se puede abrir el fichero.\n");
		exit(0);
	}
	fread(&amp;reg0,sizeof(struct registro0),1,f);
	for (i=0; i<reg0.num_cubeta;i++){
		valor=dispersion(devuelve_clave(dato),reg0.num_cubeta)+intento
			 *(dispersion2(devuelve_clave(dato),reg0.num_cubeta)+1);
		fseek(f,sizeof(struct registro0)+(sizeof(int)*3+
								sizeof(struct hash_xxx_typo)*reg0.tam_cubeta)*valor,SEEK_SET);
		ardi_tipo_leefich(tabla->cubeta,f);
		for (j=0; j<reg0.tam_cubeta;j++){
			ardi_tipo_obti(tabla->cubeta,j,&amp;elem);
			if (!strcmp(devuelve_clave(&amp;elem), devuelve_clave(dato))){
				*dato=elem;
				strcpy(devuelve_clave(&amp;elem),"");
				ardi_tipo_asig(tabla->cubeta,j,elem);
				encontrado=1;
				if (ardi_tipo_tama(tabla->cubeta)==reg0.tam_cubeta)
				  ardi_tipo_modborrado(tabla->cubeta);
				j=reg0.tam_cubeta;
				i=reg0.num_cubeta;
			}
			ardi_tipo_dismlogico(tabla->cubeta);
		}
		if (!encontrado){
		  if (ardi_tipo_borrado(tabla->cubeta))
			  intento++;
		  else{
			  printf("El dato no existe. \n");
			  i=reg0.num_cubeta;
		  }
		}
	}
	fseek(f,sizeof(struct registro0)+(sizeof(int)*3+
							sizeof(struct hash_xxx_typo)*reg0.tam_cubeta)*valor,SEEK_SET);
	ardi_tipo_copiafich(tabla->cubeta,f);
	fclose(f);
}

/********************************************************************/

int hash_xxx_consulta(disperso tabla,struct hash_xxx_typo *dato,
												char *(*devuelve_clave) (const void *a)){

	FILE *f;
	int valor, intento=0;
	struct registro0 reg0;
	int i,j, encontrado=0;
	struct hash_xxx_typo elem;


	if ((f = fopen(tabla->f, "r+b"))== NULL){
		fprintf(stderr, "Hash_xxx_consulta: No se puede abrir el fichero.\n");
		exit(0);
	}
	fread(&amp;reg0,sizeof(struct registro0),1,f);
	for (i=0; i<reg0.num_cubeta;i++){
		valor=dispersion(devuelve_clave(dato),reg0.num_cubeta)+intento
			 *(dispersion2(devuelve_clave(dato),reg0.num_cubeta)+1);
		fseek(f,sizeof(struct registro0)+(sizeof(int)*3+
								sizeof(struct hash_xxx_typo)*reg0.tam_cubeta)*valor,SEEK_SET);
		ardi_tipo_leefich(tabla->cubeta,f);
		for (j=0; j<reg0.tam_cubeta;j++){
			ardi_tipo_obti(tabla->cubeta,j,&amp;elem);
			if (!strcmp(devuelve_clave(&amp;elem), devuelve_clave(dato))){
				*dato=elem;
				encontrado=1;
				return 1;
			}
		}
		if (!encontrado){
		  if (ardi_tipo_borrado(tabla->cubeta))
			  intento++;
		  else{
			  printf("El dato no existe. \n");
			  return 0;
		  }
		}
	}
	fclose(f);
}

Estructura de datos auxiliar

Para que funcione correctamente éste TAD, necesitaremos de una estructura de datos auxiliar; concretamente una array dinámico. Vamos a ver cada una de las funciones y procedimientos

Fichero .h

#ifndef ARDI_TIPO_TDA

#define ARDI_TIPO_TDA

struct hash_xxx_typo {

	char clave[32];
	int val;
};

typedef struct ardi_tipo_cubeta  *ardi_tipo;

ardi_tipo ardi_tipo_const(int tama, struct hash_xxx_typo valorinicial);
int ardi_tipo_tama(ardi_tipo a);
int ardi_tipo_borrado(ardi_tipo a);
void ardi_tipo_dismlogico(ardi_tipo a);
void ardi_tipo_aumlogico(ardi_tipo a);
void ardi_tipo_modborrado(ardi_tipo a);
void ardi_tipo_obti(ardi_tipo a, int i, struct hash_xxx_typo *e);
void ardi_tipo_asig(ardi_tipo a, int i, struct hash_xxx_typo e);
void ardi_tipo_copiafich(ardi_tipo a,  FILE *f);
void ardi_tipo_leefich(ardi_tipo a,  FILE *f);
void ardi_tipo_dest(ardi_tipo *a);

#endif

Fichero .c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arditipo.h"

struct ardi_tipo_cubeta {
	int tamal;
	int tamar;
	int borrado;
	struct hash_xxx_typo *arr;
};

/********************************************************************/
/***************   PROCEDIMIENTOS Y FUNCIONES PRIVADOS   ************/
/********************************************************************/

/* Crea el vector con un tama¤o determinado. */

struct hash_xxx_typo	*ardi_tipo_aloarr(int tamano) {

	struct hash_xxx_typo *arr;

	if (!tamano) return(NULL);
	else {
		arr=(	struct hash_xxx_typo *)malloc(sizeof(struct hash_xxx_typo)*tamano);
		if (!arr) {
			fprintf(stderr,"ardi_tipo_aloarr: no hay memoria.\n");
			exit(2);
		}
		return(arr);
	}
}

/********************************************************************/

/* Destruye el vector. */

void ardi_tipo_daloarr(struct hash_xxx_typo *arr) {

	if (arr) free(arr);
}

/********************************************************************/

/* Crea la cabecera del ardi, con un vector de tama¤o indicado. */

ardi_tipo ardi_tipo_alo(int tamano) {

	ardi_tipo p;

	p=(ardi_tipo)malloc(sizeof(struct ardi_tipo_cubeta));
	if (!p) {
		fprintf(stderr,"ardi_tipo_alo: no hay memoria.\n");
		exit(2);
	}
	p->tamal=0;
	p->tamar=tamano;
	p->borrado=0;
	p->arr=ardi_tipo_aloarr(tamano);
	return(p);
}


/********************************************************************/

/* Detruye el vector junto con la cabecera. */

void ardi_tipo_dalo(ardi_tipo *p) {

	if (*p!=NULL) {
		ardi_tipo_daloarr((*p)->arr);
		free(*p);
		*p=NULL;
	}
}

/********************************************************************/
/*************  PROCEDIMIENTOS Y FUNCIONES PUBLICOS   ***************/
/********************************************************************/

ardi_tipo ardi_tipo_const(int tama, struct hash_xxx_typo valorinicial){

	int i;
	ardi_tipo x;
	struct hash_xxx_typo *array;

	if (tama<1) {
		fprintf(stderr, "ardi_tipo_const: tama < 1.\n");
		exit(1);
	}
	x=ardi_tipo_alo(tama);
	for (i=0;i<tama;i++)
		x->arr[i]= valorinicial;
	return (x);
}
/********************************************************************/

/* Te devuelve el tama¤o logico del vector. */

int ardi_tipo_tama(ardi_tipo a) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_tama: el argumento no ha sido creado.\n");
		exit(3);
	}
	return(a->tamal);
}

/********************************************************************/

int ardi_tipo_borrado(ardi_tipo a) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_borrado: el argumento no ha sido creado.\n");
		exit(3);
	}
	return(a->borrado);
}

/********************************************************************/

void ardi_tipo_dismlogico(ardi_tipo a) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_dismlogico: el argumento no ha sido creado.\n");
		exit(3);
	}
	a->tamal--;
}

/********************************************************************/

void ardi_tipo_aumlogico(ardi_tipo a) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_dismlogico: el argumento no ha sido creado.\n");
		exit(3);
	}
	a->tamal++;
}

/********************************************************************/


void ardi_tipo_modborrado(ardi_tipo a) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_modborrado: el argumento no ha sido creado.\n");
		exit(3);
	}
	a->borrado=1;
}

/********************************************************************/

/* Obtienes en *e el valor que se encuentra en la posicion i. La posicion
 * esta dentro del rango de los indices del vector. */

void ardi_tipo_obti(ardi_tipo a, int i, struct hash_xxx_typo *e) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_obti: el argumento no ha sido creado.\n");
		exit(3);
	}
	if (i<0 || i>a->tamar) {
		fprintf(stderr,"ardi_tipo_obti: indice fuera de rango.\n");
		exit(4);
	}
	*e=a->arr[i];
}

/********************************************************************/

/* Asigna el valor de e en la posicion i del vector. i esta dentro del rango. */

void ardi_tipo_asig(ardi_tipo a, int i, struct hash_xxx_typo e) {

	if (!a) {
		fprintf(stderr,"ardi_tipo_asig: el argumento no ha sido creado.\n");
		exit(3);
	}
	if (i<0 || i>a->tamar) {
		fprintf(stderr,"ardi_tipo_asig: indice fuera de rango.\n");
		exit(4);
	}
	a->arr[i]=e;
}

/********************************************************************/

void ardi_tipo_copiafich(ardi_tipo a,  FILE *f){

	 int i;

	 fwrite(&amp;a->tamal, sizeof(int),1,f);
	 fwrite(&amp;a->tamar, sizeof(int),1,f);
	 fwrite(&amp;a->borrado, sizeof(int),1,f);
	 for(i=0; i<a->tamar; i++)
		 fwrite(&amp;a->arr[i], sizeof(struct hash_xxx_typo),1, f);

}

/*******************************************************************/

void ardi_tipo_leefich(ardi_tipo a,  FILE *f){

	 int i;

	 fread(&amp;a->tamal, sizeof(int),1,f);
	 fread(&amp;a->tamar, sizeof(int),1,f);
	 fread(&amp;a->borrado, sizeof(int),1,f);
	 for(i=0; i<a->tamar; i++)
		 fread(&amp;a->arr[i], sizeof(struct hash_xxx_typo),1, f);

}
/*******************************************************************/

/* Destruye el vector dinamico. */

void ardi_tipo_dest(ardi_tipo *a) {

	if (!*a) {
		fprintf(stderr,"ardi_tipo_dest: el argumento no ha sido creado.\n");
		exit(3);
	}
	ardi_tipo_dalo(a);
}

Programa de prueba

Para verificar que todo funciona correctamente, aquí tenéis un programita de prueba en el que se podrá verificar cada una de las funciones y procedimientos de ésta estructura de datos.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash_xxx.h"
#include "arditipo.h"

char *devuelve_clave (const void *a){

	return(((struct hash_xxx_typo*)a)->clave);
}

void main(){

	struct hash_xxx_typo dato;
	int tam_cubeta,n,i,num;
	int tama,opcion;
	disperso t;
	char cad[12];

	printf("Introduce el numero de cubetas.\n");
	scanf("%d",&amp;tama);
	printf("Introduce el tama¤o de las cubetas.\n");
	scanf("%d", &amp;tam_cubeta);
	printf("Introduce el nombre del fichero.\n");
	scanf("%s",cad);
	t= hash_xxx_nuev(cad,tama,tam_cubeta,devuelve_clave);
	do {
	 printf("1 .- Insertar.\n");
	 printf("2 .- Borra.\n");
	 printf("3 .- Consulta.\n");
	 printf("Cualquier otra para salir.\n");
	 printf("Introduce una opcion.\n");
	 scanf("%d",&amp;opcion);
	 switch(opcion) {
		case 1:
		  printf("Dime el numero de elementos que quieres introducir.\n");
		  scanf("%d",&amp;num);
		  for (i=0; i!=num; i++){
			 printf("Introduce una clave.\n");
			 scanf("%s",dato.clave);
			 printf("Introduce un valor.\n");
			 scanf("%d",&amp;dato.val);
			 hash_xxx_inserta(t,&amp;dato,devuelve_clave);
		  }
		  break;
		case 2:
		  printf("Introduce una clave.\n");
		  scanf("%s",dato.clave);
		  hash_xxx_borrar(t,&amp;dato,devuelve_clave);
		  break;
		case 3:
		  printf("Introduce una clave.\n");
		  scanf("%s",dato.clave);
		  if (hash_xxx_consulta(t,&amp;dato,devuelve_clave)){
			 printf("La clave es:   %s.\n", dato.clave);
			 printf("El valor es:   %d.\n", dato.val);
		  }
		  break;
	 }
	} while ((opcion==1) || (opcion==2) || (opcion==3));
   hash_xxx_dest(&amp;t);
}

Conclusión

Me gusta concluir invitando a los lectores de éste blog a que comenten, dejen su opinión y aportaciones tanto en la sección de comentario como en mis redes sociales.

No Comments

Post a Comment