Árboles binarios AVL

Árboles binarios AVL

Vamos a dedicar ésta publicación dedicar ésta publicación a los llamados árboles AVL.  Esta estructura de datos toma el nombre de sus inventores: Georgii Adelson-Velskii y Yevgenly Landys. Se trata de árboles binarios que estén siempre equilibrados, de tal modo que la altura de su rama izquierda tenga la misma altura que la de su rama derecha.

Gracias a éste equilibrio o balanceo, la complejidad de una búsqueda en uno de éstos árboles siempre se mantiene en orden de complejidad igual a O (log n).

Para conseguir éste equilibrio tanto la inserción como el borrado de nodos ha de hacerse  de una manera distinta a como lo hicimos con los árboles binarios de búsqueda (ABB). Cuando se rompe el equilibrio en el árbol al insertar o borrar un elemento, siempre se ha de hacer una operación de rotaciones de nodos para volver al punto de equilibrio.

Pero vamos a dejarnos de introducciones y comencemos a examinar el código fuente. Como siempre comenzamos con la declaración de las cabeceras de las funciones en el fichero .h.

#ifndef AVL_CHAR_TYPO

#define AVL_CHAR_TYPO

struct avl_char_typo   {
	char cadena [20];
	struct ardi_int_rep *punt_arr;
    };

typedef struct avl_char_ele *avl_char;

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

avl_char avl_char_nuev (void);
int avl_char_vacio (avl_char a);
void avl_char_raiz (avl_char a, struct avl_char_typo *e);
void avl_char_mete (avl_char *a, struct avl_char_typo e,
		int (*cmp_char) (const void *, const void *));
void avl_char_saca (avl_char *a, struct avl_char_typo *e,
		int (*cmp_char) (const void *, const void *));
void avl_char_dest (avl_char *a);
void avl_char_copy (avl_char a, avl_char *d);
avl_char avl_char_find (avl_char a, struct avl_char_typo *e,
		int (*cmp_char) (const void *, const void *));
void avl_char_printf (avl_char a, int posicion);
void avl_char_glosario (FILE *fp, avl_char a);

#endif

En éste código veremos que además del constructor y destructor de la estructura de datos, también implementaremos las funciones y procedimientos básicos que podemos encontrar en cualquier estructura de datos: insertar, sacar copiar, buscar e imprimir.

Vamos a ver ahora la implementación de cada una de las funciones y procedimientos en el fichero .c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include "avl.h"
#include "arrdina.h"

struct avl_char_ele    {
	struct avl_char_typo val;
	struct avl_char_ele *izq, *der;
	char altura;
    };

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

void avl_char_error (char primit [20], int error)    {
	switch (error)    {
		case 1:	fprintf (stderr, "\n\t %s: No hay suficiente memoria.\n", primit);
			break;
		case 2: fprintf (stderr, "\n\t %s: El arbol binario esta vacio.\n", primit);
			break;
	  }
   }

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

void avl_char_swap (struct avl_char_typo *a, struct avl_char_typo *b)    {
	struct avl_char_typo tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
   }

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

int avl_char_max (int a, int b)    {

	return (a > b ? a : b);
   }

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

int avl_char_altura (avl_char a)   {

	return (a == NULL ? -1 : a -> altura);
   }

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

void avl_char_zig (avl_char *a)    {   // Rotacion simple a derechas
	avl_char b = (*a) -> izq;

	(*a) -> izq = b -> der;
	b -> der = *a;
	(*a) -> altura = avl_char_max (avl_char_altura ((*a) -> izq), avl_char_altura ((*a) -> der)) + 1;
	b -> altura = avl_char_max (avl_char_altura (b -> izq), (*a) -> altura) + 1;
	*a = b;
   }

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

