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(&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(&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(&(*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(&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,&elem);
				if (!strcmp(devuelve_clave(&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(&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,&elem);
			if (!strcmp(devuelve_clave(&elem), devuelve_clave(dato))){
				*dato=elem;
				strcpy(devuelve_clave(&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(&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,&elem);
			if (!strcmp(devuelve_clave(&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(&a->tamal, sizeof(int),1,f);
	 fwrite(&a->tamar, sizeof(int),1,f);
	 fwrite(&a->borrado, sizeof(int),1,f);
	 for(i=0; i<a->tamar; i++)
		 fwrite(&a->arr[i], sizeof(struct hash_xxx_typo),1, f);
}
/*******************************************************************/
void ardi_tipo_leefich(ardi_tipo a,  FILE *f){
	 int i;
	 fread(&a->tamal, sizeof(int),1,f);
	 fread(&a->tamar, sizeof(int),1,f);
	 fread(&a->borrado, sizeof(int),1,f);
	 for(i=0; i<a->tamar; i++)
		 fread(&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",&tama);
	printf("Introduce el tama¤o de las cubetas.\n");
	scanf("%d", &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",&opcion);
	 switch(opcion) {
		case 1:
		  printf("Dime el numero de elementos que quieres introducir.\n");
		  scanf("%d",&num);
		  for (i=0; i!=num; i++){
			 printf("Introduce una clave.\n");
			 scanf("%s",dato.clave);
			 printf("Introduce un valor.\n");
			 scanf("%d",&dato.val);
			 hash_xxx_inserta(t,&dato,devuelve_clave);
		  }
		  break;
		case 2:
		  printf("Introduce una clave.\n");
		  scanf("%s",dato.clave);
		  hash_xxx_borrar(t,&dato,devuelve_clave);
		  break;
		case 3:
		  printf("Introduce una clave.\n");
		  scanf("%s",dato.clave);
		  if (hash_xxx_consulta(t,&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(&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.

Dejar respuesta

Please enter your comment!
Please enter your name here