SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Rombus en Viernes 10 de Octubre de 2008, 16:49

Título: Cola Generica
Publicado por: 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

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. #include <assert.h>
5.  
6. #define FALSE 0
7. #define TRUE !FALSE
8.  
9. typedef char boolean;
10. //Cola propiamente dicha
11. typedef struct{
12.     void *elementos;
13.     int size;
14.     int head,   //Cantidad de puts();
15.         tail;   //Cantidad de Gets();
16. }cola_t;
17. //Estructura Administrativa
18. typedef struct{
19.     cola_t *cola;
20.     int sizeTipo;
21. }queue_t;
22.  
23. queue_t *qCreate(int size, int sizeTipo){
24.     queue_t *queue = (queue_t *)malloc(sizeof(queue_t));    
25.     assert(queue);
26.    
27.     queue->cola = (cola_t *)malloc(sizeof(cola_t));    
28.     assert(queue->cola);    
29.     queue->sizeTipo = sizeTipo;
30.    
31.     queue->cola->elementos = (void *)malloc(sizeTipo * size);
32.     assert(queue->cola->elementos);
33.    
34.     queue->cola->size = size;
35.     queue->cola->head = queue->cola->tail = 0;
36.    
37.     return queue;
38. }
39. void qDestroy(queue_t *queue){
40.     free(queue->cola);
41.     free(queue);
42. }  
43. int qFull(queue_t *queue){
44.     if(queue && queue->cola)    //Si tengo queue
45.         return ((queue->cola->tail - queue->cola->head) == queue->cola->size);
46.     return -1;  //No hay cola, devuelvo -1
47. }
48. int qEmpty(queue_t *queue){
49.     if(queue && queue->cola)    //si tengo queue
50.         return (queue->cola->tail == queue->cola->head);
51.     return -1; //No hay cola    
52. }
53. boolean qPut(queue_t *queue, void *valor){
54.     if(qFull(queue))
55.         return FALSE;   //Esta llena y no puedo ingresar nada
56.    
57.     memcpy( (char *)(queue->cola->elementos)+(queue->cola->tail % queue->cola->size), valor, queue->sizeTipo);
58.    
59.     printf("Guardado: %dn",*(char *)((queue->cola->elementos)+(queue->cola->tail)));
60.     //printf("  ingresado en: %dn",queue->cola->tail % queue->cola->size);
61.    
62.     queue->cola->tail++;
63.     return TRUE;
64. }
65. boolean qGet(queue_t *queue, void *valor){
66.     if(qEmpty(queue))
67.         return FALSE;   //Esta vacia y no puedo ingresar nada
68.     /*
69.      * Resuelvo el problema de q los
70.      * indices crezcan hacia el infinito
71.      */
72.     if(queue->cola->head > queue->cola->size){
73.         queue->cola->head %= queue->cola->size;
74.         queue->cola->tail %= queue->cola->size;
75.     }
76.    
77.     memcpy(valor,(void*)(queue->cola->elementos)+(queue->cola->head % queue->cola->size), queue->sizeTipo);
78.    
79.     printf("Removido: %dn",*(int *)valor);
80.     //printf("  removido de: %dn",queue->cola->head % queue->cola->size);
81.    
82.     queue->cola->head++;
83.     return TRUE;
84. }
85.  
86.  
87. int main(void){
88.     queue_t *queue;
89.     int a = 3, b = 2, c,d;
90.  
91.     queue = qCreate(5,sizeof(int));
92.    
93.     qPut (queue,(void *)&a);
94.     qPut (queue,(void *)&b);
95.    
96.     printf("n");
97.    
98.     qGet(queue,(void *)&c);
99.     qGet(queue,(void *)&d);
100.    
101.     printf("n");
102.    
103.     printf("Extraje en el main: %dn",(char)c);
104.     printf("Extraje en el main: %dn",d);
105.    
106.     qDestroy(queue);
107.    
108.    
109.     return 0;
110. }
111.  
112.  

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.

Título: Re: Cola Generica
Publicado por: m0skit0 en Lunes 13 de Octubre de 2008, 14:26

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?