void avl_char_zag (avl_char *a)    {   // Rotacion simple a izquierdas
	avl_char b = (*a) -> der;

	(*a) -> der = b -> izq;
	b -> izq = *a;
	(*a) -> altura = avl_char_max (avl_char_altura ((*a) -> der), avl_char_altura ((*a) -> izq)) + 1;
	b -> altura = avl_char_max (avl_char_altura (b -> der), (*a) -> altura) + 1;
	*a = b;
    }

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

void avl_char_zagzig (avl_char *a)   {   // Rotacion doble a derechas

	avl_char_zag (&amp;(*a) -> izq);
	avl_char_zig (a);
    }

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

void avl_char_zigzag (avl_char *a)   {  //Rotacion doble a izquierdas
	avl_char_zig (&amp;(*a) -> der);
	avl_char_zag (a);
    }

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

avl_char avl_char_nuev ()   {

	return (NULL);
   }

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

int avl_char_vacio (avl_char a)   {

	return (a == NULL);
    }

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

void avl_char_raiz (avl_char a, struct avl_char_typo *e)   {

	if (!a)    {
		avl_char_error ("avl_char_raiz", 2);
		exit (1);
	   }

	*e = a -> val;
    }

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

void avl_char_mete (avl_char *a, struct avl_char_typo e,
		int (*cmp_char) (const void *, const void *))   {

	if (!*a)   {
		*a = (struct avl_char_ele *) malloc (sizeof (struct avl_char_ele));
		if (!*a)    {
			avl_char_error ("avl_char_mete", 1);
			exit (1);
		    }
		(*a) -> izq = (*a) -> der = NULL;
		(*a) -> val = e;
		(*a) -> altura = 0;
	  }
	else   {
	    if (cmp_char (&amp;e, &amp;(*a) -> val) < 0)    {
		 avl_char_mete (&amp;(*a) -> izq, e, cmp_char);
		 if ((avl_char_altura ((*a) -> izq) - avl_char_altura ((*a) -> der)) == 2)
		    if (cmp_char (&amp;e, &amp;(*a) -> izq -> val) < 0)
			avl_char_zig (a);
		    else   avl_char_zagzig (a);
		 else (*a) -> altura = avl_char_max (avl_char_altura ((*a) -> izq), avl_char_altura ((*a) -> der)) + 1;
	      }

	    else if (cmp_char (&amp;e, &amp;(*a) -> val) > 0)   {
		 avl_char_mete (&amp;(*a) -> der, e, cmp_char);
		 if ((avl_char_altura ((*a) -> izq) - avl_char_altura ((*a) -> der)) == -2)
		    if (cmp_char (&amp;e, &amp;(*a) -> der -> val) > 0)
			avl_char_zag (a);
		    else   avl_char_zigzag (a);
		 else (*a) -> altura = avl_char_max (avl_char_altura ((*a) -> izq), avl_char_altura ((*a) -> der)) + 1;
	      }

	    else;   // Entrada Duplicada
	 }
    }

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

