Autor
|
Tema: Primero en Entrar, primero en salir FIFO, Cola o Fila (Leído 3,462 veces)
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
No es lo mas eficiente, hay muchas cosas se podrian mejorar, en especifico la forma en la que se organizan el arreglo de elementos actuales en la Fila, sin embargo funciono para el proposito. Yo se que la mayoría de estas estructuras ya están implementadas. Pero no se puede decir que eres programador si no sabes implementarlas por tu cuenta. /* El tipo de dato se puede cambiar dependiendo de la implementación que se le quiera dar, también se tendrían que cambiar los tipos de datos devueltos por las funciones En este caso yo quería un arreglo de apuntadores char* por lo cual el contenedor es char** */ typedef struct str_queue { char **queue; int len; int max; }Queue; Queue *create_queue() { Queue *r = malloc(sizeof(struct str_queue )); r->len = 0; r->max = 2; r ->queue = malloc(sizeof(char*)*r ->max ); return r; } void free_queue(Queue *q) { if(q) { if(q->queue) } } void en_queue(Queue *q, char *ptr) { if((q->len+1) == q->max) { q->max *= 2; q ->queue = realloc(q ->queue ,q ->max *sizeof(char*)); } if(q->queue != NULL) { q->queue[q->len] = ptr; q->len++; } } char * de_queue(Queue *q) { char *r = NULL; int i = 0; if(q->len >= 1) { r = q->queue[0]; q->len--; while(i < q->len) { q->queue[i] = q->queue[i+1]; i++; } q->queue[i] = NULL; } return r; }
Yo en su momento lo utilize para un post, donde realizaba una versión iterativa y necesitaba almacenar en una Cola el listado de los directorios que aun faltaba por recorrer: problema de memoria con readdir (Solucionado)Ejemplo de uso: int main() { char *cadenas[10] = { "Cadena_0","Cadena_1","Cadena_2","Cadena_3","Cadena_4","Cadena_5","Cadena_6","Cadena_7","Cadena_8","Cadena_9"}; char *actual; int index1,index2,i =0; Queue *q = create_queue(); while(i < 10) { printf("Agregando a la fila: %s\n",cadenas [index1 ]); en_queue(q,cadenas[index1]); printf("Agregando a la fila: %s\n",cadenas [index2 ]); en_queue(q,cadenas[index2]); printf("Saliendo de la fila %s\n",de_queue (q )); i++; } free_queue(q); }
Como es randon la salida es variada, pero podemos observar el funcionamiento: Agregando a la fila: Cadena_5 Agregando a la fila: Cadena_5 Saliendo de la fila Cadena_5 Agregando a la fila: Cadena_8 Agregando a la fila: Cadena_2 Saliendo de la fila Cadena_5 Agregando a la fila: Cadena_5 Agregando a la fila: Cadena_7 Saliendo de la fila Cadena_8 Agregando a la fila: Cadena_8 Agregando a la fila: Cadena_7 Saliendo de la fila Cadena_2 Agregando a la fila: Cadena_9 Agregando a la fila: Cadena_2 Saliendo de la fila Cadena_5 Agregando a la fila: Cadena_1 Agregando a la fila: Cadena_3 Saliendo de la fila Cadena_7 Agregando a la fila: Cadena_8 Agregando a la fila: Cadena_5 Saliendo de la fila Cadena_8 Agregando a la fila: Cadena_0 Agregando a la fila: Cadena_3 Saliendo de la fila Cadena_7 Agregando a la fila: Cadena_4 Agregando a la fila: Cadena_0 Saliendo de la fila Cadena_9 Agregando a la fila: Cadena_7 Agregando a la fila: Cadena_1 Saliendo de la fila Cadena_2
Funcion actualizada de de_queue char * de_queue(Queue *q) { char *r = NULL; int i = 0; if(q->len >= 1) { r = q->queue[0]; q->len--; while(i < q->len) { q->queue[i] = q->queue[i+1]; i++; } q->queue[i] = NULL; } return r; }
|
|
« Última modificación: 2 Diciembre 2018, 04:43 am por AlbertoBSD »
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
Solo un detalle, en de_queue estás usando memcpy para mover el contenido de un vector sobre sí mismo. Cuando usas memcpy sobre dos buferes que se superponen (como en este caso) el comportamiento queda indefinido (puede que a veces funcione y otras no o puede depender del compilador...). Lo correcto en estos casos es utilizar memmove, que utiliza un bufer auxiliar y así evitar que la información del vector se pueda "machacar".
¡Saludos!
|
|
|
En línea
|
- Doctor, confundo los números y los colores. - Vaya marrón. - ¿Marrón? ¡Por el culo te la hinco!
|
|
|
CalgaryCorpus
|
Por qué free_queue dice que devuelve int y no devuelve valor alguno?
|
|
|
En línea
|
|
|
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
Solo un detalle, en de_queue estás usando memcpy para mover el contenido de un vector sobre sí mismo. Cuando usas memcpy sobre dos buferes que se superponen (como en este caso) el comportamiento queda indefinido (puede que a veces funcione y otras no o puede depender del compilador...). Lo correcto en estos casos es utilizar memmove, que utiliza un bufer auxiliar y así evitar que la información del vector se pueda "machacar".
¡Saludos!
Si me imagine que si la implementación empieza de alravez puede pasar eso, lo voy editar como mentas o en su defecto con una versión iterativa con while moviendo los elementos del buffer. char * de_queue(Queue *q) { char *r = NULL; int i = 0; if(q->len >= 1) { r = q->queue[0]; q->len--; while(i < q->len) { q->queue[i] = q->queue[i+1]; i++; } q->queue[i] = NULL; } return r; }
Por qué free_queue dice que devuelve int y no devuelve valor alguno?
Por mala practica de programación, viejo habito de declarar las funciones como int, cuando no he definido si van a retornar valor o no. En un momento corrijo el código. Saludos!
|
|
« Última modificación: 1 Diciembre 2018, 20:09 pm por AlbertoBSD »
|
En línea
|
|
|
|
CalgaryCorpus
|
O bien no estas compilando el codigo, o estas ignorando los warnings que se presentan y si no hay warnings, sugiero cambiar de compilador.
Linea 16, el prototipo de la funcion en_queue dice retornar int, pero la definicion, linea 34 establece void en el tipo de retorno.,
|
|
|
En línea
|
|
|
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
Gracias, si no lo compile, solo lo edite y se me olvido editar el prototipo.
Saludos
|
|
|
En línea
|
|
|
|
CalgaryCorpus
|
Te estas ganando innecesariamente un problema al poner los prototipos al lado de la implementacion. No tienen ningun uso alli, deberian estar al lado del main que usa las funciones o un en un header file aparte.
Por otro lado, estar pidiendo memoria y copiando el contenido de la cola todas las veces que insertas, y andar moviendo todos los elementos cada vez que borras parece ineficiente, especialmente a medida que la cola se use mas y mas,
Sugiero usar un buffer circular: No mueves los contenidos al borrar, y solo pides memoria al agregar si ya no queda espacio en el buffer, pero si lo hay solo se copia el contenido en algun lugar disponible. Solo es necesario pedir memoria y mover si el buffer esta lleno,
Por esa ultima razon, parece mejor pedir memoria en potencias de 2, o en algo mayor que 1 cada vez, para darle la oportunidad a la cola que o bien desocupe algunos espacios para las siguientes inserciones o bien haya algun espacio antes de pedir otra vez.
|
|
|
En línea
|
|
|
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
Por lo mismo lo dije: No es lo mas eficiente, hay muchas cosas se podrian mejorar, en especifico la forma en la que se organizan el arreglo de elementos actuales en la Fila, sin embargo funciono para el proposito.
Si claramente se puede manejar de mejor manera, me gusta lo de pedir memoria en potencias de 2, y lo del buffer Circular. Pidiendo memoria de 2 en 2, requiere cambios en la estructura, en la funcion de crear para inicializar con 2 espacios disponibles y en la funcion en_queue typedef struct str_queue { char **queue; int len; int max; }Queue; Queue *create_queue() { Queue *r = malloc(sizeof(struct str_queue )); r->len = 0; r->max = 2; r ->queue = malloc(sizeof(char*)*r ->max ); return r; } void en_queue(Queue *q, char *ptr) { if((q->len+1) == q->max) { q->max *= 2; printf("Tamanio actual %i\n",q ->max ); q ->queue = realloc(q ->queue ,q ->max *sizeof(char*)); } if(q->queue != NULL) { q->queue[q->len] = ptr; q->len++; } }
Saludos!
|
|
« Última modificación: 2 Diciembre 2018, 04:41 am por AlbertoBSD »
|
En línea
|
|
|
|
AlbertoBSD
Programador y
Moderador Global
Desconectado
Mensajes: 3.705
🏴 Libertad!!!!!
|
En teoría quedo esta versión, utilizando un buffer semi circular y creciendo la memoria en potencias de 2. Tiene muchos printf para depuración, y mostrar el funcionamiento. #include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> typedef struct str_queue { char **queue; int len; /* Las siguientes variales son para hacer mas eficiente la asignacion de memoria len_max indica el numero de espacios len_maximos reservados actualmente, este siempre esta en potencias de 2 offset indica cuantos espacios vacios hay al principio del arreglo, con el fin de no tener que reacomodar el arreglo con cada de-queue offset_max indica la cantidad cada cuantos movimientos se va a reorganizar la memoria. */ int len_max; int offset; int offset_max; }Queue; Queue *create_queue() { Queue *q = malloc(sizeof(struct str_queue )); q->len = 0; q->offset = 0; q->len_max = 2; q->offset_max = 1; q ->queue = malloc(sizeof(char*)*q ->len_max ); return q; } void free_queue(Queue *q) { if(q) { if(q->queue) } } void en_queue(Queue *q, char *ptr) { char **temp; int i; //printf("%i == %i ?\n",q->len,q->len_max); if( q->len == q->len_max) { q->len_max *= 2; //printf("%p -> ",q->queue); temp = q->queue; q ->queue = realloc(temp ,q ->len_max *sizeof(char*)); //printf("%p\n",q->queue); if(q->queue == NULL) { } else { printf("Tamanio actual %i\n",q ->len_max ); } } if(q->queue != NULL) { printf("q->queue[%i] <- %p\n",q ->len ,ptr ); q->queue[q->len] = ptr; q->len++; } } char * de_queue(Queue *q) { char *r = NULL; int i,j; if((q->len - q->offset) >= 1) { r = q->queue[q->offset]; printf("q->queue[%i] : %p -> out\n",q ->offset ,q ->queue [q ->offset ]); q->queue[q->offset] = NULL; q->offset++; if(q->offset == q->offset_max) { //printf("%i == %i\n",q->offset,q->offset_max); i = q->offset; j = 0; //printf("i:%i j:%i\n",i,j); while(i < q->len) { //printf("i:%i < q->len:%i\n",i,q->len); printf("q->queue[%i]: %p <- q->queue[%i]: %p\n",j ,q ->queue [j ],i ,q ->queue [i ]); q->queue[j] = q->queue[i]; q->queue[i] = NULL; j++; i++; } //printf("%i:q->len %i -= q->offset %i\n",(q->len-q->offset),q->len,q->offset); q->len -= q->offset; q->offset = 0; q->offset_max *=2; } } //printf("r: %p, %s\n",r,r); return r; } int main() { char *cadenas[10] = { "Cadena_0","Cadena_1","Cadena_2","Cadena_3","Cadena_4","Cadena_5","Cadena_6","Cadena_7","Cadena_8","Cadena_9"}; char *actual; int index1,index2,i =0; Queue *q = create_queue(); while(i < 1000) { //printf("Agregando a la fila: %p %s\n",cadenas[index1],cadenas[index1]); en_queue(q,cadenas[index1]); //printf("Agregando a la fila: %p %s\n",cadenas[index2],cadenas[index2]); en_queue(q,cadenas[index2]); de_queue(q); //printf("Saliendo de la fila %s\n",de_queue(q)); i++; } free_queue(q); }
Salidos!
|
|
|
En línea
|
|
|
|
CalgaryCorpus
|
Si haces el buffer circular, simplificaras el codigo, pues no necesitaras hacer copias en de_queue como lo haces ahora.
|
|
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
cola fifo
Programación C/C++
|
hbk50
|
1
|
3,624
|
3 Junio 2010, 19:17 pm
por Eternal Idol
|
|
|
Mi primero pograma en C!
Programación C/C++
|
barnix456
|
4
|
3,731
|
2 Mayo 2012, 05:22 am
por barnix456
|
|
|
Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor
Programación General
|
painkillerpucela
|
1
|
3,611
|
20 Noviembre 2012, 13:37 pm
por Oblivi0n
|
|
|
Cerrar segundo programa al salir del primero en batch?
Scripting
|
Dickzen
|
0
|
2,120
|
3 Febrero 2017, 05:35 am
por Dickzen
|
|
|
Primero murió su fundador y ahora aseguran que las billeteras del exchange ...
Noticias
|
wolfbcn
|
0
|
1,272
|
4 Marzo 2019, 15:09 pm
por wolfbcn
|
|