Introducción a los tipos de datos abstractos · Introducción a los tipos de datos abstractos...

Introducción a los tipos de datos abstractos (TAD)

SINTAXIS Y SEMÁNTICA DEL LENGUAJE

Prof. Lic. Ma. Gabriela Cerra

Definición de abstracción

Abstracción: idea general que se concentrasobre las cualidades o aspectos esenciales dealgún objeto del mundo real e ignora laspropiedades accidentales.

La abstracción es la capacidad de encapsular yaislar la información del diseño, de laimplementación y de la ejecución.

Tipos de Abstracción

Procedural

De datos

Abstracción Procedural

Un programa es un modelo o abstracciónde la realidad y los lenguajes deprogramación son las herramientas a través delas cuales se implementan esos modelosabstractos.

Abstracción Procedural

A través del diseño descendente separticiona un programa en subprogramas omódulos.

Esa descomposición divide el problema Pteniendo en cuenta qué es lo que hace cadamódulo (qué tarea lleva a cabo),independientemente de cómo.

Abstracción de datos

En una abstracción de datos se piensa enqué se puede hacer con una colección dedatos independientemente de cómo se llevaa cabo.

Definición

Un TAD (tipo abstracto de datos) es:

una colección de datos

acompañada de un conjunto de operaciones para manipularlos, de forma tal que queden ocultas la representación interna del nuevo tipo y la implementación de las operaciones, para todas las unidades de programa que lo utilice.

Evolución hacia el concepto de TAD

Lenguaje de máquina datos son cadenas de

bits + op. de desplazamiento (pto.flot)

Fortran, Cobol y Algol 60 definen tipos de datos standard: entero – real- bool – carácter

Algol 68 define constructores de tipos o tipos definidos por el usuario: alumno, curso

Comparación entre tipos

Semejanzas entre tipos estándar y def. por usuario:

Ambos tienen estructura interna

Entero: es una cadena de bits

Alumno: es un registro

Curso: vector

Ambos tienen operaciones asociadas

Entero: +, -, *, /

Alumno: asignar valor a cada campo- imprimir campos

Comparación entre tipos

Diferencias:

Los tipos estándar ocultan su representacióninterna al programador (no se puedemanipular)

Los tipos definidos por el usuario exigen elegirla representación interna al programador ypermiten manipularla para asignar valor ymodificarlo.

Comparación entre tipos

Diferencias:

Un tipo de dato estándar NO permite modificarsu representación interna al programador

En un tipo definido por el usuario elprogramador puede cambiar la estructurainterna del mismo, lo que obliga a modificartambién las operaciones

Combinando características nacen los TAD’s

Si definimos nuevos tipos de datos peroocultando tanto su representación internacomo la implementación de sus operacionesmediante un mecanismo de encapsulamiento,obtenemos un

TIPO ABSTRACTO DE DATOS.

TAD’s

De esta forma el usuario solo conoce

para qué sirve el nuevo TAD,

qué operaciones puede aplicarle y

qué valores puede almacenar

pero no conoce cómo lo hace: no tiene acceso al almacenamiento ni a la implementación de las operaciones

Características de los TAD’s

Ocultamiento de la información

El usuario desconoce la estructura interna elegida por el diseñador ni cómo se implementan las operaciones

El acceso a los datos almacenados solo se puede hacer mediante las operaciones

Características de los TAD’s

Encapsulamiento

Tanto la representación interna como la implementación de las operaciones se ubican en un lugar particular

Generalización

El programador puede definir un TAD cuyos elementos a almacenar sean de tipos genéricos (si el lenguaje lo permite)

Características de los TAD’s

Ventajas:

Mejor modelización del problema

Clasifica los objetos basados en su estructura y su comportamiento

Separa especificación de implementación

Reduce los efectos laterales

Permite llevar mejor control de los cambios

Facilita la extensibilidad del código y el mantenimiento

TAD’s

Un TAD se compone de:

Una interfaz de usuario, pública

Especifica para qué sirve el TAD

Especifica qué hace cada operación

Una implementación, privada

