3. tipos de datos

1

3. TIPOS DE DATOS

2

Un tipo de dato es: Un conjunto de objetos Con una colección de operaciones

Tipos de datos: Elementales o primitivos, por ejemplo, float Estructurados o agregados, por ejemplo, struct Abstractos

Modelo de definición de datos, por ejemplo, typedef

Modelo de definición de objetos, por ejemplo, class

Conceptos básicos

3

Estructura de tipos

La estructura de tipos en un lenguaje se establece mediante dos conceptos:

Equivalencia (criterio para decidir que dos objetos son del mismo tipo)

Nominal, si los tipos tienen el mismo nombre Estructural, si los tipos tienen la misma estructura

Conversión (transformación de la representación interna de un r-valor según la representación interna del respectivo l-valor)

Implícita o coerción Explícita o casting

4

Ejemplo en PascalProgram Ejemplo;

Type Vector1 = Array[1..10] of Real; Vector2 = Array[1..10] of Real;

Var X, Z : Vector1; Y : Vector2;

Procedure Rutina(A : Vector1); Begin … End;

BeginX := Y;Rutina(Y);

End.

Error!! según equivalencia nominalCorrecto según equivalencia

estructural

Equivalencia

5

Ejemplo en Cfloat x,y,z;

int i=5, j=2, k=4;x = i/k;y = i/(float)j;z = (float)i/k;printf("%f %f \n", x, y,z);

x = 5/4 = 1 x=1.0 coerción

y = 5/2.0 = 5.0/2.0 y = 2.5 casting coerción

z = 5.0/4 = 5.0/4.0 z = 1.25 casting coerción

Conversión

6

Comprobación de tipos es la acción de verificar la consistencia entre un l-valor y un r-valor

La comprobación puede ser: Estática (lenguajes fuertemente tipados) Dinámica (lenguajes débilmente tipados)

NO existen lenguajes de programación que realicen TODA la comprobación de tipos durante compilación

Comprobación de tipos

7

Ocurre casi totalmente durante compilación Requiere declarar datos Participa de la tabla de símbolos Dota a los códigos ejecutables de:

Escasa flexibilidad Gran eficiencia Alta seguridad

Comprobación estática

8

Ocurre durante ejecución Excluye la declaración de datos Acepta modificar tipos de datos durante

ejecución Demanda espacio de almacenamiento

adicional Dota a los códigos ejecutables de:

Gran flexibilidad Escasa eficiencia Insuficiente seguridad

Comprobación dinámica

9

Para la sentencia en Cx = f(x) + z;

El compilador comprobará la compatibilidad de los tipos de:

x y el parámetro formal de f

f y z x y la operación +

Comprobación de tipos

En PascalType Rango = 1..100;Var k, n : Rango;Begin

n = 2*k + 1;End;

El r-valor de n sólo se podrá comprobar en tiempo de ejecución

10

Modelos de Definición deTipos Estructurados de Datos

11

El producto cartesiano de n conjuntos C1, C2, C3, ... Cn, denotado en la forma C1 x C2 x ... x Cn, es un conjunto cuyos elementos son n-tuplas (c1, c2, ... cn) con ci Ci

Los lenguajes de programación proveen el modelo de producto cartesiano a través de los conceptos de estructura o registro

Los polígonos regulares se pueden caracterizar por: Un número entero que representa el numero de lados, y Un número real que representa la longitud de un lado

Todo polígono regular así expresado es un elemento del producto cartesiano Z X R

Producto Cartesiano

12

Una aplicación indexada es una función de un conjunto de valores pertenecientes a un dominio D, sobre un conjunto de valores pertenecientes a una imagen I

Los lenguajes de programación proveen el modelo de aplicación indexada a través del concepto de arreglo

La declaración en C, float v[5]; constituye una aplicación del subrango de enteros [0, 4] sobre los números reales

Aplicación Indexada

f :

D I

13