Título: Re: Cola Generica
Publicado por: Rombus en Lunes 13 de Octubre de 2008, 19:20

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

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4. #include <assert.h>
5.  
6. #define FALSE 0
7. #define TRUE !FALSE
8.  
9. typedef char boolean;
10. //Cola propiamente dicha
11. typedef struct{
12.     void *elementos;
13.     int size;
14.     int head,   //Cantidad de puts();
15.         tail;   //Cantidad de Gets();
16. }cola_t;
17. //Estructura Administrativa
18. typedef struct{
19.     cola_t *cola;
20.     int sizeTipo;
21. }queue_t;
22.  
23. queue_t *qCreate(int size, int sizeTipo){
24.     queue_t *queue = (queue_t *)malloc(sizeof(queue_t));    
25.     assert(queue);
26.    
27.     queue->cola = (cola_t *)malloc(sizeof(cola_t));    
28.     assert(queue->cola);    
29.     queue->sizeTipo = sizeTipo;
30.    
31.     queue->cola->elementos = (void *)malloc(sizeTipo * size);
32.     assert(queue->cola->elementos);
33.    
34.     queue->cola->size = size;
35.     queue->cola->head = queue->cola->tail = 0;
36.    
37.     return queue;
38. }
39. void qDestroy(queue_t *queue){
40.     free(queue->cola);
41.     free(queue);
42. }  
43. int qFull(queue_t *queue){
44.     if(queue && queue->cola)    //Si tengo queue
45.         return ((queue->cola->tail - queue->cola->head) == queue->cola->size);
46.     return -1;  //No hay cola, devuelvo -1
47. }
48. int qEmpty(queue_t *queue){
49.     if(queue && queue->cola)    //si tengo queue
50.         return (queue->cola->tail == queue->cola->head);
51.     return -1; //No hay cola    
52. }
53. boolean qPut(queue_t *queue, void *valor){
54.     if(qFull(queue))
55.         return FALSE;   //Esta llena y no puedo ingresar nada
56.    
57.     memcpy( ((char *)(queue->cola->elementos))+(queue->cola->tail % queue->cola->size), valor, queue->sizeTipo);
58.     valor = (void *)valor;
59.    
60.     printf("Guardado: %dn",*( ((char*)(queue->cola->elementos))+(queue->cola->tail)) );
61.     //printf("  ingresado en: %dn",queue->cola->tail % queue->cola->size);
62.    
63.     queue->cola->tail++;
64.     return TRUE;
65. }
66. boolean qGet(queue_t *queue, void *valor){
67.     if(qEmpty(queue))
68.         return FALSE;   //Esta vacia y no puedo ingresar nada
69.     /*
70.      * Resuelvo el problema de q los
71.      * indices crezcan hacia el infinito
72.      */
73.     if(queue->cola->head > queue->cola->size){
74.         queue->cola->head %= queue->cola->size;
75.         queue->cola->tail %= queue->cola->size;
76.     }
77.    
78.     memcpy(valor,((char *)(queue->cola->elementos))+(queue->cola->head % queue->cola->size), queue->sizeTipo);
79.    
80.     printf("Removido: %dn",*((char *)(queue->cola->elementos))+(queue->cola->head % queue->cola->size));
81.     //printf("en exa: %0xn",valor);
82.     //printf("  removido de: %dn",queue->cola->head % queue->cola->size);
83.    
84.     queue->cola->head++;
85.     return TRUE;
86. }
87.  
88.  
89. int main(void){
90.     queue_t *queue;
91.     int a = 15, b = 22, c,d;
92.  
93.     queue = qCreate(5,sizeof(int));
94.    
95.     qPut (queue,(void *)&a);
96.     qPut (queue,(void *)&b);
97.    
98.     printf("n");
99.    
100.     qGet(queue,(void *)&c);
101.     qGet(queue,(void *)&d);
102.    
103.     printf("n");
104.    
105.     printf("El primer valor que extraje fue : %dn",c);
106.     printf("Ese mismo valor mostrado antes pero casteado a (char) : %dn",(char)c);
107.    
108.     printf("el segundo valor que extraje fue: %dn",d);
109.    
110.    
111.     qDestroy(queue);
112.    
113.    
114.     return 0;
115. }
116.  
117.  

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!

Título: Re: Cola Generica
Publicado por: m0skit0 en Martes 14 de Octubre de 2008, 10:00

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

Título: Re: Cola Generica
Publicado por: Rombus en Martes 14 de Octubre de 2008, 15:39

uh buenisimo!

gracias moskito, espero tu respuesta :comp:

Título: Re: Cola Generica
Publicado por: EL_UNI en Jueves 16 de Octubre de 2008, 11:09

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 ^^

Título: Re: Cola Generica
Publicado por: Rombus en Jueves 16 de Octubre de 2008, 14:21

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

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

capaz se ve mejor de esta manera:

Código: C

1. queue->cola->elementos[queue->cola->tail % queue->cola->size]
2.  

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  :D) 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 :D


saludos!

Título: Re: Cola Generica
Publicado por: EL_UNI en Jueves 16 de Octubre de 2008, 14:35

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

1.  
2. struct cola_rep{
3.     void *datos;     //Vector de datos.
4.     int primero;     //Posicion del primer elemento. Inicialmente 0.
5.     int usados;      //Cantidad de elementos dentro de la cola.
6.     int tam;          //Tamaño de la cola.
7.     int tam_dato;  //Tamaño de los datos.
8. };
9.  
10.  

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

Código: C

1.  
2. int cola_gen_mete(cola_gen c,void *dato)
3. {
4.     if(!(cola_gen_llena(c))){
5.         memcpy(c->datos+((c->primero+c->usados++)%c->tam)*c->tam_dato,dato,c->tam_dato);
6.         return 0;
7.     }
8.     return -1;   //No se puede meter
9. };
10.  
11. int cola_gen_saca(cola_gen c,void *dato)
12. {
13.     if((cola_gen_vacia(c))){
14.         memcpy(dato,c->datos+(c->primero)*c->tam_dato,c->tam_dato);
15.         c->primero++;
16.         c->primero %= c->tam //Para que el valor de c->primero no se nos dispare se va actualizando
17.         c->usados--;
18.         return 0;
19.     }
20.     return -1;   //No se puede sacar
21. };
22.  
23.  

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

