guia-13
DESCRIPTION
Colas de PrioridadTRANSCRIPT
1
Tema: Colas de Prioridad.
Definir brevemente el concepto de cola.
Implementar la estructura de datos cola en C #.
Implementar la estructura de datos cola de prioridad en C #.
Guía Número 13.
Computadora con programa Microsoft Visual C#.
Cola.
Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la
que la operación de inserción se realiza por un extremo y la operación de extracción por el otro.
También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer
elemento en entrar será también el primero en salir.
Las operaciones básicas de una cola son las siguientes.
1. Crear cola vacía.
2. Encolar: Insertar elemento al final de la cola.
3. Frente: Ver el primer elemento de la cola.
Facultad: Ingeniería
Escuela: Computación
Asignatura: Programación III
Objetivos Específicos
Materiales y Equipo
Introducción
Teórica
Programación III. Guía 13
4. Desencolar: Sacar y devolver el primer elemento de la cola.
Además se pueden agregar otras operaciones las cuales serían un conjunto de las operaciones
anteriores:
Verificar si la cola esta vacía.
Mostrar cola.
Colas de prioridad.
Las colas de prioridad es una extensión de la estructura de datos Cola. Se basan en el orden de
salida de sus elementos: en el orden de llegada y orden de prioridad; asi un elemento que
ingresa a la cola se posicionará al final del segmento de elementos de su misma prioridad.
Las colas de prioridad permiten alterar el orden de salida de los elementos de una cola:
no es necesario seguir un orden FIFO.
el orden se puede basar en una función de comparación.
Las operaciones de las colas de prioridad son las mismas que las de las colas con un
comportamiento diferente.
Una cola de prioridad es una cola a cuyos elementos se les ha asignado una prioridad, de
forma que el orden en que los elementos son procesados sigue las siguientes reglas:
El elemento con mayor prioridad es procesado primero.
Dos elementos con la misma prioridad son procesados según el orden en que fueron
introducidos en la cola.
Así, si tenemos que la prioridad más alta es 0, y la más baja es 3, la estructura se vería así:
La cola de prioridad cuenta con las mismas rutinas que la estructura de cola genérica, con la
salvedad que al encolar elementos y desencolar elementos se debe de tomar en cuenta su
prioridad para su posicionamiento.
Algunas aplicaciones de las colas de prioridad.
3
Gestión de procesos en un sistema operativo. Los procesos no se ejecutan uno tras otro en
base a su orden de llegada. Algunos procesos deben tener prioridad (por su mayor importancia,
por su menor duración, etc.) sobre otros.
Implementación de algoritmos voraces, los cuales proporcionan soluciones globales a
problemas basándose en decisiones tomadas sólo con información local. La determinación de
la mejor opción local suele basarse en una cola de prioridad.
Algunos algoritmos sobre grafos, como la obtención de caminos o árboles de expansión de
mínimo coste, son ejemplos representativos de algoritmos voraces basados en colas de
prioridad.
Ejemplo 1. Implementaremos una cola genérica en C#:
1. Crear un proyecto de consola y nombrarlo “colas”.
2. Agregar las clases “nodo” y “cola” al namespace “colas”
Clase Nodo:
Clase Cola:
Clase Cola:
Procedimien
to
Bibliografí
a
Guía 1
class Nodo { public int info;
public nodo sgte; }
class Cola { public Nodo primero;
public Nodo ultimo; public Cola( ) { primero = null;
ultimo = null; } public void encolar(int valor) { Nodo aux = new Nodo();
aux.info = valor; if(primero == null) //si cola esta vacia { primero = aux;
ultimo = aux; aux.sgte = null;
}
else //si cola no esta vacia { ultimo.sgte = aux;
aux.sgte = null; ultimo = aux;
} } public void desencolar( ) { if (primero == null)
Console.WriteLine("Cola vacia"); else { primero = primero.sgte; }
} public int desencolarValor( ) { int valor = 0;
if(primero == null) //si cola esta vacia Console.WriteLine("Cola vacia");
else //si cola no esta vacia { valor = primero.info;
primero = primero.sgte; } return valor;
}
public void Mostrar( ) { if (primero == null)
Console.WriteLine("Cola vacia"); else { Nodo puntero;
puntero = primero; do { Console.WriteLine("{0}\t", puntero.info);
puntero = puntero.sgte; } while(puntero != null); }
} } // Fin de la clase Cola
5
3. Sustituir la función “Main” del proyecto con el siguiente código de prueba:
4. Ejecutar el proyecto y ver sus resultados.
1. Desarrollar en una interfaz gráfica de formulario (Windows Forms) para la implementación de
las clases nodo y cola.
2. Modifique las clases nodo y cola para implementar una cola de prioridad (en una interfaz
gráfica de formulario (Windows Forms)).
Análisis de resultados
Investigación
Complementaria
Guía 3
Guía 4
public static void Main( ) { Cola micola = new Cola( );
Console.WriteLine("Colocando 5 elementos en la cola...");
micola.encolar(11);
micola.encolar(12); micola.encolar(13); micola.encolar(14); micola.encolar(15); micola.Mostrar( ); Console.WriteLine("Retirando 2 elementos de la cola..."); micola.desencolar( ); micola.desencolar( ); micola.Mostrar( ); Console.WriteLine("Se retiro el elemento:{0}", micola.desencolarValor( )); micola.Mostrar( ); Console.ReadLine( );
}
Para la siguiente semana:
En una unidad de emergencia, se atienden personas lesionadas tomando en cuenta el orden de
llegada y la gravedad de la lesión.
Implemente una solución en software (usando colas de prioridad y una interfaz gráfica de
formulario (Windows Forms)) que lleve un orden de atención para los pacientes, teniendo en
cuenta las siguientes condiciones:
a) Entrada de pacientes: selección de la gravedad de la lesión e ingreso del paciente a la
cola tomando como datos: nombre del paciente, la gravedad de la lesión y descripción
de la lesión.
b) Visualización de cola de pacientes: visualizar el orden de atención de los pacientes
detallando la gravedad de las lesiones.
c) Atención de paciente: se descarga al paciente de la cola mostrando los datos
recogidos en la “Entrada de pacientes” para su atención inmediata.
7
EVALUACIÓN
% 1-4 5-7 8-10 Nota
CONOCIMIENTO
Del 20
al 30%
Conocimiento
deficiente
de los
fundamentos
teóricos
Conocimiento
y explicación
incompleta de
los
fundamentos
teóricos
Conocimiento
completo y
explicación
clara de los
fundamentos
teóricos
APLICACIÓN
DEL
CONOCIMIENTO
Del 40%
al 60%
ACTITUD
Del 15%
al 30%
No tiene
actitud
proactiva.
Actitud
propositiva y
con
propuestas no
aplicables al
contenido de
la guía.
Tiene actitud
proactiva y
sus propuestas
son concretas.
TOTAL 100%