PDF de programación - Definición de Tipo de Dato Abstracto (TDA)

Definici´on de Tipo de Dato Abstracto (TDA)

1

John Guttag (1974):

Un tipo de dato abstracto es aqu´el definido por el programador que

puede ser manipulado de forma similar a los definidos por el sistema.

Al igual que estos ´ultimos, un tipo de dato abstracto corresponde a un
conjunto de valores l´ıcitos y de operaciones asociadas a los mismos, ope-
raciones que se definen mediante una especificaci´on que es independiente
de la implementaci´on de esos datos.

Niveles de especificaci´on, implementaci´on y uso de un TAD

2

Programador(cid:13) del(cid:13)tipo(cid:13)Usuario(cid:13)Diseño(cid:13) TAD(cid:13)Especificación(cid:13)Valores(cid:13)Operaciones(cid:13)((cid:13)Sintaxis(cid:13)y(cid:13)Semántica(cid:13))(cid:13)Implementación(cid:13)Implementación(cid:13)de(cid:13)las(cid:13)Operaciones(cid:13)Representación(cid:13)del(cid:13)tipo(cid:13) Especificaci´on informal de un TAD

3

TAD Nombre del tipo

VALORES: valores que pueden tomar los datos del tipo

OPERACIONES: nombre de las operaciones que los manipulan

Para cada operaci´on (SINTAXIS y SEM ´ANTICA):

Nombre de operaci´on (tipo de argumento) → tipo de resultado

{Objetivo: Descripci´on de la operaci´on

Entrada: Descripci´on de los datos de entrada

Salida: Indica qu´e es lo que retorna la operaci´on al invocarla

Precondiciones: Posibles excepciones. Caracter´ısticas que tendr´an que re-
unir los datos de entrada para que se realice bien la tarea.

Poscondiciones: Indica un efecto lateral en la invocaci´on a una funci´on.
Afirmaciones que podemos hacer sobre los datos despu´es de que se ejecute la
operaci´on y que complete la informaci´on del objetivo y las salidas}

Pasos en la especificaci´on de un TAD T

4

1. Seleccionar las operaciones, teniendo en cuenta para qu´e se va a utilizar

dicho TAD T.

2. Clasificarlas:

Constructoras: Su resultado es de tipo T
• Generadoras: S´olo con ellas es posible generar cualquier valor del
tipo T y excluyendo cualquiera de ellas hay valores que no pueden
ser generados.

• Modificadoras: El resto
Observadoras/Acceso: Su resultado no es de tipo T.

Destructoras: Su resultado es de tipo T.

Ejemplo: Especificaci´on del Tipo de Dato Abstracto Racional

5

VALORES

Concepto matem´atico de n´umeros racionales, es decir, un par de n´umeros
enteros tal que el primero es el numerador y el segundo el denominador.

OPERACIONES (Sint´axis y Sem´antica)
• Generadoras

◦ Crear Racional (n,d:entero)→ Racional

{Objetivo: Crear un n´umero racional
Entrada:

n: numerador del nuevo racional
d: denominador del nuevo racional

Salida: El n´umero racional creado}

◦ Suma (r1,r2:Racional) → Racional

{Objetivo: Calcula la suma de dos n´umero racionales
Entrada: r1, r2: n´umeros racionales a sumar
Salida:

Un nuevo racional que contiene la suma de los n´umeros a la
entrada}
• Observadoras

◦ Numerador (Racional)→ Entero

{Objetivo: Obtener el numerador de un n´umero racional
Entrada:

N´umero racional del que obtener el numerador

Salida: numerador del n´umero a la entrada}

◦ Denominador (Racional)→ Entero

{Objetivo: Obtener el denominador de un n´umero racional
Entrada:

N´umero racional del que obtener el denominador

Salida: denominador del n´umero a la entrada}

Definici´on Ampliada de Tipo de Abstracto Dato (TAD)

6

Ghezzi (1987):

Un nuevo tipo de dato se considera un TAD s´olo si:

El lenguaje proporciona alg´un m´etodo para permitir asociar la repre-
sentaci´on de los datos con las operaciones que los manipulan.

La representaci´on del nuevo tipo de dato as´ı como la implementaci´on de
las operaciones pueden permanecer ocultas al resto de los m´odulos que
los utilizan.

Es decir, para construir un tipo de dato abstracto, debemos ser capaces de:

Exportar una definici´on de tipo.

Proporcionar un conjunto de operaciones que puedan usarse para mani-
pular los ejemplares de tipo.

Proteger los datos asociados con el tipo de tal manera que se pueda operar
con ellos s´olo mediante las operaciones provistas.

Estructura de una unit en Pascal

7

unit <nombre unidad>;

interface

<clausula uses>

<constantes, tipos y variables publicas>

<cabeceras de procedimientos y funciones>

implementation

<clausula uses>

<constantes, tipos y variables privadas>

<procedimientos/funciones privadas>

<cuerpos procedimientos/funciones publicas>

begin

<secuencia de inicializacion >

end.

Ejemplo de Tipo de dato como conjunto de valores