Detalla la estructura de datos que soporta el almacenamiento de datos

Codifica la implementación de cada operación

Diseño de TAD’s

Pasos en la creación de un nuevo TAD

1°- Especificación (sintáctica y semántica)

2°- Diseño de la Representación Interna

3°- Implementación de las Operaciones

Especificación (sintáctica)

Se elige el nombre del TAD

Se definen las operaciones que actúan sobre lasinstancias del TAD: Se indican los nombres, tipos y parámetros de dichas

operaciones.

Especificación (sintáctica)

Tipos de operaciones

Creación (vacía o inicializada- reserva espacio)

Asignación de valor

Modificación de valor

Consulta de valor

Destrucción (libera memoria, no siempre se define)

Especificación semántica

Se explica cuál es la utilidad del TAD en la vidareal

Se detalla mediante un comentario para qué sirvecada operación del mismo (qué efecto tiene, quédatos recibe y qué datos retorna)

Representación Interna

Elegir la estructura interna de la entidad en base a las estructuras o tipos de datos disponibles en el lenguaje de programación de alto nivel elegido

Implementación

Desarrollar los algoritmos correspondientes a las operaciones, en el código del lenguaje elegido y de acuerdo a la representación interna definida en el paso previo

Ejemplo:Especificación TAD Alumno

TAD Alumno: sirve para almacenar los datos personales de un alumno determinado (su documento, nombre y apellido, legajo y promedio)

Operaciones:

Cargar datos de un alumno

Modificar datos de un alumno

Consultar datos de un alumno

Especificación

Procedure Cargar (var A: alumno; nom: string[20]; dni: integer; leg:integer; prom:real);

{retorna un alumno A con todos sus datos cargados}

Procedure ModNom(var A: alumno; nom: string[20]);

{retorna un alumno A con su nombre modificado}

Procedure ModDni(var A: alumno; doc: integer);

{retorna un alumno A con su dni modificado}

Especificación

Procedure ModProm(var A: alumno; pr: real);

{retorna un alumno A con su promedio modificado}

Procedure ModLeg(var A: alumno; nrle: integer);

{retorna un alumno A con su legajo modificado}

Procedure copiar(var A1: alumno; A2: alumno);

{copia en A1 todos los datos de A2 }

Especificación

Function VerNom(A: alumno): string[20];

{retorna el nombre de A}

Funtion verDni(A: alumno): integer;

{retorna el dni de A}

Funtion verProm( A: alumno):real;

{retorna el promedio de A}

Especificación

Funtion verLeg(A: alumno): integer;

{retorna el legajo de A}

Uso del TAD - APLICACIÓN

Ejercicio: Sin terminar el diseño, es decir, SIN SABER CUÁL SERÁ LA IMPLEMENTACIÓN NI LA EST. INTERNA, vamos a desarrollar una aplicación que cree dos alumnos y determine cuál tiene mejor promedio

uses tad_alu;varal1, al2: alumno;nomb: string[20];nrodoc, nroleg: integer;notap:real;Begin

writeln(ingrese nombre, legajo, dni y promedio del 1er alumno);

readln(nomb, nroleg, nrodoc, notap);cargar(a1,nomb,nrodni,nroleg,notap);

writeln(ingrese nombre, legajo, dni y promedio del 2do alumno);readln(nomb, nroleg, nrodoc, notap);cargar(a2,nomb,nrodni,nroleg,notap);

If (verProm(a1) < verProm(a2)) then write(‘mejor promedio :’, verNom(a1))

elsewrite(‘mejor promedio :’, verNom(a2))

Representación interna

Volviendo al diseño:

Qué estructura de datos nos es más conveniente para almacenar un producto en Pascal??

Se define en type

Representación interna

type

cad: string[20];

alumno=record

nom: cad;

prom: real;

dni: integer;

leg: integer

end;

Implementación

Se codifica en Pascal cada operación especificada, respetando la estructura de datos elegida

En Pascal un TAD se implementa con una UNIT (se simula pues Pascal no soporta la implementación de Tads)

UNIT Pascal

