Tipos
Abstractos de Datos y Programación por Objetos
Se discute qué es Abstracción de Datos y
Programación por Objetos, usando como base el lenguaje Pascal.
La
ingeniería de sistemas de información ha progresado gracias a la introducción
de nuevas técnicas para construir programas. El primer gran avance lo
constituye la programación modular, que complementa a la programación
estructurada. Otros logros lo constituyen los llamados lenguajes de cuarta
generación, que permiten desarrollar sistemas de información en un lenguaje muy
especializado. Pero conforme avanza la tecnología de computadores es necesario
crear programas cada vez más sofisticados. En la última década ha tomado gran
auge el uso de la programación por objetos, que tiene como requisito la
abstracción de datos, y que implica una nueva manera de diseñar programas. El
lenguaje Smalltalk ha causado gran
revuelo, hasta tal punto que existen compiladores para lenguajes como C++, que
han sacado la programación por objetos de los laboratorios de investigación,
para ser utilizados en el quehacer diario de las empresas.
La programación que utiliza
abstracción de datos se basa en el hecho de que en un programa se deben
integrar y combinar los tipos básicos de datos, como números y caracteres, para
formar estructuras de datos más complejas y así representar información dentro
del computador. En general existe una fuerte relación entre todos los datos
manipulados por un programa, por lo que es conveniente que esa relación esté
claramente especificada y controlada, de forma que cada parte del programa
"vea" sólo lo que necesita.
Esto último es muy importante
para separar el programa en partes independientes, o módulos, evitando así que
cambios en una parte produzcan errores en otras partes del programa. Por
ejemplo, en un programa que usa varios arreglos y matrices para almacenar
información, es frecuente que al aumentar el tamaño de una dimensión se olvide
aumentar la de los demás arreglos, por lo que el mantenimiento del programa es
más difícil. El objetivo perseguido al usar abstracción de datos es lograr
aislar todas estas dependencias, de forma que los cambios puedan ser hechos con
un mínimo de esfuerzo y en una forma localizada. En nada ayuda tener que buscar
por todo el programa en qué lugar debe hacerse cada cambio. También es
importante especificar mediante la abstracción de datos qué es cada estructura
de datos. Una lista, por ejemplo, es una estructura de datos que tiene un
comportamiento muy bien definido: pueden insertársele nuevos elementos,
recorrérsela, encontrar el primer y último elemento, etc. Un programador que
use el tipo de datos Lista no debe necesitar descubrir de nuevo ese concepto:
simplemente debe poderlo importar de una biblioteca.
Al implementar la Lista como un
Tipo Abstracto de Datos (ADT: Abstract Data Type en inglés), el
programador decide cuáles procedimientos se necesitan para manipular una lista,
y define su interrelación. Un usuario del tipo de datos "lista" no
necesitará entonces conocer cómo se interrelacionan (a nivel de implementación)
los datos ni los procedimientos que manipulan listas pues le bastará usar las
operaciones de la Lista para manejarla.
Al usar abstracción de datos el programador define cómo puede
comportarse cada una de las variables de su programa. O sea que además de usar
abstracción de procedimientos para construir el programa modularmente, deben
especificarse las operaciones válidas sobre los datos. El objetivo es programar
módulos que definan nuevos tipos de datos, y además que incluyan varios
procedimientos (operaciones) que permitan manipularlos. Este dúo
procedimiento-dato es un Tipo Abstracto de Datos. El programador-usuario del
ADT podrá manipular las variables del tipo de datos únicamente por medio de sus
procedimientos asociados. En un sólo módulo se "encapsula" el nuevo
tipo de datos junto con sus procedimientos.
Al hablar de ADTs se dice que se
usa Abstracción de Datos porque al definir un ADT el programdor especifica
cuáles son las estructuras de datos que su programa utiliza. Se dice que se usa
Encapsulamiento de Datos porque junto al tipo de datos también se definen las
rutinas que permitirán utilizarlo. Por medio del Ocultamiento de Datos se evita
que un programador-usuario del Tipo de Datos Abstracto cambie de forma impropia
el valor de una variable. Generalmente al usar ADTs también se usan iteradores,
que son módulos que permiten obtener todos los valores almacenados en una
variable compuesta, como lo son la lista o el arreglo.
{ Ejemplo de
Encapsulamiento }
{ Turbo Pascal v5.5 } { ADTs, sin ocultamiento }
TYPE TYPE
Persona_T = OBJECT Persona_T = RECORD
direccion: STRING[20]; direccion: STRING[20];
telefono : STRING[6]; telefono : STRING[6];
nombre
: STRING[35];
nombre : STRING[35];
cedula
: STRING[9];
cedula : STRING[9];
nacido :
INTEGER; nacido : INTEGER;
{ ... más campos ... } { ... más campos ... }
FUNCTION Edad : INTEGER; END;
{ Persona_T }
{ ... más métodos ... } { más operaciones ... }
FUNCTION
Edad(VAR p: Person_T)
END;
{ Persona_T } : INTEGER;
VAR VAR
p : Person_T; p : Person_T;
{...} {...}
i := p.Edad; i := Edad(p);
{ "p recibe el mensaje Edad" } { Se "calcula" la Edad de p }
|
|
Figura N° 2
|
Un lenguaje de programación
soporta el uso de Abstracción de Datos si tiene construcciones sintácticas que
le permiten al programador usar ADTs cómodamente. Por ejemplo, el Turbo
Pascal v5.5 soporta encapsulamiento, pues le permite al programador
definir un tipo de datos junto a sus operaciones, como se muestra en la
Figura 2. Sin embargo, la versión 5.0 de ese mismo lenguaje no
soporta encapsulamiento, aunque el programador puede simular encapsulamiento
usando módulos Turbo Pascal (unidades). El ejemplo de la Figura 2 muestra que al
implementar un ADT deben definirse dos cosas: primero, los campos que se
necesitan para almacenar los valores del dato, y segundo los procedimientos que
permiten utilizarlo.
El asociar un tipo de datos con
sus procedimientos en un módulo se conoce como encapsulamiento. En Pascal el
encapsulamiento se simula mediante unidades, y en Modula-2 usando módulos. En
otros lenguajes, como Turbo Pascal, Smalltalk, Simula y C++, el lenguaje
incluye construcciones sintácticas que permiten encapsular un tipo de datos,
también llamado una clase, con sus procedimientos. En este caso, los
procedimientos se conocen por los nombres "operación",
"procedimiento miembro" o "método". La diferencia entre una operación, en el
contexto de los ADTs, y un método, en el contexto de un lenguaje que soporta
encapsulamiento, es puramente sintáctica. En el ejemplo Turbo Pascal v5.5
de la Figura 2 la forma sintácticamente correcta de invocar al método
Edad() de Person_T es "p.Edad;" mientras que si se usa un lenguaje
que no soporta encapsulamiento (como Modula-2) debe usarse la conocida forma
sintáctica "Edad(p);".
La única diferencia entre las dos
formas de invocar a la operación (o método) Edad() es el lugar en que la
variable de tipo Person_T debe escribirse. La primera es la forma
"Orientada o los Objetos" porque la variable "p" aparece de
primero, mientras que la segunda es orientada a los procedimientos porque lo
primero que aparece es el nombre de la rutina. Es este el simple cambio
sintáctico que, con demasiada pompa, ha dado el nombre a la Programación
Orientada a los Objetos (OOP: Object Oriented Programming en
inglés). En el ejemplo de la Figura 2 la forma sintáctica
"p.Edad;" se interpreta como si el objeto "p" es un ente
activo en el programa, mientras que la forma "Edad(p);" es
interpretada como si el trabajo en un programa lo realizan los procedimientos (que
calculan), y no los objetos.
|
|
Procedimiento
|
Tipo de Dato
|
Mensaje
|
|
Encapsulación
|
Procedimiento
|
Tipo de Dato
|
Mensaje
|
|
Abstracción
|
Subrutina
|
Objeto
|
Parámetro
|
|
Especificación
|
Rutina
|
Clase
|
Argumento
|
|
Diseño
|
Método
|
ADT
|
|
|
Ocultamiento
|
Operación
|
Tipo Abstracto de Datos
|
|
|
|
Figura N° 3: Tabla de sinónimos
|
Los computólogos hemos tenido la
costumbre de crear muchos nuevos términos para viejos conceptos. Los términos
estructuran de datos, tipo de datos, tipo abstracto de datos, objeto, clase y
variable son muy similares. Todos sirven básicamente para lo mismo: definir
variables en un programa, o sea, instancias del tipo de datos (aunque tiene más
prestigio hablar de "objetos" o de ADTs, que de simples tipos). La
Figura 3 es una lista de los términos usados para referirse a los mismos
conceptos (aunque no todos son sinónimos exactos). Sin embargo, el contexto del
discurso es muy importante: al hablar de ADTs en Smalltalk necesariamente debe
suponerse que el concepto incluye cualidades como herencia y funciones
virtuales. Las mismas palabras dichas en el contexto de Pascal o Modula-2 no
pueden significar más que abstracción de datos.
Entonces, una operación es una rutina que está asociada a un tipo de
datos, y que permite manipularlo, examinarlo y cambiarlo. El término "método"
es sinónimo de operación y, aunque es bastante confuso, es el utilizado en
ambientes Smalltalk.
Intrínsecamente ligado al
concepto de encapsulamiento y abstracción está el concepto de ocultamiento de
datos. Al ocultar datos, básicamente lo que se persigue es evitar que la
representación usada para un ADT sea accesible a un programador-usuario. Por
ejemplo, al implementar el ADT pila puede usarse una lista de nodos con
punteros, o un arreglo. Si la representación del ADT es privada, entonces al
usar una pila el programador no podría saber si la implementación que usa es
una o la otra. El ocultamiento de datos es muy importante para lograr una mejor
modularización, pues garantiza que el programador descuidado tenga acceso
controlado a las campos que conforman una instancia de un ADT, evitando así que
destruya inadvertidamente alguna relación necesaria entre esos campos.
Paradójicamente, los muy conocidos lenguajes Smalltalk y Simula soportan tanto
abstracción como encapsulamiento de datos, pero que no soportan ocultamiento de
datos. El que los diseñadores de esos lenguajes no consideraran necesario el
ocultamiento de datos indica que no es hasta hace muy pocos años que se ha
llegado a entender bien cuáles son las cualidades que debe tener un programa
que está bien modularizado.
La Programación
por Objetos es una extensión natural del uso de abstracción de datos. Si los
conceptos asociados con ADTs se les agrega la Herencia y le Polimorfismo el
resultado es OOP. Sin embargo, en la mente de muchos autores y programdores el
término Programación por Objetos sólo significa usar herencia y polimorfismo,
aunque no se utilice ocultamiento de datos o programación estructurada. OOP
introduce nuevos vocablos para viejos conceptos, lo que en muchos casos
confunde al neófito.
La herencia es una facilidad puramente sintáctica del lenguaje de programación
que permite extender un tipo de datos, agregándole al final nuevos campos. El
efecto de la herencia puede simularse en la mayoría de los lenguajes
tradicionales, pero el resultado es un programa menos elegante.
{ SIN Herencia } { CON Herencia }
TYPE TYPE
Punto_T = RECORD Punto_T = OBJECT
x,y : INTEGER x,y : INTEGER
END; END;
Circulo_T = RECORD Circulo_T = OBJECT(Punto_T)
p : Punto_T;
r : REAL; r : REAL;
END; END;
PROCEDURE Mueva(VAR p: Punto_T); PROCEDURE Mueva(VAR p: Punto_T);
VAR VAR
p : Punto_T; p : Punto_T;
c : Circulo_T; c : Circulo_T;
BEGIN BEGIN
p.x := ... p.x := ...
c.p.y := ... { .p se ve feo } c.y := ... { Uso directo de }
c.r := ... c.r := ... { los campos. }
Mueva(p); Mueva(p);
Mueva(c.p); { otra vez .p! } Mueva(c); { SIN .p!!! }
END; END;
|
|
Figura N° 4
|
En la Figura 4 se
muestra como es posible extender un tipo de datos por medio de la herencia.
Como cualquier instancia del tipo extendido tiene como prefijo al tipo base,
entonces cualquier función que utiliza una variable del tipo base puede también
aplicarse al tipo extendido. Es por eso que en la columna derecha de laFigura 4 el
procedimiento Mueva() se puede aplicar a las variables "p"
y "c" indistintamente: como "c" es una variable de
tipo Circulo_T necesariamente contiene a una variable de
tipo Punto_T, sobre la que el procedimiento Mueva() puede
operar.
La reutilización de componentes, tan mentada por los adeptos a la OOP, es
precisamente la posibilidad de usar una función sobre un tipo extendido. Pero
esto realmente no es nada nuevo, como puede verse en la columna izquierda de
la Figura 4, en la que
basta incluir una referencia a un campo en un registro (.p) para obtener el
mismo efecto que se logra por medio de la herencia.
El otro componente importante de la programación por objetos es el uso del
polimorfismo, que se implementa por medio del uso de punteros a funciones.
Cuando se usa herencia para extender de muchas formas un tipo de datos, puede
resultar luego conveniente que el procedimiento que se use para operar sobre un
dato dependa del dato en sí, aunque el programador no haya especificado
exactamente cuál es ese procedimiento.
Punto_T PROCEDURE Punto_T.Despliegue(); VIRTUAL;
.
/ \
/ \
__ _____
/ \ | | PROCEDURE Circulo_T.Despliegue(); VIRTUAL;
| | | |
\__/ |_____| PROCEDURE Cuadrado_T.Despliegue(); VIRTUAL;
Circulo_T Cuadrado_T
VAR
VEC : ARRAY [1..3] OF ^Punto_T;
p : Punto_T;
c : Circulo_T;
r : Cuadrado_T;
BEGIN
{ ... }
VEC[1] := ADDR(p);
VEC[2] := ADDR(c);
VEC[3] := ADDR(r);
{ ... }
FOR i := 1 TO 3 DO BEGIN
VEC[i]^.Despliegue;
END;
|
|
Figura N° 5
|
Por ejemplo, en
la Figura 5 se
muestra una jeraquía de objetos en que, por medio de la herencia, se extiende
el tipo de datos Punto_T a un Circulo_T o a unCuadrado_T.
Es natural que el procedimiento para desplegar un círculo sea totalmente
diferente al que despliega un cuadrado. Sin embargo, ambos procedimientos tiene
en común que existe un procedimiento llamado Despliegue() que permite
desplegar variables de tipo Punto_T, que es el tipo base
para Circulo_T yCuadrado_T.
El código al final de la Figura 5 muestra
como es posible tener un arreglo de punteros a variables de tipo Punto_T,
en el que el procedimiento a usar para hacer el despliegue se escoge en tiempo
de ejecución. Para que la decisión de cuál es "polimórficamente" el
procedimiento que debe usarse para operar sobre una variable se tome en tiempo
de ejecución, lo que se hace es almacenar en cada variable la dirección del
procedimiento que le corresponde. Así, la variable "p" tendrá un
puntero al procedimiento Punto_T.Despliegue(), "c" a Circulo_T.Despliegue() y
"r" a Rectangulo_T.Despliegue(). A estas
operacionesDespliegue() se les conoce como métodos virtuales, pues es en
tiempo de ejecución cuando se decide cuál de ellas será invocada para cada una
de las variables.
┌─────>o<*>────>Punto_T::Dibuje()
VEC[] │ P
┌───┐ │
│ *─┼────────┘ __
├───┤ / \
│ *─│───────────>│ C │<*>──>Circulo_T::Dibuje()
├───┤ \__/
│ *─┼────────┐ __
└───┘ │ / \
│ │ ││
└───>││ │<*>───>Cilindro_T::Dibuje()
│ ││
\__/
T
|
|
Figura N° 6
|
En la Figura 6 se ve
que cada valor de una clase polimórfica incluye un puntero a su método
polimórfico. Por eso, el valor de la variable "P" incluye un puntero
aPunto_T::Dibuje(), la variable "C" tiene un puntero al método
polimórfico Circulo_T::Dibuje() así como la variable "T"
incluye su puntero polimórfico haciaCilindro_T::Dibuje(). Este puntero
polimórfico es el que se usa en la ejecución del ciclo "FOR" en que
se invoca VEC[i]^.Despliegue, pues es usando el puntero polimórfico que
siempre es posible determinar cuál es el método correcto que hay que invocar.
Aunque parece que los valores del vector son uniformes, en realidad cada uno de
ellos apunta a un valor de un tipo diferente que está bien identificado por su
puntero polimórfico. De hecho, el tipo de "VEC[1]" es diferente al de
"VEC[0]" ya al de "VEC[2]" aunque todos tienen en comúm que
también son de tipo Punto_T.
VEC[] P
┌───┐ ┌───┐
│ *─┼───────>│ x │
├───┤ ├───┤
│ *─┼──>C │ y │ VMT Punto_T (Virtual Method Table)
├───┤ ├───┤ ┌───┐
│ *─┼──>T │VMT│────>│ 8 │ == 2 + 2 + 4 sizeof(Punto_T)
└───┘ └───┘ ├───┤
│ *─┼───>"class Punto_T" Hilera con el nombre RTTI
├───┤
│ *─┼───>Punto_T::Dibuje() Método virtual No.1
├───┤
│ *─┼───>Punto_T::Borre() Método virtual No.2
└───┘
|
|
Figura N° 7
|
En realidad es muy honeroso repetir en cada valor todos los punteros
polimórficos. Por eso, para cada tipo polimórfico el compilador crea una tabla
de métodos virtuales (VMT: Virtual Method Table), en la que están
unificados todos los punteros a métodos polimórficos, como se muesta en
la Figura 7. De esta manera,
cuando un valor tiene métodos virtuales, este hecho se represanta con un
puntero a la VMT.
┌─────┬─────┬─┐
│ x │ y │!│ Punto_T
└─────┴─────┴─┘
││
││
\/
//───────────────────────────────────\\
││───────────────────────────────────││
││ ││
\/ Circulo_T \/ Cuadrado_T
┌───────────┬─┬───────┐ ┌───────────┬─┬───────┐
│ x │ y │!│ radio │ │ x │ y │!│ largo │
└───────────┴─┴───────┘ └───────────┴─┴───────┘
││ ││
││ ││
\/ Cilindro_T \/ Rectangulo_T
┌───────────┬─┬───────┬────────┐ ┌───────────┬─┬───────┬───────┐
│ x │ y │!│ radio │ altura │ │ x │ y │!│ largo │ ancho │
└───────────┴─┴───────┴────────┘ └───────────┴─┴───────┴───────┘
|
|
Figura N° 8
|
En la Figura 8 se
muestran los campos de la jerarquía de tipos ( Punto_T ( Circulo_T (
Cilindro_T ) Cuadrado_T ( Rectangulo_T ) ) . El campo marcado
"!" es el puntero a la VMT.
Cabe mencionar que a las variables de programas que siguen el paradigma OOP se
les llama objetos, o sea, que un objeto es una instancia de un tipo.
En el argot popular se acepta que un lenguaje soporta la Programación por
Objetos si brinda facilidades para implementar herencia (extensión de tipos),
polimorfismo (funciones virtuales) y encapsulamiento. Sin embargo, cada
lenguaje orientados a objeto soporta de manera distinta cada uno de estos
conceptos. Como ha sucedido con otros lenguajes y paradigmas de programación,
el ser orientado a objetos es una cuestión más de fé que académica.
TIPOS ABSTRACTOS DE DATOS
1.
La Abstracción
A pesar de que estamos
acostumbrados a utilizar el término abstracción dentro del contexto de la
programación, la verdad es que esta palabra tiene un origen mucho más lejano.
Desde siempre, el hombre se ha tenido que enfrentar a problemas muy complejos,
sin embargo con el paso del tiempo hemos descubierto un buen método para
enfrentarnos a ellos: la abstracción. Abstraer consiste en centrarse sólo en la
parte principal y esencial de los problemas, dejando así a un lado todos los
detalles insignificantes o menos importantes.
Un buen ejemplo de la
capacidad humana para la abstracción es la elaboración y lectura y un mapa.
Cuando dibujamos un mapa de carreteras, reflejamos en él los elementos
principales, los que tienen utilidad para su interpretación, como por ejemplo
las autopistas, autovías, carreteras nacionales, áreas de servicio,
gasolineras, etc. Otros datos como podrían ser museos, parques o monumentos no
aparecen ya que se consideran innecesarios en este tipo de mapas. La
abstracción es una de las herramientas fundamentales de la mente humana, ya que
nos permite dividir los problemas en partes independientes y solucionar cada
una por separado.
2. La Evolución De La Abstracción En La Programación
En los primeros
tiempos de la informática, los programadores se comunicaban con las máquinas en
binario, lo cual resultaba ser una tarea extremadamente larga y complicada. Al
cabo de un tiempo apareció el código ensamblador, cuyos nemotécnicos
facilitaron notablemente el trabajo de los programadores al evitar que tuviesen
que recordar las secuencias de unos y ceros que formaban cada instrucción.
Estos nemotécnicos constituyeron la primera escala de abstracción de la era
informática.
Unos años más tarde
llegaron los lenguajes de alto nivel y con ellos las macroinstrucciones.
Gracias a estos lenguajes, los programadores pudieron comenzar a escribir
software genérico, es decir, podían programar sin preocuparse de la máquina
sobre la que iba a correr el programa. Esto se debía a que las instrucciones de
los lenguajes de alto nivel producían varias acciones en la máquina,
independientemente de las arquitecturas concretas de cada una de ellas. Con
este tipo de lenguajes llegaron también las sentencias de control más
habituales como los bucles o sentencias if-then.
En definitiva, la
complejidad iba creciendo a medida que lo hacía la abstracción. Así fueron
surgiendo los procedimientos y funciones, los módulos y posteriormente los
tipos abstractos de datos.
3. Abstracción Funcional Y Abstracción De Datos
En la programación, la
abstracción puede aplicarse de dos modos distintos dando lugar a la abstracción
funcional y la abstracción de datos.
La abstracción
funcional aparece al pensar de manera abstracta las operaciones que necesitamos
para resolver un problema. Este tipo de abstracción nos permite definir
operaciones nuevas en una aplicación que anteriormente carecía de ellas. La
abstracción funcional fue la primera en aparecer ya que es fácil de llevar a la
práctica debido a que su implementación es posible en la gran mayoría de los
lenguajes de programación. Suele corresponderse con el uso de procedimientos o
funciones.
La abstracción de
datos surge cuando se abstrae el significado de los diferentes tipos de datos
que aparecen en nuestro problema. Este tipo de abstracción nos permite crear
nuevos tipos de datos pensando en los posibles valores que pueden tomar y en
las operaciones que los manipulan. Como cabe esperar, estas operaciones serán a
su vez abstracciones funcionales.
La abstracción de
datos es más reciente que la funcional, ya que los primeros lenguajes de
programación no ofrecían demasiadas facilidades para su uso. Uno de los
primeros mecanismos que permitió esta abstracción fueron las clases de Simula.
4.
Datos, Tipos De Datos Y TAD
Para hablar de la
abstracción es necesario tener clara la diferencia que existe entre los datos,
los tipos de datos y los tipos abstractos de datos.
Los datos son los
valores que manejamos en la resolución de un problema, tanto los valores de
entrada, como los de proceso y los de salida. Es decir, los datos son
información y por lo tanto distinguimos varios tipos de datos.
Un tipo de dato se
puede definir como un conjunto de valores y un conjunto de operaciones
definidas por esos valores. Clasificar los datos en distintos tipos aporta
muchas ventajas, como por ejemplo indicarle al compilador la cantidad de
memoria que debe reservar para cada instancia dependiendo del tipo de dato al
que pertenezca.
Los tipos de datos
abstractos van todavía más lejos; extienden la función de un tipo de dato
ocultando la implementación de las operaciones definidas por el usuario. Esta
capacidad de ocultamiento nos permite desarrollar software reutilizable y
extensible, lo cual veremos más adelante cuando hablemos de modularidad.
Tipos Abstractos De
Datos
Un tipo de datos
definido por el programador se denomina tipo abstracto de datos (TAD) para
distinguirlo de los tipos predefinidos de datos. Los tipos abstractos de datos
están formados por los datos (estructuras de datos) y las operaciones
(procedimientos o funciones) que se realizan sobre esos datos. El conjunto de
operaciones definidas sobre el TAD debe ser cerrado, es decir, sólo se debe
acceder a los datos mediante las operaciones abstractas definidas sobre ellos.
La abstracción de datos sólo permite acceder a ellos de manera controlada.
Las estructuras de los
TAD se componen de dos partes: la interfaz y la implementación. Esto se debe a
que las estructuras de datos reales que utilizamos para almacenar la
representación de un tipo abstracto de datos son invisibles para los usuarios o
clientes. Mientras que en la interfaz se declaran las operaciones y los datos,
la implementación contiene el código fuente de las operaciones y lo mantiene
oculto al usuario.
Las principales
ventajas que nos aportan los TAD son las siguientes:
1. Mejoran la conceptualización y hacen más claro y comprensible el código.
2. Hacen que el sistema sea más robusto.
3. Reducen el tiempo de compilación.
4. Permiten modificar la implementación sin que afecte al interfaz público.
5. Facilitan la extensibilidad.
5.
Construcción De Un TAD
La construcción de un
TAD consta de dos fases bien diferenciadas entre ellas: la especificación
(formal e informal) y la implementación.
Las características de
un TAD no deben depender de su realización concreta, sino solamente de cómo
queremos que sea su comportamiento, lo cual llamamos especificación. Para la
especificación de un tipo abstracto de datos en lenguaje natural
(especificación informal) hemos de seguir el siguiente esquema:
TIPO DE DATOS Nombre
del tipo (Lista de operaciones)
VALORES: Descripción de los posibles valores
OPERACIONES: Descripción de cada operación
Primero indicaremos el
nombre del TAD y citaremos todas las operaciones definidas. En el apartado
valores describiremos los posibles valores de los datos de este tipo, pero lo
haremos desde un punto de vista abstracto, sin pensar en la posible realización
concreta. Finalmente en el apartado operaciones haremos una descripción de cada
una de las operaciones definidas sobre el TAD. En la especificación informal,
habitualmente hacemos referencia a conceptos con los cuales el lector está
familiarizado (como por ejemplo conceptos matemáticos). El problema surge
cuando estos datos auxiliares no están definidos tan precisamente.
La especificación
formal nos permite definir conceptos de manera mucho más precisa. Para ello
utilizaremos este esquema:
Tipo: Nombre del tipo
de datos
Sintaxis: Forma de las operaciones
Semántica: Significado de las operaciones
En el apartado
sintaxis proporcionamos el tipo de datos de entrada y de salida de cada una de
las funciones definidas sobre el TAD, mientras que en semántica describiremos
sus comportamientos. Sin embargo, ésta vez lo haremos siguiendo unas normas
algebraicas básicas.
En la implementación
del TAD lo que hacemos es elegir la forma en que se van a representar los
distintos valores que tomarán los datos. También seleccionaremos la manera en
que se realizarán las operaciones. Para esta elección debemos tener en cuenta
que todas las operaciones se realicen de la forma más eficiente posible, aunque
con la práctica veremos que la mayoría de las veces una implementación facilita
mucho algunas operaciones mientras que complica otras.
6.
Modularidad
La programación
modular descompone un programa en un pequeño número de abstracciones
independientes unas de otras pero fáciles de conectar entre sí. Como hemos
visto anteriormente, un módulo se caracteriza principalmente por su interfaz y
su implementación. La programación modular sigue el criterio de ocultación de
información: si no se necesita algún tipo de información, no se debe tener
acceso a ella.
La modularidad es un
aspecto muy importante en los TAD, ya que es el reflejo de la independencia de
la especificación y la implementación. Es la demostración de que un TAD puede
funcionar con diferentes implementaciones.
Además de esto, la
programación modular ofrece otras ventajas, como por ejemplo un mejor reparto
del trabajo y una detección de fallos mucho mejor.
7.
TAD Más Comunes
Los tipos abstractos
de datos básicos se clasifican habitualmente, atendiendo a su estructura, en
lineales y no lineales.
8.1. TAD lineales
8.1.1 Listas
Esta forma de almacenar elementos consiste en colocarlos
en una lista lineal que tiene un enlace por cada elemente para determinar cual
es el elemento siguiente. Las listas se utilizan habitualmente para guardar
elementos del mismo tipo y se caracterizan porque pueden contener un número
indeterminado de elementos y porque siguen un orden explícito. La lista de cero
elementos se denomina lista vacía.
8.1.2 Colas
En el contexto de la
programación, una cola es una lista en la que los elementos se insertan por un
extremo (llamado fondo) y se suprimen por el otro (llamado frente). En esta
estructura de datos el primer elemento que entra es el primero en salir. Es un
tipo de dato muy común tanto dentro de la informática como en la vida real.
8.1.3 Pilas
Una pila es una
estructura de datos en la cual todas las inserciones y las eliminaciones se
realizan por el mismo extremo, denominado cima de la pila. En una pila, el
último elemento en entrar es el primero en salir, al contrario de lo que pasa
en las colas.
8.2 TAD no lineales
8.2.1 Árboles
El árbol es un TAD que
organiza sus elementos (nodos) de forma jerárquica. Si una rama va del nodo a
al nodo b, entonces a es el padre de b. Todos los nodos tienen un padre,
excepto el nodo principal, denominado raíz del árbol.
8.2.2 Árboles binarios de
búsqueda
El árbol
binario de búsqueda es una variación del TAD árbol. Se trata de aquellos
árboles binarios (cada nodo tiene dos hijos como máximo) en los cuales todos
los datos del subárbol izquierdo son menores que los datos del nodo, y los
datos del subárbol derecho son mayores que los datos del nodo.
8.2.3 Grafos
Hemos visto que los
árboles binarios representan datos entre los cuales existe una jerarquía. Los
grafos sin embargo se utilizan para representar relaciones arbitrarias entre
datos. En su representación, cada elemento de problema forma un nodo. La
relación entre nodos forma una arista que puede ser dirigida o bidireccional
(no dirigida).
Cibergrafia.