void avl_char_saca (avl_char *a, struct avl_char_typo *e,
		int (*cmp_char) (const void *, const void *))   {
	avl_char viejo;

	if (!*a)    {
		avl_char_error ("avl_char_saca", 2);
		exit (1);
	    }
	else  {
	    if (cmp_char (e, &amp;(*a) -> val) < 0)    {
		 avl_char_saca (&amp;(*a) -> izq, e, cmp_char);
		 if ((avl_char_altura ((*a) -> izq) - avl_char_altura ((*a) -> der)) == -2)
		    if ((avl_char_altura ((*a) -> der -> izq) - avl_char_altura ((*a) -> der -> der)) == 1)
			avl_char_zigzag (a);
		    else   avl_char_zag (a);
		 else (*a) -> altura = avl_char_max (avl_char_altura ((*a) -> izq), avl_char_altura ((*a) -> der)) + 1;
	      }

	    else if (cmp_char (e, &amp;(*a) -> val) > 0)   {
		 avl_char_saca (&amp;(*a) -> der, e, cmp_char);
		 if ((avl_char_altura ((*a) -> izq) - avl_char_altura ((*a) -> der)) == 2)
		    if ((avl_char_altura ((*a) -> izq -> izq) - avl_char_altura ((*a) -> izq -> der)) == -1)
			avl_char_zagzig (a);
		    else   avl_char_zig (a);
		 else (*a) -> altura = avl_char_max (avl_char_altura ((*a) -> izq), avl_char_altura ((*a) -> der)) + 1;
	      }

	    else   {
		if (!(*a) -> izq)    {
			viejo = *a;
			(*a) = (*a) -> der;
                        ardi_int_dest (&amp;viejo -> val.punt_arr);
			free (viejo);
		   }
		else if (!(*a) -> der)    {
			viejo = *a;
			(*a) = (*a) -> izq;
                        ardi_int_dest (&amp;viejo -> val.punt_arr);
			free (viejo);
		   }
		else   {
			viejo = (*a) -> izq;
			while (viejo -> der)	viejo = viejo -> der;
			avl_char_swap (&amp;viejo -> val, &amp;(*a) -> val);
			avl_char_saca (&amp;(*a) -> izq, e, cmp_char);
			if ((avl_char_altura ((*a) -> izq) - avl_char_altura ((*a) -> der)) == -2)
			    if ((avl_char_altura ((*a) -> der -> izq) - avl_char_altura ((*a) -> der -> der)) == 1)
				avl_char_zigzag (a);
			    else   avl_char_zag (a);
			else (*a) -> altura = avl_char_max (avl_char_altura ((*a) -> izq), avl_char_altura ((*a) -> der)) + 1;
		   }
	      }
	 }
    }

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

void avl_char_dest (avl_char *a)   {

	if (*a)   {
	      avl_char_dest (&amp;(*a) -> izq);
	      avl_char_dest (&amp;(*a) -> der);
	      ardi_int_dest (&amp;(*a) -> val.punt_arr);
	      free (*a);
	      *a = NULL;
	 }
    }

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

void avl_char_copy (avl_char a, avl_char *d)    {
	int prim = 0, count;

	if (a)   {
		*d = (struct avl_char_ele *) malloc (sizeof (struct avl_char_ele));
		if (!*d)    {
			avl_char_error ("avl_char_copy", 1);
			exit (1);
		    }
		strcpy ((*d) -> val.cadena, a -> val.cadena);
		(*d) -> altura = a -> altura;
		count = ardi_int_tamlog (a -> val.punt_arr);
		(*d) -> val.punt_arr = ardi_int_copy (a -> val.punt_arr, prim, count);

		avl_char_copy (a -> der, &amp;(*d) -> der);
		avl_char_copy (a -> izq, &amp;(*d) -> izq);
	    }
	 else *d = NULL;
    }

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

avl_char avl_char_find (avl_char a, struct avl_char_typo *e,
		int (*cmp_char) (const void *, const void *))    {

	if (!a) return (NULL);
	if (cmp_char (&amp;a -> val, e) > 0)
	      return (avl_char_find (a -> izq, e, cmp_char));
	else if (cmp_char (&amp;a -> val, e) < 0)
	      return (avl_char_find (a -> der, e, cmp_char));
	else    {
		*e = a -> val;
		return (a);
	 }
   }

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

void avl_char_printf (avl_char a, int posicion)     {

	if (a) {
		avl_char_printf (a -> der, posicion + 6);
		printf ("%*s %d \n", posicion, a -> val.cadena, a -> altura);
		avl_char_printf (a -> izq, posicion + 6);
	   }
    }

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

void avl_char_glosario (FILE *fp, avl_char a)   {
	struct ardi_int_typo e, d;
	int tam, i;

	if (a)    {
	      avl_char_glosario (fp, a -> izq);
              tam = ardi_int_tamlog (a -> val.punt_arr);
              fprintf (fp, "%s", a -> val.cadena);
              fprintf (fp, "%c", ':');
              d.x = 0;
	      for (i = 0; i < tam; i++)   {
		     ardi_int_obti (a -> val.punt_arr, i, &amp;e);
                     if (d.x != e.x)    {
                          fprintf (fp, "%c", ' ');
		          fprintf (fp, "%d", e.x);
                          fprintf (fp, "%c", ',');
                       }
                     d.x = e.x;
		 }
	      fprintf (fp, "%c", '\n');
	      avl_char_glosario (fp, a -> der);
	  }
   }

