Tipo de datos abstracto doble cola dinámica

Tipo de datos abstracto doble cola dinámica

Vamos a dedicar éste artículo a describir la estructura de datos doble cola dinámica. Os podéis descargar los ficheros desde mi repositorio personal en github, ( tanto ficheros txt, como ficheros .h/.c).

Comenzamos por las cabeceras de las funciones y procedimientos de la estructura en el fichero .h:

#ifndef _TAD_BICOLA_DINAMICA_PRACT_2000_01_EDI1_
#define _TAD_BICOLA_DINAMICA_PRACT_2000_01_EDI1_

#define ED_TRUE	1	
#define ED_FALSE 0	

typedef void* tGenData;


typedef struct ddqueueHead* DDQUEUE;

DDQUEUE create ( void );
int erase (  DDQUEUE* dDQueue );
int insertLeft ( tGenData data,
		 unsigned int size,
		 DDQUEUE dDQueue );
int insertRight ( tGenData data,
		  unsigned int size,
		  DDQUEUE dDQueue );
int deleteLeft ( tGenData data,	
	         DDQUEUE dDQueue );
int deleteRight ( tGenData data,
		  DDQUEUE dDQueue );
void acrossLeft ( tGenData data,
		  unsigned int ndata,
		  DDQUEUE dDQueue );
void acrossRight ( tGenData data,
		   unsigned int ndata,
		   DDQUEUE dDQueue );
int emptyLeft ( DDQUEUE dDQueue );
int emptyRight ( DDQUEUE dDQueue );
int nnQueueLeft ( DDQUEUE dDQueue );
int nnQueueRight ( DDQUEUE dDQueue );

#endif

La doble cola dinamica esta formada por una lista continua de nodos acabada en NULL; en principio está construida como una lista de nodos dinamico tradicional. No obstante esta estructura de datos tiene una cabecera con dos punteros, los cuales, apuntan al primer nodo de cada cola ( izquierda y derecha, respectivamente ) manteniendo el siguiente orden: los primeros nodos pertenecen a la cola izquierda, y los últimos nodos pertenecen a la cola de la derecha.

Las inserciones y borrados se realizan utilizando su propia primitiva o procedimiento, así como el recorrido o la funcion booleana que comprueba que la cola esta vacia. De ésta forma, el único código que permanece común a ambas colas es el construtor de la estructura y el destructor de la misma.

Las operaciones que se realizan sobre ésta estructura de datos son las siguientes.-

  • Insercion de nodos en orden FIFO.
  • Borrado de nodos en orden FIFO.
  • Recorrido de cada una de las colas por separado ( derecha o
    izquierda ).
  • Comprobación booleana de que la cola está vacia.
  • Visualizacion del numero de nodos contenido en cada cola.

Las primitivas las agruparemos en la siguiente clasificación.-

  • Constructores: create
  • Destructores: erase
  • Modificadores: insertLeft, insertRight, deleteLeft y deleteRight
  • Observadores: acrossLeft, acrossRight, emptyLeft, emptyRight, nnQueueLeft y nnQueueRight.

A continuación, vamos a ver el desarrollo, uno por uno, de cada uno de los procedimientos y funciones:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#include "../include/ddqueue.h"


struct ddqueueNode {
	tGenData data;		    		
	struct ddqueueNode* next;       
};

struct ddqueueHead {
	struct ddqueueNode* leftQueue;  
	struct ddqueueNode* rightQueue;	
	unsigned int leftQueueNn; 		
	unsigned int rightQueueNn; 		
};


DDQUEUE create ( void )
{
	struct ddqueueHead* ddq;
	
	ddq = ( struct ddqueueHead* ) malloc ( sizeof ( struct ddqueueHead ));
	if ( ddq == NULL ) return NULL;
	
	ddq->leftQueue = NULL;
	ddq->rightQueue = NULL;
	ddq->leftQueueNn = 0;
	ddq->rightQueueNn = 0;
	
	return ( ddq );
}

