Tipo de Datos Abstracto Conjunto Genérico

Tipo de Datos Abstracto Conjunto Genérico

Quiero compartir en ésta ocasión una implementación del tipo de datos abstracto conjunto genérico en C. Posiblemente es una de las implementaciones que más me costó desarrollar durante mis estudios universitarios aunque, vista ahora desde la perspectiva del tiempo, no es demasiado complicada.

La justificación de éste tipo de estructura de datos es evidente puesto que constituye una poderosísima herramienta con muchísimas aplicaciones: desde el chequeo en los conjunto de caracteres hasta los dicionarios pasando por los métodos de búsqueda ( hashing ).

No hay una tipología concreta de operaciones en ésta estructura de datos, pues dependerá del tipo de conjunto del que se trate aunque, por regla general, tiene las operaciones: inserta, suprime y miembro.

Hoy vamos a ver una implementación particular. Es un ejemplo, una propuesta particular que, por supuesto, no tiene por qué ser la única ni la más eficiente algorítmicamente.

Comenzaremos por la declaración de las funciones y tipos de datos en el fichero conjuntogen.h:

#ifndef CONJUNTOGEN	
#define CONJUNTOGEN

struct cj_int {
	int x;
};

typedef struct conj_rep *conj_enteros;

conj_enteros conjunto_enteros_crea ( void );
void conj_enteros_insertar ( conj_enteros *c, cj_int e,
		int (*compar) ( const void *, const void * ));
void conj_enteros_borrar ( conj_enteros *c, cj_int e,
		int (*compar) ( const void *, const void * ));
int conj_enteros_miembro ( conj_enteros c, struct cj_int e,
		int (*compar) ( const void *, const void * ));
int conj_enteros_tama ( conj_enteros *c );
void conj_enteros_destruir ( conj_enteros *c );

conj_enteros conj_enteros_union ( conj_enteros c, conj_enteros d,
		int (*compar) ( const void *, const void * ));

conj_enteros conj_enteros_interseccion ( conj_enteros c, conj_enteros d,
		int (*compar) ( const void *, const void * ));

conj_enteros conj_enteros_diferencia ( conj_enteros c, conj_enteros d,
		int (*compar) ( const void *, const void * ));




#endif

Como puedes apreciar, tenemos las funciones y procedimientos típicos de un conjunto que ya he enumerado en el párrafo anterior. Además tenemos tres procedimientos más que son habituales en el álgebra de conjuntos en matemáticas: unión, intersección y diferencia.

El siguiente fragmento de código que quiero compartir (incluido en el fichero conjuntogen.c ) son una serie de funciones y procedimientos auxiliares que nos servirán para codificar la libreria conjunto genérico, simplificando y clarificando todo el código. Vamos a verlo:

