Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de...
-
Upload
hoangthien -
Category
Documents
-
view
219 -
download
1
Transcript of Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de...
![Page 1: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/1.jpg)
Universidad de ValladolidDepartamento de informática
Campus de Segovia
Estructura de datosTema 3:El TAD Lista lineal
Prof. Montserrat Serrano Montero
![Page 2: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/2.jpg)
ÍNDICE
• El TAD lista lineal• Implementación con estructuras estáticas• Implementación con variables dinámicas• El TAD lista enlazada• Operaciones para lista enlazada ordenada
![Page 3: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/3.jpg)
EL TAD LISTA LINEAL
• Conjunto de valores:
- Una lista es una secuencia elementos de undeterminado tipo ⇒ la lista es homogénea.
(a1, a2, a3, ..., an) donde n ≥ 0,si n = 0, la lista es vacía.
- Los elementos de una lista tienen la propiedad de estar ordenados de forma lineal, según las posiciones que ocupan.
ai precede a ai+1 para i = 1, 2, 3, ..., n-1ai sucede a ai-1 para i = 2, 3, 4, ..., n
(significa que cada elemento tiene un único predecesor, excepto el primero, y un único sucesor, excepto el último)
![Page 4: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/4.jpg)
EL TAD LISTA LINEAL
• Observaciones:
- La lista es una estructura dinámica desde el punto de vista lógico, ya que su longitud dependerá del número de elementos que tenga, aumentará al insertar y se reducirá al suprimir.
- El TAD lista puede implementarse de formas estática o dinámica.
- Igualmente, considerar las operaciones básicas depende de:a) La implementación elegida para las listas b) El problema que se va a resolver.
![Page 5: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/5.jpg)
EL TAD LISTA LINEAL• Especificación informal: Sintaxis Semántica
TAD lista (VALORES: secuencia de elementos; OPERACIONES: Inicia, Localiza, Recupera, Inserta, SuprimeDir, Modifica)
Modifica (Lista, Posicion, Elemento) → ListaEfecto: Devuelve la lista con el nuevo Elemento en la Posición especificada.Excepciones: Que la Posición no sea un índice de la Lista, que la Lista sea vacía.
SuprimeDir (Lista, Posicion) → ListaEfecto: Devuelve la lista sin el elemento de la Posición especificada.Excepciones: Que la posición no sea un índice de la Lista, que la Lista sea vacía.
Inserta (Lista, Posición, Elemento) → ListaEfecto: Devuelve la Lista después de añadir el Elemento en la Posición.Excepciones: Que la posición no sea un índice de la Lista, que la Lista esté llena.
Recupera (Lista, Posición) → ElementoEfecto: Devuelve el Elemento que está en la Posición.Excepción: Que la posición no sea un índice de la Lista.
Localiza (Lista, Elemento) → PosicionEfecto: Devuelve la posición donde está el Elemento de la Lista. Si no está, devuelve nulo.
Inicia (Lista) → ListaEfecto: Devuelve una lista vacía.
![Page 6: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/6.jpg)
EL TAD LISTA LINEAL
• Especificación formal:
TAD lista (VALORES: secuencia de elementos; OPERACIONES:Inicia, Localiza, Recupera, Inserta, SuprimeDir, Modifica)Sintaxis:
*Inicia (Lista ) → ListaLocaliza (Lista, Elemento) → PosicionRecupera (Lista, Posicion) → Elemento
*Inserta (Lista, Posicion, Elemento) → ListaSuprimeDir (Lista, Posicion) → ListaModifica (Lista, Posicion, Elemento) → ListaSemántica:SuprimeDir (Inicia (Lista )) ⇒ errorSuprimeDir (Inserta (L, P, E), P) ⇒ LModifica (Inicia (Lista ), P, E) ⇒ errorModifica (Inserta (L, P, E), P, E1) ⇒Inserta (L,P,E1)
* Constructores
![Page 7: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/7.jpg)
TAD E IMPLEMENTACIÓN
• En este punto hay que marcar la distinción entre un TAD y la naturaleza de su implementación.
• Ambos conceptos pueden considerarse de forma estática o dinámica.
Ej: 1. Una variable de tipo array es una estructura estática, pero puede almacenarse en memoria de forma estática (declarada en la zona de declaración de variables) o de forma dinámica (variables dinámicas). 2. Una pila o una lista son por naturaleza dinámicas pero pueden implementarse con asignación de memoria estática (dentro de un array) o con asignación de memoria dinámica (variables dinámicas y punteros).
![Page 8: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/8.jpg)
IMPLEMENTACIÓN ESTÁTICA
unit LEstatic;interfaceconst Max = ...; {especifica tamaño máximo lista}type
tInfo = ...;{tipo de campo de información lista}Lista = record
Elementos: array [1..Max] of tInfo;Ultimo: integer
end;Posicion = 0 .. Max;
procedure Inicia (var L: Lista);function Localiza (L: Lista; E: tInfo): Posicion;procedure Recupera (L: Lista; P:Posicion; var E: tInfo);procedure Inserta (var L: Lista; P:Posicion; E: tInfo);procedure SuprimeDir (var L: Lista; P: Posicion);procedure Modifica (var L: Lista; P: Posicion; E: tInfo);
![Page 9: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/9.jpg)
IMPLEMENTACIÓN ESTÁTICA
implementationprocedure Inicia;beginL.Ultimo := 0
end;function Localiza;var Q: Posicion; Lc: boolean;beginQ := 1; Lc := false;while (Q <= L.Ultimo) and not Lc dobegin
Lc := L.Elementos [Q] = E;if not Lc then Q := Q + 1
end;if Lc then Localiza := Qelse Localiza := 0
end;
![Page 10: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/10.jpg)
IMPLEMENTACIÓN ESTÁTICAimplementation (continúa...)
procedure Error (n: integer); {procedimiento oculto que sólo se ve en el módulo}begin
case n of1: writeln (‘Error: posición no existe’);2: writeln (‘Error: lista llena. No se pueden
añadir elementos);3: writeln (‘Error: lista vacía. No se pueden
suprimir o modificar elementos’);end; {case}readln {Pausa}
end;procedure Recupera;
beginif (P > L.Ultimo) or (P < 1) then Error (1)else E := L.Elementos [P]end;
![Page 11: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/11.jpg)
IMPLEMENTACIÓN ESTÁTICAimplementation (continúa...)procedure Inserta;var Q: Posicion;beginif L.Ultimo = Max then Error (2)else if (P > L.Ultimo) or (P < 1) then Error (1)
else beginfor Q := L.Ultimo downto P do
L.Elementos [Q + 1] := L.Elementos [Q] ;L.Ultimo := L.Ultimo + 1;L.Elementos [P] := E
endend;procedure Suprime;var Q: Posicion;beginif L.Ultimo = 0 then Error (3)else if (P > L.Ultimo) or (P < 1) then Error (1)
else beginL.Ultimo := L.Ultimo – 1;for Q := P to L.Ultimo do
L.Elementos [Q] := L.Elementos [Q+1]end
end;
![Page 12: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/12.jpg)
IMPLEMENTACIÓN ESTÁTICAimplementation (continúa...)
procedure Modifica;beginif L.Ultimo = 0 then Error (3)else if (P > L.Ultimo) or (P < 1) then Error (1)
elseL.Elementos [P] := E
end;end.
![Page 13: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/13.jpg)
IMPLEMENTACIÓN DINÁMICA
• Las desventajas de la implementación anterior son:a) Estructura rígida. Inserción y supresión desplazando el resto del array.b) No se utiliza de forma óptima la memoria. Hay que reservar espacio en memoria para toda la estructura durante toda la ejecución.
• Estos inconvenientes pueden solucionarse utilizando variables dinámicas.
• Los elementos de la lista dinámica se definen como datos de tipo registro con, al menos, dos componentes:1. Almacén del dato de la lista.2. Puntero, que almacena la posición de memoria del siguiente elemento de la lista o nil si es el último elemento.
![Page 14: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/14.jpg)
EL TAD LISTA ENLAZADA
• Una lista dinámica simple se llama lista enlazada. Cada uno de los elementos de una lista dinámica se llaman nodos.
• El número de nodos puede variar rápidamente en un proceso, aumentando por inserción de nodos o disminuyendo por supresión de nodos.
• Una lista enlazada es aquella en la que el orden de las componentes se determina mediante un campo enlace explícito en cada nodo.
• Las operaciones sobre una lista enlazada permiten acceder a la misma mediante un puntero externo, que contiene la dirección del primer nodo de la lista.
![Page 15: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/15.jpg)
TAD LISTA IMPLEMENTADO CON LISTAS ENLAZADAS
unit LDinami;interfacetype
tInfo = ...;{tipo de campo de información lista}Ptr = ^Nodo;Nodo = record
Info: tInfo;Sig: Ptr
end;
procedure Inicia (var L: Ptr);function Localiza (L: Ptr; E: tInfo): Ptr;procedure Recupera (L: Ptr; P: Ptr; var E: tInfo);procedure Inserta (var L: Ptr; P: Ptr; E: tInfo);procedure SuprimeDir (var L: Ptr; P: Ptr);procedure Modifica (L: Ptr; P: Ptr; E: tInfo);
{Excepción a la regla de que los identificadores deben definirse antes de usarse. El tipo Ptr se define como un puntero a un registro del tipo Nodo, el cual no ha sido aún definido.}
![Page 16: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/16.jpg)
TAD LISTA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation
procedure Inicia;beginL := nil
end;
function Localiza; beginwhile (L^.Sig < > nil) and (L^.Info < > E) do
L := L^.Sig;if L^.Info < > E then Localiza := nilelse Localiza := L
end;
L
L^.Sig
EL
![Page 17: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/17.jpg)
TAD LISTA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation (continúa ...)procedure Recupera; beginif not (L=nil) thenif (P < > nil) then E := P^.Info
end;function Anterior (P: Ptr; L: Ptr): Ptr;{El anterior de lista vacía, de dirección no existente y del primer nodo de la lista, devuelve nil}beginif (L = nil) or (P = nil) or (L = P) then
Anterior := nilelse beginwhile (L^.Sig<>P) and (L^.Sig<>nil) doL := L^.Sig;
if L^.Sig = P then Anterior := Lelse Anterior := nilend {else}
end;
L L^.Sig = P
![Page 18: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/18.jpg)
TAD LISTA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation (continúa ...)procedure Inserta; {Inserta en L un nodo con elvar A: Ptrnodo; campo E, delante del nodo debegin dirección P}
new (A);A^.Info := E;if (L = nil) then L := A {si L vacía}else if P = L then {si P primer nodo}begin
A^.Sig := P;L := A
endelse begin {si P es oto nodo, A entre anterior y P}
Anterior (P, L)^.Sig := A;A^.Sig := P
endend;
L=AA^.Sig = nil
E
A^.Sig = PE
L=P
A
Anterior (P, L)^.Sig
b)
a)
c)
L
![Page 19: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/19.jpg)
TAD LISTA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation (continúa ...)procedure SuprimeDir; begin
if P = L then {Primer nodo}begin
L := L^.Sig;dispose (P)
endelse if Anterior (P, L) < > nil then
begin{Enlaza anterior con siguiente}Anterior (P, L)^.Sig := P^.Sigdispose (P)
endend;
procedure Modifica;beginif not (L = nil) then
if (P < > nil) then P^.Info := Eend;
end.
????P = L
????L P
Anterior (P,L)^.Sig:=P^.Sig
![Page 20: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/20.jpg)
CLASIFICACIÓN OPERACIONES DE TAD LISTA ENLAZADA
• Iniciar una lista enlazada:- Inicia (L)- EsVacia(L)
• Búsqueda en una lista:- Localiza (E, L)- Existe (E, L)
• Operaciones de dirección:- Siguiente (P, L)- Anterior (P, L)- Último (L)
• Inserción de un elemento en la lista:- Inserprim (E, L)- Inserta (E, P, L)- Inserfin (E, L)
• Supresión de un elemento de una lista:- Suprime (E, L)- SuprimeDir (P, L)- Anula (L)
• Recorrido de una lista:- Visualiza (L)
![Page 21: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/21.jpg)
ALGUNAS OPERACIONES DEL TAD LISTA ENLAZADA
• EsVacia (L): Función que determina si L es vacía o no.
• Existe (E, L): Función que determina si el elemento E se encuentra en L o no.
• Inserprim (E, L): Inserta un nodo con la información E como primer nodo de la lista.
• Inserfin (E, L): Inserta un nodo con el campo E como último nodo de la lista L.
• Suprime (E, L): Elimina el nodo de la lista que contiene E
• Siguiente (P, L): Función que devuelve la dirección del nodo siguiente a P.
• Anterior (P, L): Función que devuelve la dirección del nodo anterior a P.
• Primero (L): Función que devuelve la dirección del primer nodo de la lista L.
• Último (L): Función que devuelve la dirección del último nodo de la lista L.
• Anula (L): Esta operación vacía la lista L.• Visualiza (L): Visualiza el campo de información de
todos los elementos de la lista.
![Page 22: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/22.jpg)
IMPLEMENTACIÓN DEL TAD LISTA ENLAZADA
unit LEnlaza;interfacetype
tInfo = ...;{tipo de campo de información lista}Ptr = ^Nodo;Nodo = record
Info: tInfo;Sig: Ptr
end;procedure Inicia ( var L: Ptr);function Esvacia (L: Ptr): boolean;function Localiza (E: tInfo; L: Ptr): Ptr;function Existe (E: tInfo; L: Ptr): boolean;function Anterior (P, L: Ptr): Ptr;function Siguiente (P, L: Ptr):Ptr;function Ultimo (L: Ptr): Ptr;procedure Inserprim (E: tInfo; var L: Ptr);procedure Inserta (E:tInfo; P:Ptr; var L:Ptr);procedure Inserfin (E: tInfo; var L: Ptr);procedure Suprime (E: tInfo; var L: Ptr);procedure Suprimedir (P: Ptr; var L: Ptr);procedure Anula (var L: Ptr);procedure Visualiza (L: Ptr);
![Page 23: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/23.jpg)
IMPLEMENTACIÓN DEL TAD LISTA ENLAZADA
implementation
function EsVacia;beginEsVacia:= L=nil
end;
function Existe;beginif not EsVacia (L) thenbeginwhile (L^.Sig<>nil) and (L^.Info<>E) do
L := L^.Sig; Existe := (L^.Info = E)
end;else Existe := false
end;
![Page 24: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/24.jpg)
IMPLEMENTACIÓN DEL TAD LISTA ENLAZADA
implementation (continúa...)function Siguiente;beginif EsVacia (L) or (P = nil) then
Siguiente := nilelse
Siguiente := P^.Sigend;
function Ultimo;beginif EsVacia(L) then Ultimo := nilelse
beginwhile (L^.Sig<>nil) do
L := L^.Sig; Ultimo := L;
endend;
P P^.Sig
L L^.Sig = nil
![Page 25: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/25.jpg)
IMPLEMENTACIÓN DEL TAD LISTA ENLAZADA
implementation (continúa...)function Crea (E: tInfo): Ptr;var N: Ptr; beginnew (N);N^.Info := E;N^.Sig := nil;Crea := Nend;procedure Inserprim;var A: Ptr; beginA := Crea (E);A^.Sig := L;L := Aend;
NN^.Sig = nil
E
EA
L
A^.Sig = LE
L
A
![Page 26: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/26.jpg)
IMPLEMENTACIÓN DEL TAD LISTA ENLAZADA
implementation (continúa...)procedure Inserfin;var A: Ptr; beginA := Crea (E);if EsVacia (L) then
L := Aelse
Ultimo(L)^.Sig := A;end;procedure Suprime;var A: Ptr; beginA := Localiza(E, L);if A<>nil then begin
if A = L then L := L^.Sig {primer nodo}else Anterior (A, L)^.Sig := A^.Sig;dispose(A)
end {if}end;
L
E
L
Ultimo(L)^.Sig=A
???
L
???L
![Page 27: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/27.jpg)
IMPLEMENTACIÓN DEL TAD LISTA ENLAZADA
implementation (continúa...)
procedure Anula;begin
while not EsVacia (L) doSuprimeDir (Ultimo(L), L)
end;
procedure Visualiza;begin
while L< > nil do begin
write(L^.Info,’ ’);L := L^.Sig
endend;
end.
![Page 28: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/28.jpg)
TAD LISTA ORDENADA
• En las listas vistas anteriormente los elementos están ordenados con respecto a la posición que ocupan dentro de la lista.
• Si el tipo de información que representa cada elemento es un tipo ordinal se puede mantener la lista ordenada respecto a dicho campo.
• La formación de una lista ordenada se basa en dos operaciones:– Posinser (E, L): Devuelve la dirección del
nodo anterior al que contiene el campo E según la ordenación dada y nil si es el anterior al primero.
– Inserorden (E, L): Si la lista está vacía el nodo se inserta como el primero de la lista, si no se inserta en la posición que le corresponde.
![Page 29: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/29.jpg)
IMPLEMENTACIÓN DE OPERACIONES LISTA ORDENADA
function Posinser (E: tInfo; L: Ptr): Ptr;var T: Ptr; begin
T := nil;if not EsVacia (L) thenbegin
while (E >= L^.Info) and (L^.Sig <> nil) do begin
T := L;L := L^.Sig
end;if E >= L^.Info then T := L
end;Posinser := T
end;
EL
T
L^.Sig
![Page 30: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/30.jpg)
IMPLEMENTACIÓN DE OPERACIONES LISTA ORDENADAprocedure Inserorden (E: tInfo; var L: Ptr);
var A, N: Ptr; begin
N := Crea (E);if EsVacia(L) then L := Nelse begin
A := Posinser (E, L);if A = nil then begin{primera posición}
N^.Sig := L;L := N
end;else begin {posición intermedia}
N^.Sig := A^.Sig;A^.Sig := N
endend {else}
end;
2912 36L
15N
2912 36
L
15N
N^.SigA^.Sig
A
![Page 31: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/31.jpg)
IMPLEMENTACIÓN DE OPERACIONES LISTA ORDENADA
• Ahora la operación de búsqueda es más eficiente, ya que para decidir si un elemento está o no en la lista, basta con encontrar un elemento mayor.
– Buscorden (E, L): Devuelve la dirección del nodo que contiene el campo e o nil si no se encuentra en la lista.
function Buscorden (E: tInfo; L: Ptr): Ptr;beginwhile (L^.Sig <> nil) and (L^.Info < E) do
L := L^.Sig;if L^.Info = E then Buscorden := Lelse Buscorden := nil
end;El resto de operaciones son iguales a las listas no ordenadas. Cambiar las llamadas a Localiza por Buscorden.
![Page 32: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/32.jpg)
Universidad de ValladolidDepartamento de informática
Campus de Segovia
Estructura de datosTema 3: TAD Pila
Prof. Montserrat Serrano Montero
![Page 33: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/33.jpg)
ÍNDICE
• Definición• Especificación• Implementación estática• Implementación dinámica• Aplicaciones de pilas• Esquema recursivo
TAD Pila
![Page 34: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/34.jpg)
EL TAD PILA
- Una pila es una lista (estructura dinámica) de elementos en la que todas las inserciones y supresiones se realizan por el mismo extremo de la lista.
- La característica de esta estructura de datos es que el primer elemento obtenido es el último que se ha introducido; motivo por el que se conoce como estructura Lifo (Last in first out).
- Se utiliza siempre que se quiere recuperar una serie de elementos en orden inverso a como se introdujeron.
- Ejs.: pila de platos, de libros, etc.
![Page 35: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/35.jpg)
EL TAD PILA
• Especificación informal:
TAD pila (VALORES: pila de elementos; OPERACIONES: Inicia, EsVacia, Apilar, Desapilar, Cima)Inicia ( ) → PilaEfecto: Devuelve una pila vacía.EsVacia (Pila) → Boolean
Efecto: Devuelve true si la pila está vacía y false en caso contrario.Apilar (Pila, Elemento) → PilaEfecto: Devuelve una pila resultado de poner el elemento en la cima de la pila.Excepción: Que la pila esté llena.Desapilar (Pila) → PilaEfecto: Devuelve la Pila sin el elemento de la cima.Excepción: Si la Pila está vacía produce error.Cima (Pila) → ElementoEfecto: Devuelve el Elemento cima de la Pila.Excepción: Si la Pila está vacía produce error.
![Page 36: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/36.jpg)
EL TAD PILA
• Especificación formal:
TAD pila (VALORES: pila de elementos; OPERACIONES: Inicia, EsVacia, Apilar, Desapilar, Cima)Sintaxis:*Inicia ( ) → PilaEsVacia (Pila) → Boolean*Apilar (Pila, Elemento) → PilaDesapilar (Pila) → PilaCima (Pila) → ElementoSemántica:EsVacia (Inicia ( )) ⇒ trueEsVacia (Apilar (P, E)) ⇒ falseCima (Inicia ( )) ⇒ errorCima (Apilar (P, E)) ⇒ ΕDesapilar (Inicia ( )) ⇒ errorDesapilar (Apilar (P, E)) ⇒ P
* Constructores
![Page 37: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/37.jpg)
IMPLEMENTACIÓN ESTÁTICA
unit PEstatic;interfaceconst Max = ...; {especifica tamaño máximo lista}
typetInfo = ...;{tipo de campo de información lista}
Pila = recordElementos: array [1..Max] of tInfo;ultimo: integer
end;procedure Inicia (var P: Pila);function EsVacia (P: Pila): Boolean;procedure Apilar (var P: Pila; E: tInfo);procedure Desapilar (var P: Pila);procedure Cima (P: Pila; var E: tInfo);
![Page 38: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/38.jpg)
IMPLEMENTACIÓN ESTÁTICA
implementationprocedure Inicia;beginP.ultimo := 0
end;function EsVacia;
beginEsVacia:= P.ultimo = 0;
end;procedure Error (n: integer); {procedimiento oculto que sólo se ve en el módulo}begincase n of
1: writeln (‘Error: Pila llena.’);2: writeln (‘Error: Pila vacía.’);
end; {case}readln
end;
![Page 39: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/39.jpg)
IMPLEMENTACIÓN ESTÁTICAimplementation (continúa...)procedure Apilar;
beginif P.ultimo = Max then Error (1)else
beginP.ultimo := P.ultimo +1;P.Elementos [P.ultimo] := Eend
end;procedure Desapilar;
beginif EsVacia (P) then Error (2)else P.ultimo := P.ultimo - 1;
end;procedure Cima;
beginif EsVacia (P) then Error (2)else E := P.Elementos [P.ultimo]
end;
![Page 40: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/40.jpg)
IMPLEMENTACIÓN DINÁMICA
• La pila será un puntero a un nodo, puntero que señala el extremo de una lista enlazada por el que se efectúan las operaciones de manejo de la pila:
P
![Page 41: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/41.jpg)
TAD PILA IMPLEMENTADO CON LISTAS ENLAZADAS
unit PDinami;interfacetypetInfo = ...; {tipo de campo de información lista}
Ptr = ^Nodo;Nodo = record
Info: tInfo;Sig: Ptr
end;
procedure Inicia (var P: Ptr);function EsVacia (P: Ptr): boolean;procedure Apilar (var P: Ptr; E: tInfo);procedure Desapilar (var P: Ptr);procedure Cima (P: Ptr; var E: tInfo);
![Page 42: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/42.jpg)
implementationprocedure Inicia;
beginP := nil
end;function EsVacia; begin
EsVacia := P = nilend;
procedure Apilar;var aux: ptrnodo;beginnew (aux);with aux^ dobegin(1) Info := E;(2) Sig := P;end;
(3) P := auxend;
TAD PILA IMPLEMENTADO CON LISTAS ENLAZADAS
8
15
1 (1)
aux
8
15
P
P
aux
(3) (2)
![Page 43: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/43.jpg)
TAD PILA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation (continúa ...)
procedure Desapilar; var aux: Ptr;begin
if not EsVacia(P) thenbegin(1) aux := P;(2) P := P^.Sig;(3) dispose(aux);
endelse writeln (‘Error: Pila vacía’)
end;procedure Cima;beginif not EsVacia(P) thenE := P^.Info
else writeln (‘Error: Pila vacía’)end;
8
????
aux
Pila
8
15
P
aux
3
8
15
P
(1) (3)
(2)
![Page 44: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/44.jpg)
APLICACIONES DE LAS PILAS
a) Eliminar la recursividad.
b) Transformar expresiones aritméticas de unas notaciones a otras:
1. Infija: es la empleada normalmente y requiere el uso de paréntesis para modificar la prioridad de los operadores.2. Prefija o polaca: es aquella en la que el operador se coloca delante de los dos operandos. En ella, no es necesario el uso de paréntesis.3. Postfija o polaca inversa: coloca el operador a continuación de sus dos operandos. La ventaja que ofrece es que la expresión puede evaluarse de izquierda a derecha recorriéndola una sola vez.
![Page 45: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/45.jpg)
A) ELIMINAR LA RECURSIVIDAD
• En cada llamada se añade una tabla de activación en una pila denominada recursiva. En esta pila se almacenan los argumentos y objetos locales con su valor en el momento de producirse la llamada.
• La recursividad se puede implementar mediante una unidad pila. Bajo esta perspectiva la recursividad se convierte en un par de bucles. El primero apila, el segundo desapila y evalúa.
![Page 46: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/46.jpg)
EJEMPLO: FACTORIAL DE n
function factorial (n: word): real;var
pila: Ptr;i: word; fac: real;
beginInicia (pila);{primer bucle: apila las distintas llamadas}for i := n downto 1 do Apilar (i, pila);{Segundo bucle: resuelve las llamadas}fac:=1 {caso base}while pila < > nil do
beginfac := Cima(pila) * fac;Desapilar(pila)
end;factorial := fac
end;
function factorial (n: word): real;beginif n = 0 then factorial :=1else factorial := n*factorial (n-1)
end;
![Page 47: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/47.jpg)
B) EVALUAR EXPRESIONES ARITMÉTICAS
• Pasos que sigue el ordenador:a) Transformar la expresión de infijaa postfija.b) Evaluar la expresión postfija.
• Ejemplo inverso: a) Postfija a infija:Postfija: AB+CD*AB-/-Infija: ((A+B)-((C*D)/(A-B)))
B (A+B) D (C*D)A C (A+B)
(A+B)
![Page 48: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/48.jpg)
B) EVALUAR EXPRESIONES ARITMÉTICAS
B (A-B) ((C*D)/(A-B)) A (C*D) (A+B)
(C*D) (A+B)(A+B)
((A+B)-((C*D) /(A-B)))
b) Se calcularía el valor expresión sustituyendo los correspondientes valores, respetando el orden de operación.
![Page 49: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/49.jpg)
ESQUEMAS RECURSIVOS CON PILAS
uses Upila;... procedure X (var P);var elem: tElem;beginif not EsVacia(P) thenbeginCima (P, elem);Desapilar (P);Operación (elem);X (P);Apilar (P, elem);
endend;
Desapilar (P, elem);
![Page 50: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/50.jpg)
IMPLEMENTACIÓN PILAS
procedure Desapilar (var P: Ptr; var E: tInfo);var aux: Ptr;beginif not EsVacia (P) thenbeginE := P^.Info;aux := P;P:= P^.Sig;dispose (aux);
endelse writeln (‘Error: Pila vacía’)
end;
![Page 51: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/51.jpg)
EJ. ESQUEMA RECURSIVOImplementar un algoritmo en Pascal que cuente el número de elementos de una pila de forma recursiva sin utilizar ninguna estructura de datos auxiliar.
a) Escribir la sección interface de la unidad Pila.b)
function Contar (var P: Ptr): integer;var long, elem: integer; beginif not EsVacia (P) thenbeginDesapilar (P, elem);long := Contar (P) + 1;Apilar (P, elem);Contar := long;
endelse Contar := 0
end;
![Page 52: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/52.jpg)
Universidad de ValladolidDepartamento de informática
Campus de Segovia
Estructura de datosTema 3:TAD cola
Prof. Montserrat Serrano Montero
![Page 53: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/53.jpg)
ÍNDICE
• Definición• Especificación del TAD• Implementaciones estáticas• Implementación dinámica• Esquemas recursivos
![Page 54: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/54.jpg)
EL TAD COLA- Una cola es una lista de elementos, en la cual las eliminaciones se realizan por el frente o principio de la cola, y los nuevos elementos son añadidos por el otro extremo, llamado fondo o final de la cola.
- En esta estructura el primer elemento que entra es el primero en salir, por eso se les llama listas Fifo (First in, firstout).
- Ejs.: espectadores esperando en la taquilla de un cine, tareas a realizar por una impresora, etc.
- Las colas son estructuras de datos dinámicas.
![Page 55: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/55.jpg)
EL TAD COLA
• Especificación informal:
TAD cola (VALORES: cola de elementos; OPERACIONES: Inicia, EsVacia, Primero, Encolar, Desencolar);Inicia ( ) → ColaEfecto: Devuelve una cola vacía.EsVacia (Cola) → Boolean
Efecto: Devuelve true si la cola está vacía y false en caso contrario.Primero (Cola) → ElementoEfecto: Devuelve el Elemento Frente de la cola.Excepción: Si la Cola está vacía produce error. Encolar (Cola, Elemento) → ColaEfecto: Añade un nuevo Elemento a la Cola por el Final.Excepción: Que la cola esté llena.Desencolar (Cola) → ColaEfecto: Elimina el elemento Frente de la cola.Excepción: Si la Cola está vacía produce error.
![Page 56: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/56.jpg)
EL TAD COLA• Especificación formal:
TAD cola (VALORES: cola de elementos; OPERACIONES: Inicia, EsVacia, Primero, Encolar, Desencolar)Sintaxis:*Inicia ( ) → ColaEsVacia (Cola) → BooleanPrimero (Cola, Elemento) → Cola*Encolar (Cola) → Cola Desencolar (Cola) → ColaSemántica:EsVacia (Inicia ( )) ⇒ trueEsVacia (Poner (Cola, E)) ⇒ falsePrimero (Inicia ( )) ⇒ errorPrimero (Encolar (Cola, E)) ⇒ si EsVacia (Cola)
entonces Esi_no Primero (Cola)
Desencolar (Inicia ( )) ⇒ errorDesencolar (Encolar (Cola, E)) ⇒ si EsVacia (Cola)
then Inicia ( )si_no Encolar (Desencolar (Cola), E)
![Page 57: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/57.jpg)
IMPLEMENTACIÓN ESTÁTICA
unit CEstatic;interfaceconst Max = ...; {especifica tamaño máximo lista}type
Posicion = 0..Max;tInfo = ...; {tipo de campo de información lista}Cola = record
Elementos: array [1..Max] of tInfo;frente, final: Posicion
end;procedure Inicia (var C: Cola);function EsVacia (C: Cola): boolean;procedure Primero (C: Cola; var E: tInfo);procedure Encolar (var C: Cola; E: tInfo);procedure Desencolar (var C: Cola);
![Page 58: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/58.jpg)
IMPLEMENTACIÓN ESTÁTICAimplementation
procedure Inicia;begin
C.frente := 1;C.final := 0
end;
function EsVacia;begin
EsVacia := C.final < C.frenteend;
function EsLlena (C: Cola): boolean;begin
EsLlena := C.final = Maxend;
procedure Primero; beginif not EsVacia (C) then
E := C.Elementos [C.frente]end;
![Page 59: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/59.jpg)
IMPLEMENTACIÓN ESTÁTICAimplementation (continúa...)
procedure Encolar;beginif not EsLlena (C) thenwith C do
beginfinal := final +1;Elementos [final] := E
endend;procedure Desencolar; beginif not EsVacia (C) thenbeginfor i:= 1 to C.final-1 doC.Elementos [i] := C.Elementos [i+1];
C.final:=C.final-1;end
end;end.
![Page 60: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/60.jpg)
IMPLEMENTACIÓN CIRCULAR
unit CCEstatic;interfaceconst long = ...; {especifica tamaño máximo lista}type
Posicion = 0..long;tInfo = ...; {tipo de campo de información lista}Cola = record
Elementos: array [1..long] of tInfo;frente, final: Posicion
end;procedure Inicia (var C: Cola);function EsVacia (C: Cola): boolean;function Primero (C: Cola): tInfo;procedure Encolar (E: tInfo; var C: Cola);procedure Desencolar (var C: Cola);
Es preferible esta implementación porque no se desplazan los elementos del array, al suprimir el primer elemento de la cola, como ocurre en la implementación lineal.
![Page 61: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/61.jpg)
implementationfunction Siguiente (P: integer): integer;beginSiguiente := (P mod long) + 1
end; procedure Inicia;beginC.frente := 1;C.final := long;
end;function EsVacia;beginEsVacia := Siguiente (C.final) = C.frente
end;function EsLlena(C: Cola): boolean; beginEsLlena :=
Siguiente(Siguiente(C.final)) = C.frenteend;
TAD COLA IMPLEMENTADO CON ARRAY CIRCULAR
![Page 62: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/62.jpg)
implementation (continúa...)function Primero; beginif not EsVacia (C) thenPrimero := C.Elementos[C.frente]
end; procedure Encolar;beginif not EsLlena (C) thenwith C do
beginfinal := Siguiente (final);Elementos [final] := E
endend;procedure Desencolar; beginif not EsVacia (C) then
C.frente := C.frente + 1end; end.
TAD COLA IMPLEMENTADO CON ARRAY CIRCULAR
![Page 63: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/63.jpg)
IMPLEMENTACIÓN DEL TAD COLA CON LISTAS ENLAZADAS
unit CDinamic;interfacetype
tInfo = ...; {tipo de campo de información lista}Ptr = ^Nodoc;Nodoc = record
Info: tInfo;Sig: Ptr
end;Cola = record
frente, final: Ptrend;
procedure Inicia (var C: Cola);function EsVacia (C: Cola): boolean;procedure Primero (C: Cola; var E: tInfo);procedure Desencolar (var C: Cola); procedure Encolar (var C: Cola; E: tInfo);
Frente Final
![Page 64: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/64.jpg)
TAD COLA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation
procedure Inicia;beginC.frente := nil;C.final := nil
end;
function EsVacia;beginEsVacia := C.frente = nil
end;
procedure Primero; beginif not EsVacia (C) thenE := C.frente^.Info
end;
![Page 65: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/65.jpg)
TAD COLA IMPLEMENTADO CON LISTAS ENLAZADAS
implementation (continúa...)
procedure Desencolar;var A: ptr;begin
if not EsVacia (C) thenwith C dobeginA:= frente;frente := frente^.Sig;if frente = nil then final := nil;dispose (A);
endend;
![Page 66: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/66.jpg)
implementation (continúa...)function Crea (E: tInfo): Ptr;var A: ptr;beginnew (A);A^.Info:= E;A^.Sig := nil;Crea := A
end;procedure Encolar;var N: ptr;beginN := Crea (E)with C dobeginif EsVacia (C) then frente := Nelse final^.Sig := N;final := N;
endend; end.
TAD COLA IMPLEMENTADO CON LISTAS ENLAZADAS
![Page 67: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/67.jpg)
ESQUEMAS RECURSIVOS CON COLAS
uses Ucola;...procedure X (var C);var elem: tInfo;begin
if not EsVacia (C) thenbeginelem := Primero (C); Desencolar (C);Operación (elem);X (C);Encolar (C, elem);
endend;
Desencolar (C, elem)
![Page 68: Estructura de datos - Departamento de Informáticamserrano/EDI/cap3.pdf · Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 3: El](https://reader036.fdocumento.com/reader036/viewer/2022062600/5a72e1e17f8b9abb538e1bb8/html5/thumbnails/68.jpg)
ESQUEMAS RECURSIVOS CON COLAS
Ejemplo: Dado el TAD Cola de enteros se pide implementar una operación que invierta el contenido de una Cola.
a) Escribir la sección interface de la unidad cola.
b)procedure Invertir (var C: Cola);var elem: integer;beginif not EsVacia (C) thenbeginDesencolar (C, elem);Invertir (C);Encolar (C, elem)
endend;