Unit nombre;

Interface

{parte pública lleva estructura interna +

especificación de las operaciones}

Implementation

{parte privada implementación de cada op}

Initialization {opcional}

Begin

….

end.

UNIT Pascal

Una UNIT encapsula el Tad pero no lo oculta completamente, ya que deja ver la estructura interna (type) al estar declarada en la parte pública de la unidad.

Todo lo que sea público puede ser utilizado en la unidad de programa que incluye a la UNIT. Está bien poder invocar a las operaciones, pero no respeta el concepto de abstracción poder usar el type. (simula no soporta Tads)

Tad’s en ADA (tercera clase)

Este lenguaje de programación tiene herramientas para implementar tipos de datos abstractos y proveer tanto ocultamiento como encapsulamiento de forma eficiente, a través de los packages.

ADA

Todo programa en ADA tiene 4 partes:

- Especificación de contexto (uso de librerías ej.

with ada_io);

- Especificación del programa (encabezado)

- Parte declarativa

- Cuerpo

Ejemplo

1)

with ada_io;

use ada_io;

procedure Doble is

x, y: integer;

Begin

get(x);

y:=x+2;

put(y);

End Doble;

2)

use ada_io;

Function pepe (n:integer) return integer is

z: integer;

Begin

z:= 2 + n

return z

End pepe;

Parámetros en ADA

- Por defecto siempre in copia

- Pueden ser out resultado

- Pueden ser in out valor resultado si es un

tipo primitivo o referencia si no lo es

TAD’s en ADA

Encapsula mediante paquetes.

Los paquetes se definen en archivos fuentes separados de la aplicación que los usa.

El paquete tiene dos partes:

Especificación – pública nombre+protocolo+

estruc. interna privada.

Cuerpo o body- privada contiene la

implementación de las operaciones

TAD’s en ADA

La parte visible o pública del TAD es leída por el compilador cuando se compila la aplicación que lo usa

La parte privada NO.

Para usar un TAD debo incluirlo en la aplicación con with (calificado) o use.

Ejemplo

package Tpersona is

type cadena is string(1..30);

type persona is private;

function vernom(p:persona) return cadena;

function veredad(p:persona) return integer;

procedure modedad(p: in out persona; nue:integer);

procedure modnom(p: in out persona; otro: cadena);

private

type persona is record Esto se compila y genera un

nom: cadena; archivo Tpersona.ads

edad: integer;

endrecord;

End Tpersona;

package body Tpersona is

function vernom (p:persona) return cadena is

begin

return p.nom;

end;

function veredad(p:persona) return integer is

begin

return p.edad;

end;

procedure modedad(p: in out persona; nue: integer) is

begin

p.edad:= nue

end;

……

end Tpersona; Se compila y genera un arch Tpersona.adb

Ejemplo

use Tpersona;

Procedure Main is

p1, p2:persona;

e: integer;

begin

----

----

e:=veredad(p1);

put( e);

end;

Características particulares:

En la parte pública de la especificación se pueden declarar tipos públicos, privados y limitados privados

A los datos privados solo los accedo por operaciones del TAD pero admiten asignación directa, comparación y desigualdad

Si el dato es limitado-privado solo se accede por operaciones del TAD.

TAD’s genéricos

Permite definir un parámetro o elemento genérico que se instancia en ejecución con un tipo de dato específico

Pueden ser uno o varios parámetros genéricos

Generic

type elemento is private;

package Tpila is

type pila is private;

function vacia(p:pila) return boolean;

procedure crear(p:in out pila);

procedure apilar(p: in out pila; e:elemento);

procedure desapilar(p: in out pila; e: in out elemento);

Private

type pila is record

datos: array[1..30] of elemento;

tope: integer;

endrecord;

end Tpila;

Package body Tpila is

function vacia(p:pila) return boolean is

begin

if p.tope=0 then return true

else return false

end;

…….

end Tpila;

declare

package PilaEnt is new Tpila(integer);

package PilaReal is new Tpila(float);

…..

use PilaEnt;

Procedure Main is

p1: pila;

……….