PDF de programación - Tipos de datos abstractos - Programación I

TIPOS DE DATOS ABSTRACTOS



PROGRAMACIÓN I



ARISTIDES DASSO, ANA FUNES



Área de Programación y Metodologías de Desarrollo del Software

Departamento de Informática

Facultad de Ciencias Físico-Matemáticas y Naturales

Universidad Nacional de San Luis

Argentina

2014

A. DASSO, A. FUNES



TIPOS DE DATOS ABSTRACTOS

Tipos de Datos Abstractos (TDA)

Abstracciones

La abstracción es una capacidad intelectual que poseemos los seres humanos que nos permite
concentrarnos en los aspectos importantes de un problema, dejando de lado los detalles irrelevantes.
Esta capacidad nos permite, asimismo, dividir el problema en partes más pequeñas y, en
consecuencia, más fácilmente tratables, para luego integrar todo en una solución. Es decir, es una
capacidad humana que nos permite lidiar con la complejidad.

Cuando programamos resolvemos un problema y creamos un programa que es una abstracción
de la realidad; en consecuencia, es importante contar con mecanismos de programación que
favorezcan la abstracción. Si analizamos los lenguajes de programación convencionales, podemos
ver que cuentan con un mecanismo que ayuda a la abstracción: la modularidad. Así, cuando
hacemos uso de un módulo (por ejemplo, una función en C) en un programa, uno sólo se debe
preocupar por conocer qué es lo que ese módulo hace, es decir, qué funcionalidad provee, sin
preocuparse por saber cómo lo hace. Además, la modularidad nos proporciona un medio para
descomponer una tarea en partes más pequeñas. Es decir, la modularidad en programación, llega
bastante cerca de capturar el significado de abstracción.

Sin embargo, este tipo de abstracción, referida como abstracción procedural, no es suficiente.
En programación, existe también lo que se conoce como abstracción de datos, que nos lleva al
concepto de Tipo de Dato Abstracto (TDA). Un TDA define datos de forma abstracta
caracterizados por las operaciones que se pueden llevar a cabo sobre ellos. Esto significa que
podemos decir que un TDA puede ser definido definiendo las operaciones que lo caracterizan.

Cuando un programador hace uso de un objeto de dato abstracto, sólo se preocupa del
comportamiento que ese objeto exhibe y no de los detalles de cómo ese comportamiento es logrado
por medio de una implementación. Es decir, se preocupa por conocer qué hacen esas operaciones
sobre el dato pero no cómo lo hacen. El comportamiento de un objeto de dato abstracto es capturado
por el conjunto de operaciones que lo caracterizan. La información de implementación, tal como la
forma en que el objeto es representado internamente en el almacenamiento, es necesaria conocerla
sólo cuando se quiere definir la forma en que sus operaciones características van a ser
implementadas. Así, el usuario de un objeto de dato abstracto no necesita conocer la
implementación del mismo, solo debe conocer cuáles son las operaciones características para operar
con objetos de ese tipo de dato abstracto. Es decir, la implementación de los objetos de datos
abstractos necesita conocerla solo aquel que hará su implementación y no quién o quiénes la usen.

Los TDA son muy similares a los tipos primitivos provistos por un lenguaje de programación. El
usuario de un tipo primitivo, tal como el tipo entero o arreglo de caracteres, solo se preocupa por
crear objetos de esos tipos y luego usarlos, llevando a cabo operaciones sobre ellos. Este usuario,
por lo general, no se preocupa de la forma en que esos objetos de datos se encuentran representados
o soportados en el almacenamiento; asimismo, ve las operaciones que sobre estos datos se pueden
llevar a cabo como atómicas e indivisibles, cuando en realidad varias instrucciones de máquina
pueden estar siendo requeridas para llevarlas a cabo. Además, en general, el usuario no puede
descomponer esos objetos. Consideremos, por ejemplo, el tipo primitivo entero. Un programador
puede necesitar declarar objetos de datos de tipo entero y llevar a cabo las operaciones aritméticas
usuales sobre ellos; sin embargo, usualmente, no le va a interesar ver su representación interna
como una cadena de bits, ni tampoco le interesa conocer qué instrucciones de máquina ejecuta el
compilador para llevar a cabo las operaciones requeridas.

Si bien, decíamos que los TDA son muy similares a los tipos primitivos de los lenguajes, la
diferencia está en el nivel de abstracción considerado en cada caso. En el caso de los tipos

Departamento de Informática - U.N.S.L. Argentina

Página 2 de 7

Programación I

A. DASSO, A. FUNES



TIPO DE DATOS ABSTRACTO

