PDF de programación - Tema 3 - Tipos abstractos de datos

TEMA 3

TIPOS ABSTRACTOS DE DATOS


1. Introducción a la programación con TADs
2. Especificación de TADs
3. Implementación de TADs
4. Módulos. Diseño modular
5. Estructuras de datos dinámicas



Bibliografía:



Fundamentals of Data Structures in C++
E. Horowitz, S. Sahni, D. Mehta
Computer Science Press, 1995
Data Abstraction and Problem Solving with C++, Second
Edition
Carrano, Helman y Veroff



Tipos abstractos de datos



1

3.1 Introducción a la programación con tipos abstractos

de datos

La abstracción es un método de resolución de problemas

Los problemas reales tienden a ser complejos porque involucran demasiados
detalles, y resulta imposible considerar todas las posibles interacciones a la vez.
Hay estudios en Psicología que afirman que en la memoria a corto plazo sólo
es posible almacenar 7 elementos distintos.


Una abstracción es un modelo simplificado de un problema, donde se con-

templan los aspectos de un determinado nivel, ignorándose los restantes.
Por ejemplo. Para indicarle a un robot cómo cambiar la rueda de un coche po-
demos utilizar una descripción con distintos niveles de abstracción:

1. Bajar del coche
2. Sacar la rueda de repuesto y el gato
3. Quitar la rueda pinchada
4. Poner la rueda de repuesto
5. Guardar la rueda pinchada
Para quitar la rueda pinchada

3.1. Se coloca el gato debajo del coche
3.2. Se levanta el coche haciendo girar la manivela del gato
3.2. ...


Este es un ejemplo de resolución de problemas por refinamientos sucesivos o
diseño descendente.


El razonar en términos de abstracciones conlleva una serie de ventajas:


— La resolución de los problemas se simplifica
— Las soluciones son más claras y resulta más sencillo razonar sobre su co-

rrección

— Pueden obtenerse soluciones (o fragmentos de ellas) de utilidad más gene-

ral, que puedan adaptarse para resolver otros problemas

— Permite la división de tareas



Tipos abstractos de datos



2

3.1.1 La abstracción como metodología de programación
La programación es un proceso de resolución de problemas y como tal tam-

bién se beneficia del uso de abstracciones.


La evolución de la Programación muestra una tendencia a incluir mecanismos

de abstracción cada vez de más alto nivel
— Ensamblador
— Lenguajes de alto nivel

— Estructuras de control
— Procedimientos y funciones
— Tipos de datos
— Módulos
— Tipos abstractos de datos
— Clases en programación orientada a objetos

— Generadores de aplicaciones (hojas de cálculo, gestores de bases de datos,

diseño visual de interfaces, ...)



En todos estos mecanismos, aunque a diferente nivel, tenemos una situación

como esta

Especificación

Abstracción

Implementación


Un mecanismo de abstracción es una barrera que, para una cierta entidad, deja a
un lado la especificación, con la que los clientes de la abstracción pueden ra-
zonar, y a otro la implementación. De esta forma, los clientes sólo han de en-
tender la especificación para utilizar la entidad, a través de su abstracción.



Tipos abstractos de datos



3

La abstracción funcional

Hace tiempo que se descubrió y hoy en día es un lugar común en prácticamente


todos los lenguajes de programación: las funciones y los procedimientos.

— Se reúnen un conjunto de sentencias que realizan una determinada opera-

— Se les asigna un nombre y se parametrizan por medio de argumentos, cons-
truyéndose así una abstracción del conjunto de sentencias: la cabecera del
procedimiento o la función

ción sobre unos datos (la implementación)


— Para que los clientes puedan usar esta abstracción (invocar al procedimien-
to o la función) se le adjunta una especificación que indica sus condiciones
de uso –precondición– y la operación que realiza –postcondición–. La es-
pecificación también se puede realizar informalmente.


De esta forma se puede utilizar ese conjunto de sentencias como si fuese una
operación definida en el propio lenguaje, abstrayéndonos de los detalles de su
implementación.


La abstracción de datos



— Tipos predefinidos

El nivel de abstracción de los datos ha ido aumentando a lo largo de los años

Por ejemplo, en un lenguaje de programación de alto nivel, generalmente,
no debemos preocuparnos por la representación binaria de los caracteres,
los enteros o los reales.


— Tipos de datos definidos por el programador

Por ejemplo, un array de un cierto tipo se representa internamente como
una sucesión de celdas de memoria adyacentes, donde el acceso directo se
consigue mediante sencillas operaciones aritméticas.


— Tipos abstractos de datos (TADs) definidos por el programador

Una entidad donde se reúnen un tipo de datos y las operaciones que mani-
pulan los valores de ese tipo.



Tipos abstractos de datos