int erase ( DDQUEUE* dDQueue )
{
	struct ddqueueNode* ddqIndex;
	struct ddqueueNode* ddqFreeNode;
	int auxFreeNode=0;
	
	if ( dDQueue == NULL ) return ED_FALSE;
	if ( emptyLeft ( *dDQueue ) == ED_TRUE )
		if ( emptyRight ( *dDQueue ) == ED_TRUE )
			ddqIndex = NULL;
		else {
			ddqIndex = (*dDQueue)->rightQueue;
			auxFreeNode = 1;
		}
	else {
		ddqIndex = (*dDQueue)->leftQueue;
		auxFreeNode = 1;
	}
	
	
	if ( auxFreeNode == ED_FALSE ) {
		while ( ddqIndex != NULL ) {
			ddqFreeNode = ddqIndex;
			ddqIndex = ddqFreeNode->next;
			free ( ddqFreeNode );
		}
	}
	
	free ( *dDQueue );
	return ED_TRUE;
}

int insertLeft ( tGenData data,
		 unsigned int size,
		 DDQUEUE dDQueue )
{
	struct ddqueueNode* ddqIndex;
	struct ddqueueNode* ddqEndNode;
	struct ddqueueNode* ddqnn;	
	
	if ( dDQueue == NULL ) return ED_FALSE;
	
	ddqnn = ( struct ddqueueNode* ) malloc ( sizeof ( struct ddqueueNode ));
	if ( ddqnn == NULL ) return ED_FALSE;
	
	ddqnn->data = ( void* ) malloc ( sizeof ( size ));
	if ( ddqnn->data == NULL ) return ED_FALSE;
		
	memcpy ( ddqnn->data, data, sizeof ( size ));
	ddqnn->next = NULL;
	
	if ( emptyRight ( dDQueue ) == ED_TRUE ) ddqEndNode = NULL;
	else ddqEndNode = dDQueue->rightQueue;
	
	if ( emptyLeft ( dDQueue ) == ED_TRUE )
		dDQueue->leftQueue = ddqnn;
	else {
		ddqIndex = dDQueue->leftQueue;
		while ( ddqIndex->next != ddqEndNode ) ddqIndex = ddqIndex->next;
	
		ddqIndex->next = ddqnn;
	}

	if ( ddqEndNode != NULL ) ddqnn->next = dDQueue->rightQueue;
	
	dDQueue->leftQueueNn++;
	return ED_TRUE;
}

int insertRight ( tGenData data,
		  unsigned int size,
		  DDQUEUE dDQueue )
{
	struct ddqueueNode* ddqnn;
	struct ddqueueNode* ddqIndex;
	struct ddqueueNode* ddqAuxLeftNode;
	
	if ( dDQueue == NULL ) return ED_FALSE;
	
	ddqnn = ( struct ddqueueNode* ) malloc ( sizeof ( struct ddqueueNode ));
	if ( ddqnn == NULL ) return ED_FALSE;
	
	ddqnn->data = ( void* ) malloc ( sizeof ( size ));
	if ( ddqnn->data == NULL ) return ED_FALSE;
	
	memcpy ( ddqnn->data, data, sizeof ( size ));
	ddqnn->next = NULL;
	
	if ( emptyRight ( dDQueue ) == ED_TRUE ) {
		dDQueue->rightQueue = ddqnn;
 		if ( emptyLeft ( dDQueue ) == ED_FALSE )  {
			ddqAuxLeftNode = dDQueue->leftQueue;
			while ( ddqAuxLeftNode->next != NULL )
				ddqAuxLeftNode = ddqAuxLeftNode->next;
			ddqAuxLeftNode->next = dDQueue->rightQueue;
		}	
 	}
	else {
		ddqIndex = dDQueue->rightQueue;
		while ( ddqIndex->next != NULL ) ddqIndex = ddqIndex->next;
		ddqIndex->next = ddqnn;
	}
	
	dDQueue->rightQueueNn++;
	return ED_TRUE;
}

int deleteLeft ( tGenData data,
		 DDQUEUE dDQueue )
{
	struct ddqueueNode* auxDeleteNode;
	struct ddqueueNode* endLeftNode;
	
	if ( dDQueue == NULL ) return ED_FALSE;
	
	if  ( emptyLeft ( dDQueue ) == ED_TRUE ) return ED_FALSE;
	
	auxDeleteNode = dDQueue->leftQueue;
	endLeftNode = dDQueue->rightQueue;
	
	if ( dDQueue->leftQueue->next == endLeftNode )	dDQueue->leftQueue = NULL;
	else dDQueue->leftQueue = dDQueue->leftQueue->next;

	memcpy ( data, auxDeleteNode->data, sizeof ( auxDeleteNode->data ));
	
	free ( auxDeleteNode->data );
	free ( auxDeleteNode );
	dDQueue->leftQueueNn--;
	
	return ED_TRUE;
}