Para terminar ésta estructura siempre se suele incluir un programita que verifica que cada una de las funciones y procedimientos del blog funcionan correctamente. Podría tener el siguiente aspecto:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include "avl.h"
#include "arrdina.h"

#define PAGINA 60

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

int cmp_int (const void *a, const void *b)   {
	return (*((int *) a) - *((int *) b));
    }

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

int cmp_char (const void *a, const void *b)   {
	return (strcmp ((char *) a, (char *) b));
   }

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

void blancos (char cadena [25])    {
	int i;
	for (i = 0; i < strlen (cadena); i++)   cadena [i] = ' ';
   }

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

int delimitador (char c)    {
        return ((strchr ("+-*/=%|!­¨?()[]{}#&amp;$.,:;<>§¦", c)) ? 1 : 0);
   }

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

void fichero_arbol (char *argv [], avl_char *a)    {
    FILE *fp;
    char palabra [25];
    avl_char basura;
    struct avl_char_typo arbol;
    struct ardi_int_typo array;
    int linea = 1, pagina = 1, i = 0, aparicion;
    char c;

    if ((fp = fopen (argv [1], "rt")) == NULL)   {
	 fprintf (stderr, "Fichero_arbol: El fichero %s no existe.\n", argv [1]);
	 exit (1);
      }

    printf ("\n\n\n\t N£mero m ximo de apariciones permitidas para los t‚rminos: ");
    scanf ("%d", &amp;aparicion);

    basura = avl_char_nuev ();

    while ((c = fgetc (fp)) != EOF)    {
         if ((!delimitador (c)) &amp;&amp; (!isdigit (c)) &amp;&amp; (c != ' ') &amp;&amp;
             (c != '\n') &amp;&amp; (c != '"') &amp;&amp; (c != '\0'))   {
	        palabra [i] = c;
	        i++;
	    }
	 else     {
	      palabra [i] = '\0';
	      i = 0;
	      if (palabra [i] != '\0')    {
		   arbol.punt_arr = NULL;
		   strcpy (arbol.cadena, palabra);
		   array.x = pagina;

		   if (avl_char_find (basura, &amp;arbol, cmp_char) == NULL)   {
		       if (avl_char_find (*a, &amp;arbol, cmp_char) == NULL)   {
			    arbol.punt_arr = ardi_int_const (1, array);
			    avl_char_mete (a, arbol, cmp_char);
			 }
		       else  {
			    if (ardi_int_tamlog (arbol.punt_arr) < aparicion)
				  ardi_int_aumd (arbol.punt_arr, array);
			    else    {
				  avl_char_saca (a, &amp;arbol, cmp_char);
				  arbol.punt_arr = ardi_int_nuev ();
				  avl_char_mete (&amp;basura, arbol, cmp_char);
			      }
			 }
		     }
		   blancos (palabra);
		}
	   }

	 if (c == '\n')   linea++;
	 if (linea > PAGINA)    {
		linea = 1;
		pagina++;
	   }
      }

    fclose (fp);

    avl_char_dest (&amp;basura);
  }

// ------------------------------------------------------------------------
//			    PROGRAMA PRINCIPAL
// ------------------------------------------------------------------------

