PDF de programación - Capítulo 7. Implementación y uso de TADs

Implementación y uso de TADs1

Capítulo 7

La perfección no se obtiene
cuando se ha añadido todo lo añadible,
sino cuando se ha quitado todo lo superfluo.

Antoine de Saint-Exupéry (Escritor francés,
1900-1944)

Resumen: En este tema se introducen los tipos abstractos de datos (TADs),
que permiten definir y abstraer tipos de forma similar a como las funciones definen y
abstraen código. Presentaremos la forma de definir un TAD, incluyendo tanto su es-
pecificación externa como su representación interna, y veremos, como caso de estudio,
el TAD “iterador”.

1. Motivación

Te plantean el siguiente problema: Dado un número x, se cogen sus dígitos y se suman
sus cuadrados, para dar x1. Se realiza la misma operación, para dar x2, y así mucho rato
hasta que ocurra una de las dos cosas siguientes:

se llega a 1, y se dice entonces que el número es “feliz”

nunca se llega a 1 (porque se entra en un ciclo que no incluye el 1), y se dice entonces
que el número es “infeliz”

Ejemplos:

el 7 es feliz: 7 → 49 → 97 → 130 → 10 → 1

el 38 es infeliz: 38 → 73 → 58 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58

Sin estructuras ni TADs, necesitarás bastante imaginación para encontrar una solución
(existe, eso sí). Al final de este capítulo verás una solución mucho más legible, usando un
TAD Conjunto.

1Manuel Freire es el autor principal de este tema.

135

136

Capítulo 7. Implementación y uso de TADs

2.

Introducción

2.1. Abstracción

⋆

⋆

El exceso de detalles hace más difícil tratar con los problemas. Para concentrarnos
en lo realmente importante, abstraemos el problema, eliminando todos los detalles
innecesarios.

Por ejemplo, para leer un fichero de configuración desde un programa, el programador
no tiene que preocuparse del formato del sistema de archivos, ni de su soporte físico
concreto (si se trata de una unidad en red, una memoria USB o un disco que gira
miles de veces por segundo) - en lugar de eso, las librerías del sistema y el sistema
operativo le permiten usar la abstracción “fichero” – una entidad de la que se pueden
leer y a la que se pueden escribir bytes, y que se identifica mediante una ruta y un
nombre. Un fichero es un ejemplo de tipo abstracto de datos (TAD).

⋆

Se puede hablar de dos grandes tipos de abstracción:

funcional: abstrae una operación. Es la que hemos visto hasta ahora. La opera-
ción se divide en “especificación” (qué es lo que hago) e “implementación” (cómo
lo llevo a cabo). De esta forma, un programador puede llamar a ordena(v, n)
con la plena confianza de que obtendrá un vector ordenado en O(n log n), y sin
tener que preocuparse por los detalles de implementación del algoritmo concreto.

de datos: abstrae un tipo de dato, o mejor dicho, el uso que se puede hacer
de este tipo (por ejemplo, un fichero) de la forma en que está implementado
internamente (por ejemplo, bloques de un disco magnetizado estructurados como
un sistema de archivos NTFS). Si la abstracción funcional es una forma de añadir
operaciones a un lenguaje, la abstracción de datos se puede ver como una forma
de añadir tipos al lenguaje.

TADs predefinidos

⋆

Algunos tipos de TADs vienen predefinidos con los lenguajes. Por ejemplo, enteros,
caracteres, números en coma flotante, booleanos o arrays tienen todos representa-
ciones internas “opacas” que no es necesario conocer para poderlos manipular. Por
ejemplo:

los enteros (char, int, long y derivados) usan, internamente, representación
binaria en complemento a 2. Las operaciones +, -, *, /, % (entre otras) vienen
predefinidas, y en general no es necesario preocuparse por ellas

los números en coma flotante (float y double) usan una representación bi-
naria compuesta por mantisa y exponente, y disponen de las operaciones que
cabría esperar; en general, los programadores evitan recurrir a la representación
interna.

los vectores (en el sentido de arrays) tienen su propia representación interna
y semántica externa. Por ejemplo, v[i] se refiere a la i-ésima posición, y es
posible tanto escribir como leer de esta posición, sin necesidad de pensar en
cómo están estructurados los datos físicamente en la memoria.

Estructura de Datos y Algoritmos

2. Introducción

137

⋆

⋆

⋆

⋆

⋆

Aunque, en general, los TADs se comportan de formas completamente esperadas
(siguiendo el principio de la mínima sorpresa), a veces es importante tener en cuenta
los detalles. Por ejemplo, este código demuestra una de las razones por las cuales los
float de C++ no se pueden tratar igual que los int: sus dominios se solapan, pero
a partir de cierto valor, son cada vez más distintos.

int ejemplo() {

// 31 b i t s en complemento a 2 + b i t de s i g n o
// 24 b i t s en complemento a 2 + 7 de e x p o n e n t e + s i g n o

int i=0;
float f=0;
while (i == f) { i++; f++; } // i n t ( 224+1) 6= f l o a t ( 224+1)
return i;

( ! )

}

los dominios de float e int no son equivalentes

Este otro fragmento calcula, de forma aproximada, la inversa de la raíz cuadrada de
un número n - abusando para ello de la codificación de los enteros y de los flotantes
en C/C++. Es famosa por su uso en el videojuego Quake, y aproxima muy bien (y de
forma más rápida que pow) el resultado de pow(n, .5). Los casos en los que está
justificado recurrir a este tipo de optimizaciones son muy escasos; pero siempre que
se realiza una abstracción que no permite acceso a la implementación subyacente,
se sacrifican algunas optimizaciones (como ésta, y a menudo más sencillas) en el
proceso.