int deleteRight ( tGenData data,
                  DDQUEUE dDQueue )
{
	struct ddqueueNode* previousNode;
	struct ddqueueNode* auxdeleteNode;
	
	if ( dDQueue == NULL ) return ED_FALSE;
	
	if ( emptyRight ( dDQueue ) == ED_TRUE ) return ED_FALSE;
	
	previousNode = dDQueue->leftQueue;
	while ( previousNode->next != dDQueue->rightQueue ) previousNode = previousNode->next;
	
	auxdeleteNode = dDQueue->rightQueue;
	if ( dDQueue->rightQueue->next == NULL ) dDQueue->rightQueue = NULL;
	else dDQueue->rightQueue = dDQueue->rightQueue->next;
	
	previousNode->next = auxdeleteNode->next;

	memcpy ( data, auxdeleteNode->data, sizeof ( auxdeleteNode->data ));
	
	free ( auxdeleteNode->data );
	free ( auxdeleteNode );
	dDQueue->rightQueueNn--;
	
	return ED_TRUE;
}

void acrossLeft ( tGenData data,
		  unsigned int ndata,		
		  DDQUEUE dDQueue )
{
	struct ddqueueNode* ddqIndex;
	register i;
	
	if ( dDQueue == NULL ) return;
	
	if ( emptyLeft ( dDQueue ) == ED_TRUE ) return;
	
	if ( dDQueue->leftQueueNn < ndata ) return;
	
	ddqIndex = dDQueue->leftQueue;
	for ( i=1; i<ndata; i++ ) ddqIndex = ddqIndex->next;
	memcpy ( data, ddqIndex->data, sizeof ( ddqIndex->data ));	
}

void acrossRight ( tGenData data,
		   unsigned int ndata,
		   DDQUEUE dDQueue )
{
	struct ddqueueNode* ddqIndex;
	register i=1;
	
	if ( dDQueue == NULL ) return;
	
	if ( emptyRight ( dDQueue ) == ED_TRUE ) return;
	
	if ( dDQueue->rightQueueNn < ndata ) return;
	
	ddqIndex = dDQueue->rightQueue;
	
        while ( i < ndata ) {
        	ddqIndex = ddqIndex->next;
        	i++;
        }
        	
	memcpy ( data, ddqIndex->data, sizeof ( ddqIndex->data ));
}

int emptyLeft ( DDQUEUE dDQueue )
{
	if ( dDQueue == NULL ) return ED_FALSE;
	
	if ( dDQueue->leftQueue == NULL ) return ED_TRUE;
	else return ED_FALSE;
}


int emptyRight ( DDQUEUE dDQueue )
{
	if ( dDQueue == NULL ) return ED_FALSE;
	
	if ( dDQueue->rightQueue == NULL ) return ED_TRUE;
	else return ED_FALSE;
}

int nnQueueLeft ( DDQUEUE dDQueue )
{
	if ( dDQueue == NULL ) return -1;
	
	return dDQueue->leftQueueNn;
}

int nnQueueRight ( DDQUEUE dDQueue )
{
	if ( dDQueue == NULL ) return -1;
	
	return dDQueue->rightQueueNn;
}

A continuación vamos a describir uno por uno cada uno de los procedimientos y funciones de ésta estructura de datos.

Constructor: Construye la cabecera de la cola dinamica estableciendo los punteros al primero nodo de cada cola a NULL, e inicializando los contadores de cada cola a 0.

Destructor: Destruye el tipo de dato abstracto doble cola dinamica devolviendo los recursos que utiliza al sistema. Para ello, utiliza la variable ddqindex como indice de la lista de nodos a borrar y ddqFreeNode como la variable auxiliar que necesito para ir borrando cada nodo. Además uso una variable booleana para acceder directamente al borrado de la cabecera si su valor es ED_FALSE o borrar los nodos si su valor es ED_TRUE. En caso contrario, la función devuelve ED_FALSE.

