Tipos De Datos TDA

Tipos de Datos Abstractos (TDA)

Un TDA es un tipo de dato definido por el programador que se puede manipular de un modo similar a los tipos de datos definidos por el sistema.

Está formado por un conjunto válido de elementos y un número de operaciones primitivas que se pueden realizar sobre ellos.

Ejemplo:

- Definición del tipo

Numero racional: Conjunto de pares de elementos (a,b)

de tipo entero, con b<>0.

- Operaciones:

CrearRacional: a, b = (a,b)

Suma: (a,b) + (c,d) = (a*d+b*c , b*d)

Resta: (a,b) - (c,d) = (a*d-b*c , b*d)

Producto: (a,b) * (c,d) = (a*c , b*d)

División: (a,b) / (c,d) = (a*d , b*c)

Numerador: (a,b) = a

Denominador: (a,b) = b

ValorReal: (a,b) = a/b

MCD: (a,b) ...

Potencia: (a,b)^c = (a^c , b^c)

Simplifica: (a,b) = ( a/mcd(a,b) , b/mcd(a,b) )

Una vez definido se podrán declarar variables de ese tipo y operar con ellas utilizando las operaciones que aporta el tipo.

Ejemplo: TRacional r1,r2, rsuma; CrearRacional(4,7, &r1); CrearRacional(5,8,&r2); Suma(r1, r2, &rsuma);

printf(“El valor real es %f”, ValorReal(rsuma) );

Un TDA es el elemento básico de la abstracción de datos. Su desarrollo es independiente del lenguaje de programación utilizado, aunque este puede aportar mecanismos que faciliten su realización. Debe verse como una caja negra.

En un TDA existen dos elementos diferenciados:

- La Interfaz de utilización

- La representación

A la hora de utilizar el TDA, la representación debe permanecer oculta. Solo podremos utilizar las operaciones del tipo para trabajar con sus elementos.

7' $

,QWH UI D ]

' H I LQLF LyQ

2SH UD F LRQH V

5H SUH VH QWD F LyQ

,P SOH P H QWD F LyQ

Para construir un tipo abstracto debemos:

1. Exponer una definición del tipo.

2. Definir las operaciones (funciones y procedimientos) que permitan operar con instancias de ese tipo.

3. Ocultar la representación de los elementos del tipo de modo

que sólo se pueda actuar sobre ellos con las operaciones proporcionadas.

4. Poder hacer instancias múltiples del tipo.

Tipos básicos de operaciones en un TDA

Constructores: Crean una nueva instancia del tipo. Transformación: Cambian el valor de uno o más elementos de una instancia del tipo.

Observación: Nos permiten observar el valor de uno o varios elementos de una instancia sin modificarlos. Iteradores: Nos permiten procesar todos los componentes en un TDA de forma secuencial.

Implementación

Una vez definido el TAD se escoge una representación interna utilizando los tipos que proporciona el lenguaje y/o otros TAD ya definidos previamente.

La representación deberá

T C o m p lejo .h

o p erac ió n1

o p erac ió n2 +

o p erac ió n3

...

T C o m p lejo .c

D efinic ió n d el tip o

ocultarse utilizando los mecanismos que nos proporcione el lenguaje. Ocultamiento de Información.

Normalmente la implementación del tipo se realiza en un módulo aparte que será enlazado al programa principal

R ep res entac ió n :

es truc tura d e d ato s

Im p lem en tac ió n d e o p erac io n es :

C ó d ig o d e op erac ió n1

C ó d ig o d e op erac ió n2

C ó d ig o d e op erac ió n3

Se necesitará un fichero cabecera que contenga la definición de las operaciones y la declaración del tipo (representación). Con esta información se podrán definir elementos del tipo y acceder a sus operaciones

Ejemplo: Fichero cabecera

struct _TRacional { int a,b};

typedef struct _TRacional TRacional;

void CreaRacional (int a, int b, TRacional *r );

void SumaRacional(TRacional r1, TRacional r2, TRacional *rsum);

TDA Pila

Definición del Tipo

Es una colección lineal, dinámica y homogénea, en la que los elementos de insertan y se extraen por el mismo extremo. También conocida como estructura LIFO (Last In, First Out).

Operaciones: CrearPila Meter Sacar

DestruirPila

EstaVacia

0 H WH U

& LP D

6D F D U

Representación:

Utilizaremos un array para representar la pila. Definiremos un tamaño máximo de array (MaxElemPila). Llevaremos una variable: cima que indicará cual es el último elemento ocupado en el array.

#define MaxElemPila struct _TPilaEnteros {

int elementos[MaxElemPila];

int cima;

& LP D

};

typedef struct _TPilaEnteros TPilaEnteros;

void CreaPila (TPilaEnteros *p) { p->cima = 0; };

int InsertaPila (int nelem, TpilaEnteros *p) {

if (p->cima==MaxElemPila) {

return 0; /*No se ha podido insertar*/

} else {

p->cima++;

p->elementos[p->cima]=nelem;

return 1;

};

};

TDA Lista

Notas

Es una estructura homogénea, dinámica y de acceso por posición.

El tipo lista no existe en C por lo que habrá que implementarlo como un TAD.

Definición del tipo:

Una lista es una colección homogénea de elementos con una relación lineal entre ellos. Es decir, cada elemento de la lista (excepto el primero) tiene un único elemento predecesor y cada elemento (excepto el último) tienen un elemento sucesor

Operaciones:

...