Tipos Abstractos de Datos (TDA)

Cap´
ıtulo

12

Tipos Abstractos de Datos (TDA)
Hasta ahora se ha trabajado con tipos de datos primitivos y arreglos. Los Tipos de
Datos Abstractos (TDA) nos permiten realizar una mayor abstracci´n de las cosas que
o
existen en el mundo real, pues nos permiten olvidar detalles sobre implementaciones y
mantener la esencia.
Cuando se tiene un tipo de dato primitivo como los enteros, setiene la definici´n
o
de entero Z, que representa datos de tipo entero. En los enteros, se tienen definidas las
operaciones aritm´ticas +, ∗, −, /, mod que nos permiten realizar operaciones con este tipo
e
de datos sin conocer como se esta realizando una suma o una divisi´n a nivel de m´quina.
o
a
En este libro se definieron funciones de lectura y escritura a flujos de datos para enteros.
Unavez definida la funci´n si otra persona desea utilizarla lo unico que debe hacer es llamar
o
a la funci´n e ignorar los detalles implementacion de la funci´n en si.
o
o

12.1. Estructura y Operaciones
Se puede considerar un TDA como una estructura que tiene una serie de operaciones. Como estructura, los tipos abstractos de datos permiten agrupar varios datos que
mantengan alg´n tipo derelaci´n aunque sean de distinto tipo. Si se tienen los conjuntos
u
o
A1 , A2 , A3 , ..., An , que definen diferentes tipos de datos se puede definir el TDA A dado el
producto cartesiano como A = A1 × A2 × A3 × ... × An .
Las operaciones que se pueden definir sobre un tipo de datos son las constructoras,
las analizadoras, las modificadoras, las liberadoras, y otras funciones de utilidad que serequieran en un TDA.
Funciones constructoras: Las funciones constructoras permiten como su nombre lo indica construir la estructura del TDA dado. Debe tenerse en cuenta que las variables
no estan definidas. Para el caso de los enteros si se desea definir una variable como
entera x ∈ Z la equivalencia de dicha expresi´n en un lenguaje de programaci´n coo
o
mo C++ ser´ int x. Si se tratase de unarreglo de tipo entero x ∈ Z∗ , su definici´n
ıa
o
en C++ ser´ la encargada de crear la variable como int* x. Los tipos primitivos
ıa
de datos no necesitan ser construidos en memoria pero en el caso de TDA din´micos
a
definidos por un programador en lenguaje C++ se requiere una asignaci´n en la
o
memoria con el operador new.
109

110

CAP´
ITULO 12. TIPOS ABSTRACTOS DE DATOS (TDA)Funciones Modificadoras: Estas funciones permiten cambiar un dato de un TDA, est´n
a
relacionadas con las asignaciones.
Funciones Analizadoras: Estas funciones permiten obtener un dato miembro de un
TDA.
Funciones Liberadoras: Estas funciones permiten devolver la memoria empleada por
un TDA al sistema operativo. Los tipos de datos primitivos no requieren esta definici´n pero tipos de datos comolos arreglos o los TDA escritos por un programador
o
deben ser liberados. Est´n asociadas al operador delete en C++.
a
Funciones de persistencia: Son funciones que permiten mantener el dato a trav´s del
e
tiempo. En este caso se han utilizado los flujos de datos para leer o escribir los datos
en archivos o enviarlos a la salida est´ndar de la consola.
a

12.2. Definici´n de un TDA
o
Paradefinir un TDA, llamado A partiendo de la definici´n de producto cartesiano
o
o
a
A = A1 × A2 × A3 ... × An La definici´n de dicho TDA en C++ ser´ la siguiente:
struct
A_1
A_2
A_3
.
.
.
A_n
};

base_A{
a_1;
a_2;
a_3;

a_n;

typedef base_A* A;
La palabra struct declara la construcci´n de la estructura como el producto cartesiano
o
y typedef nos permite nombrar un puntero a laestructura base A y as´ poder manipular
ı
el TDA como par´metro en una funci´n o retornarlo como salida de funciones sin realizar
a
o
cambios adicionales utilizando memoria din´mica.
a
Como ejemplo pueden definirse los numeros complejos C como un TDA constituido por
dos numeros reales, uno que representa la parte real del y otro que representa la parte
imaginaria. C = R × R. En C++ se...