void conj_dalo ( conj_entero *p ) {
	
	if ( *p != NULL ) {
		free ((*p)->arr );
		free (*p);
		*p = NULL;
}

void conj_alo ( int tama ) {
	
	conj_enteros p;
	
	p = (conj_enteros) malloc ( sizeof ( struct conj_rep ));
	if ( p == NULL ) {
		fprintf ( stderr, "No hay memoria suficiente.\n" );
		exit (1);
	}
	
	if ( tama >=1 ) {
		p->arr = (struct cj_int) malloc ( sizeof (struct cj_int)*tama);
		if ( p->arr == NULL ) {
			fprintf ( stderr, "No hay memoria suficiente.\n" );
			exit (1);
		}
		p->tama = tama;
	}
	else {
		p->arr = (struct cj_int) malloc ( sizeof (struct cj_int));
		if ( p->arr == NULL ) {
			fprintf ( stderr, "No hay memoria suficiente.\n" );
			exit (1);
		}
		p->tama = 0;
	}
	
	return p;
}

int conj_blseq ( conj_enteros a, struct cj_int e, 
		int (*compar) ( const void *, const void * )) {
			
	int i;
	
	if ( a->tama )
		for (i=0; i<a->tama; i++ )
			if (!compar(&amp;(a->arr[i], &amp;e)) return i+1);
	
	return -1;

}

void conj_aumd ( conj_enteros *a, struct cj_int e ) {


	conj_enteros b;
	
	if (!(*a)->tama ) {
		(*a)->tama = 1;
		*((*a)->arr) = e;
	}
	else {
		b=conj_alo (((*a)->tama+1));
		memcpy ( b->arr, (*a)->arr, (*a)->tama*sizeof( struct cj_int ));
		*e = *((*a)->arr+(*a)->tama-1 );
		conj_dalo (a);
		*a = b;
		
	}
}

void conj_disd ( conj_enteros *a, struct cj_int *e ) {
	
	conj_enteros b;
	
	if ((*a)->tama == 1 ) {
		
		(*a)->tama = 0;
		*e = *(*a)->arr;
	
	}	
	
	else {
		
		b = conj_alo (((*a)->tama - 1));
		memcpy ( b->arr, (*a)->arr, b->tama*sizeof ( struct cj_ont ));
		*e = *((*a)->arr+(*a)->tama-1):
		conj_dalo ( a );
		*a = b;
	
}

Por último, os dejo el código de la libreria en C del TDA conjunto genérico:

#include <stdio.h>
#include <stdlib.h>
#include "conjuntogen.h"

struct conj_rep {
	int tama;
	struct cj_entero *arr;
};

conj_enteros conjunto_enteros_crea ( void ) {

	conj_enteros c;
	
	c = conj_alo(0);
	
	return c;
	
}

void conj_enteros_insertar ( conj_enteros *c, cj_int e,
		int (*compar) ( const void *, const void * )) {
	
	if (!(*c) {
		
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
		
	}
	
	if ( conj_blseq (*c, e, compar ) == -1 )
		conj_aumd ( c, e );
			
}

void conj_enteros_borrar ( conj_enteros *c, cj_int e,
		int (*compar) ( const void *, const void * )) {
			

	int i;
	struct cj_int v;
	
	
	if ( !*c ) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	if (( i = conj_blseq ( *c, e, compar)) != -1 ) {
		conj_disd ( c, &amp;v );
		if ( i<=(*c)->tama ) (*c)->arr[i-1] = v;
	}
			
}

int conj_enteros_miembro ( conj_enteros c, struct cj_int e,
		int (*compar) ( const void *, const void * )) {
	
	if (!c) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	return ( conj_blseq ( c, e, compar ) != -1 );	
			
}

int conj_enteros_tama ( conj_enteros *c ) {

	if (!c) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	return (c->tama);

}

void conj_enteros_destruir ( conj_enteros *c ) {
	
	if (!*c) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	conj_dalo ( c );
	
}

conj_enteros conj_enteros_union ( conj_enteros c, conj_enteros d,
		int (*compar) ( const void *, const void * )) {
			

	conj_enteros r;
	int i;
	struct cj_int e;
	
	if ( !c || !d ) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	r = conj_alo ( c->tama );
	memcpy ( r->arr, c->arr, c->tama*sizeof( struct cj_int ) );
	for ( i=i; i<=d->tama; i++ ) {
	
		e = d->arr[i-1];
		if ( conj_blsqe (r, e, compar ) == -1 )
			conj_aumd ( &amp;r, e );	
	}		
	
	return (r);	
}

conj_enteros conj_enteros_interseccion ( conj_enteros c, conj_enteros d,
		int (*compar) ( const void *, const void * )) {
			
	conj_enteros r;
	int i;
	struct cj_int e;
	
	if ( !c || !d ) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	r = conj_crea ();
	for ( i=1; i<=c->tama; i++ ) {
		e = c->arr[i-1];
		if ( conj_blseq ( d, e, compar ) != -1 )
			conj_aumd ( &amp;r, e );
	}
	
	return (r);
	
}

conj_enteros conj_enteros_diferencia ( conj_enteros c, conj_enteros d,
		int (*compar) ( const void *, const void * )) {

	conj_enteros r;
	int i;
	struct cj_int e;
	
	if ( !c || !d ) {
		fprintf ( stderr, "El conjunto no existe.\n" );
		exit (1);
	}
	
	r = conj_crea ();
	for ( i=1; i<=c->tama; i++ ) {
		e = c->arr[i-1];
		if ( conj_blseq ( d, e, compar ) == -1 )
			conj_aumd ( &amp;r, e );
	}
	
	return (r);
			
}

Espero que éste código os pueda ser útil. Espero vuestros comentarios y aportaciones en la sección de comentarios de éste blog o en mi página  de facebook o en mi perfil profesional de twitter.

Si lo preferís, también podéis descargar éste código desde mi cuenta de github.

No Comments

Post a Comment