Programación de una lista genérica en C

Programación de una lista genérica en C

Hoy os voy a dejar el código fuente de una lista genérica programada en C. Es una práctica que hice durante mis estudios universitarios y confío en que os sea de utilidad.

Podéis descargarlo desde mi cuenta de github y usarlo como mejor pueda adaptarse a vuestras necesidades.

En esta lista pueden almacenarse elementos de cualquier tipo con la única precondición de que sean de igual tamaño. Esta lista tiene tres entradas: por el principio, en una zona intermedia y por el final de la lista.

Precondiciones y postcondiciones de las funciones y procedimientos del TDA

En esta sección vamos a dejar un listado de las cabeceras de cada una de las funciones y procedimientos que componen éste tipo de datos abstracto y las precondiciones, modificaciones y postcondiciones que son necesarias para que funcione correctamente.

lista l_nueva (unsigned int tam);

Precondiciones: Haya memoria para el nuevo objeto. No se realiza ninguna

comprobación sobre el valor de tam.

Postcondiciones: Devuelve un objeto del tipo lista que no contiene ningún

elemento, inicializada para el tamaño del tipo base, el expresado en tam..

int l_vacia (lista l);

Precondiciones: La lista l debe existir.

Postcondiciones: Devuelve un valor != 0 si la lista l no contiene ningún

elemento y 0 en caso contrario.

void l_meterizq (lista l, void *e);

Precondiciones: La lista l debe existir. Haya memoria para el nuevo elemento.

Postcondiciones: Añade el elemento *e a la lista l por la izquierda.

void l_sacarizq (lista l, void *e);

Precondiciones: La lista l debe existir y no estar vacía.

Modifica: *e.

Postcondiciones: Elimina y devuelve en *e el elemento más a la izquierda de la

lista l, liberando la memoria asignada.

void l_meterder (lista l, void *e);

Precondiciones: La lista l debe existir. Haya memoria para el nuevo elemento.

Postcondiciones: Añade el elemento *e a la lista l por la derecha.

void l_sacarder (lista l, void *e);

Precondiciones: La lista l debe existir y no estar vacía.

Modifica: *e.

Postcondiciones: Elimina y devuelve en *e el elemento más a la derecha de la

lista l, liberando la memoria asignada.

void l_meterx (lista l, void *e, int (compar) (const void *, const void *));

Precondiciones: La lista l debe existir. Haya memoria para el nuevo elemento.

Postcondiciones: Añade el elemento *e a la lista l en la posición que le

corresponde, manteniéndose el orden de los elementos de la lista.

int l_sacarx (lista l, void *e, int (compar) (const void *, const void *));

Precondiciones: La lista l debe existir y no estar vacía.

Modifica: *e.

Postcondiciones: Devuelve != 0 si el elemento *e está en la lista l, lo elimina y

libera la memoria asignada, manteniéndose el orden de los elementos de la lista,

y cero en otro caso. El elemento lo devuelve en *e.

void l_destruir (lista l );

Precondiciones: La lista l debe existir.

Modifica: l.

Postcondiciones: Libera la memoria asignada a la lista l y a la salida

l = NULL.

int l_buscar (lista l, void *e, int (compar) (const void *, const void *));

Precondiciones: La lista l debe existir y no estar vacía.

Modifica: *e.

Postcondiciones: Busca *e en la lista l. Si no existe devuelve 0. Si existe

devuelve 1 y en *e el elemento encontrado.

lista l_copiar (lista l);

Precondiciones: Haya memoria para el nuevo objeto. La lista l debe existir.

Postcondiciones: Devuelve una lista que es una copia similar de l.

void i_inicializar (lista l);

Precondiciones: La lista l debe existir y no estar vacía.

Postcondiciones: Inicicializa el iterador al primer elemento de la lista l.

int i_quedan (lista l);

Precondiciones: La lista l debe existir y no estar vacía.

Postcondiciones: Devuelve != 0 si el iterador apunta a un elemento de la lista l,

0 en caso contrario.

void i_dame (lista l, void *e);

Precondiciones: La lista l debe existir y no estar vacía.

Modifica:*e

Postcondiciones: Devuelve en *e el elemento al que apunta el iterador y avanza

el iterador al siguiente elemento.

Fichero de las cabeceras del tipo de datos abstracto lista genérica

