introducción a los tipos de datos abstractos · introducción a los tipos de datos abstractos...
TRANSCRIPT
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;
……….