Página 7. Estructura de Datos en C++

• 1.6. TIPOS ABSTRACTOS DE DATOS.

Algunos lenguajes de programación tienen características que nos permiten ampliar el lenguaje añadiendo sus propios tipos de datos. Un tipo de dato definido por el programador se denomina tipo abstracto de datos (TAD) para diferenciarlo del tipo fundamental (predefinido) de datos. Por ejemplo, en C++ el tipo Punto, que representa las coordenadas x e y de un sistema de coordenadas rectangulares, no existe. Sin embargo, es posible implementar el tipo abstracto de datos, considerando los valores que se almacenan en las variables y qué operaciones están disponibles para manipular estas variables. En esencia un tipo abstracto de datos es un tipo que consta de datos (estructuras de datos propias) y operaciones que se pueden realizar sobre esos datos. Un TAD se compone de estructuras de datos y los procedimientos o funciones que manipulan esa estructuras de datos. 

Un tipo abstracto de datos puede definirse mediante la ecuación: TAD = Representación (datos) + Operaciones (funciones y procedimientos)

La estructura de de tipo de dato abstracto, desde un punto de vista global, se compone de la interfaz y de la implementación (Figura 1.2).

Las estructuras de datos reales elegidas para almacenar la representación de un tipo abstracto de datos son invisibles a los usuarios o clientes. Los algoritmos utilizados para implementar cada una de las operaciones de los TAD, están encapsuladas dentro de los propios TAD.

La característica de ocultamiento de la información significa que los objetos tienen interfaces públicos. Sin embargo, las representaciones e implementaciones de esos interfaces son privados.

Método 1 Método 2 Método 3 Método 4 Interfaz pública Representación Estructura de datos Variables (instancia) Implementación de métodos:    Código del método 1    Código del método 2    Código del método 3    Código del método 4 Implementación privada

Figura 1.2. Estructura de un tipo abstracto de datos (TAD).

• 1.6.1. Ventajas de los tipos abstractos de datos

Los tipos abstractos de datos proporcionan numerosos beneficios al programador, que se pueden resumir en los siguientes:

1. Permite una mejor conceptualización y modelización (modelo) del mundo real. Mejora la representación y la  comprensibilidad. Clasifica los objetos basados en estructuras y comportamientos comunes.
2. Mejora la robustez del sistema. Permiten la especificación del tipo de cada variable, de tal forma que se facilita la comprobación de tipos para evitar errores de tipo en tiempo de ejecución.
3. Mejora el rendimiento (prestaciones). Para sistemas tipificados, el conocimiento de los objetos permite la optimización de tiempo de compilación.
4. Separa la implementación de la especificación. Permite la modificación y la mejora de la implementación sin afectar a la interfaz público del tipo abstracto de dato.
5. Permite la extensibilidad del sistema. Los componentes de software reutilizables son más fáciles de crear y mantener.
6. Recoge mejor la semántica del tipo. Los tipos abstractos de datos agrupan o localizan las operaciones y la representación de atributos.

Un programa que maneja un TAD, lo hace teniendo en cuenta las operaciones o funcionalidad que tiene, sin interesarse por la representación física de los datos. Es decir, los usuarios de un TAD se comunican con éste a partir de la interfaz que ofrece el TAD mediante funciones de acceso. Podría cambiarse la implementación de tipo de datos sin afectar al programa que usa el TAD ya que para el programa esta oculta.

Las unidades de programación de lenguajes que pueden implementar un TAD reciben distintos nombres:

Modula -2           módulo

Ada                      paquete

C++                     clase

C#                       clase

Java                    clase

Estos lenguajes definen la especificación del TAD, que declara las operaciones y los datos, y la implementación, que muestra el código fuente de las operaciones y que permanece oculto al exterior del módulo.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

EJEMPLO 1.6. Clase hora que tiene datos separados de tipo int para horas, minutos y segundos. Un constructor inicializará este dato a 0, y otro lo inicializará a valores fijos. Una función miembro deberá visualizar la hora en formato 11:59:59. Otra función miembro sumará dos objetos de tipo hora pasados como argumentos. Una función principal main() creará dos objetos inicializados y otro que no está inicializado. Se suman los dos valores inicializados y se deja el resultado en el objeto no inicializado. Por último se muestra el valor resultante.

#include <cstdlib>

#include <iostream>

using namespace std;

class hora

{

private:

       int horas, minutos, segundos

public

       hora(){hora = 0; minutos = 0; segundos = 0;}

       hora(int h, int m, int s){horas = h; minutos = m; segundos = s;}

       void(visualizar);

       void sumar(hora h1, hora h2);

};

void hora::visualizar()
{
       cout << horas << ":" << minutos << ":" << segundos << endl;
}

void hora::sumar(hora h1, hora h2)
{
       segundos = h2.segundos + h1.segundos;
       minutos = h2.minutos + h1.minutos + segundos / 60;
       segundos = segundos % 60;
       horas = h2.horas + h1.horas + minutos / 60;
       minutos = minutos % 60;
}

int main(int argc, char *argv[])
{
       hora h1(10,40,50), h2(12,35,40),h;
       h1.visualizar();
       h2.visualizar();
       h.sumar(h1,h2);
       h.visualizar();
       return 0;
}

• 1.6.2. Especificación de los TAD

El objetivo de la especificación es describir el comportamiento del TAD; consta de dos partes, la descripción matemática del conjunto de datos, y de las operaciones definidas en ciertos elementos de ese conjunto de datos.

La especificación del TAD puede tener un enfoque informal, éste describe los datos y las operaciones relacionadas en lenguaje natural. Otro enfoque más riguroso, especificación formal, supone suministrar un conjunto de axiomas que describen las operaciones en su aspecto sintáctico y semántico.