int main (int argc, char *argv [])   {
      FILE *fp;
      avl_char arbol;
      int pos = 0;

      if (argc != 3)    {
             fprintf (stderr, "\tError: N£mero de par metros incorrecto.\n");
             fprintf (stderr, "\tUso: programa <fichero entrada> <fichero glosario>\n");
             exit (1);
         }

      printf ("\n\n\t\t 'GENERACIàN DE UN GLOSARIO DE TRMINOS'\n\n");
      printf ("\n\t Espere un momento......");

      arbol = avl_char_nuev ();
      fichero_arbol (argv, &amp;arbol);

      clrscr ();
      avl_char_printf (arbol, pos);

      if ((fp = fopen (argv [2], "wt")) != NULL)
		avl_char_glosario (fp, arbol);
      else fprintf (stderr, "Ha ocurrido un error al abrir el fichero %s.\n", argv [2]);
      fclose (fp);

      avl_char_dest (&amp;arbol);
      return;
  }

Para terminar, os voy a dejar el código de la estructura de datos auxiliar -array dinámico- que utilizo para implementar el TDA árbol binario AVL. Veamos el fichero .h:

#ifndef ARDI_INT_TYPO

#define ARDI_INT_TYPO

struct ardi_int_typo  {
	int x;
   };

typedef struct ardi_int_rep *ardi_int;

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

ardi_int ardi_int_nuev (void);
ardi_int ardi_int_const (int tamano, struct ardi_int_typo valorinicial);
ardi_int ardi_int_copy (ardi_int a, int prim, int count);
int ardi_int_tamfis (ardi_int a);
int ardi_int_tamlog (ardi_int a);
int ardi_int_infe (ardi_int a);
int ardi_int_supe (ardi_int a);
void ardi_int_obti (ardi_int a, int i, struct ardi_int_typo *e);
void ardi_int_asig (ardi_int a, int i, struct ardi_int_typo e);
void ardi_int_aumd (ardi_int a, struct ardi_int_typo e);
void ardi_int_disd (ardi_int a, struct ardi_int_typo *e);
void ardi_int_dest (ardi_int *a);
void ardi_int_swap (ardi_int a, int l, int r);
int ardi_int_bbin (ardi_int a, struct ardi_int_typo e,
	int (*cmp_int) (const void *, const void *));
int ardi_int_bsecd (ardi_int a, struct ardi_int_typo e,
	int (*cmp_int) (const void *, const void *));
int ardi_int_bseci (ardi_int a, struct ardi_int_typo e,
	int (*cmp_int) (const void *, const void *));
void ardi_int_qsort (ardi_int a, int (*cmp_int) (const void *, const void *));

#endif

Y a continuación el fichero .c en el que se implementan todas y cada una de las funciones y procedimientos:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "arrdina.h"

struct ardi_int_rep   {
	int tamfis;
	int tamlog;
	struct ardi_int_typo *arr;
   };

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

void ardi_int_error (int error, char prim [20])     {

	switch (error)    {
		case 1: fprintf (stderr, "\n\t%s: Error, no hay memoria suficiente.\n", prim);
			break;
		case 2: fprintf (stderr, "\n\t%s: Error, el array no existe.\n", prim);
			break;
		case 3:	fprintf (stderr, "\n\t%s: Error, el array esta vacio.\n", prim);
			break;
		case 4:	fprintf (stderr, "\n\t%s: Error, tama¤o < 1.\n", prim);
			break;
		case 5:	fprintf (stderr, "\n\t%s: Error, prim < 0.\n", prim);
			break;
		case 6:	fprintf (stderr, "\n\t%s: Error, count > elementos del array.\n", prim);
			break;
		case 7:	fprintf (stderr, "\n\t%s: Error, fuera de rango del array.\n", prim);
			break;
	  }
    }

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

struct ardi_int_typo *ardi_int_aloarr (int tamano)   {
	struct ardi_int_typo *arr;

	if (tamano == 0) return (NULL);
	else   {
		arr = (struct ardi_int_typo *) malloc (sizeof (struct ardi_int_typo) * tamano);
		if (arr == NULL)   {
		     ardi_int_error (1, "ardi_int_aloarr");
		     exit (1);
		   }
		return (arr);
	  }
   }

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

