TDA Vector dinámico

TDA Vector dinámico

Otro artículo más en el que voy recuperando aquellas prácticas de programación en C que realicé en mis tiempos universitarios. En ésta ocasión llega el turno de la implementación de un vector dinámico.

Os dejo en mi repositorio personal el enlace de ésta estructura de datos para quien quiera descargarsela.

Primitivas del tipo de dato abstrato

ardi_[tip] ardi_[tip]_nuev (void);

Precondición: Haya memoria para el nuevo objeto.
Postcondición: Devuelve un nuevo vector dinámico, que no contiene ningún elemento, pero con capacidad para albergar un elemento.

ardi_[tip] ardi_[tip]_const (int tamano, struct ardi_[tip]_typo valorinicial);

Precondición: Haya memoria para el nuevo objeto. Tamano tiene que ser mayor que 0.
Postcondición: Devuelve un nuevo vector dinámico, de tamaño lógico igual a tamano y con todos los elementos inicializados con valorinicial.

ardi_[tip] ardi_[tip]_copy (ardi_[tip] a, int prim, int count);

Precondición: a debe existir. Haya memoria para el nuevo objeto. El intervalo de índices de los elementos a copiar debe estar incluido en el vector a.
Postcondición: Devuelve un nuevo vector dinámico, que es copia del vector a desde el elemento prim al prim + count – 1.

int ardi_[tip]_tamfis (ardi_[tip] a);

Precondición: a debe existir.
Postcondición: Devuelve el tamaño físico del vector a.

int ardi_[tip]_tamlog (ardi_[tip] a);

Precondición: a debe existir.
Postcondición: Devuelve el tamaño lógico del vector a.

int ardi_[tip]_infe (ardi_[tip] a);

Precondición: a debe existir.
Postcondición: Devuelve el menor índice del vector a.

int ardi_[tip]_supe (ardi_[tip] a);

Precondición: a debe existir.
Postcondición: Devuelve el mayor índice del vector a.

void ardi_[tip]_obti (ardi_[tip] a, int i, struct ardi_[tip]_typo *e);

Precondición: a debe existir. i debe estar dentro del rango de elementos del vector.
Modifica: *e.
Postcondición: Devuelve en *e el elemento de la posición i del vector a.

void ardi_[tip]_asig (ardi_[tip] a, int i, struct ardi_[tip]_typo e);

Precondición: a debe existir. i debe estar dentro del rango de elementos del vector.
Postcondición: Actualiza el elemento de la posición i del vector a con el valor e.

void ardi_[tip]_aumd (ardi_[tip] a, struct ardi_[tip]_typo e);

Precondición: a debe existir. Haya suficiente memoria.
Postcondición: Asigna el valor e por la derecha del vector a. Si el vector a está lleno, aumenta su tamaño físico al doble de su tamaño actual.

void ardi_[tip]_disd (ardi_[tip] a, struct ardi_[tip]_typo *e);

Precondición: a debe existir y su tamaño no puede ser 0. Haya suficiente memoria.
Modifica: *e
Postcondición: Devuelve en *e el elemento ardi_[tip]_supe del vector a. Si el número de elementos contenidos en el vector a es menor que la mitad del tamaño del vector, disminuye su tamaño físico a la mitad de su tamaño actual.

void ardi_[tip]_dest (ardi_[tip] *a);

Precondición: *a debe estar creado.
Modifica: *a.
Postcondición: Libera la memoria asignada al vector *a. A la salida *a == NULL.

void ardi_[tip]_swap (ardi_[tip] a, int l, int r);

Precondición: a debe existir, su tamaño no puede ser 0 y ardi_[tip]_infe <= l = r <= ardi_[tip]_supe.
Postcondición: Intercambia los elementos de las posiciones l y r del vector.

int ardi_[tip]_bbin (ardi_[tip] a, struct ardi_[tip]_typo e, int (*cmp_[tip]) (const void *, const void *));

Precondición: a debe existir y su tamaño debe ser mayor de 0.
Postcondición: Búsqueda dicotómica. Devuelve la posición lógica de e en el vector. Si no existe tal elemento devuelve -1.

int ardi_[tip]_bsecd (ardi_[tip] a, struct ardi_[tip]_typo e, int (*cmp_[tip]) (const void *, const void *));

Precondición: a debe existir.
Postcondición: Búsqueda secuencial por la derecha. Devuelve la posición lógica de e en el vector. Si no existe tal elemento devuelve -1.

int ardi_[tip]_bseci (ardi_[tip] a, struct ardi_[tip]_typo e, int (*cmp_[tip]) (const void *, const void *));