Modificador Insertar Izquierda; Esta es quizás la forma de insertar que resulta más complicada, pero no demasiado, en éste caso, creamos una variable cuyo tamaño lo pasamos como argumento. Es cierto que esta variable la podríamos haber pasado en el constructor como se hace habitualmente y nos ahorramos éste argumento, pero por otro lado, el tamaño de la variable se puede definir como una constante en el programa principal o podemos usar distintas variables para cada nodo introduciendo más versatilidad, si cabe.

Uso tres variables: ddqnn es la que utilizo para reservar la memoria del nuevo nodo y del nuevo dato respectivamente; la variable ddqIndex, como su nombre indica es un indice que utilizo para encontrar el último nodo de la cola izquierda; por ultimo, ddqEndNode me sirve para indicar cual es el primer nodo de la cola derecha o si, por el contrario, la cola derecha está actualmente vacia.

El procedimiento es sencillo, compruebo las precondiciones; hago las reservas de memoria oportunas y copio en el nuevo nodo el dato que quiero insertar y el puntero next lo actualio a NULL. A continuación compruebo si la cola derecha esta vacia o no, de forma que actualizo el puntero auxiliar a NULL o a dDQueue->rightQueue. La insercion se realiza como en una cola normal. Por último, actualizo la dirección del nodo que acabo de insertar con la dirección del primer nodo de la cola derecha o a NULL si no hay; la ultima operación es incrementar el contador.

En caso de que ocurra un error la funcion devuelve ED_FALSE;

Modificador Insertar Derecha: En este caso, al ser el orden de la cola FIFO, el nodo será insertado al final de la cola, en caso de que haya mas de un nodo o al principio de esta, en caso de que sea el primer nodo que introducimos en la cola. Puesto que, según nuestra estructura, la cola derecha esta situada en el segmento final de la lista, la inserción se reduce a
una inserción tradicional: busco el final de la cola e inserto el nuevo nodo.

Hay que realizar, no obstante, una consideración, y es que como la estructura de datos se ha concebido como una lista continua, en la que se distinguen dos colas de forma lógica y no física, se ha de poner especial cuidado en que el último nodo de la cola de la izquierda apunte al primer nodo de la cola de la derecha, y que esa referencia no se pierda.

Las variables locales que utilizo aqui son: ddqnn que me sirve para la reserva de memoria del nuevo nodo, ddqIndex, que la utilizo como indice para localizar el último nodo de la cola a fin de realizar la inserción, y ddqAuxLeftNode que apunta al último nodo de la cola de la izquierda, de forma que se pueda realizar correctamente el enlace de ambas colas.

La función devolverá ED_TRUE si todo va bien o ED_FALSE si ha ocurrido
algún error.

Modificador Borrar Izquierda: Esta rutina borra el primer nodo de la cola de la izquierda, esto es, borra el primer nodo de la lista que conforma la estructura de datos que hemos construido, por tanto, la eliminación de dicho nodo no reviste ningún tipo de dificultad, pudiendo ser equivalente al borrado de un nodo en una cola tradicional.

Las variables locales que aquí utilizo son: auxDeleteNode que es la variable que apunta al nodo que voy a borrar y endLeftNode, que me indica cual es el primer nodo de la cola de la derecha o, si bien, en esta cola no hay ningún nodo en cuyo caso su valor será NULL.

Modificador Borrar Derecha: Esta operación revistirá, quizás, alguna complicación mas que la rutina anterior, puesto que, ahora, lo que estamos intentando borrar es el primer nodo de la cola de la derecha, esto es, un nodo que se encuentra dentro de la lista que conforma la estructura de datos; esto requerirá, por tanto, una serie de actualizaciones de punteros que deberemos realizar con cuidado no sea que perdamos alguna referencia, y, por tanto, corrompamos la estructura de datos.

El primer nodo de la cola de la derecha lo encontramos de forma trivial, no obstante, es necesario encontrar una referencia al último nodo de la cola de la izquierda, y eso se realiza usando la variable local previousNode. El resto de la función tiene un funcionamiento análogo al de la función anterior.