ardi_int ardi_int_alo (int tamano)    {
	ardi_int p;

	p = (ardi_int) malloc (sizeof (struct ardi_int_rep));
	if (p == NULL)   {
	     ardi_int_error (1, "ardi_int_alo");
	     exit (1);
	   }

	p -> arr = ardi_int_aloarr (tamano);
	p -> tamfis = tamano;
	p -> tamlog = 0;
	return (p);
   }

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

void ardi_int_daloarr (struct ardi_int_typo *arr)   {

	if (arr)   free (arr);
   }

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

void ardi_int_dalo (ardi_int *p)    {

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

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

ardi_int ardi_int_nuev ()  {
	ardi_int x;

	x = ardi_int_alo (0);
	return (x);
  }

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

ardi_int ardi_int_const (int tamano, struct ardi_int_typo valorinicial)   {
	ardi_int x;
	int i = 0, tamfis;

	if (tamano < 1)   {
		ardi_int_error (4, "ardi_int_const");
		exit (1);
	    }

	tamfis = (int) pow (2, ceil (log (tamano) / log (2)));
	x = ardi_int_alo (tamfis);
	while (i < tamano)     *(x -> arr+i++) = valorinicial;
	x -> tamlog = tamano;

	return (x);
  }

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

ardi_int ardi_int_copy (ardi_int a, int prim, int count)  {
	ardi_int x;
	int tamfis;

	if (!a)   {
		ardi_int_error (2, "ardi_int_copy");
		exit (1);
	   }
	if ((prim < 0) || (prim > a -> tamlog - 1))   {
		ardi_int_error (5, "ardi_int_copy");
		exit (1);
	   }
	if (count + prim - 1 > a -> tamlog - 1)   {
		ardi_int_error (6, "ardi_int_copy");
		exit (1);
	   }

	tamfis = (int) pow (2, ceil (log (count) / log (2)));
	x = ardi_int_alo (tamfis);
	memcpy (x -> arr, a -> arr + prim, count * sizeof (struct ardi_int_typo));
	x -> tamlog = count;

	return (x);
  }

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

int ardi_int_tamfis (ardi_int a)  {

	if (!a)   {
		ardi_int_error (2, "ardi_int_tamfis");
		exit (1);
	   }
	return (a -> tamfis);
   }

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

int ardi_int_tamlog (ardi_int a)  {

	if (!a)   {
		ardi_int_error (2, "ardi_int_tamlog");
		exit (1);
	   }
	return (a -> tamlog);
   }

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

int ardi_int_infe (ardi_int a)   {

	if (!a)   {
		ardi_int_error (2, "ardi_int_infe");
		exit (1);
	   }
	return (0);
   }

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

int ardi_int_supe (ardi_int a)   {

	if (!a)   {
		ardi_int_error (2, "ardi_int_supe");
		exit (1);
	   }
	return (a -> tamlog - 1);
   }

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

void ardi_int_obti (ardi_int a, int i, struct ardi_int_typo *e)     {

	if (!a)   {
		ardi_int_error (2, "ardi_int_obti");
		exit (1);
	   }
	if ((i < 0) || (i > a -> tamlog - 1))   {
		ardi_int_error (7, "ardi_int_obti");
		exit (1);
	   }

	*e = a -> arr [i];
  }

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

void ardi_int_asig (ardi_int a, int i, struct ardi_int_typo e)    {

	if (!a)   {
		ardi_int_error (2, "ardi_int_asig");
		exit (1);
	   }
	if (i < 0 || i > a -> tamlog - 1)   {
		ardi_int_error (7, "ardi_int_asig");
		exit (1);
	   }

	a -> arr [i] = e;
   }

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

void ardi_int_aumd (ardi_int a, struct ardi_int_typo e)   {
	struct ardi_int_typo *b;

	if (!a)   {
		ardi_int_error (2, "ardi_int_aumd");
		exit (1);
	   }

	if (!a -> tamlog)    *(a -> arr) = e;
	else if ((a -> tamlog) < (a -> tamfis))    a -> arr [a -> tamlog] = e;
	else   {
		b = ardi_int_aloarr (a -> tamfis * 2);
		memcpy (b, a -> arr, a -> tamfis * sizeof (struct ardi_int_typo));
		b [a -> tamlog] = e;
		ardi_int_daloarr (a -> arr);
		a -> arr = b;
		a -> tamfis *= 2;
	  }
	a -> tamlog++;
   }

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

void ardi_int_disd (ardi_int a, struct ardi_int_typo *e)   {
	struct ardi_int_typo *b;

	if (!a)   {
		ardi_int_error (2, "ardi_int_disd");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_disd");
		exit (1);
	   }

	*e = a -> arr [a -> tamlog - 1];
	a -> tamlog--;

	if (a -> tamlog < (a -> tamfis / 2))   {
		b = ardi_int_aloarr (a -> tamfis / 2);
		memcpy (b, a -> arr, (a -> tamfis / 2) * sizeof (struct ardi_int_typo));
		ardi_int_daloarr (a -> arr);
		a -> arr = b;
		a -> tamfis /= 2;
	   }
   }

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

void ardi_int_dest (ardi_int *a)   {

	if (!*a)   {
		ardi_int_error (2, "ardi_int_dest");
		exit (1);
	   }
	ardi_int_dalo (a);
   }

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

void ardi_int_swap (ardi_int a, int l, int r)   {
	struct ardi_int_typo aux;

	if (!a)   {
		ardi_int_error (2, "ardi_int_swap");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_swap");
		exit (1);
	   }
	if (l < 0 || l > a -> tamlog - 1 || r < 0 || r > a -> tamlog - 1)   {
		ardi_int_error (7, "ardi_int_swap");
		exit (1);
	   }
	aux = a -> arr [l];
	a -> arr [l] = a -> arr [r];
	a -> arr [r] = aux;
   }

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

int ardi_int_bbin (ardi_int a, struct ardi_int_typo e,
			int (*cmp_int) (const void *, const void *))   {
	struct ardi_int_typo *t;

	if (!a)   {
		ardi_int_error (2, "ardi_int_bbin");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_bbin");
		exit (1);
	   }

	t = (struct ardi_int_typo *) bsearch (&amp;e, a -> arr, a -> tamlog,
		sizeof (struct ardi_int_typo), cmp_int);

	if (!t)   return (-1);
	else   return (t - a -> arr);
   }

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

int ardi_int_bsecd (ardi_int a, struct ardi_int_typo e,
			int (*cmp_int) (const void *, const void *))   {
	int i;

	if (!a)   {
		ardi_int_error (2, "ardi_int_bsecd");
		exit (1);
	   }

	if (a -> tamlog)
		for (i = a -> tamlog - 1; i >= 0; i--)
		      if (!cmp_int (&amp;(a -> arr [i]), &amp;e))    return (i);
	return (-1);
   }

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

int ardi_int_bseci (ardi_int a, struct ardi_int_typo e,
			int (*cmp_int) (const void *, const void *))    {
	int i;

	if (!a)   {
		ardi_int_error (2, "ardi_int_bseci");
		exit (1);
	   }

	if (a -> tamlog)
		for (i = 0; i <= a -> tamlog - 1; i++)
		      if (!cmp_int (&amp;(a -> arr [i]), &amp;e))    return (i);
	return (-1);
   }

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

void ardi_int_qsort (ardi_int a, int (*cmp_int) (const void *, const void *))   {

	if (!a)   {
		ardi_int_error (2, "ardi_int_qsort");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_qsort");
		exit (1);
	   }

	qsort (a -> arr, a -> tamlog, sizeof (struct ardi_int_typo), cmp_int);
  }

Como siempre, dejo la sección de comentarios abierta para que me dejéis vuestras impresiones, opiniones o códigos alternativos que se podría usar en este tipo de datos abstracto.

No Comments

Post a Comment