Autor Tema: Cola Generica (Leído 5477 veces)

Rombus · « **en:** Viernes 10 de Octubre de 2008, 16:49 »

Hola gente!

estoy realizando la implementacion de estructuras de datos genericas, la de pila ya la tengo y no tube mayores problemas, pero cuando llegue a la de cola se me complico un poco.

bien este es mi codigo, esta completo asi se puede pegar a un compilador o algun lugar donde se pueda leer mejor:

Código: C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
#define FALSE 0
#define TRUE !FALSE
 
typedef char boolean;
//Cola propiamente dicha
typedef struct{
    void *elementos;
    int size;
    int head,   //Cantidad de puts();
        tail;   //Cantidad de Gets();
}cola_t;
//Estructura Administrativa
typedef struct{
    cola_t *cola;
    int sizeTipo;
}queue_t;
 
queue_t *qCreate(int size, int sizeTipo){
    queue_t *queue = (queue_t *)malloc(sizeof(queue_t));    
    assert(queue);
    
    queue->cola = (cola_t *)malloc(sizeof(cola_t));     
    assert(queue->cola);    
    queue->sizeTipo = sizeTipo; 
    
    queue->cola->elementos = (void *)malloc(sizeTipo * size);
    assert(queue->cola->elementos);
    
    queue->cola->size = size;
    queue->cola->head = queue->cola->tail = 0;
    
    return queue;
}
void qDestroy(queue_t *queue){
    free(queue->cola);
    free(queue);
}   
int qFull(queue_t *queue){
    if(queue && queue->cola)    //Si tengo queue
        return ((queue->cola->tail - queue->cola->head) == queue->cola->size);
    return -1;  //No hay cola, devuelvo -1
}
int qEmpty(queue_t *queue){
    if(queue && queue->cola)    //si tengo queue
        return (queue->cola->tail == queue->cola->head);
    return -1; //No hay cola    
}
boolean qPut(queue_t *queue, void *valor){
    if(qFull(queue))
        return FALSE;   //Esta llena y no puedo ingresar nada
    
    memcpy( (char *)(queue->cola->elementos)+(queue->cola->tail % queue->cola->size), valor, queue->sizeTipo);
    
    printf("Guardado: %dn",*(char *)((queue->cola->elementos)+(queue->cola->tail)));
    //printf("  ingresado en: %dn",queue->cola->tail % queue->cola->size);
    
    queue->cola->tail++;
    return TRUE;
}
boolean qGet(queue_t *queue, void *valor){
    if(qEmpty(queue))
        return FALSE;   //Esta vacia y no puedo ingresar nada
    /* 
     * Resuelvo el problema de q los
     * indices crezcan hacia el infinito 
     */
    if(queue->cola->head > queue->cola->size){
        queue->cola->head %= queue->cola->size;
        queue->cola->tail %= queue->cola->size;
    }
    
    memcpy(valor,(void*)(queue->cola->elementos)+(queue->cola->head % queue->cola->size), queue->sizeTipo);
    
    printf("Removido: %dn",*(int *)valor);
    //printf("  removido de: %dn",queue->cola->head % queue->cola->size);
    
    queue->cola->head++;
    return TRUE;
}
 
 
int main(void){
    queue_t *queue;
    int a = 3, b = 2, c,d;
 
    queue = qCreate(5,sizeof(int));
    
    qPut (queue,(void *)&a);
    qPut (queue,(void *)&b);
    
    printf("n");
    
    qGet(queue,(void *)&c); 
    qGet(queue,(void *)&d);
    
    printf("n");
    
    printf("Extraje en el main: %dn",(char)c);
    printf("Extraje en el main: %dn",d);
    
    qDestroy(queue);
    
    
    return 0;
}
 
 

mi problema es la parte de qGet(), osea, extraer elementos de la cola.
A simple vista no puedo encontrarle el error, pero de tantas pruebas que realice, me di cuenta que si casteo la variable donde guarde el valor removido de la cola a char, el resultado que obtengo es el esperado (linea 103).

Pero sinceramente no entiendo porque pasa esto, ni como hacer para que no haga falta hacer ese casteo a char.

¿tendra algo que ver con el hecho de que en la funcion qPut donde esta el memcpy lo castie a (char *) ? (linea59), aunque probe en no castearlo y dejarlo void * pero me tira un error de compilacion, desreferenciando puntero void.

m0skit0

Cita de: "Rombus"

me di cuenta que si casteo la variable donde guarde el valor removido de la cola a char, el resultado que obtengo es el esperado (linea 103).

Entonces funciona, ¿cuál es el problema?

Rombus

hola moskito!

gracias por responder

la cola generica que hice anda bien, pero no anda como deberia andar, bah... mejor dicho, no anda como yo quiero que ande.

