PDF de programación - Tema 4 - Tipos abstractos de datos con estructura lineal

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