#ifndef LISTAVOID

#define LISTAVOID

typedef void *lista;

lista l_nueva (unsigned int tam);
int l_vacia (lista l);
void l_meterder (lista l, void *e);
void l_meterizq (lista l, void *e);
void l_sacarder (lista l, void *e);
void l_sacarizq (lista l, void *e);
void l_meterx (lista l, void *e, int (compar)(const void *, const void *));
int l_sacarx (lista l, void *e, int (compar)(const void *, const void *));
lista l_copiar (lista l);
int l_buscar (lista l, void *e, int (compar)(const void *, const void *));
void l_destruir (lista *l);

void i_inicializar (lista l);
void i_dame (lista l, void *e);
int i_quedan (lista l);

#endif

Implementación del tipo de dato abastracto

#include <stdio.h>
#include <stdlib.h>
#include <mem.h>
#include "lvoid.h"

struct tlista    {
	unsigned int tam;
	void *iter;
	void *prim;
	void *ult;
   };

// ----------------------------------------------------------------------
//			FUNCIONES PRIVADAS
// ----------------------------------------------------------------------

void l_error (int error, char *prim)    {
	switch (error)   {
	     case 1: fprintf (stderr, "\n\n\t%s: No hay suficiente memoria.\n", prim);
		     break;
	     case 2: fprintf (stderr, "\n\n\t%s: La lista no existe.\n", prim);
		     break;
	     case 3: fprintf (stderr, "\n\n\t%s: La lista esta vacia.\n", prim);
		     break;
	  }
   }

// ----------------------------------------------------------------------
//			FUNCIONES PUBLICAS
// ----------------------------------------------------------------------

lista l_nueva (unsigned int tam)    {
	struct tlista *nueva;

	nueva = (struct tlista *) malloc (sizeof (struct tlista));
	if (!nueva)   {
		l_error (1, "l_nueva");
		exit (1);
	    }

	nueva -> tam = tam;
	nueva -> prim = nueva -> ult = nueva -> iter = NULL;
	return (nueva);
   }

// ----------------------------------------------------------------------

int l_vacia (lista l)    {
	if (!l)    {
		l_error (2, "l_vacia");
		exit (1);
	   }

	return (((struct tlista *) l) -> prim == NULL);
   }

// ----------------------------------------------------------------------

void l_meterder (lista l, void *e)    {
	void *nuevo;

	if (!l)    {
		l_error (2, "l_meterder");
		exit (1);
	   }
	nuevo = (void *) malloc (sizeof (nuevo) + ((struct tlista *) l) -> tam);
	if (!nuevo)    {
		l_error (1, "l_meterder");
		exit (1);
	   }

	memcpy ((char *) nuevo + sizeof (nuevo), e, ((struct tlista *) l) -> tam);

	if (((struct tlista *) l) -> prim == NULL)    {
		memcpy (nuevo, &amp;((struct tlista *) l) -> prim, sizeof (nuevo));
		((struct tlista *) l) -> prim = ((struct tlista *) l) -> ult = nuevo;
	   }
	else    {
		memcpy (nuevo, ((struct tlista *) l) -> ult , sizeof (nuevo));
		memcpy (((struct tlista *) l) -> ult, &amp;nuevo, sizeof (nuevo));
		((struct tlista *) l) -> ult = nuevo;
	   }
   }

// ----------------------------------------------------------------------

void l_meterizq (lista l, void *e)   {
	void *nuevo;

	if (!l)    {
		l_error (2, "l_meterizq");
		exit (1);
	   }
	nuevo = (void *) malloc (sizeof (nuevo) + ((struct tlista *) l) -> tam);
	if (!nuevo)    {
		l_error (1, "l_meterizq");
		exit (1);
	   }

	memcpy ((char *) nuevo + sizeof (nuevo), e, ((struct tlista *) l) -> tam);

	if (((struct tlista *) l) -> prim == NULL)    {
		memcpy (nuevo, &amp;((struct tlista *) l) -> prim, sizeof (nuevo));
		((struct tlista *) l) -> prim = ((struct tlista *) l) -> ult = nuevo;
	   }
	else    {
		memcpy (nuevo, &amp;((struct tlista *) l) -> prim, sizeof (nuevo));
		((struct tlista *) l) -> prim = nuevo;
	  }
   }

