Programación Estructuras de Datos 2

Implementación
de tipos abstractos de datos
89
__________________________________________________________________________________

Capítulo 2 Implementación de tipos abstractos de datos

La especificación de un tipo abstracto es el paso previo a la escritura de cualquier programa
que lo manipule, porque permite describir inequívocamente su comportamiento; una vez
establecida, se pueden construirdiversas implementaciones usando un lenguaje de
programación convencional. En este capítulo se introducen los mecanismos que
proporciona la notación Merlí para codificar los tipos de datos, que son los habituales en los
lenguajes de programación imperativos más utilizados (excepto algún aspecto puntual como
la genericidad, ausente en los lenguajes más antiguos), se estudian las relaciones que sepueden establecer entre la implementación y la especificación de un TAD y, por último, se
definen diversas estrategias de medida de la eficiencia de las implementaciones que
permiten compararlas y determinar bajo qué circunstancias se puede considerar una
implementación más adecuada que otra.
A lo largo del capítulo se supone que el lector conoce los constructores habituales que
ofrecen loslenguajes de programación imperativos más habituales, como Modula-2, Pascal o
C y, en general, todos aquellos que se pueden considerar derivados del Algol; por ello, no
se explicarán en detalle los esquemas adoptados en Merlí, sino que tan sólo se mostrará su
sintaxis, fácilmente traducible a cualquiera de ellos. Eso sí, se insistirá en los aspectos
propios de la metodología de uso de tipos abstractos,derivados básicamente de la
distribución en universos de las aplicaciones.

2.1 El lenguaje de implementación
En el primer capítulo se ha destacado la diferencia entre la especificación y la implementación
de un TAD, que resulta en su visión a dos niveles diferentes. En concreto, dada la
especificación (única) de un tipo se pueden construir diversas implementaciones y así
escoger la más adecuada encada contexto de uso. Cada una de estas implementaciones se
encierra en un universo diferente, llamado universo de implementación, en contraposición a
los universos de especificación y de caracterización explicados detalladamente en el capítulo
anterior. Notemos que un universo de implementación no puede existir de forma
independiente, sino que siempre se referirá a una especificación yaexistente; para

© Los autores, 1998; © Edicions UPC, 1998.

9
0
Estructuras de datos. Especificación, diseño e implementación
__________________________________________________________________________________

establecer claramente el nexo entre un universo de implementación y el universo de
especificación correspondiente, se consignará siempre en la cabecera del primero el nombre
del segundo precedidopor la palabra clave "implementa".
La construcción de un universo de implementación consta de dos fases:
- Elección de una representación para los diferentes géneros definidos en la
especificación. Es habitual el uso de tipos auxiliares para estructurar el resultado, los
cuales son invisibles a los usuarios del universo1. También se pueden definir
constantes, implícitamente privadas.
-Codificación de todas y cada una de las diversas operaciones visibles de la
especificación, en términos de las representaciones que se acaban de escribir.
Igualmente puede ser necesario, e incluso recomendable, usar una o más operaciones
auxiliares que surjan de la implementación de las operaciones usando la técnica de
diseño descendente1; las operaciones auxiliares de la implementación no han de serforzosamente las mismas de la especificación, y en general no lo son.

universo U_IMP implementa U
usa U1, ..., Un
const c1 vale v1, ... fconst
tipo T1 es ... ftipo
...
tipo privado Taux1 es ... ftipo
...
función F1 ...
...
función / acción privada Faux1 ...
...
funiverso
Fig. 2.1: esquema general de los universos de implementación.

Tanto en la representación como en la codificación de las operaciones...