Título: Re: Cola Generica
Publicado por: Rombus en Jueves 16 de Octubre de 2008, 14:54

claro, es parcticamente lo mismo no?

si :D

tu haces:

Código: Text

1. c->datos+((c->primero+c->usados++)%c->tam
2.  

y el mio es:

Código: Text

1. (queue->cola->elementos))+(queue->cola->tail % queue->cola->size)
2.  

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!

Título: Re: Cola Generica
Publicado por: EL_UNI en Jueves 16 de Octubre de 2008, 15:02

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 ^^

Título: Re: Cola Generica
Publicado por: Rombus en Jueves 16 de Octubre de 2008, 15:12

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 :D


espero tus comentarios  :beer:

Título: Re: Cola Generica
Publicado por: EL_UNI en Jueves 16 de Octubre de 2008, 17:50

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

Código: C

1.  
2. void qDestroy(queue_t *queue){
3.     free(queue->cola);
4.     free(queue);
5. }  
6.  
7.  

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

1.  
2. void qDestroy(queue_t *queue){
3.     free(queue->cola);
4.     free(queue);
5.     queue = NULL;
6. }  
7.  
8.  

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

1.  
2. boolean qPut(queue_t *queue, void *valor){
3.     if(qFull(queue))
4.         return FALSE;   //Esta llena y no puedo ingresar nada
5.    
6.     memcpy(((queue->cola->elementos))+(queue->cola->tail % queue->cola->size)*queue->sizeTipo, valor, queue->sizeTipo);  
7.    
8.     queue->cola->tail++;
9.     return TRUE;
10. }
11.  
12.  

qGet:

Código: C

1.  
2. boolean qGet(queue_t *queue, void *valor){
3.     if(qEmpty(queue))
4.         return FALSE;   //Esta vacia y no puedo ingresar nada
5.     /*
6.      * Resuelvo el problema de q los
7.      * indices crezcan hacia el infinito
8.      */
9.     if(queue->cola->head > queue->cola->size){
10.         queue->cola->head %= queue->cola->size;
11.         queue->cola->tail %= queue->cola->size;
12.     }
13.    
14.     memcpy(valor,queue->cola->elementos+(queue->cola->head*queue->sizeTipo), queue->sizeTipo);
15.    
16.     queue->cola->head++;
17.     return TRUE;
18. }
19.  
20.  

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.

Título: Re: Cola Generica
Publicado por: Eternal Idol en Jueves 16 de Octubre de 2008, 18:08

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

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

Título: Re: Cola Generica
Publicado por: EL_UNI en Jueves 16 de Octubre de 2008, 18:11

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 :D

Título: Re: Cola Generica
Publicado por: Eternal Idol en Jueves 16 de Octubre de 2008, 18:14

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.

Título: Re: Cola Generica
Publicado por: Rombus en Jueves 16 de Octubre de 2008, 20:08

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

1. if(queue)
2.  

al haber hecho el queue = NULL no entraria :D


 :beer: gracias nuevamente!!


saludos ;)

Título: Re: Cola Generica
Publicado por: EL_UNI en Viernes 17 de Octubre de 2008, 15:21

De nada, para eso estamos ^^

Ya tienes un quebradero menos de cabeza xDD

Saludos. EL_UNI

Título: Re: Cola Generica
Publicado por: Eternal Idol en Viernes 17 de Octubre de 2008, 16:27

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

1. if(queue)
2.  

al haber hecho el queue = NULL no entraria :D

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).

Título: Re: Cola Generica
Publicado por: Rombus en Viernes 17 de Octubre de 2008, 16:35

ah!..


lo q dices es q deberia ser

Código: Text

1. void qDestroy(queue_t **queue)
2.  

para q tenga sentido la asignacion?

Título: Re: Cola Generica
Publicado por: Eternal Idol en Viernes 17 de Octubre de 2008, 17:51

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

Título: Re: Cola Generica
Publicado por: Rombus en Viernes 17 de Octubre de 2008, 18:28

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

1.  void qDestroy(queue_t *&queue){
2.      free((*queue)->cola);
3.      free( (*queue) );
4.     (*queue) = NULL;
5.  }
6.  

Título: Re: Cola Generica
Publicado por: Eternal Idol en Viernes 17 de Octubre de 2008, 19:01

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

Código: Text

1. void qDestroy(queue_t *&queue){
2.     free(queue->cola);
3.     free(queue);
4.     queue = NULL;
5. }
6.  

En C tenes que usar un doble puntero.

Título: Re: Cola Generica
Publicado por: Rombus en Viernes 17 de Octubre de 2008, 21:50

ah! por eso no lo habia visto jeje


uso C

al doble puntero entonces


saludos!