// ----------------------------------------------------------------------

void l_sacarder (lista l, void *e)   {
	void *viejo, *aux;

	if (!l)    {
		l_error (2, "l_sacarder");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "l_sacarder");
		exit (1);
	   }

	viejo = ((struct tlista *) l) -> ult;
	memcpy (e, (char *) viejo + sizeof (viejo), ((struct tlista *) l) -> tam);

	if (((struct tlista *) l) -> prim == ((struct tlista *) l) -> ult)
		((struct tlista *) l) -> prim = ((struct tlista *) l) -> ult = NULL;
	else   {
		((struct tlista *) l) -> ult = ((struct tlista *) l) -> prim;
		memcpy ((char *)&amp;aux, ((struct tlista *) l) -> ult, sizeof (aux));

		while (aux != viejo)     {
			memcpy (&amp;((struct tlista *) l) -> ult, (char *)&amp;aux, sizeof (aux));
			memcpy ((char *)&amp;aux, ((struct tlista *) l) -> ult, sizeof (aux));
		   }
		memcpy (((struct tlista *) l) -> ult, viejo, sizeof (viejo));
	  }

	free (viejo);
   }

// ----------------------------------------------------------------------

void l_sacarizq (lista l, void *e)   {
	void *viejo;

	if (!l)    {
		l_error (2, "l_sacarizq");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "l_sacarizq");
		exit (1);
	   }

	viejo = ((struct tlista *) l) -> prim;
	memcpy (e, (char *) viejo + sizeof (viejo), ((struct tlista *) l) -> tam);

	if (((struct tlista *) l) -> prim == ((struct tlista *) l) -> ult)
		((struct tlista *) l) -> prim = ((struct tlista *) l) -> ult = NULL;
	else   	memcpy (&amp;((struct tlista *) l) -> prim, viejo, sizeof (viejo));

	free (viejo);
   }

// ----------------------------------------------------------------------

void l_meterx (lista l, void *e, int (compar)(const void *, const void *))    {
	void *nuevo, *corr, *ant, *dato;

	if (!l)    {
		l_error (2, "l_meterx");
		exit (1);
	   }

	nuevo = (void *) malloc (sizeof (nuevo) + ((struct tlista *) l) -> tam);
	if (!nuevo)    {
		l_error (1, "l_meterx");
		exit (1);
	   }
	memcpy ((char *) nuevo + sizeof (nuevo), e, ((struct tlista *) l) -> tam);

	if (((struct tlista *) l) -> prim == NULL)    {
		memcpy (nuevo, &amp;((struct tlista *) l) -> prim, sizeof (nuevo));
		((struct tlista *) l) -> prim = ((struct tlista *) l) -> ult = nuevo;
	   }
	else    {
		corr = ((struct tlista *) l) -> prim;
		ant = NULL;
                dato = (char *) malloc (((struct tlista *) l) -> tam);
                if (!dato)    {
                      l_error (1, "l_meterx");
                      exit (1);
                 }
		memcpy (dato, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);

		while ((compar (e, dato) > 0) &amp;&amp; corr)     {
			ant = corr;
			memcpy (&amp;corr, (char *) corr, sizeof (corr));
			memcpy (dato, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);
		   }

		memcpy ((char *) nuevo, &amp;corr, sizeof (nuevo));
		if (ant == NULL)    ((struct tlista *) l) -> prim = nuevo;
		else  if (ant == ((struct tlista *) l) -> ult)     {
			      memcpy ((char *) ant, &amp;nuevo, sizeof (nuevo));
			      ((struct tlista *) l) -> ult = nuevo;
			 }
		      else  memcpy ((char *) ant, &amp;nuevo, sizeof (nuevo));

              free (dato);
	  }
   }

// ----------------------------------------------------------------------