Para ligar el dominio D a un subconjunto específico de valores, los lenguajes optan por una de tres estrategias:

Estática, para la cual el subconjunto se determina en tiempo de compilación

Semidinámica, para la cual el subconjunto se determina en tiempo de creación

Dinámica, para la cual el subconjunto se determina en tiempo de ejecución

Aplicación Indexada

14

Estrategia EstáticaEn C, int v[5]; declara un arreglo de tamaño 5

Estrategia SemidinámicaEn Algol, [m : n] int a; declara un arreglo de tamaño

conforme a los valores actuales de m y n

Estrategia DinámicaEn Algol, flex [1: 0] int b; declara un arreglo vacío, de

modo que b := (2, 3, 8) cambia sus límites a [1:3]

Aplicación Indexada

15

Unión Discriminada

Modo PascalEs una extensión del producto cartesiano, la cual consta de:

Una parte fija, cuyo último campo es un discriminante

Una parte variable, definida como un conjunto de variantes

En este modelo: La parte fija precede a la parte variable El discriminante permite seleccionar una de las

variantes pertenecientes al conjunto definido Cada variante es, a su vez, un producto cartesiano

Técnicamente se conoce como registro con variantes

16

Unión Discriminada

Type RegVar = Recordf1 : Integer;f2 : Real;case variable : Boolean

ofTrue : (v1 : Real);False : (v2 : Char);

End;Var rv : RegVar;

Ejemplo

17

Unión

Modo CUna union se caracteriza por

Ser, sintácticamente, un producto cartesiano Declararse como un conjunto de campos variantes Ser, semánticamente, una estructura variable Disponer, durante ejecución, de tan sólo uno de los

campos variantesEn C, un registro con variantes se simula mediante una struct:

Cuyo último campo es una union Cuyo penúltimo campo se utiliza como discriminante

18

Unión

typedef struct {int f1;float f2;int variable;union { float v1;

char v2;} var;

} regvar;regvar rv;

Ejemplo

19

Conjunto Potencia

Modo PascalUn conjunto potencia es el conjunto de todos los subconjuntos que se pueden formar con los elementos de cierto conjunto base T; se denota P(T)

Permite declarar variables cuyos valores son elementos de P(T)

Si T = {a, b, c} entonces

P(T) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

#(P(T)) = 2#(T) = 23 = 8

20

Modelos de Construcción deTipos Estructurados de Datos

21

Modelos de Construcción

Un tipo estructurado de datos se obtiene a partir de tipos elementales mediante un constructor de tipo

Un constructor de tipo impone la necesidad de contar con un modelo de construcción para la futura creación de objetos en memoriaLos traductores de lenguajes operan con tales modelos con el propósito de satisfacer abstracciones de alto nivelUn modelo de construcción está formado por un descriptor y un modelo de representación

22

Modelos de Construcción

El descriptor es un conjunto de atributos del objetoEl modelo de representación corresponde a la forma física que adoptará el objeto en RAMComo la RAM es lineal, todo objeto adopta la forma física unidimensionalLuego, se debe proveer una funcionalidad que convierta acciones de alto nivel en acciones sobre la representaciónUna fórmula de acceso es una función que transforma referencias lógicas en referencias físicas, a partir de los atributos contenidos en el descriptor

23

Representación Secuencial: La estructura de datos se guarda en un bloque contiguo de almacenamiento

Representación Enlazada: La estructura de datos se guarda en varios bloques no contiguos enlazados entre sí a través de punteros

Un puntero del bloque A al bloque B (enlace) se representa guardando la

dirección de la primera localidad del bloque B en una localidad reservada para ese fin

en el bloque A

Tipos Estructurados

24

Componente

Componente

Componente

Componente

Componente

.

.

.

Descriptor

Componente

Componente

Componente

......

Representación Secuencial

enlace

Tipos Estructurados

Representación Enlazada

25

