Estructura de Datos

ESTRUCTURA DE DATOS


Conceptos preliminares

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 (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 datossirven sobre todo para clasificar los objetos de los programas (variables, parámetros y constantes) y determinar que valores pueden tomar y que operaciones se les puede aplicar.

Esta noción, no obstante, se revelo insuficiente en el desarrollo de software a gran escala, dado que el uso de los datos dentro de los programas no conocía mas restricciones que las impuestas por el compilador, lo queera muy inconveniente en los nuevos tipos de datos definidos por los usuario, sobre todo porque no se restringía de ninguna manera su ámbito de manipulación. Para solucionar esta carencia se introduce a mediados de la década de los 70 el concepto de tipo abstracto de datos (abstract data type; TDA), que considera un tipo de datos no solo como el conjunto de valores que lo caracteriza sino tambiéncomo las operaciones que sobre el se pueden aplicar, juntamente con las diversas propiedades que determinan inequívocamente su comportamiento.

En realidad, el concepto TDA ya existe en los lenguajes de programación estructurados bajo la forma de los tipos predefinidos, que se pueden considerar como tipos abstractos sin mucho esfuerzo. Por ejemplo, consideremos el tipo de datos de los enteros queofrece el lenguaje Pascal; la definición del TDA correspondiente consiste en determinar:
 Cuales son sus valores. Los números enteros dentro del intervalo [minint,maxint]
 Cuales son su operaciones. La suma, la resta, el producto y el cociente y le resto de la división.
 Cuales son las propiedades que cumplen estas operaciones. Hay muchas; por ejemplo: a+b=b+a, a*0=0, etc.

Resumiendo, sepuede 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.

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 estascumplen, sin que sea necesario ningún conocimiento anterior sobre el tipo; en concreto, su implementación en la maquina es absolutamente irrelevante. En otras palabras, la manipulación de los objetos de un tipo solo depende del comportamiento descrito en su especificación y es independiente de su implementación.

 La especificación de un TDA consiste en establecer las propiedades que lo definen.Para que sea útil, una especificación ha de ser precisa (solo tiene que decir aquello realmente imprescindible), general (adaptable a diferentes contextos), legible (que sirva como instrumento de comunicación entre el especificador y los usuario del tipo, por un lado; y entre el especificador y el implementador, por el otro) y no ambigua (que evite posteriores problemas de implementació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á mas o menos fácil de escribir y de leer, y mas o menos propensa a ser ambigua o incompleta.
 La implementación de un TDA consiste en determinar una representación para los valores del tipo y en codificar sus operaciones a partir de esta representación, todoello 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 mantenimiento).

Una implementación del TDA (puede haber muchas, cada una de ellas pensada para un contexto de uso diferente) es totalmente transparente a los...