int l_sacarx (lista l, void *e, int (compar)(const void *, const void *))    {
	void *viejo, *ant, *dato;

	if (!l)    {
		l_error (2, "l_sacarx");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "l_sacarx");
		exit (1);
	   }

	viejo = ((struct tlista *) l) -> prim;
	ant = NULL;
        dato = (char *) malloc (((struct tlista *) l) -> tam);
        if (!dato)    {
               l_error (1, "l_sacax");
               exit (1);
           }
	memcpy (dato, (char *) viejo + sizeof (viejo), ((struct tlista *) l) -> tam);

	while ((compar (e, dato) != 0) &amp;&amp; viejo)     {
		ant = viejo;
		memcpy (&amp;viejo, (char *) viejo, sizeof (viejo));
		memcpy (dato, (char *) viejo + sizeof (viejo), ((struct tlista *) l) -> tam);
	   }
        free (dato);

	if (viejo != NULL)    {
		memcpy (e, (char *) viejo + sizeof (viejo), ((struct tlista *) l) -> tam);

		if (((struct tlista *) l) -> prim == viejo)
			memcpy (&amp;((struct tlista *) l) -> prim, viejo, sizeof (viejo));
		else    {
			memcpy ((char *) ant, (char *) viejo, sizeof (viejo));
			if (((struct tlista *) l) -> ult == viejo)
				((struct tlista *) l) -> ult = ant;
		   }

		if (((struct tlista *) l) -> prim == NULL)
			((struct tlista *) l) -> ult = NULL;

		free (viejo);
		return (1);
	   }
	else return (0);
    }

// ----------------------------------------------------------------------

lista l_copiar (lista l)    {
	void *nueva, *corr, *dato;

	if (!l)    {
		l_error (2, "l_copiar");
		exit (1);
	   }

	nueva = l_nueva (((struct tlista *) l) -> tam);
	corr = ((struct tlista *) l) -> prim;
        dato = (char *) malloc (((struct tlista *) l) -> tam);
        if (!dato)    {
               l_error (1, "l_copiar");
               exit (1);
           }

	while (corr)   {
		memcpy (dato, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);
		l_meterder (nueva, dato);
		memcpy (&amp;corr, (char *) corr, sizeof (corr));
	  }

        free (dato);
	return (nueva);
   }

// ----------------------------------------------------------------------

int l_buscar (lista l, void *e, int (compar)(const void *, const void *))   {
	void *corr, *dato;

	if (!l)    {
		l_error (2, "l_buscar");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "l_buscar");
		exit (1);
	   }

	corr = ((struct tlista *) l) -> prim;
        dato = (char *) malloc (((struct tlista *) l) -> tam);
        if (!dato)    {
               l_error (1, "l_buscar");
               exit (1);
           }
	memcpy (dato, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);

	while ((compar (e, dato) != 0) &amp;&amp; corr)     {
		memcpy (&amp;corr, (char *) corr, sizeof (corr));
		memcpy (dato, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);
	   }
        free (dato);

	if (corr != NULL)    {
		memcpy (e, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);
		return (1);
	   }
	else  return (0);
   }

// ----------------------------------------------------------------------

void l_destruir (lista *l)    {
	void *viejo;

	if (!*l)    {
		l_error (2, "l_destruir");
		exit (1);
	   }

	viejo = ((struct tlista *) *l) -> prim;
	while (viejo)   {
		memcpy (&amp;((struct tlista *) *l) -> prim, viejo, sizeof (viejo));
		free (viejo);
		viejo = ((struct tlista *) *l) -> prim;
	   }

	free (((struct tlista *) *l));
	*l = NULL;
    }

// ----------------------------------------------------------------------
//			FUNCIONES DEL ITERADOR
// ----------------------------------------------------------------------

void i_inicializar (lista l)    {

	if (!l)    {
		l_error (2, "il_inicializar");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "il_inicializar");
		exit (1);
	   }

	((struct tlista *) l) -> iter = ((struct tlista *) l) -> prim;
   }

// ----------------------------------------------------------------------

void i_dame (lista l, void *e)    {
	void *corr;

	if (!l)    {
		l_error (2, "il_siguiente");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "il_siguiente");
		exit (1);
	   }

	corr = ((struct tlista *) l) -> iter;
	memcpy (e, (char *) corr + sizeof (corr), ((struct tlista *) l) -> tam);
	memcpy (&amp;((struct tlista *) l) -> iter, corr, sizeof (corr));
   }

// ----------------------------------------------------------------------

int i_quedan (lista l)    {

	if (!l)    {
		l_error (2, "il_quedan");
		exit (1);
	   }
	if (((struct tlista *) l) -> prim == NULL)    {
		l_error (3, "il_quedan");
		exit (1);
	   }

	if (((struct tlista *) l) -> iter != NULL)   return (1);
	else  return (0);
   }

