elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Primero en Entrar, primero en salir FIFO, Cola o Fila		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Primero en Entrar, primero en salir FIFO, Cola o Fila  (Leído 3,495 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Primero en Entrar, primero en salir FIFO, Cola o Fila
« en: 30 Noviembre 2018, 18:38 pm »
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.



Código
  1. /*
  2.  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
  3.  En este caso yo quería un arreglo de apuntadores char* por lo cual el contenedor es char**
  4.  */
  5.  
  6.  
  7. typedef struct str_queue	{
  8. 	char **queue;
  9. 	int len;
  10. 	int max;
  11. }Queue;	
  12.  
  13. Queue *create_queue()	{
  14. 	Queue *r = malloc(sizeof(struct str_queue));
  15. 	r->len = 0;
  16. 	r->max = 2;
  17. 	r->queue = malloc(sizeof(char*)*r->max);
  18. 	return r;
  19. }
  20.  
  21. void free_queue(Queue *q)	{
  22. 	if(q)	{
  23. 		if(q->queue)
  24. 			free(q->queue);
  25. 		free(q);
  26. 	}
  27. }
  28.  
  29. void en_queue(Queue *q, char *ptr)	{
  30. 	if((q->len+1) == q->max)	{
  31. 		q->max *= 2;
  32. 		q->queue = realloc(q->queue,q->max*sizeof(char*));	
  33. 	}
  34. 	if(q->queue != NULL)	{
  35. 		q->queue[q->len] = ptr;
  36. 		q->len++;
  37. 	}
  38. }
  39.  
  40. char * de_queue(Queue *q)	{
  41. 	char *r = NULL;
  42. 	int i = 0;
  43. 	if(q->len >= 1)	{
  44. 		r = q->queue[0];
  45. 		q->len--;
  46. 		while(i < q->len)	{
  47. 			q->queue[i] = q->queue[i+1];
  48. 			i++;
  49. 		}
  50. 		q->queue[i] = NULL;
  51. 	}
  52. 	return r;
  53. }

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:

Código
  1. int main()	{
  2. 	char *cadenas[10] = { "Cadena_0","Cadena_1","Cadena_2","Cadena_3","Cadena_4","Cadena_5","Cadena_6","Cadena_7","Cadena_8","Cadena_9"};
  3. 	char *actual;
  4. 	int index1,index2,i =0;
  5. 	srand(time(NULL));
  6. 	Queue *q = create_queue();
  7. 	while(i < 10)	{
  8. 		index1 = rand() % 10;
  9. 		index2 = rand() % 10;
  10. 		printf("Agregando a la fila: %s\n",cadenas[index1]);
  11. 		en_queue(q,cadenas[index1]);
  12. 		printf("Agregando a la fila: %s\n",cadenas[index2]);
  13. 		en_queue(q,cadenas[index2]);
  14. 		printf("Saliendo de la fila %s\n",de_queue(q));
  15. 		i++;
  16. 	}
  17. 	free_queue(q);
  18. }
  19.  

Como es randon la salida es variada, pero podemos observar el funcionamiento:



Código:
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

Código
  1. char * de_queue(Queue *q)	{
  2. 	char *r = NULL;
  3. 	int i = 0;
  4. 	if(q->len >= 1)	{
  5. 		r = q->queue[0];
  6. 		q->len--;
  7. 		while(i < q->len)	{
  8. 			q->queue[i] = q->queue[i+1];
  9. 			i++;
  10. 		}
  11. 		q->queue[i] = NULL;
  12. 	}
  13. 	return r;
  14. }
  15.  
« Última modificación: 2 Diciembre 2018, 04:43 am por AlbertoBSD » En línea
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #1 en: 1 Diciembre 2018, 16:56 pm »
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


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #2 en: 1 Diciembre 2018, 17:04 pm »
Por qué free_queue dice que devuelve int y no devuelve valor alguno?
En línea
Aqui mi perfil en LinkedIn, invitame un cafe aqui
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #3 en: 1 Diciembre 2018, 20:02 pm »
Cita de: do-while en  1 Diciembre 2018, 16:56 pm
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.

Código
  1. char * de_queue(Queue *q)	{
  2. 	char *r = NULL;
  3. 	int i = 0;
  4. 	if(q->len >= 1)	{
  5. 		r = q->queue[0];
  6. 		q->len--;
  7. 		while(i < q->len)	{
  8. 			q->queue[i] = q->queue[i+1];
  9. 			i++;
  10. 		}
  11. 		q->queue[i] = NULL;
  12. 	}
  13. 	return r;
  14. }
  15.  

Cita de: CalgaryCorpus en  1 Diciembre 2018, 17:04 pm
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


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #4 en: 1 Diciembre 2018, 22:41 pm »
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
Aqui mi perfil en LinkedIn, invitame un cafe aqui
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #5 en: 1 Diciembre 2018, 23:07 pm »
Gracias, si no lo compile, solo lo edite y se me olvido editar el prototipo.

Saludos
En línea
CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #6 en: 1 Diciembre 2018, 23:38 pm »
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
Aqui mi perfil en LinkedIn, invitame un cafe aqui
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #7 en: 1 Diciembre 2018, 23:49 pm »
Por lo mismo lo dije:

Cita de: AlbertoBSD en 30 Noviembre 2018, 18:38 pm
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

Código
  1. typedef struct str_queue	{
  2. 	char **queue;
  3. 	int len;
  4. 	int max;
  5. }Queue;
  6.  
  7. Queue *create_queue()	{
  8. 	Queue *r = malloc(sizeof(struct str_queue));
  9. 	r->len = 0;
  10. 	r->max = 2;
  11. 	r->queue = malloc(sizeof(char*)*r->max);
  12. 	return r;
  13. }
  14.  
  15. void en_queue(Queue *q, char *ptr)	{
  16. 	if((q->len+1) == q->max)	{
  17. 		q->max *= 2;
  18. 		printf("Tamanio actual %i\n",q->max);
  19. 		q->queue = realloc(q->queue,q->max*sizeof(char*));	
  20. 	}
  21. 	if(q->queue != NULL)	{
  22. 		q->queue[q->len] = ptr;
  23. 		q->len++;
  24. 	}
  25. }
  26.  

Saludos!
« Última modificación: 2 Diciembre 2018, 04:41 am por AlbertoBSD » En línea
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #8 en: 2 Diciembre 2018, 22:50 pm »
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.

Código
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<time.h>
  5.  
  6. typedef struct str_queue	{
  7. 	char **queue;
  8. 	int len;
  9. 	/*
  10. 		Las siguientes variales son para hacer mas eficiente la asignacion de memoria
  11. 		len_max indica el numero de espacios len_maximos reservados actualmente, este siempre esta en potencias de 2
  12. 		offset indica cuantos espacios vacios hay al principio del arreglo, con el fin de no tener que reacomodar el arreglo con cada de-queue
  13. 		offset_max indica la cantidad cada cuantos movimientos se va a reorganizar la memoria.
  14. 	*/
  15. 	int len_max;
  16. 	int offset;
  17. 	int offset_max;
  18. }Queue;	
  19.  
  20. Queue *create_queue()	{
  21. 	Queue *q = malloc(sizeof(struct str_queue));
  22. 	q->len = 0;
  23. 	q->offset = 0;
  24. 	q->len_max = 2;
  25. 	q->offset_max = 1;
  26. 	q->queue = malloc(sizeof(char*)*q->len_max);
  27. 	return q;
  28. }
  29.  
  30. void free_queue(Queue *q)	{
  31. 	if(q)	{
  32. 		if(q->queue)
  33. 			free(q->queue);
  34. 		free(q);
  35. 	}
  36. }
  37.  
  38. void en_queue(Queue *q, char *ptr)	{
  39. 	char **temp;
  40. 	int i;
  41. 	//printf("%i == %i ?\n",q->len,q->len_max);
  42. 	if( q->len == q->len_max)	{
  43. 		q->len_max *= 2;
  44. 		//printf("%p -> ",q->queue);
  45. 		temp = q->queue;
  46. 		q->queue = realloc(temp,q->len_max*sizeof(char*));
  47. 		//printf("%p\n",q->queue);
  48.  
  49. 		if(q->queue == NULL)	{
  50. 			fprintf(stderr,"error realloc\n");
  51. 		}
  52. 		else	{
  53. 			printf("Tamanio actual %i\n",q->len_max);
  54. 		}
  55. 	}
  56. 	if(q->queue != NULL)	{
  57. 		printf("q->queue[%i] <- %p\n",q->len,ptr);
  58. 		q->queue[q->len] = ptr;
  59. 		q->len++;
  60. 	}
  61. }
  62.  
  63. char * de_queue(Queue *q)	{
  64. 	char *r = NULL;
  65. 	int i,j;
  66. 	if((q->len - q->offset) >= 1)	{
  67. 		r = q->queue[q->offset];
  68. 		printf("q->queue[%i] : %p -> out\n",q->offset,q->queue[q->offset]);
  69. 		q->queue[q->offset] = NULL;
  70. 		q->offset++;
  71. 		if(q->offset == q->offset_max)	{
  72. 			//printf("%i == %i\n",q->offset,q->offset_max);
  73. 			i = q->offset;
  74. 			j = 0;
  75. 			//printf("i:%i  j:%i\n",i,j);
  76. 			while(i < q->len)	{
  77. 				//printf("i:%i < q->len:%i\n",i,q->len);
  78. 				printf("q->queue[%i]: %p  <- q->queue[%i]: %p\n",j,q->queue[j],i,q->queue[i]);
  79. 				q->queue[j] = q->queue[i];
  80. 				q->queue[i] = NULL;
  81. 				j++;
  82. 				i++;
  83. 			}
  84. 			//printf("%i:q->len %i -= q->offset %i\n",(q->len-q->offset),q->len,q->offset);
  85. 			q->len -= q->offset;
  86. 			q->offset = 0;
  87. 			q->offset_max *=2;
  88. 		}
  89. 	}
  90. 	//printf("r: %p, %s\n",r,r);
  91. 	return r;
  92. }
  93.  
  94. int main()	{
  95. 	char *cadenas[10] = { "Cadena_0","Cadena_1","Cadena_2","Cadena_3","Cadena_4","Cadena_5","Cadena_6","Cadena_7","Cadena_8","Cadena_9"};
  96. 	char *actual;
  97. 	int index1,index2,i =0;
  98. 	srand(time(NULL));
  99. 	Queue *q = create_queue();
  100. 	while(i < 1000)	{
  101. 		index1 = rand() % 10;
  102. 		index2 = rand() % 10;
  103. 		//printf("Agregando a la fila: %p %s\n",cadenas[index1],cadenas[index1]);
  104. 		en_queue(q,cadenas[index1]);
  105. 		//printf("Agregando a la fila: %p %s\n",cadenas[index2],cadenas[index2]);
  106. 		en_queue(q,cadenas[index2]);
  107. 		de_queue(q);
  108. 		//printf("Saliendo de la fila %s\n",de_queue(q));
  109. 		i++;
  110. 	}
  111. 	free_queue(q);
  112. }
  113.  

Salidos!
En línea
CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
« Respuesta #9 en: 3 Diciembre 2018, 00:01 am »
Si haces el buffer circular, simplificaras el codigo, pues no necesitaras hacer copias en de_queue como lo haces ahora.
En línea
Aqui mi perfil en LinkedIn, invitame un cafe aqui
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
cola fifo
Programación C/C++ 		hbk50 1 3,627 Último mensaje 3 Junio 2010, 19:17 pm
por Eternal Idol
Mi primero pograma en C!
Programación C/C++ 		barnix456 4 3,736 Último mensaje 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,624 Último mensaje 20 Noviembre 2012, 13:37 pm
por Oblivi0n
Cerrar segundo programa al salir del primero en batch?
Scripting 		Dickzen 0 2,141 Último mensaje 3 Febrero 2017, 05:35 am
por Dickzen
Primero murió su fundador y ahora aseguran que las billeteras del exchange ...
Noticias 		wolfbcn 0 1,295 Último mensaje 4 Marzo 2019, 15:09 pm
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines