View
51
Download
3
Category
Preview:
DESCRIPTION
Cola con Punteros
Citation preview
ColasImplementadas con Punteros
Algoritmos y Estructuras de Datos II
Lic. Ana María Company
Qué es una Cola?
Es una lista en la que las inserciones se realizan por un
extremo(final) y las eliminaciones se realizan por el
otro extremo (principio de la lista o frente).
También se llaman listas FIFO, del inglés First-In-
First-Out, es decir, el primero en entrar es el primero
en salir
Definición del tipo Lista
Las colas podrían definirse siguiendo la misma definición de
las listas, pero para algunas operaciones resulta ineficiente.
Entonces, podemos utilizar una definición que considera a
una cola como un par de punteros:type
tElem = char; {o lo que corresponda}
tApNodo = ^tNodoCola;
tNodoCola = record
contenido: tElem;
siguiente: tApNodo
end; {tNodoCola}
tCola = record
principio: tApNodo;
final: tApNodo
end; {tCola}
Operaciones básicas sobre colas I
Creación de una cola vacía
ColaVacía
Consulta del primer elemento
Añadir un elemento
Suprimir el primer elemento
Operaciones básicas sobre colas II
Creación de una cola vacía
Solo debemos iniciar a nil los campos principio y final delregistro.
ColaVacía
Es conveniente considerar una lista vacía a aquella cuyo punterofinal tiene el valor nil ; sólo es necesario evaluar la expresiónlógica cola.final = nil.
Consulta del primer elemento
Esta operación es idéntica a Cima de una pila, ya que nosinteresa el contenido del primer nodo de la cola.
Operaciones básicas sobre colas III
Añadir un elemento
si cola no está vacía:
Crear y dar valores al nuevoNodo
Actualizar los punteros y el final de cola
en otro caso
Crear y dar valores al nuevoNodo
Actualizar principio y final de cola
Operaciones básicas sobre colas IV
Suprimir el primer elemento
tenemos que considerar dos casos distintos:
1. Que la cola sea unitaria, pues al sacar su único
elemento se queda vacía, por lo tanto hay que
actualizar tanto su principio como su final.
2. Que la cola tenga longitud mayor o igual a dos, en
cuyo caso sólo hay que actualizar el campo
principio.
Ejercicio de ejemplo I{
Ejercicio colas - Operaciones básicas
sobre colas
}
program colas;
uses crt;
type
tElem = String;
tApNodo = ^tNodoCola;
tNodoCola = record
contenido: tElem;
siguiente: tApNodo
end;
tCola = record
principio: tApNodo;
final: tApNodo
end;
var
vc_cola:tCola;
procedure CrearCola(var cola: tCola);
begin
cola.principio:= nil;
cola.final:= nil
end;
function colaVacia(var cola:tCola):Boolean;
begin
if cola.final =nil then
colaVacia := true
else
colaVacia := false;
end;
function primerElemento(var cola:tApNodo):tElem;
begin
primerElemento:= cola^.contenido;
end;
Ejercicio de ejemplo IIprocedure PonerEnCola(dato: tElem; var cola: tCola);
var
nuevoNodo: tApNodo;
begin
New(nuevoNodo);
nuevoNodo^.contenido:= dato;
nuevoNodo^.siguiente:= nil;
if cola.final <> nil then
begin
{Si la cola no está vacía se
actualizan los punteros}
cola.final^.siguiente:=
nuevoNodo;
cola.final:= nuevoNodo
end
else
begin
{Actualización de punteros}
cola.principio:=
nuevoNodo;
cola.final:= nuevoNodo
end
end;
procedure SacarDeCola(var cola: tCola);
var
apuntaAux : tApNodo;
begin
if cola.principio = cola.final then
begin
{La cola es unitaria}
apuntaAux:= cola.principio;
Dispose(apuntaAux);
cola.principio:= nil;
cola.final:= nil
end
else
begin
{Si Longitud(cola) >= 2}
apuntaAux:= cola.principio;
cola.principio:=
apuntaAux^.siguiente;
Dispose(apuntaAux)
end
end;
Ejercicio de ejemplo IIIprocedure MostrarCola(cola: tCola);
var
apuntaAux: tApNodo;
begin
if cola.final= nil then
WriteLn('Cola vacía')
else
begin
apuntaAux:= cola.principio;
while apuntaAux <> nil do
begin
Write(apuntaAux^.contenido);
write(' ');
apuntaAux:=
apuntaAux^.siguiente
end;
end
end;
{Programa principal}
BEGIN
CrearCola(vc_cola);
PonerEnCola('Primero', vc_cola);
PonerEnCola('Segundo', vc_cola);
PonerEnCola('Tercero', vc_cola);
MostrarCola(vc_cola);
SacarDeCola(vc_cola);
writeln();
MostrarCola(vc_cola);
writeln();
END.
Bibliografía Mark Allen Weiss - Estructuras de Datos y Algoritmos - Florida
International University - Año: 1995 - Editorial: Addison-WesleyIberoamericana .
Joyanes Aguilar, Luis - Programación en Pascal - 4ª Edición - Año: 2006 -Editorial: McGraw-Hill/Interamericana de España, S.A.U.
Cristóbal Pareja Flores, Manuel Ojeda Aciego, Ángel Andeyro Quesada, Carlos Rossi Jiménez - Algoritmos y Programación en Pascal.
Joyanes Aguilar, Luis - Fundamentos de la Programación. Algoritmos, Estructuras de Datos y Objetos - 3ª Edición - Editorial: McGraw-Hill
Recommended