Observador Ver Cola Izquierda: Este observador devuelve el valor del nodo cuya posicion se le indica como argumento. Por tanto habrá que indicar cuál es la posisión que ocupa el nodo cuyo valor queremos visualizar en pantalla y que quedará almacenado en la variable data que se le pasa como argumento. Los indices que utilizamos están comprendidos entre 1 y el número total de nodos de la cola.

Observador Ver Cola Derecha: De la misma forma que en la rutina anterior, devolvemos el valor del nodo contenido en la cola de la derecha en la posicion indicada por ndata.

Observador Cola Izquierda Vacia: Este observador comprueba si la cola izquierda tiene algún nodo o por el contrario apunta a NULL, En el primer caso devolverá ED_TRUE, en caso contrario ED_FALSE.

Observador Cola Derecha Vacia: Este observador comprueba si la cola derecha tiene algún nodo o por el contrario el puntero de la cabecera correspondiente apunta a NULL. Al igual que la rutina anterior, devolverá ED_TRUE en caso de que este vacia o devolvera ED_FALSE en caso de que la cola no exista o no este vacia.

Observador Numero de Nodos Cola Izquierda: Este observador es una función que nos devuelve el numero de nodos que tiene actualmente la cola izquierda.

Observador Numero de Nodos Cola Derecha: Este Observador es una funcion que nos devuelve el numero de nodos que tiene actualmente la cola derecha.

Para terminar este artículo, os voy a dejar un programa con el que podréis poner a prueba todas las funcionalidades de ésta estructura de datos.

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


#include "../include/ddqueue.h"

int main ( int argc, char** argv )
{
	DDQUEUE cola;
	int operacion;
	int contador, numero;
	
	
	cola = create ( );         	
		
	
	for ( contador=1; contador<=10; contador++ ) {
		insertLeft ( ( tGenData ) &amp;contador, sizeof ( contador ), cola );
		acrossLeft ( ( tGenData ) &amp;numero, contador, cola );
		printf ( "El valor del numero    izquierda es igual a ... %d\n", numero );
		insertRight ( ( tGenData )&amp;contador, sizeof ( contador ), cola );
		acrossRight ( ( tGenData )&amp;numero, contador, cola );
		printf ( "El valor del numero derecha es igual a ... %d\n", numero );
	}
	
	
	for ( contador=1; contador<=5; contador++ ) {
		deleteLeft ( ( tGenData )&amp;numero, cola );
		printf ( "El valor que saco es igual a %d\n", numero );
	}
	
	
	for ( contador=1; contador<=5; contador++ ) {
		acrossLeft ( ( tGenData ) &amp;numero, contador, cola );
		printf ( "El valor del numero izquierda es igual a ... %d\n", numero );
	}
	
	
	for ( contador=1; contador<=5; contador++ ) {
		deleteRight ( ( tGenData )&amp;numero, cola );
		printf ( "El valor que saco es igual a %d\n", numero );
	}
	
	
	for ( contador=1; contador<=5; contador++ ) {
		acrossRight ( ( tGenData ) &amp;numero, contador, cola );
		printf ( "El valor del numero derecha es igual a ... %d\n", numero );
	}
	
	
	printf ( "El numero de nodos que tiene la cola izquierda es %d\n", nnQueueLeft ( cola ));
	
	
	printf ( "El numero de nodos que tiene la cola derecha es %d\n", nnQueueRight ( cola ));
	
	
	for ( contador=1; contador<=5; contador++ ) {
		deleteLeft ( ( tGenData )&amp;numero, cola );
		printf ( "El numero que saco de la cola izquierda es igual a %d\n", numero );
	}
	
	
	if ( emptyLeft ( cola ) == ED_TRUE ) printf ( "La cola izquierda esta vacia..\n" );
	else printf ( "La cola izquierda no esta vacia.\n" );
	
	
	operacion = erase ( &amp;cola );
	if ( operacion == ED_TRUE )
		printf ( "\nLa cola ha sido destruida ...\n" );
	else printf ( "La cola no ha sido destruida correctamente ...\n" );
}

Como siempre, tenéis a vuestra disposición la sección de comentarios de éste blog personal para que dejéis vuestras impresiones, vuestras aportaciones o código fuente alternativo.

No Comments

Post a Comment