4

Para entender el concepto de tipo abstracto de datos analicemos la diferencia

entre los tipos predefinidos y los tipos definidos por el programador.
— Un tipo predefinido es un tipo abstracto de datos porque

— Está fijado el conjunto de valores permitidos y los compiladores se en-
cargan de garantizar que no se asignan valores erróneos. No es posible
acceder directamente a la representación interna de los datos1.

— Está fijado el conjunto de operaciones permitidas sobre dichos valores

y el compilador se encarga de garantizar que se usan correctamente.

— Como programadores sólo necesitamos conocer el comportamiento de
las operaciones (por ejemplo, los enteros se rigen por unas leyes alge-
braicas conocidas por todos) sin que tengamos acceso a su implementa-
ción concreta, ni nos interese lo más mínimo.

— Un lenguaje no soporta la implementación de tipos abstractos de datos si

— La estructura de datos donde se representa la información se define por

una parte y las operaciones que manipulan esos datos por otra.

— No es posible definir una abstracción que reúna la estructura de datos y

las operaciones de forma que
—

la representación de los datos y la implementación de las operacio-
nes sea oculta para los clientes y, por lo tanto,

— el acceso a la información esté protegido y los clientes no puedan
hacer ninguna suposición sobre la implementación de las operacio-
nes que no aparezca explícitamente en la especificación.


Por ejemplo, si queremos definir un tipo de datos para representar fechas, po-
demos utilizar una representación como esta:


typedef int TDia;
typedef enum { enero, febrero, ... , diciembre } TMes;
typedef int TAnyo;
typedef struct { TDia dia; TMes mes; TAnyo anyo; } TFecha;


Si se tiene libre acceso a la representación del tipo de datos, es posible realizar
operaciones absurdas con respecto a la semántica pretendida, como:


fecha.mes = febrero;
fecha.dia = 30;



1 Esto no es cierto en general, pues normalmente se pueden hacer manipulaciones binarias sobre los valores de tipos predefi-

nidos. Sin embargo, debemos considerar que este es un mecanismo “peligroso” con el cual saltarnos la barrera de la abstracción.


Tipos abstractos de datos



5

3.1.2 Tipos abstractos de datos



Un tipo abstracto de datos se compone de

— Una especificación
— Una implementación

Especificación de un tipo abstracto de datos

La especificación de un TAD debe incluir:



— El dominio de valores del tipo
— Las operaciones que permiten manipular los valores del tipo –y que pueden

hacer referencia a otros tipos–

— El comportamiento de las operaciones (especificado formal o informal-

mente)

Como ejemplo, escribamos la especificación informal del TAD fecha



— Dominio: las fechas desde el 1/1/1
— Las operaciones, con su comportamiento especificado informalmente


TFecha NuevaFecha ( TDia d, TMes m, TAnyo a );
// P: d/m/a cumplen las restricciones de una fecha, según el
calendario
// Q: devuelve una fecha que representa a la fecha d/m/a

int distancia ( TFecha f1, TFecha f2 );
// P:
// Q: devuelve la distancia, medida en número de días, entre
f1 y f2

TFecha suma ( TFecha f, int d );
// P:
// Q: devuelve la fecha resultante de sumar d días a la
fecha f
¡Cuidado! d puede ser un número negativo de forma que g no sea una fecha
posterior al 1/1/0. Algunas operaciones pueden fallar y es necesario deter-
minar algún mecanismo de tratamiento de errores.



Tipos abstractos de datos



6

TDia dia( TFecha f );
// P:
// Q: devuelve el día de la fecha f

TMes mes( TFecha f );
// P:
// Q: devuelve el mes de la fecha f

TAnyo anyo( TFecha f );
// P:
// Q: devuelve el año de la fecha f

TDiaSemana diaSemana( TFecha f );
// P:
// Q: devuelve el día de la semana correspondiente a la
fecha f

TFecha primerDiaMes( TDiaSemana d, TMes m, TAnyo a );
// P:
// Q: devuelve la primera fecha del mes m del año a cuyo
// día de la semana es d



Implementación de un tipo abstracto de datos

La implementación de un TAD consiste en:



— Elegir una estructura de datos para representar los valores del TAD con

ayuda de otros tipos ya disponibles.

— Implementar las operaciones del TAD como funciones o procedimientos,
usando la representación elegida, y de modo que se satisfaga la especifica-
ción.



En general cualquier TAD admite varias representaciones posibles.

— Por ejemplo, una secuencia de números de longitud variable se puede im-

plementar como
— un registro con un vector y un campo longitud,
— o como un vector con una marca al final.



Tipos abstractos de datos



7

Cuando hay varias representaciones posibles, normalmente una representación
concreta facilita unas determinadas operaciones y dificulta otras, con resp