Representación Secuencial: • Se usa para estructuras de tamaño fijo• Ocasionalmente en estructuras homogéneas de

tamaño variableEjemplo : registros, vectores, strings, etc.

Representación Enlazada:• Se usa para estructuras de tamaño variableEjemplo : listas enlazadas

Tipos Estructurados

26

Modelos de Representación deTipos Estructurados de Datos

27

Pascal

Var R : Recorda : integer;

b : real; End;

C

struct { int a; float b;}R ;

Producto Cartesiano

28

Descriptor

Objeto : a

b

Nombre R

Constructor record

Selector 1 a

Tipo Selector 1 int

Tamaño Selector 1 t1

Dirección relativa Selector 1 K1 = 0

Selector 2 b

Tipo Selector 2 float

Tamaño Selector 2 t2

Dirección relativa Selector 2 K2

Dirección Base

Producto Cartesiano

29

1

1

).(i

kki tSRDir

donde es la dirección base de R, resuelta

en tiempo de creación, y tk el tamaño del k-ésimo selector

:

Objeto

Producto Cartesiano

Fórmula de acceso

Dirección absoluta de memoria donde se encuentra el i-ésimo selector del registro R

30

Sin embargo, la expresión

se resuelve en tiempo de traducción. Luego,

con

y = 0, constantes

i - 1

tkk = 1

ii kSRDir ).(

i - 1

tkk = 1

=

ik 1k

Producto Cartesiano

31

a) Declararla en C++b) Establecer una fómula de acceso a una componente del registro

Rc) Aplicar la fórmula para determinar la dirección absoluta del

campo g del registro R, si la dirección base es 1000

a b c d e f g h j

int

float

char

int

boolean float

float

puntero

int

R:

Ejercicio: Dada la estructura

Producto Cartesiano

32

typedef float *puntero;struct Registro{ int a, d, j;

float b, f, g;char c ;bool e ;puntero h;

} ;Registro R;

Producto Cartesiano

a) Declaración en C++

33

b) Fórmula de acceso:

Dir(R.Si) = + tk

Dir(R.Si) = + (t1 + … + ti-1)

k=1

i-1

Producto Cartesiano

34

Dir(R.g) = Dir(R.S7)

Dir(R.g) = + t1 + t2 + t3 + t4 + t5 + t6

Dir(R.g) = + t(a) + t(b) + t(c) + t(d) + t(e) + t(f)

Como = 1000, se tiene

Dir(R.g) = 1000 + 2 + 4 + 1 + 2 + 1 + 4 = 1000 + 14

Por lo tanto, Dir(R.g) = 1014

Producto Cartesiano

c) Aplicación de la fórmula de acceso:a b c d e f g h j

35

Caso unidimesional

Como resultado de la declaración

Var A : array[0 .. 4] of integer;

los elementos del arreglo A ocupan localidades consecutivas de memoria

A[0] A[1] A[2] A[3] A[4]

Aplicación Indexada

36

Dada una representación secuencial, en la selección directa de un elemento intervienen:

la dirección base + el desplazamiento

a través de una fórmula de acceso

Localidad relativa del elemento seleccionado

dentro del bloque secuencial

Localidad inicial del bloque completo

Aplicación Indexada

37

Ejemplo : Considérese el arreglo en C, char s[10];

• Este arreglo se dispone, secuencialmente en memoria, como s[0], s[1], ..., s[9]

• La dirección de s[1] es la dirección base de s más 1

• Para arreglos de char en C, la dirección del i-ésimo elemento es

Dir(s[i]) = l-value(s[0]) + i

Aplicación Indexada

38

Dirección base = localidad de s[0]

Desplazamiento = i * tamaño del elemento

= 5 * 1 = 5Dirección base + desplazamiento

= l-valor( s[0] ) + 5

= l-valor( s[5] )

154:

155:

156:

157:

158:

159:

160:

161:

162:

163:

s[5]

s[0]s[1]s[2]s[3]s[4]