8

program ejemplo1;

type

Racional = record

num, den: integer

end;

var

r1,r2,r3,r4, s :Racional;

begin

r1.num:=2; r1.den:=3; r2.num:=5;
r2.den:=7;

r3.num:=7; r3.den:=8; r4.num:=5;
r4.den:=0;
(∗ s suma de r1 y r2 ∗)
s .num:=r1.num ∗ r2.den + r2.num ∗ r1.den;
s .dem:=r1.den ∗ r2.den;
writeln( ’ la suma es ’, s .num,’/’,s .den);
(∗ s suma de r3 y r4 ∗)
s .num:=r3.num ∗ r4.den + r4.num ∗ r3.den;
s .dem:=r3.den ∗ r4.den;
writeln( ’ la suma es ’, s .num,’/’,s .den);

end.

Ejemplo de Tipo de dato como conjunto de valores y operaciones

9

program ejemplo2;
type Racional = record

num,den:integer

var r1,r2, s :Racional;

end;

function Crear Racional (n,d:integer ) :Racional;
(∗ Operacion para crear un racional ∗)
var temp:Racional;
begin

if d=0 then writeln(’Error: el denominador no puede ser 0’)
else begin

temp.num:=n; temp.den:=d;
Crear Racional:=temp;

end;

end;

function Numerador (r:Racional):integer;
(∗ Operacion que retorna el numerador de un racional ∗)
begin

Numerador:=r.num

end;

function Denominador (r:Racional):integer;
(∗ Operacion que retorna el denominador de un racional ∗)
begin

Denominador:=r.den

end;

function Suma (r1,r2:Racional):racional ;
(∗ Operacion que retorna la suma de dos racionales ∗)
var s : racional ;
begin

s .num:=r1.num ∗ r2.den + r2.num ∗ r1.den;
s .den:=r1.den ∗ r2.den;
Suma:=s;

end;

begin

r1:=Crear Racional(2,3); r2:=Crear Racional(5,7);
r3:=Crear Racional(7,3); r4:=Crear Racional(5,4);

s:=Suma(r1,r2);
writeln( ’La suma es ’, Numerador(s),’/’,Denominador(s));

s:=Suma(r3,r4);
writeln( ’La suma es ’, Numerador(s),’/’,Denominador(s));

end.

Encapsulando y compilando de forma independiente...utilizando como es-

tructura de datos un registro...

10

Unit UnitRacional;
Interface
type

Racional = record

num,den:integer

end;

function Crear Racional (n,d:integer ) :Racional;
function Numerador (r:Racional):integer;
function Denominador (r:Racional):integer;
function Suma (r1,r2:Racional):racional ;

Implementation

function Crear Racional (n,d:integer ) :Racional;
(∗ Operacion para crear un racional ∗)
var temp:Racional;
begin

temp.num:=n; temp.den:=d; Crear Racional:=temp

end;

function Numerador (r:Racional):integer;
(∗ Operacion que retorna el numerador de un racional ∗)
begin

Numerador:=r.num

end;

function Denominador (r:Racional):integer;
(∗ Operacion que retorna el denominador de un racional ∗)
begin

Denominador:=r.den

end;

function Suma (r1,r2:Racional):racional ;
(∗ Operacion que retorna la suma de dos racionales ∗)
var s : racional ;
begin

s .num:=r1.num ∗ r2.den + r2.num ∗ r1.den;
s .den:=r1.den ∗ r2.den;
Suma:=s;

end;

end.

...utilizando como estructura de datos un puntero a un registro...

11

Unit UnitRacional;
Interface
type

Racional = ˆdatos;
datos = record

num,den:integer

end;

function Crear Racional (n,d:integer ) :Racional;
function Numerador (r:Racional):integer;
function Denominador (r:Racional):integer;
function Suma (r1,r2:Racional):racional ;

Implementation

function Crear Racional (n,d:integer ) :Racional;
var temp:Racional;
begin

new(temp);
tempˆ.num:=n; tempˆ.den:=d; Crear Racional:=temp

end;

function Numerador (r:Racional):integer;
begin

Numerador:=rˆ.num

end;

function Denominador (r:Racional):integer;
begin

Denominador:=rˆ.den

end;

function Suma (r1,r2:Racional):racional ;
var s : racional ;
begin

new(s);
sˆ.num:=r1ˆ.num ∗ r2ˆ.den + r2ˆ.num ∗ r1ˆ.den;
sˆ.den:=r1ˆ.den ∗ r2ˆ.den;
Suma:=s;

end;

end.

El programa que utiliza el tipo de datos es independiente de la representa-

12

ci´on del tipo de dato

program ejemplo3;

uses UnitRacional;
(∗uso del tipo de dato Racional∗)

var

r1,r2, s :Racional;

begin

r1:=Crear Racional(2,3); r2:=Crear Racional(5,7);
(∗ s es la suma de r1 y r2 ∗)
s:=Suma(r1,r2);
writeln( ’La suma es ’, Numerador(s),’/’,Denominador(s));

end.