estube probando mas formas y termine creo con el mismo codigo pero con un par de printf's que meustran cosas que sinceramente no entiendo que son.

hice esta prueba:

Código: C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
#define FALSE 0
#define TRUE !FALSE
 
typedef char boolean;
//Cola propiamente dicha
typedef struct{
    void *elementos;
    int size;
    int head,   //Cantidad de puts();
        tail;   //Cantidad de Gets();
}cola_t;
//Estructura Administrativa
typedef struct{
    cola_t *cola;
    int sizeTipo;
}queue_t;
 
queue_t *qCreate(int size, int sizeTipo){
    queue_t *queue = (queue_t *)malloc(sizeof(queue_t));    
    assert(queue);
    
    queue->cola = (cola_t *)malloc(sizeof(cola_t));     
    assert(queue->cola);    
    queue->sizeTipo = sizeTipo; 
    
    queue->cola->elementos = (void *)malloc(sizeTipo * size);
    assert(queue->cola->elementos);
    
    queue->cola->size = size;
    queue->cola->head = queue->cola->tail = 0;
    
    return queue;
}
void qDestroy(queue_t *queue){
    free(queue->cola);
    free(queue);
}   
int qFull(queue_t *queue){
    if(queue && queue->cola)    //Si tengo queue
        return ((queue->cola->tail - queue->cola->head) == queue->cola->size);
    return -1;  //No hay cola, devuelvo -1
}
int qEmpty(queue_t *queue){
    if(queue && queue->cola)    //si tengo queue
        return (queue->cola->tail == queue->cola->head);
    return -1; //No hay cola    
}
boolean qPut(queue_t *queue, void *valor){
    if(qFull(queue))
        return FALSE;   //Esta llena y no puedo ingresar nada
    
    memcpy( ((char *)(queue->cola->elementos))+(queue->cola->tail % queue->cola->size), valor, queue->sizeTipo);
    valor = (void *)valor;
    
    printf("Guardado: %dn",*( ((char*)(queue->cola->elementos))+(queue->cola->tail)) );
    //printf("  ingresado en: %dn",queue->cola->tail % queue->cola->size);
    
    queue->cola->tail++;
    return TRUE;
}
boolean qGet(queue_t *queue, void *valor){
    if(qEmpty(queue))
        return FALSE;   //Esta vacia y no puedo ingresar nada
    /* 
     * Resuelvo el problema de q los
     * indices crezcan hacia el infinito 
     */
    if(queue->cola->head > queue->cola->size){
        queue->cola->head %= queue->cola->size;
        queue->cola->tail %= queue->cola->size;
    }
    
    memcpy(valor,((char *)(queue->cola->elementos))+(queue->cola->head % queue->cola->size), queue->sizeTipo);
    
    printf("Removido: %dn",*((char *)(queue->cola->elementos))+(queue->cola->head % queue->cola->size));
    //printf("en exa: %0xn",valor);
    //printf("  removido de: %dn",queue->cola->head % queue->cola->size);
    
    queue->cola->head++;
    return TRUE;
}
 
 
int main(void){
    queue_t *queue;
    int a = 15, b = 22, c,d;
 
    queue = qCreate(5,sizeof(int));
    
    qPut (queue,(void *)&a);
    qPut (queue,(void *)&b);
    
    printf("n");
    
    qGet(queue,(void *)&c); 
    qGet(queue,(void *)&d);
    
    printf("n");
    
    printf("El primer valor que extraje fue : %dn",c);
    printf("Ese mismo valor mostrado antes pero casteado a (char) : %dn",(char)c);
    
    printf("el segundo valor que extraje fue: %dn",d);
    
    
    qDestroy(queue);
    
    
    return 0;
}
 
 

Descripcion de lo que obtengo

puse printf's en la funcion qPut para ver que los valores insertados en la pila sea correctos y descartar la posibilidad de la carga de valores erroneos.

el resultado de esos printf's en mi prueba fueron los correctos 15 y 22 como le dije q lo haga

despues puse printf's en la qGet para ver si lo que remuevo es correcto, y obtengo 15 y 16, osea, el primer valor es correcto, yo ingrese 15 y removi 15, pero el segundo valor es incorrecto, yo ingrese 22 como segundo valor pero remuevo 16 :S.

y finalmente puse printf's en el main de la variable que agarra los valores que remueve la qGet y obtengo esto: 5647 y 22, osea al revez que antes, el primer valor es erroneo (esperaba un 15), y el segundo valor es correcto.

por alguna razon, se me ocurrio castear la variable donde guardo el valor que saca el qGet a char (solo la primera vez q imprime, ya que la segunda vez obtengo el resultado esperado) y magicamente andubo!

el problema es que no entiendo que es lo q pasa, deberia darme los valores correctos sin tener que hacer el cast.

no parece muy generico el hecho de tener que adivinar a q variable hacerle el cast y a cual no :S