s[6]s[7]s[8]s[9]

Aplicación Indexada

39

Vectores (modalidad Pascal)Var V = Array [1..10] of Real;

: V[1]

V[2]V[3]

V[10]

ObjetoDescriptor

Nombre V

Constructor Array

Tipo Elemento Real

Tamaño Elem T

Dimensiones 1

Tipo índice IntegerLímite inf (li) 1Límite sup (ls) 10

Dir Base

Aplicación Indexada

40

Fórmula de accesoLa ubicación en RAM del i-ésimo elemento de V, durante ejecución, se determina mediante

Dir(V[i]) = + (i – li)*T

Aquí,

li y T se determinan en tiempo de traducción

, la dirección base, se determina en tiempo de creación

Aplicación Indexada

41

a) Declararlo en Pascal

b) Proponer una fórmula para acceder al i-ésimo elemento de V

c) Determinar la dirección absoluta de V[4], si la dirección base es 1000

-2 -1 0 1 2 3 4 5 6 7 8

V:

Real

Aplicación Indexada

Ejercicio: Con respecto al vector

42

a) Type Vector = Array[-2..8] of Real;Var V : Vector;

b) Dir(V[i]) = + (i – li)*T

c) Dir(V[4]) = 1000 + ( 4 – -2 )*4= 1000 + (4 + 2)*4

= 1000 + 6*4 = 1024

Aplicación Indexada

43

Var A : Array [1..10, 1..5] of Real;

A: 1 2 3 4 5 1

2

3

4

5

6

7

8

9

10

Linealización

1,1 2,1 3,1 4,1 10,1 1,2 2,2 3,2 .. 10,5 ...

Por columnas:

...1,1 1,2 1,3 1,4 1,5 2,1 2,2 10,5

Por filas:

Aplicación Indexada

Caso bidimesional (modalidad Pascal)

44

A[1,1]A[1,2]A[1,3]

A[10,5]

b :

Objeto

A[1,4]A[1,5]A[2,1]A[2,2]A[2,3] :

Nombre AConstructor Array

Tipo Elemento Real

Tamaño Elem T

Dimensiones 2

Tipo índice IntegerLímite inf. fila (if) 1Límite sup. fila (sf) 10Límite inf. col (ic) 1Límite sup. col (sc) 5

Dir Base b

Descriptor

Aplicación Indexada

Vectores (modalidad Pascal)Var A = Array [1..10, 1..5] of Real;

45

Fórmula de accesoLa ubicación en RAM del elemento de A[i, j] durante ejecución, se determina mediante

Dir(A[i, j]) = b + (i – if)*S + (j – ic)*T con S = (sc – ic + 1)*T

Aquí, if, S y T se determinan en tiempo de traducción b, la dirección base, se determina en tiempo de

creación

Aplicación Indexada

46

1

2

3

4

5

6

7

8

9

10

B:

1 2 3 4 5

Aplicación Indexada

Ejercicio: Con respecto a la matriz

a) Declararlo en Pascal, asumiendo elementos reales

b) Determinar la dirección absoluta del elemento situado en la tercera columna de la cuarta fila

47

Aplicación Indexada

a) Var B = Array[1..10, 1..5] of Real;

b) Dir(B[i, j]) = b + (i – if )*S + (j – ic)*T S = (sc – ic + 1)*T S = (5 – 1 + 1)*4 = 20

Dir(B[4, 3]) = b + ( 4 – 1)*20 + (3 – 1)*4= b + 3*20 + 2*4

= b + 60 + 8 = b + 68

48

Var C : Array [1..4, 1..10, 1..5] of Real;

41

1

10

1 5

j

k

i

Acceso a un elemento C[i, j, k] en un vector de

matrices

Aplicación Indexada

Caso tridimesional (modalidad Pascal)

49

Por planos

1 5

k

1

10

j

i

Por filas

j

41i

1 5

k

Por columnas

1

10

j

41i

