Estructura de Datos

ESTRUCTURA DE DATOS
Con la aparición de los lenguajes de programación estructurados en la década de los 60, surge el concepto de tipo de datos (Ing., data type), definido como un conjunto de valores que sirve de dominio de ciertas operaciones. En estos lenguajes (C, Pascal y similares, derivados todos ellos -de forma más o menos directa- de Algol), los tipos de datos sirven sobre todo paraclasificar los objetos de los programas (variables, parámetros y constantes) y determinar qué valores pueden tomar y qué operaciones se les pueden aplicar.
Resumiendo, se puede definir un tipo abstracto de datos como un conjunto de valores sobre los que se aplica un conjunto dado de operaciones que cumplen determinadas propiedades. ¿Por qué "abstracto"? Éste es un punto clave en la metodología que sepresentará y se aplicará en todo el libro. El calificativo "abstracto" no significa "surrealista" sino que proviene de "abstracción", y responde al hecho de que los valores de un tipo pueden ser manipulados mediante sus operaciones si se saben las propiedades que éstas cumplen, sin que sea necesario ningún conocimiento ulterior sobre el tipo; en concreto, su implementación en la máquina esabsolutamente irrelevante. En el caso de los enteros de Pascal, cualquier programa escrito en este lenguaje puede efectuar la operación soy (siendo x e y dos variables enteras) con la certeza de que siempre calculará la suma de los enteros x e y, independientemente de su representación interna en la máquina que está ejecutando el programa (complemento a 2, signo y magnitud, etc.) porque, sea ésta cualsea, la definición de los enteros de Pascal asegura que la suma se comporta de una manera determinada. En otras palabras, la manipulación de los objetos de un tipo sólo depende del comportamiento descrito en su especificación (Ing., especificación) y es independiente de su implementación (Ing., implementación):
- La especificación de un TAD consiste en establecer las propiedades que lo definen.Para que sea útil, una especificación ha de ser precisa (sólo tiene que decir aquello realmente imprescindible), general (adaptable a diferentes contextos), legible (que sirva como instrumento de comunicación entre el especificador y los usuarios del tipo, por un lado, y entre el especificador y el implementador, por el otro) y no ambigua (que evite posteriores problemas de interpretación). Laespecificación del tipo, que es única, define totalmente su comportamiento a cualquier usuario que lo necesite.
Según su grado de formalismo, será más o menos fácil de escribir y de leer y más o menos propensa a ser ambigua o incompleta.
- La implementación de un TAD consiste en determinar una representación para los valores del tipo y en codificar sus operaciones a partir de esta representación,todo ello usando un lenguaje de programación convencional. Para que sea útil, una implementación ha de ser estructurada (para facilitar su desarrollo), eficiente (para optimizar el uso de recursos del computador) y legible (para facilitar su modificación y 2 0 Estructuras de datos. Especificación, diseño e implementación mantenimiento). Una implementación del TAD (puede haber muchas, cada una deellas pensada para un contexto de uso diferente) es totalmente transparente a los usuarios del tipo y no se puede escribir hasta haber determinado claramente su especificación; el cambio de una implementación por otra que respete el comportamiento deseado del tipo no ha de cambiar en absoluto la especificación ni, por consiguiente, la visión que de él tienen sus usuarios, que se limitarán arecompilar la aplicación correspondiente.
La verdadera utilidad de los TAD aparece en el diseño de nuevos tipos de datos. Imaginemos
Que se quiere construir un programa Pascal que calcule la suma de una secuencia de números complejos introducida por el terminal, acabada por el valor 0 + 0i (para simplificar la escritura de algunos detalles irrelevantes, supondremos que tanto la parte real como la...