espero que me puedas ayudar

gracias!

m0skit0

Hmm curioso hecho... Seguramente es un problema con los punteros. Ahora no tengo tiempo, pero intentaré depurarlo más detenidamente más tarde.

Rombus

uh buenisimo!

gracias moskito, espero tu respuesta

EL_UNI

Tengo una pregunta Rombus... ¿Que significan el head y el tail? ¿La posición del primer y el ultimo elemento respectivamente? Yo tengo una cola implementada (por mi) así que intentaré ayudarte como pueda ^^

Rombus

hola el_uni!

gracias por tomarte el tiepo para leer mi problema.

es interesante tu pregunta ya que en la implementacion que estoy realizando el head y el tail no son la posicion del ultimo y el primer elemento, sino que son la cantidad de puts y la cantidad de gets respectivamente. esto me da la libertad de hacer una cola circular tan sencillamente como con esta instruccion:

Código: C

memcpy( ((char *)(queue->cola->elementos))+(queue->cola->tail % queue->cola->size), valor, queue->sizeTipo);
 

capaz se ve mejor de esta manera:

Código: C

queue->cola->elementos[queue->cola->tail % queue->cola->size]
 

vi investigando en internet gente que realiza colas que son simplemente listas ligadas que ademas tienen un head y tail, esta bueno eso... pero queria que me ande con esta metodologia.

aparte hice el stack generico (lo dejo adjunto por si a alguien le interesa

) y no tube mayores problemas.

le di muchas vueltas, sinceramente no se donde esta el error, seguramente es algun problema como dijo moskito, algun puntero algun cast.

espero que me puedan ayudar

saludos!

EL_UNI

Creo que lo entiendo... la manera que hago yo para hacer las colas genericas, es mediante la posicion del primero y el numero de elemtos introducidos (primero y usados). Se queda un codigo facil y rapido de entender.
De todas maneras tambien hago otro tipo de estructuracion de la cola:

Código: C

 
struct cola_rep{
    void *datos;     //Vector de datos.
    int primero;     //Posicion del primer elemento. Inicialmente 0.
    int usados;      //Cantidad de elementos dentro de la cola.
    int tam;          //Tamaño de la cola.
    int tam_dato;  //Tamaño de los datos.
};
 
 

Con esta estructura, meter y sacar datos es muy sencillo:

Código: C

 
int cola_gen_mete(cola_gen c,void *dato)
{
    if(!(cola_gen_llena(c))){
        memcpy(c->datos+((c->primero+c->usados++)%c->tam)*c->tam_dato,dato,c->tam_dato);
        return 0;
    }
    return -1;   //No se puede meter
};
 
int cola_gen_saca(cola_gen c,void *dato)
{
    if((cola_gen_vacia(c))){
        memcpy(dato,c->datos+(c->primero)*c->tam_dato,c->tam_dato);
        c->primero++;
        c->primero %= c->tam //Para que el valor de c->primero no se nos dispare se va actualizando
        c->usados--;
        return 0;
    }
    return -1;   //No se puede sacar
};
 
 

Así funciona perfecto :p. De todas maneras bajaré tu código e intentaré ver donde falla ^^

Rombus

claro, es parcticamente lo mismo no?

si

tu haces:

Código: Text

c->datos+((c->primero+c->usados++)%c->tam
 

y el mio es:

Código: Text

(queue->cola->elementos))+(queue->cola->tail % queue->cola->size)
 

el codigo esta todo completo y listo para compilar, hay un par de printf's como dije mas arriba que me dan valores re confusos

seguro si comparas tu cola generica con la mia vas a descubrir el error facilmente, habiendolo implementado igual : D
en internet no hay nada de documentacion con colas implementadas asi :S, por lo menos yo no encontre

saludos!

EL_UNI

Le he dado vueltas a tu codigo y no he sido capaz de encontrarlo... En internet las encontraras dinamicas (esta es estatica)
De todas maneras, si puedo esta tarde (ahora tengo seminario...) te reviso el codigo otra vez... Seguro que es algun puntero... hasta que me acostumbre a ellos las pasaba fatal xDDD

Yo tengo tambien implementado un vector dinamico generico. Por si os inetera ^^

Saludos. EL_UNI

PD: Es mas facil hacer una sola estructura que una estructura dentro de otra estructura. Te ahorras una llamada de liberado y otra de reserva ^^

Rombus

jaja, si leer codigo ageno es todo un tema XD

ta dificil el problema :S

buenisimo!

me gustaria ver el vector generico si no te es molestia

espero tus comentarios

EL_UNI

He encontrado un fallo también en tú código.

Código: C

 
void qDestroy(queue_t *queue){
    free(queue->cola);
    free(queue);
}

