Publicado el 19 de Diciembre del 2018
489 visualizaciones desde el 19 de Diciembre del 2018
265,9 KB
60 paginas
Creado hace 16a (21/01/2008)
TEMA 4
TIPOS ABSTRACTOS DE DATOS CON
ESTRUCTURA LINEAL
1. Pilas
2. Colas
3. Colas dobles
4. Listas
5. Secuencias
Bibliografía:
Fundamentals of Data Structures in C++
E. Horowitz, S. Sahni, D. Mehta
Computer Science Press, 1995
Data Abstraction and Problem Solving with C++, Second
Edition
Carrano, Helman y Veroff
Tipos abstractos de datos con estructura lineal
1
4.1 Pilas
En el tema anterior ya hemos estudiado las dos implementaciones más habi-
tuales de las pilas. En este aparato simplemente veremos una de sus aplicacio-
nes: la transformación a iterativo de algoritmos recursivos lineales.
4.1.1 Eliminación de la recursión lineal no final
El esquema de la recursión simple
void nombreProc ( τ1 x1 , … , τn xn , δ1 & y1 , … , δm & ym ) {
// Precondición
// declaración de constantes
τ1 x1’ ; ... ; τn xn’ ; // xr ’
δ1 y1’ ; ... ; δm ym’ ; // yr ’
if ( d(xr ) )
yr = g(xr );
else if ( ¬d(xr ) ) {
xr ‘ = s(xr );
nombreProc(xr ‘, yr ‘);
yr = c(xr , yr ‘);
}
// Postcondición
}
La ejecución de nombreProc(xr , yr ) se puede ver como un “bucle descendente”
seguido de un “bucle ascendente”
xr → nombreProc(xr , yr )
↓
nombreProc (s(xr ), yr )
↓
nombreProc (s2(xr ), yr )
↓
...
nombreProc (sn–1(xr ), yr )
↓
nombreProc (sn(xr ), yr ) → g(sn(xr ))
c(xr , . ) → yr
c(s(xr ), . )
c(s2(xr ), . )
c(sn-1(xr ), . )
Tipos abstractos de datos con estructura lineal
2
La transformación a iterativo se basa en ese esquema, se utilizan dos bucles
compuestos secuencialmente, de forma que
— en el primero se van obteniendo las descomposiciones recursivas hasta llegar
al caso base, y
— en el segundo se aplica sucesivamente la función de combinación.
Nótese que en el segundo bucle, para ir aplicando sucesivamente la función de
combinación se debe disponer de los parámetros correspondientes a esa lla-
mada: sn–i(xr ).
Según la forma de obtener los valores de sn–i(xr ) en el bucle ascendente distin-
guimos tres casos, que vienen dados por la forma de la función de descompo-
sición recursiva:
— Caso especial. La función s de descomposición recursiva, posee una función
inversa calculable s–1.
Los datos sn–i(xr ) pueden calcularse sobre la marcha, usando s–1.
— Caso general. La función s no posee inversa –o, aunque la posea, ésta no es
calculable, o su cálculo resulta demasiado costoso–.
Los datos sn–i(xr ) se irán almacenando en una pila en el curso del bucle des-
cendente y se irán recuperando de ésta en el curso del bucle ascendente.
— Combinación de los casos especial y general.
— En cada iteración del bucle descendente no es necesario apilar sn–i(xr )
n–i , de forma que
n–i, obtenido
— en el bucle ascendente es fácil calcular sn–i(xr ) a partir de ur
sino que es suficiente con apilar un dato más simple ur
de la pila, y sn–i+1(xr ) obtenido en la iteración anterior.
Tipos abstractos de datos con estructura lineal
3
Caso especial
El esquema de la transformación
void nombreProcit ( τ1 x1 , … , τn xn , δ1 & y1 , … , δm & ym ) {
// Precondición
τ1 x1’ ; ... ; τn xn’ ; // xr ’
xr ’ = xr ;
while ( ¬d(xr ’) )
xr ’ = s(xr ’);
yr = g(xr ’);
while ( xr ’ != xr ) {
xr ’ = s-1(xr ’);
yr = c(xr ’, yr );
}
// Postcondición
}
Transformación de la versión recursiva no final de la función factorial
s(n) = n–1 s–1(n) = n+1
Es obvio que en este caso no se necesita el bucle descendente.
int fact ( int n ) {
// Pre : n >= 0 }
int r, nAux;
nAux = n;
while ( nAux != 0 )
nAux = nAux - 1;
r = 1;
while ( nAux != n ) {
nAux = nAux + 1;
r = r * nAux;
}
return r;
// Post: devuelve n!
}
Tipos abstractos de datos con estructura lineal
4
Caso general
Este es el caso donde nos ayudamos de una pila para almacenar los sucesivos
valores del parámetro xr
void nombreProcit ( τ1 x1 , … , τn xn , δ1 & y1 , … , δm & ym ) {
// Precondición
τ1 x1’ ; ... ; τn xn’ ; // xr ’
TPila< TTupla<τ1, ..., τn> > xs;
xr ’ = xr ;
while ( ¬d(xr ’) ) {
xs.apila(xr ’);
xr ’ = s(xr ’);
}
yr = g(xr ’);
while ( ! xs.esVacio() ) {
xr ’ = xs.cima();
yr = c(xr ’, yr );
xs.desapila();
}
// Postcondición
}
Para utilizar la implementación genérica de las pilas en este algoritmo, es nece-
sario implementar una clase que represente a las tuplas de n elementos
TTupla<τ1, ..., τn>
excepto cuando n = 1 en cuyo caso los elementos de la pila serán directamente
de tipo τ1.
Tipos abstractos de datos con estructura lineal
5
Como ejemplo, veamos cómo se aplica este esquema a la función bin que ob-
tiene la representación binaria de un número decimal
int bin( int n ) {
// Pre: n >= 0
int r;
if ( n < 2 )
r = n;
else if ( n >= 2 )
r = 10 * bin(n / 2) + (n % 2);
return r;
// Post: devuelve la representación binaria de n
}
La transformación a iterativo
int binIt( int n ) {
// Pre: n >= 0
int r, nAux;
TPilaDinamica<int> ns;
nAux = n;
while ( nAux >= 2 ) {
ns.apila(nAux);
nAux = nAux / 2; // n' = s(n')
}
r = nAux;
while ( ! ns.esVacio() ) {
nAux = ns.cima();
r = 10 * r + nAux % 2; // r = c(n',r)
ns.desapila();
}
return r;
// Post: devuelve la representación binaria de n
}
Tipos abstractos de datos con estructura lineal
6
Combinación de los casos especial y general
En este caso sólo es necesario apilar una parte de la información que contie-
nen los parámetros xr de forma que luego sea posible reconstruir dicho pará-
metro a partir de la información apilada y s(xr ).
Formalmente, hemos de encontrar dos funciones f y h que verifiquen:
La versión iterativa queda entonces
¬d(x) ⇒ ur = f(xr ) está definido y cumple que xr = h(ur , s(xr ))
void nombreProcit ( τ1 x1 , … , τn xn , δ1 & y1 , … , δm & ym ) {
// Precondición
τ1 x1’ ; ... ; τn xn’ ; // xr ’
σ1 u1 ; ... ; σp up ;
TPila< TTupla<σ1, ..., σp> > us;
xr ’ = xr ;
while ( ¬d(xr ’) ) {
ur = f(xr ’);
us.apila(ur );
xr ’ = s(xr ’);
}
yr = g(xr ’);
while ( ! us.esVacio() ) {
ur = us.cima();
xr ’ = h(ur , xr ’);
yr = c(xr ’, yr );
us.desapila();
}
// Postcondición
}
Para utilizar la implementación genérica de las pilas en este algoritmo, es nece-
sario implementar una clase que represente a las tuplas de p elementos
TTupla<σ1, ..., σp>
excepto cuando p = 1 en cuyo caso los elementos de la pila serán directamente
de tipo σ1.
Tipos abstractos de datos con estructura lineal
7
En la función bin la descomposición recursiva es:
s(n) = n / 2;
Aquí no se puede aplicar la técnica del caso especial porque no existe la inversa
de esta función: para obtener n a partir de n /2 tenemos que saber si n es par o
impar. Sin embargo, en realidad no hace falta apilar n, basta con apilar su pari-
dad, pues a partir de n / 2 y la paridad de n podemos obtener n.
f(n) = par(n) = u
h(u, s(n)) =
2 * s(n)
2 * s(n) + 1
si u
si NOT u
Con lo que la versión iterativa aplicando este nuevo esquema quedará:
int binIt2( int n ) {
// Pre: n >= 0
int r, nAux;
bool u;
TPilaDinamica<bool> us;
nAux = n;
while ( nAux >= 2 ) {
u = (nAux % 2) == 0; // u = f(n')
us.apila(u);
nAux = nAux / 2; // n' = s(n')
}
r = nAux;
while ( ! us.esVacio() ) {
u = us.cima();
if ( u )
nAux = 2 * nAux;
else // n' = h(u, n')
nAux = 2 * nAux + 1;
r = 10 * r + nAux % 2; // r = c(n',r)
us.desapila();
}
return r;
// Post: devuelve la representación binaria de n
}
Tipos abstractos de datos con estructura lineal
8
4.2 Colas
Este TAD representa una colección de datos del mismo tipo donde las opera-
ciones de acceso hacen que su comportamiento se asemeje al de una cola de
personas esperando a ser atendidas: los elementos se añaden por el final y se
eliminan por el principio, o dicho de otra forma, el primero en llegar es el pri-
mero en salir –en ser atendido–: FIFO –first in first out–.
Especificación
tad COLA [E :: ANY]
usa
BOOL
tipo
Cola[Elem]
operaciones
Nuevo: → Cola[Elem]
PonDetras: (Elem, Cola[Elem]) → Cola[Elem]
quitaPrim: Cola[Elem] – → Cola[Elem]
primero: Cola[Elem] – → Elem
esVacio: Cola[Elem] → Bool
ecuaciones
∀ x : Elem : ∀ xs : Cola[Elem] :
def quitaPrim(PonDetras(x, xs))
quitaPrim(PonDetras(x, xs)) = Nuevo
quitaPrim(PonDetras(x, xs)) =
PonDetras(x, quitaPrim(xs))
def primero(PonDetras(x, xs))
primero(PonDetras(x, xs)) = x
primero(PonDetras(x, xs)) = primero(xs)
esVacio(Nuevo)
= Cierto
esVacio(PonDetras(x, xs)) = Falso
errores
avanza(Nuevo)
primero(Nuevo)
ftad
/* gen */
/* gen */
/* mod */
/* obs */
/* obs */
si esVacio(xs)
si NOT esVacio(xs)
si esVacio(xs)
si NOT esVacio(xs)
Tipos abstractos de datos con estructura lineal
9
Implementación estática basada en un vector
Tipo representante
La idea de la representación es almacenar los datos en posiciones consecutivas
de un array, indicando con dos índices el principio, ini, y el final, fin, de la zona
utilizada. Inicialmente ini y fin están al principio del vector, pero tras un cierto
número de invocaciones a
Comentarios de: Tema 4 - Tipos abstractos de datos con estructura lineal (0)
No hay comentarios