Precondición: a debe existir.
Postcondición: Búsqueda secuencial por la izquierda. Devuelve la posición lógica de e en el vector. Si no existe tal elemento devuelve -1.

void ardi_[tip]_qsort (ardi_[tip] a, int (*cmp_[tip]) (const void *, const void *));

Precondición: a debe existir y su tamaño debe ser mayor que 0.
Postcondición: Ordena el vector dinámico.

A continuación pasaremos a mostrar el fichero .h en el que se declaran las cabeceras de las funciones y procedimientos que darán la funcionalidad al tipo de dato abstracto.

#ifndef ARDI_CHAR_TYPO

#define ARDI_CHAR_TYPO

struct ardi_char_typo  {
	char x;
   };

typedef struct ardi_char_rep *ardi_char;

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

ardi_char ardi_char_nuev (void);

ardi_char ardi_char_const (int tamano, struct ardi_char_typo valorinicial);

ardi_char ardi_char_copy (ardi_char a, int prim, int count);

int ardi_char_tamfis (ardi_char a);

int ardi_char_tamlog (ardi_char a);

int ardi_char_infe (ardi_char a);

int ardi_char_supe (ardi_char a);

void ardi_char_obti (ardi_char a, int i, struct ardi_char_typo *e);

void ardi_char_asig (ardi_char a, int i, struct ardi_char_typo e);

void ardi_char_aumd (ardi_char a, struct ardi_char_typo e);

void ardi_char_disd (ardi_char a, struct ardi_char_typo *e);

void ardi_char_dest (ardi_char *a);

void ardi_char_swap (ardi_char a, int l, int r);

int ardi_char_bbin (ardi_char a, struct ardi_char_typo e,
	int (*cmp_char) (const void *, const void *));

int ardi_char_bsecd (ardi_char a, struct ardi_char_typo e,
	int (*cmp_char) (const void *, const void *));

int ardi_char_bseci (ardi_char a, struct ardi_char_typo e,
	int (*cmp_char) (const void *, const void *));

void ardi_char_qsort (ardi_char a, int (*cmp_char) (const void *, const void *));

#endif

El fichero .c contiene las implementaciones de todas las funciones y procedimientos de éste sencillo tipo de datos abastracto vector dinámico:

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

struct ardi_char_rep   {
	int tamfis;
	int tamlog;
	struct ardi_char_typo *arr;
   };

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

void ardi_char_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_char_typo *ardi_char_aloarr (int tamano)   {
	struct ardi_char_typo *arr;

	if (tamano == 0) return (NULL);
	else   {
		arr = (struct ardi_char_typo *) malloc (sizeof (struct ardi_char_typo) * tamano);
		if (arr == NULL)   {
		     ardi_char_error (1, "ardi_char_aloarr");
		     exit (1);
		   }
		return (arr);
	  }
   }

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

