Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: ank3r en 13 Mayo 2014, 16:08 pm



Título: C - Implementar cola de prioridades
Publicado por: ank3r en 13 Mayo 2014, 16:08 pm
Me gustaría implementar una cola en la que ingreso elementos y los acomodo en la misma aplicando una función que en definitiva devuelve un número para cada elemento, compara y el menor va primero.

Los elementos que ingreso son estructuras, y la función que aplico para saber la prioridad de estos utiliza los distintos valores de la estructura, pero eso es lo de menos. Me gustaría saber cómo implementar esta cola: ir ingresando elementos (que son estructuras) de forma ordenada según la prioridad.

No busco que codifiquen todo, puede ser un pseudo-código para entender el mecanismo, porque yo sé crear una cola, hacer push, pop, eliminar etc.. sólo quiero saber como ingresar ordenado por prioridad


Título: Re: C - Implementar cola de prioridades
Publicado por: eferion en 13 Mayo 2014, 16:20 pm
Podrías tener una lista enlazada o un árbol.

En el caso de la lista, las estructuras van todas en orden, una detrás de otra... luego para añadir un elemento en su posición concreta es tan sencillo como recorrer la lista hasta encontrar su posición e insertar ahí el elemento.

Código
  1. // Ejemplo de una estructura preparada para gestionar listas enlazadas
  2. struct nodo
  3. {
  4.  int valor;
  5.  struct nodo* siguiente; // puntero al siguiente elemento de la lista, null si es el ultimo.
  6. };

En el caso de los árboles, la estructura lógica se complica ligeramente. Cada nodo tiene dos punteros, uno en el que se encuentran los nodos más pequeños y otro para los nodos más grandes.

Si no hace falta balancear el árbol, el proceso para rellenar el árbol es bastante sencillo.

Código
  1. // Ejemplo de una estructura preparada para ser utilizada en arboles
  2. struct nodo
  3. {
  4.  int valor;
  5.  struct nodo* izquierdo; // puntero a nodos de menor valor
  6.  struct nodo* derecho; // puntero a nodos de mayor valor
  7. };

Cada una de estas dos opciones tiene su teoría y sus trucos por detrás, echa un vistazo por internet y verás que información no te va a faltar. Si te escribiese aquí todo lo relacionado sobre el tema más de uno acababa dormido :)

Un saludo.