• 1.6.2.1. Especificación informal de un TAD

Costa de dos partes:

1. Detallar en los datos de tipo, los valores que se pueden tomar.
2. Describir las operaciones, relacionándolas con los datos.

El formato que generalmente se emplea, primero se especifica el nombre  del TAD y los datos:

TAD nombre del tipo (valores y su descripción)

A continuación, de cada una de las operaciones con sus argumentos, y una descripción funcional en lenguaje natural, con este formato:

Operación (argumentos).

Descripción funcional

A continuación se especifica, siguiendo esos pasos, el tipo abstracto de datos Conjunto:

TAD Conjunto (colección de elementos sin duplicidades, pueden estar en cualquier orden, se usa para representar los conjuntos matemáticos con sus operaciones).

Las operaciones básicas sobre conjuntos son las siguientes:

Conjuntovacio	Crea un conjunto sin elementos
Añadir(Conjunto, elemento)	Comprueba si el elemento forma parte del conjunto, en caso negativo se añade. La operación modifica al conjunto.
Retirar(Conjunto, elemento)	Si el elemento pertenezca al conjunto se retira. La operación modifica al conjunto.
Pertenece(Conjunto, elemento)	Verifica si el elemento forma parte del conjunto, en cuyo caso devuelve cierto.
Esvacio(Conjunto)	Verifica si el conjunto no tiene elementos, en cuyo caso devuelve cierto.
Cardinal(Conjunto)	Devuelve el número de elementos del conjunto.
Union(Conjunto, Conjunto)	Realiza la operación matemática unión de dos conjuntos. La operación devuelve un conjunto con los elementos comunes de ambos.

Se pueden especificar más operaciones sobre conjuntos, todo dependerá de la aplicación que se quiera dar al TAD.

Norma La especificación informal de un TAD tiene como objetivo describir los datos del tipo y las operaciones según la funcionalidad que tienen. No sigue normas rígidas,simplemente indica, de forma comprensible, la acción que realiza cada operación.

• 1.6.2.2. Especificación formal de un TAD

La especificación formal proporciona un conjunto de axiomas que describen el comportamiento de las operaciones. La descripción ha de incluir una parte de sintaxis, en cuanto a los tipos de argumentos y el tipo de resultado, y una parte de semántica que detalla para unos valores particulares de los argumentos de la expresión del resultado que se obtiene. La especificación formal ha de ser lo bastante potente para que cumpla el objetivo de verificar la corrección de la implementación del TAD.

El esquema que se sigue consta de una cabecera con el nombre del TAD y los datos:

TAD nombre del tipo (valores que toma los datos del tipo)

A continuación, la sintaxis de las operaciones que lista las operaciones mostrando los tipos de los argumentos y el tipo de resultado:

Operación {Tipo de argumento, ...} -> Tipo resultado

Se continua con la semántica de las operaciones. Éstas se construye dando unos valores particulares a los argumentos, a partir de los cuales se obtiene una expresión resultado. Éste puede tener referencias a tipos ya definidos, valores del tipo lógico o referencias a otras operaciones del propio TAD.

Operaciones (valores particulares argumentos) -> expresión resultado.

Al realizar la especificación formal siempre hay operaciones definidas por sí mismas, se denominan constructores del TAD. Mediante los constructores se generan todos los posibles valores del TAD. Normalmente, se elije como el constructor la operación que inicializa  (por ejemplo, Conjuntovacio en el TAD Conjunto), y la operación que añade un dato o elemento (operación común a la mayoría de los tipos abstractos de datos). Se acostumbra a marcar con un asterisco a las operaciones que son constructores.

A continuación, se especifica formalmente el TAD conjunto. Para formar la expresión resultado se hace uno, si es necesario, de la sentencia alternativa si - entonces - sino.

TAD Conjunto (colección de elementos sin duplicidades, pueden estar en cualquier orden, se usa para representar los conjuntos matemáticos con sus operaciones).

Sintaxis

*Conjuntovacio*                      ->     Conjunto
*Añadir(Conjunto, Elemento)*         ->     Conjunto
Retirar(Conjunto, Elemento)          ->     Conjunto
Pertenece(Conjunto, Elemento)        ->     boolean
Esvacio(Conjunto)                    ->     boolean
Cardinal(Conjunto)                   ->     entero

Union(Conjunto, Conjunto)            ->     Conjunto

Semántica ∀ e1, e2 € Elemento y ∀ C, D € Conjunto

Añadir(Añadir(C, e1), e1)            ->     Añadir(C, e1)
Añadir(Añadir(C, e1), e2)            ->     Añadir(Añadir(C, e2), e1)
Retirar(Conjuntovacio, e1)           ->     Conjuntovacio
Retirar(Añadir(C, e1), e2)           ->     si e1 = e2 entonces
                                            C sino
                                            Añadir(Retirar(C, e2), e1)
Pertenece(Conjuntovacio, e1)         ->     falso
Pertenece(Añadir(C, e2), e1)         ->     si e1 = e2 entonces cierto sino
                                            Pertenece(C, e1)
Esvacio(Conjuntovacio)               ->     cierto
Esvacio(Añadir(C, e1))               ->     falso
Cardinal(Conjuntovacio)              ->     cero
Cardinal(Añadir(C, e1))              ->     si Pertenece(C, e1) entonces
                                            Cardinal(C) sino 1 + Cardinal(C)
Union(Conjuntovacio, Conjuntovacio)  ->     Conjuntovacio
Union(Conjuntovacio, Añadir(C, e1))  ->     Añadir(C, e1)
Union(Añadir(C, e1), D)              ->     Añadir(Union(C,D), e1)