Deverías asginar luego NULL a queue, porque queue esta apuntando a una dirección de memoria que estaba RESERVADA y ahora no lo está. Debes de ponerlo así:

Código: C

 
void qDestroy(queue_t *queue){
    free(queue->cola);
    free(queue);
    queue = NULL;
}  
 
 

Y ya solucioné tu error a la hora de introducir y sacar datos ^^. Faltaba multiplicar la dirección donde se meterá/sacará el dato POR EL TAMAÑO DEL DATO. Entonces el qPut y el qGet te quedaría de la siguiente manera:

qPut:

Código: C

 
boolean qPut(queue_t *queue, void *valor){
    if(qFull(queue))
        return FALSE;   //Esta llena y no puedo ingresar nada
   
    memcpy(((queue->cola->elementos))+(queue->cola->tail % queue->cola->size)*queue->sizeTipo, valor, queue->sizeTipo);  
   
    queue->cola->tail++;
    return TRUE;
}

qGet:

Código: C

 
boolean qGet(queue_t *queue, void *valor){
    if(qEmpty(queue))
        return FALSE;   //Esta vacia y no puedo ingresar nada
    /*
     * Resuelvo el problema de q los
     * indices crezcan hacia el infinito
     */
    if(queue->cola->head > queue->cola->size){
        queue->cola->head %= queue->cola->size;
        queue->cola->tail %= queue->cola->size;
    }
   
    memcpy(valor,queue->cola->elementos+(queue->cola->head*queue->sizeTipo), queue->sizeTipo);
   
    queue->cola->head++;
    return TRUE;
}
 
 

Como puedes ver he quitado muchas cosas... pero lo que te faltaba era simplemente la multiplicación dentro del memcpy.

De todas maneras, esta manera de implementarla creo que puede tener algunos fallos a la hora de hacer muchos introducciones y sacadas de datos.

Espero que te haya servido de ayuda, para cualquier duda que tengas sobre el código aquí estoy.
UN SALUDO. EL_UNI

PD: Te envie un e-mail, si no es mucho pedir, contestalo.

Eternal Idol

Esto esta mal:
free(queue);
*queue = NULL;

Si queue fue liberado entonces no accedas al mismo, queue = NULL; si es correcto.

EL_UNI

Perdona ha sido un pequeño error a la hora de transquivir el codigo... de todas maneras tambien es porque en la cola que tengo hecha yo si tengo que ponerlo así porque trabajo de otra manera ^^
Ya lo he editado y gracias por la observación

Eternal Idol

Esta bien pero igual no sirve para nada, solo le asigna NULL a la variable local queue que obviamente despues de eso no va a ser usada ya que no hay mas codigo en la funcion.

Rombus

uhhhh!

el_uni muchas gracias!!!

ese error me estaba limando la cabeza, lo peor de todo es que hice un stack generico (el que adjunte mas arriba) y lo tube en cuenta a eso, despues ayude a un amigo a hacer uno y no andubo, lo revise y era por ese mismo error, nunca se me hubiera ocurrido buscarlo en esta, ya estaba muy saturado XD

y agregue tambien el queue = NULL; en la qDestroy, esta bueno, en teoria evitas fallos de segmentacion, ya que en una condicion como esta

Código: Text

if(queue)
 

al haber hecho el queue = NULL no entraria

gracias nuevamente!!

saludos

EL_UNI

De nada, para eso estamos ^^

Ya tienes un quebradero menos de cabeza xDD

Saludos. EL_UNI

Eternal Idol

Cita de: "Rombus"

y agregue tambien el queue = NULL; en la qDestroy, esta bueno, en teoria evitas fallos de segmentacion, ya que en una condicion como esta
Código: Text
if(queue)

al haber hecho el queue = NULL no entraria

Para eso tendria que ser pasado como referencia a puntero o doble puntero, de otra manera no modificas el valor de queue FUERA del metodo (en el main no cambia su valor).

Rombus

ah!..

lo q dices es q deberia ser

Código: Text

void qDestroy(queue_t **queue)
 

para q tenga sentido la asignacion?

Eternal Idol

Si, o void qDestroy(queue_t *&queue).

Rombus

ah, con eso te referias a "pasado como referencia a puntero"?

nunca habia visto algo asi :O

la implementacion quedaria igual? o deberia cambiarla como si fuera doble puntero, osea asi:

Código: C

 void qDestroy(queue_t *&queue){
     free((*queue)->cola);
     free( (*queue) );
    (*queue) = NULL;
 } 
 

Eternal Idol

Tal como lo tenias era correcto (EN C++):

Código: Text

void qDestroy(queue_t *&queue){
    free(queue->cola);
    free(queue);
    queue = NULL;
}
 

En C tenes que usar un doble puntero.

Rombus

ah! por eso no lo habia visto jeje

uso C

al doble puntero entonces

saludos!