Programa de prueba

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "lvoid.h"

//  ---------------------------------------------------------------------

int compar (const void *a, const void *b)   {
	return (* ((int *) a) < * ((int *) b) ? -1:
		* ((int *) a) > * ((int *) b) ? 1 : 0);
    }

// ----------------------------------------------------------------------

int main ()   {
	lista a = NULL, b = NULL;
	int i, d;

	clrscr ();
	a = l_nueva (sizeof (int));
	if (l_vacia (a))    printf ("\n\t La lista est  vac¡a.\n");
	else    {
		printf ("\n\t Error: La lista no se cre¢ bien.\n");
		return (1);
	   }

	printf ("\n\t Meto del 10 al 1 por la izquierda\n");
	for (i = 10; i > 0; i--)   {
		//printf ("   %d", i);
		l_meterizq (a, &amp;i);
	    }
	printf ("\n\t Meto del 11 al 20 por la derecha\n");
	for (i = 11; i < 21; i++)   {
		//printf ("   %d", i);
		l_meterder (a, &amp;i);
	   }

	printf ("\n\t Saco 5 elementos por la derecha\n");
	for (i = 0; i < 5; i++)   {
		l_sacarder (a, &amp;d);
		//printf ("   %d", d);
	   }
	printf ("\n\t Saco 5 elementos por la izquierda\n");
	for (i = 0; i < 5; i++)   {
		l_sacarizq (a, &amp;d);
		//printf ("   %d", d);
	    }

	printf ("\n Ahora tengo una lista ordenada con los n£meros del 6 al 15.");
	if (!l_vacia (a))    printf ("\n La lista no est  vac¡a.");
	else    {
		printf ("\n Error: Ni mete ni saca bien.");
		return (2);
	   }

	d = 10;
	l_sacarx (a, &amp;d, compar);
	printf ("\n Sacarx el elemento %d.", d);
	d = 6;
	l_sacarx (a, &amp;d, compar);
	printf ("\n Sacarx el elemento %d.", d);
	d = 15;
	l_sacarx (a, &amp;d, compar);
	printf ("\n Sacarx el elemento %d.", d);
	d = 10;
	l_meterx (a, &amp;d, compar);
	printf ("\n Meterx el elemento %d.", d);
	d = 6;
	l_meterx (a, &amp;d, compar);
	printf ("\n Meterx el elemento %d.", d);
	d = 15;
	l_meterx (a, &amp;d, compar);
	printf ("\n Meterx el elemento %d.", d);

	printf ("\n Ahora sigo teniendo una lista ordenada con los n£meros del 6 al 15:\n");
	i_inicializar (a);
	i = 6;
	while (i_quedan (a))    {
		i_dame (a, &amp;d);
		printf ("  %d", d);
		if (i != d)   {
			printf ("\t Error: Ten¡an que ser iguales.\n");
			return (3);
		   }
		i++;
	   }
	b = l_copiar (a);
	l_destruir (&amp;a);
	if (a != NULL) {
		printf ("Error: La destrucci¢n no es correcta.\n");
		return (4);
	    }
	i_inicializar (b);
	i = 6;
	while (i_quedan (b)) {
		i_dame (b, &amp;d);
		printf ("  %d", d);
		if (i != d)    {
			printf ("\t Error: La copia no es buena.\n");
			return (3);
		    }
		i++;
	   }
	for (i = 0; i < 20; i++) {
		d = i;
		if (l_buscar (b, &amp;d, compar))   {
			if (i < 6 || i > 15) printf ("Error: El %d est .\n", i);
		    }
		else if (i > 5 &amp;&amp; i < 16) printf ("Error: El %d no est .\n", i);
	    }
	l_destruir (&amp;b);
	printf ("\nNo he comprobado si queda la misma memoria que hab¡a al principio.\n");
	printf ("Fin de la ejecuci¢n: TODO BIEN.\n");
	return (0);
  }

Enlaces de interés

En mi blog encontrarás algunos artículos y tutoriales sobre programación de tipos de datos abstractos en C: árboles binarios avlárboles binarios, vector dinámico, bicola estática o ficheros dispersos.

Conclusión

Dejo la sección de comentarios abierto para que dejéis vuestra opinión, vuestras aportaciones o códigos alternativos para éste TAD.

No Comments

Post a Comment