01_td ed tda

Estructuras de Datos y Algoritmos
Perla Señas y Sergio Martig - 2005

Módulo I
Tipos de datos, estructuras de datos y tipos de datos abstractos.
Aunque los conceptos de tipo de datos (TD), estructura de datos (ED) y tipo de datos
abstracto (TDA) se han visto en los cursos introductorios de programación,
comenzaremos este módulo puntualizando sus características. Es importante destacar
que si bienson tres conceptos que tienen que ver con la representación de los datos de
un problema, y a veces se los confunde, tienen significados distintos.
En un lenguaje de programación, el tipo de datos de una variable1 está determinado
por el conjunto de valores que dicha variable puede tomar y el conjunto de
operaciones que se pueden realizar con variables del mencionado tipo (como
argumentos y/o comoresultado). Por ejemplo en Pascal el tipo boolean tiene dos
valores, éste se refiere al conjunto {false, true}, es decir que una variable de este tipo
podrá tomar sólo uno de esos valores; con respecto a las operaciones cuenta con la
negación, la conjunción y la disyunción cuya representación es: not, + y *
respectivamente. En cambio el tipo array [1..3] of boolean cuenta con ocho valores,estando determinado por el conjunto {(false,false,false) , (false,false,true) ,
(false,true,false) , (false,true,true) , (true,false,false) , (true,false,true) ,
(true,true,false), (true,true,true)}, donde cada una de las ternas representa uno de los
valores que puede tomar una variable declarada del mencionado tipo.
Una estructura de datos es una colección de variables (del mismo tipo o no),organizadas de alguna manera determinada. Se considera a la célula como la unidad
básica de una estructura de datos.
Además de la capacidad propia de un lenguaje de programación para agrupar las
células de una estructura de datos (por ejemplo arreglos, registros, etc.), existe la
posibilidad de crear estructuras relacionando o enlazando celdas usando apuntadores.
Un apuntador es un valor que direcciona unadeterminada célula, es decir que permite
que se pueda acceder a ella. Cuando se representa gráficamente una estructura de
datos, si un campo de una célula X es un apuntador a otra celda Y, dicho apuntador se
representa gráficamente por medio de una flecha que parte del campo correspondiente
de X hacia la célula Y.

apuntador

célula X

célula Y

Un apuntador puede implementarse como un cursor(índice de un arreglo) cuando las
células son componentes de un arreglo, o como un puntero, si es que el lenguaje de
programación cuenta con dicha facilidad. Veremos esto más adelante en detalle.
1

Puede ser también una constante o el resultado que devuelve una
función

Estructuras de Datos y Algoritmos
Perla Señas y Sergio Martig - 2005

Un tipo de datos abstracto queda determinado por el modelomatemático que lo
sustenta y por un conjunto de operaciones que se definen sobre el mencionado
modelo.
En relación con un TDA se puede hablar de definirlo o de implementarlo. Aunque
frecuentemente se confunden ambas expresiones, estas tienen significados
perfectamente diferenciados.
Definir un TDA es dar el modelo y el conjunto de operaciones correspondientes,
expresando con claridad y sin ambigüedadlas características de cada una de ellas. Por
ejemplo, podría definirse el TDA Número Complejo de la siguiente manera:
- Modelo: par ordenado de números reales.
- Conjunto de operaciones: suma, diferencia, producto, módulo, argumento,
leer_número, imprimir_número
- Descripción precisa de cada una de las operaciones
La definición de un TDA debe ser clara y precisa, ya que por un lado está elimplementador del TDA quien tomará dicha descripción como base y la seguirá
fielmente, y por otro lado está el usuario del TDA que lo usará teniendo en cuenta
también lo que indica la definición. Obviamente, para que luego el programa funcione
correctamente, ambas cosas deben concordar.
Para implementar un TDA se debe encontrar una estructura de datos adecuada (o un
TDA estructural) para representar...