float Q_rsqrt(float n) {

= n;

const float threehalfs = 1.5f;
float x2 = n * 0.5f;
float y
int i
i
y
y
return y;

= 0x5f3759df - ( i >> 1 );
= * ( float * ) &i;
= y * ( threehalfs - ( x2 * y * y ) );

= * ( long * ) &y;

// c o n v i e r t e de f l o a t a l o n g ( ! )

// c o n v i e r t e de l o n g a f l o a t

( ! )

}

optimización que rompe la encapsulación de los tipos float e int

Un ejemplo clásico de TAD predefinido de C++ es la cadena de caracteres de su
librería estándar: std::string. Dada una cadena s, es posible saber su longitud
(s.length() ó s.size()), concatenarle otras cadenas (s += t), sacar copias
(t = s), o mostrarla por pantalla (std::cout << s), entre otras muchas opera-
ciones – y todo ello sin necesidad de saber cómo reserva la memoria necesaria ni cómo
codifica sus caracteres.

2.2. TADs de usuario

Los structs de C, o los records de Pascal, sólo permiten definir nuevos tipos de
datos, pero no permiten ocultar los detalles al usuario (el programador que hace
uso de ellos). Esta ocultación sí es posible en C++ u otros lenguajes que soportan
orientación a objetos.

Un tipo de datos Fecha muy básico, sin ocultación o abstracción alguna, sería el
siguiente:

Facultad de Informática - UCM

138

Capítulo 7. Implementación y uso de TADs

struct Fecha {

int dia;
int mes;
int anyo;
Fecha(int d, int m, int a): dia(d), mes(m), anyo(a) {}

// i d e n t i f i c a d o r e s en C++: s ó l o ASCII e s t á n d a r

};

estructura Fecha. Es fácil generar fechas inválidas.

⋆

⋆

⋆

Ahora, es posible escribir Fecha f = Fecha(14, 7, 1789) ó Fecha f(14,
7, 1789), y acceder a los campos de esta fecha mediante f.dia ó f.mes: hemos
definido un nuevo tipo, que no existía antes en el lenguaje. Por el lado malo, es
posible crear fechas inconsistentes; por ejemplo, nada impide escribir f.mes = 13
ó, más sutil, f.mes = 2; f.dia = 30 (febrero nunca puede tener 30 días). Es
decir, tal y como está escrita, es facil salirse fuera del dominio de las fechas válidas.

Además, esta Fecha es poco útil. No incluye operaciones para sumar o restar días
a una fecha, ni para calcular en qué día de la semana cae una fecha dada, por citar
dos operaciones frecuentes. Tal y como está, cada programador que la use tendrá
que (re)implementar el mismo conjunto de operaciones básicas para poder usarlas,
con el consiguiente coste en tiempo y esfuerzo; y es altamente probable que dos
implementaciones distintas sean incompatibles entre sí (en el sentido de distintas
precondiciones/postcondiciones). Una buena especificación de TAD debería incluir
las operaciones básicas del tipo, facilitando así su uso estándar.

Todo TAD especifica una serie de operaciones del tipo; estas operaciones son las
que el diseñador del tipo prevee que se van a querer usar con él. Pueden hacer uso
de otros tipos; por ejemplo, un tipo Tablero podría usar un tipo Ficha y un tipo
Posicion en su operación mueve.

Ejemplo expandido: Fechas

Este ejemplo presenta un tipo Fecha2 algo más completo, donde se especifica (de for-
ma informal) el dominio de una implementación concreta y una serie de operaciones
básicas.

Nota: en este ejemplo se usa notación de C++ “orientado a objetos”. El lector que
no sea familiar con esta notación debe entender que, en todas las operaciones de una
clase (excepto los constructores), se está pasando un parámetro adicional implícito
(this): el objeto del tipo que se está definiendo (en este caso una Fecha) sobre el
que operar. De esta forma, dada una Fecha f, la instrucción f.dia() se convierte
internamente a dia(this=f ).

2 Para ver un ejemplo real (y muy, muy flexible) de TAD fecha para su uso en C++, http://www.
boost.org/doc/libs/1_48_0/doc/html/date_time.html. También hay una discusion de Fecha
más instructiva en la sección 10.2 de Stroustrup (1998).

Estructura de Datos y Algoritmos

2. Introducción

139

class Fecha {
public: // p a r t e p u b l i c a d e l TAD

// C o n s t r u c t o r
//
Fecha(int dia, int mes, int anyo);

d i a , mes y año forman una f e c h a en e l d o m i n i o e s p e r a d o

// C o n s t r u c t o r a l t e r n a t i v o
//
Fecha(const Fecha &base, int dias);

d i a s e s un número de d í a s a sumar o r e s t a r a l a f e c h a b a s e

// d i s t a n c i a , en d í a s , de l a f e c h a a c t u a l con l a dada ( Obs . )
int distancia(const Fecha &otra) const;

// d e v u e l v e
int dia() const;

e l d i a de e s t a f e c h a ( Obs . )

// d e v u e l v e
int diaSemana() const;

e l d í a de l a semana de e s t a f e c h a ( O b s e r v a d o r a )

// d e v u e l v e
int me