primitivos, el programador hace uso de una abstracción que ya se encuentra realizada o
implementada en un nivel de detalle más bajo: en el lenguaje de la máquina al cual traduce el
compilador del lenguaje de programación. En el caso de los TDA, estos también se encuentran
implementados a un nivel y usados a otro; sin embargo, un TDA es definido por alguien (muchas
veces el programador usuario), dando su implementación por medio de código escrito en el mismo
lenguaje de programación. Este código define el tipo de dato por medio de las operaciones que se
pueden realizar sobre él. Una vez definido un TDA, este código queda disponible para ser reusado
en otros programas cuantas veces se quiera.

Así, por ejemplo, podríamos definir en C un TDA Racional para operar con números
racionales, dando su representación interna o implementación así como sus operaciones
características, tales como la suma, el producto, la resta, etc. Una vez definido el TDA Racional,
este nos queda disponible para ser usado en nuevos programas C cuantas veces lo deseemos. Quien
quiera que lo use, sólo deberá conocer cuál es el nombre del TDA así como cuáles son las funciones
con las cuales puede operar, y no deberá preocuparse por cuál es la representación interna de un
dato de tipo Racional ni por cómo esas operaciones son llevadas a cabo internamente.

Otro ejemplo podría ser un TDA stack_of_char que nos permita operar con pilas de
caracteres. Este podría ser definido por solo tres operaciones sobre las pilas: una operación push,
que inserta un dato en la pila; otra operación pop, que extrae un elemento de la pila (con la
restricción de que cada pop siempre remueve el último elemento insertado y que no puede hacerse
sobre una pila vacía) y una operación peek, que permite examinar cuál es el elemento que se
encuentra en el tope de la pila, sin removerlo.

En un lenguaje de programación, el programador puede definir un nuevo tipo no provisto por el
lenguaje junto con las operaciones asociadas al nuevo tipo de datos, a través de la definición de un
TDA. Esto lo hará utilizando los mecanismos y herramientas (tipos de datos primitivos y sus
operaciones) que provea el lenguaje. Es importante notar que existe una diferencia fundamental
entre el Tipo de Dato Abstracto y la Estructura de Datos usada en su implementación. Así, por
ejemplo, el TDA stack_of_char puede ser implementado usando diversas estructuras de datos,
como por ejemplo por medio de un arreglo o usando punteros.

Ocultamiento de la Información

Un principio subyacente a los TDA es que exista ocultamiento de la información (information
hiding, en Inglés), que quiere decir que quien usa el TDA debería poder interactuar solamente con
las características públicas del TDA, sus operaciones características, y no tener acceso a la
implementación del mismo.

Cuando, en un lenguaje de programación, definimos un TDA existen dos elementos
diferenciados: (a) la interfaz pública de utilización y (b) la implementación interna de los objetos de
datos. Como ya dijimos, a la hora de utilizar el TDA, la representación interna debería permanecer
oculta al usuario del TDA, quién solo debería poder manipular los datos por medio de la invocación
a las operaciones de la interfaz pública (las operaciones definidas sobre el TDA) para operar con sus
elementos. Algunos lenguajes proveen una sintaxis adecuada para definir TDA, como por ejemplo
el lenguaje Modula-2, o el lenguaje ADA que provee los paquetes (packages) como mecanismo
para definir TDA. En otros casos, es necesario encontrar los mecanismos propios del lenguaje para
darle soporte a la definición de un TDA.

Definición de un TDA en C

Durante el proceso de resolución del problema, podemos encontrarnos frente a una situación en
que el lenguaje, cualquiera sea el que estemos utilizando, no nos provea con los tipos adecuados al

Departamento de Informática - U.N.S.L. Argentina

Página 3 de 7

Programación I

A. DASSO, A. FUNES



TIPO DE DATOS ABSTRACTO

problema que estamos resolviendo. En esa situación podemos definir nuestros propios TDA.

Veamos, entonces, cómo definir un TDA en C. Una posible solución es crear un archivo de
cabecera por cada TDA que definamos. Este archivo quedará disponible para ser usado en nuestros
programas C cuantas veces sea necesario simplemente haciendo un #include del mismo. Como
se puede notar, si bien el TDA se encuentra encapsulado dentro de un archivo de cabecera, no
cumple con el principio de ocultamiento de la información. Para logra esto en C, deberíamos crear
una biblioteca de linking estático; sin embargo, por razones de simplicidad, haremos uso de la
solución que emplea un archivo de cabecera por cada TDA. Se espera, entonces que los usuarios del
TDA lo empleen disciplinadamente,