k

Var C : Array [1..4,1..10,1..5] of Real;

i j k

Aplicación Indexada

Linealización

50

Fórmula de accesoDir(C[i, j, k]) = + (i – ip)*R+ (j – if)*S + (k – ic)*T donde

S = (sc – ic + 1)*T R = (sf – if + 1)*S = (sf – if + 1)* (sc – ic + 1)*T ip, R, S y T se determinan en tiempo de

traducción , la dirección base, se determina en tiempo de

creación

Aplicación Indexada

51

Consta de:

Un descriptor y

Espacio en RAM calculado según el tamaño de la mayor variante definida

Variante 1:

a b c

T

Variante 2:

a b d eF

Unión Discriminada

Registro con variantes (modalidad Pascal)Var Z = Record

a : integer;case b : boolean of

True: (c : integer);False: (d : integer; e : real);

End;

52

Unión Discriminada

True Falsed g

Tabla de selección

de variantes b d

Selector 3 cTipo S3 IntegerTamaño S3 T3Dir relativa S3 K3

g Selector 3 dTipo S3 IntegerTamaño S3 T3Dir relativa S3 K3Selector 4 eTipo S4 IntegerTamaño S4 T4Dir relativa S4 K4

DescriptorNombre ZConstructor UniónSelector 1 aTipo S1 IntegerTamaño S1 T1Dir relativa S1 K1=0Selector 2 bTipo S2 IntegerTamaño S2 T2Dir relativa S2 K2Dir tabla de selección b

Dir Base

Objeto

53

Fórmula de accesoLa ubicación en RAM al i-ésimo selector, durante ejecución, se determina mediante

1i

1kki Tj)Ord(i)Dir(Z.S

1-i

1jkkj

j

1kk T*True)Ord(Z.ST *j)Ord(i

1-i

1jkkj

j

1kk T*True)Ord(Z.ST *j)Ord(i

1-i

1jkkj T*False)Ord(Z.S

1-i

1jkkj T*False)Ord(Z.S

Ord(False) = 0

Ord(True) = 1

Selector discriminante

Unión Discriminada

54

Ejercicio: Con respecto a la multilista

a) Declararla en Pascal y C

b) Determinar la dirección absoluta del tercer selector

Unión Discriminada

L

1 4

32

átomo next link

info

L

1 4

32

L

1 4

32

L

1 44

3322

átomo next link

info

55

a) Type Base = Integer;

Enlace = ^Nodo;Nodo = Record

link :Enlace; case atomo : Boolean

of True : (info : Base;) False : (next :

Enlace;) End;

Var L : Enlace;

Unión Discriminada

56

typedef int base;typedef struct Nodo{ Nodo *link; int atomo; union { base info; Nodo *next; } X;} *Enlace;Enlace L;

Unión Discriminada

Selector 1Selector 2

Selector 3

link atomo X

57

b) j=2 Dir(LS3) = + Ord(3 2)*Ti

+ Ord(3 >2)*(T1 + T2) + Ord(Z.S2 = True)*(T3) + Ord(Z.S2 = False)*(T3)

= + Ord(True)*(T1 + T2) + Ord(True)*(T3)

= + 1*(T1 + T2) + 1*T3

= + T1 + T2 + T3

Unión Discriminada

58

La representación interna de un conjunto potencia está restringida a los conjuntos definidos por extensión y se sustenta en la estructura conocida como string de bitsSi T es el tipo base, P es el conjunto potencia sobre T y C es una variable de tipo P, entonces C se representa mediante un string de n bits, con n = #(T)En C, el i-ésimo bit en

1 indica presencia 0 indica ausencia

del i-ésimo valor de tipo T en C

Conjunto Potencia

59

EjemploSi T = {a, b, c}, entonces la representación de

las variables P = {a, c}, Q = {b, c} y R = P Q = {c}

esPQR

Conjunto Potencia

1 0 1

0 1 1

0 0 1