Programación Estructuras de Datos 7

Uso y diseño de tipos abstractos de datos
365
__________________________________________________________________________________

Capítulo 7 Uso y diseño de tipos abstractos de datos

A lo largo de los diferentes capítulos de este libro se ha introducido el concepto de tipo
abstracto de datos como eje central en el desarrollo de software a gran escala, y se han
presentado varias estructuras dedatos de interés surgidas del estudio de su implementación
eficiente. Ahora bien, las aplicaciones de gran tamaño son algo más que la simple definición
de uno o más tipos abstractos de datos: consisten en algoritmos, muchas veces complejos,
que se basan, o bien en el uso de los tipos clásicos vistos en los capítulos 3 a 6, ya sea tal
como se han definido o con modificaciones, o bien en la definiciónde nuevos tipos
abstractos que respondan a una funcionalidad y a unos requerimientos de eficiencia
determinados; en este último capítulo nos centramos precisamente en la problemática de
cómo usar tipos ya existentes y cómo crear nuevos tipos de datos.
Cabe decir que, actualmente, no hay ninguna estrategia universal de desarrollo de
programas a gran escala; dicho de otra manera, no existe unafórmula mágica que, dado un
enunciado, permita identificar claramente los tipos abstractos que deben formar parte de la
solución ni tampoco las implementaciones más eficientes. Por ello, este capítulo se ha
planteado como una colección de problemas resueltos, cuya elección responde al intento
de ilustrar algunas situaciones muy habituales y sus resoluciones más comunes, que
pueden extrapolarse a otroscontextos.
Como punto de partida es necesario recordar que, tal como se expuso en el apartado 2.3.5,
la programación con tipos abstractos de datos obliga frecuentemente a elegir entre eficiencia
y modularidad como criterio principal de diseño, tanto al usar tipos conocidos como al definir
nuevos tipos, y éste será el punto central de discusión en los enunciados aquí resueltos. Es
decir, unaaplicación altamente modular construida como una combinación de módulos
simples, ya existentes e implementados con sendas estructuras de datos, generalmente
acaba siendo un programa no del todo eficiente, ya que, por un lado, puede repetirse
información redundante en las diversas subestructuras y por tanto el espacio necesario será
voluminoso; por otro, puede que la codificación de las operaciones de untipo
(evidentemente, hecha después de su especificación) no explote adecuadamente todas las
características de la estructura subyacente (v. el ejemplo de los conjuntos del apartado
2.3.5). El usuario o diseñador ha de decidir cuál es el criterio más importante y desarrollar su

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

3
66
Estructuras de datos. Especificación, diseño e implementación__________________________________________________________________________________

software en consecuencia. Debe considerarse, no obstante, que hay excepciones a la regla
general en las que un programa altamente modular es también el más eficiente, en cuyo caso
no hay duda posible.
Para la resolución de los problemas presentados en este capítulo, supondremos que los
usuarios y los diseñadores tienen asu disposición una biblioteca de universos en la que
residen, como mínimo, todos los tipos vistos a lo largo del libro junto con los
enriquecimientos más interesantes que han aparecido (recorridos de árboles y grafos,
algoritmos de caminos mínimos, etc.). A veces supondremos que estos tipos presentan
algunas operaciones adicionales de interés general (por ejemplo, longitud o pertenencia en
listas).La existencia de esta biblioteca de componentes reusables es fundamental en el
desarrollo de programas a gran escala, sobre todo en aquellas instalaciones compartidas por
un gran número de usuarios, porque permite reutilizar los módulos que en ella residen,
normalmente a través de las instancias oportunas, y reducir así el tiempo de desarrollo de
nuevas aplicaciones.

7.1 Uso de tipos...