ardi_char ardi_char_alo (int tamano)    {
	ardi_char p;

	p = (ardi_char) malloc (sizeof (struct ardi_char_rep));
	if (p == NULL)   {
	     ardi_char_error (1, "ardi_char_alo");
	     exit (1);
	   }

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

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

void ardi_char_daloarr (struct ardi_char_typo *arr)   {

	if (arr)   free (arr);
   }

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

void ardi_char_dalo (ardi_char *p)    {

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

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

ardi_char ardi_char_nuev ()  {
	ardi_char x;

	x = ardi_char_alo (1);
	return (x);
  }

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

ardi_char ardi_char_const (int tamano, struct ardi_char_typo valorinicial)   {
	ardi_char x;
	int i = 0, tamfis;

	if (tamano < 1)   {
		ardi_char_error (4, "ardi_char_const");
		exit (1);
	    }

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

	return (x);
  }

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

ardi_char ardi_char_copy (ardi_char a, int prim, int count)  {
	ardi_char x;
	int tamfis;

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

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

	return (x);
  }

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

int ardi_char_tamfis (ardi_char a)  {

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

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

int ardi_char_tamlog (ardi_char a)  {

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

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

int ardi_char_infe (ardi_char a)   {

	if (!a)   {
		ardi_char_error (2, "ardi_char_infe");
		exit (1);
	   }
	return (0);
   }

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

int ardi_char_supe (ardi_char a)   {

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

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

void ardi_char_obti (ardi_char a, int i, struct ardi_char_typo *e)     {

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

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

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

void ardi_char_asig (ardi_char a, int i, struct ardi_char_typo e)    {

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

	a -> arr [i] = e;
   }

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

void ardi_char_aumd (ardi_char a, struct ardi_char_typo e)   {
	struct ardi_char_typo *b;

	if (!a)   {
		ardi_char_error (2, "ardi_char_aumd");
		exit (1);
	   }

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

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

void ardi_char_disd (ardi_char a, struct ardi_char_typo *e)   {
	struct ardi_char_typo *b;

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

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

	if (a -> tamlog < (a -> tamfis / 2))   {
		b = ardi_char_aloarr (a -> tamfis / 2);
		memcpy (b, a -> arr, (a -> tamfis / 2) * sizeof (struct ardi_char_typo));
		ardi_char_daloarr (a -> arr);
		a -> arr = b;
		a -> tamfis /= 2;
	   }
   }

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

void ardi_char_dest (ardi_char *a)   {

	if (!*a)   {
		ardi_char_error (2, "ardi_char_dest");
		exit (1);
	   }
	ardi_char_dalo (a);
   }

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

void ardi_char_swap (ardi_char a, int l, int r)   {
	struct ardi_char_typo aux;

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

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

int ardi_char_bbin (ardi_char a, struct ardi_char_typo e,
			int (*cmp_char) (const void *, const void *))   {
	struct ardi_char_typo *t;

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

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

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

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

int ardi_char_bsecd (ardi_char a, struct ardi_char_typo e,
			int (*cmp_char) (const void *, const void *))   {
	int i;

	if (!a)   {
		ardi_char_error (2, "ardi_char_bsecd");
		exit (1);
	   }

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

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

int ardi_char_bseci (ardi_char a, struct ardi_char_typo e,
			int (*cmp_char) (const void *, const void *))    {
	int i;

	if (!a)   {
		ardi_char_error (2, "ardi_char_bseci");
		exit (1);
	   }

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

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

void ardi_char_qsort (ardi_char a, int (*cmp_char) (const void *, const void *))   {

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

	qsort (a -> arr, a -> tamlog, sizeof (struct ardi_char_typo), cmp_char);
  }

Por último, os dejo un programita de prueba en el que se comprueba que todas las funciones y procedimientos funcionan de verdad.

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

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

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

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

void mostrar_linea (ardi_char array)     {
	struct ardi_char_typo e;
	int i = 0;

	while (i < ardi_char_tamlog (array))     {
	       ardi_char_obti (array, i, &amp;e);
	       i++;
	       printf ("%c", e.x);
	   }
   }

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

void buscar_palabra (ardi_char array, char *argv [], int linea)     {
	struct ardi_char_typo e;
	int num = 0, i = 0, j = 0;
	char cadena [20], fin;

	while (i < ardi_char_tamlog (array))     {
	       ardi_char_obti (array, i, &amp;e);
	       i++;
	       if ((e.x != ' ') &amp;&amp; (e.x != '\n') &amp;&amp; (e.x != '.') &amp;&amp;
		   (e.x != ',') &amp;&amp; (e.x != ':') &amp;&amp; (e.x != ';'))    {
		      cadena [j] = e.x;
		      j++;
		  }
	       else   {
		      cadena [j] = '\0';
		      j = 0;
		      if (cmp_char (cadena, argv [2]) == 0)   num++;
		 }
	  }
	if (num)    {
		printf ("\t La palabra '%s' aparece %d veces en la linea %d, igual a:\n", argv [2], num, linea);
		mostrar_linea (array);
		printf ("\nPulse una tecla para continuar: ");
		fin = getch ();
		clrscr ();
	   }
   }

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

void fichero_array (char *argv [])   {
	FILE *fp;
	ardi_char array;
	struct ardi_char_typo e;
	int linea = 1;
	char c;

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

	array = ardi_char_nuev ();

	while ((c = fgetc (fp)) != EOF)  {
		e.x = c;
		ardi_char_aumd (array, e);
		if (c == '\n')    {
			buscar_palabra (array, argv, linea);
			linea++;
			ardi_char_dest (&amp;array);

			array = ardi_char_nuev ();
		   }
	   }

	ardi_char_dest (&amp;array);
	fclose (fp);
   }

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

void main (int argc, char *argv [])     {
	char fin;

	if (argc != 3)	{
		fprintf (stderr, "Error: N£mero de par metros incorrecto.\n");
		fprintf (stderr, "Uso: programa <fichero> <palabra a buscar>\n");
		exit (1);
	   }

	fichero_array (argv);

	printf ("\nLa b£squeda ha finalizado.");
	printf (" Pulse una tecla para finalizar.");
	fin = getch ();
	clrscr ();
   }

Como siempre termino dejando abierta la sección de comentarios para que aquellos que lo deseen dejen sus opiniones o código alternativo con el que podamos aprender todos.

No Comments

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.