1 Cobol C Pascal Fortran 4. TIPOS DE DATOS SmallTalk Java C++
2 Conceptos Básicos Un tipo de dato es:un conjunto de objetos una colección de operaciones con Tipo elemental. Valores constantes Tipo estructurado. Compuestos
3 Estructura de Tipos La estructura de los tipos de datos en un lenguaje la determinan dos componentes Equivalencia Conversión
4 Equivalencia Criterio con el cual se decide que dos objetos son del mismo tipo Equivalencia Nominal Estructural C++, Pascal, Ada C Los tipos de los dos objetos tienen el mismo nombre Los dos objetos tienen la misma estructura
5 Ejemplo NOTA: El tipo de v1 es anónimo Equivalencia nominal x1 eqN x2v2 eqN v3 Type E = integer; A = array[1..10] of integer; Var x1 : integer; x2 : integer; x3 : E; v1 : array [1..10] of integer; v2 : A; v3 : A; Equivalencia estructural x1 eqE x2 eqE x3 v1 eqE v2 eqE v3 NOTA: El tipo de v1 es anónimo
6 Ejemplo Error!! en eq. nominal Permitido en eq. estructuralProgram Ejemplo; Type Vector1= Array[1..10] of Real; Vector2= array[1..10] of Real; Var X,Z : Vector1; Y : Vector2; Procedure Rutina(A: Vector1); : End; Begin X:= Y; Rutina(Y); End. Error!! en eq. nominal Permitido en eq. estructural
7 Conversión Transformar Coerción (Implícita) La conversiónla representación interna de un r-valor según representación| interna del respectivo l-valor. Coerción (Implícita) La conversión Casting (Explícita)
8 Coerción Al efectuar una asignación Al evaluar una expresión PASCALConversión de dato IMPLÍCITA, que depende del contexto Al efectuar una asignación Al evaluar una expresión PASCAL Var Z,X: Real; Y: Integer; X:= Y; Z:= X+3; FORTRAN R=I
9 Coerción PL/1 provee una conversión implícita entre TODOS los tipos elementales Caracter Real bit Integer En general, los LP proveen conversión de tipos entre tipos escalares y no entre tipos estructurados o definidos por el usuario.
10 Casting Conversión de tipo de dato EXPLÍCITA, utilizando operadores.En C: (int)x (float)y
11 Ejemplo float p, q; int s, n; s = 5; n = 2; p = s/n; /* coerción */q = (float)s/n; /* casting */ printf(%f %f \n, p, q); p: 2.0 q: 2.5
12 Ejemplo float 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= casting coerción z=5.0/4 = 5.0/4.0 z=1.25 casting coerción
13 Comprobación de Tipos La representación de datos NO incluye información sobre el tipo de dato. Acción de verificar la consistencia entre: un l-valor y un r-valor. en cada operación a ejecutarse. Recepción de: Cantidad apropiada de parámetros. y del tipo apropiado.
14 LP fuertemente tipadosComprobación de Tipos Comprobación Estática LP fuertemente tipados Dinámica LP débilmente tipados
15 Comprobación estáticaTiempo de compilación Generación de la tabla de símbolos Gran % de comprobación antes de la ejecución. Ejecución más segura y eficiente.
16 Comprobación dinámicaTiempo de ejecución No se requiere declaración ni se asume tipo. El tipo de dato de un objeto puede variar durante la ejecución. Su implementación sugiere utilizar una "marca" que indique su tipo. Mayor espacio de almacenamiento. Programas más flexibles. Mayor tiempo de ejecución. Comprobar el tipo antes de ejecutar. Código generado por el compilador.
17 Comprobación dinámicaEl compilador generará código para: ALMACENAR información del tipo de dato del objeto CONSULTAR la información alamcenada sobre los objeto durante la ejecución COMPROBAR los valores que se van obteniendo durante la ejecución.
18 Comprobación dinámicaCasi NO existen lenguajes de programación en los que TODAS las comprobaciones de tipo se realicen durante la compilación
19 El valor a asignar sólo se puede comprobar en tiempo de ejecuciónEjemplo El valor a asignar sólo se puede comprobar en tiempo de ejecución Type rango = ; Var k, n : rango; ··· n := 2*k + 1;
20 Ejemplo x:= F(x) + Z; El compilador comprobará que:X sea del tipo de dato del parámetro formal de F El tipo de dato de F y de Z deben coincidir o ser compatibles El tipo de dato de la operación coincida o sea compatible con el de X
21 Tipos Estructurados de DatosModelos de Definición
22 Producto Cartesiano 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-túplas (c1, c2, ... cn) con ci Î Ci.
23 productos cartesianosProducto Cartesiano productos cartesianos registros o estructuras struct persona { char nombre[15]; int edad; }
24 Ejemplos 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.
25 Ejemplos Todo polígono regular así expresado (3,12.5) es un elemento del producto cartesiano Z x R Type pol_reg = record num_lados: integer; longitud: real end;
26 Aplicación Finita Es una función de un conjunto de valores pertenecientes a un dominio D sobre un conjunto de valores pertenecientes a una imagen I. F : D I
27 Aplicación Finita aplicaciones finitas arreglosAplicación del subrango de enteros sobre los números reales. A[k] k : 1..5 A: array [1..5] of real; un objeto del conjunto imagen
28 Aplicación Finita Estrategias de los lenguajes para ligar el dominio de la función a un subconjunto específico de valores: Estática Semidinámica Dinámica
29 Estrategia estática Pascal : Lista = array [1..5] of real; C :El subconjunto se determina en tiempo de compilación. Pascal : Lista = array [1..5] of real; C : typedef float Lista[5];
30 Estrategia semidinámicaEl subconjunto se determina en tiempo de creación del objeto. En Algol : [m : n] int A; declara un arreglo semidinámico cuyo espacio en memoria se asigna de acuerdo a los valores actuales de m y n y permanece mientras A exista en el ambiente en el que fue definido.
31 Estrategia dinámica El subconjunto puede cambiar en cualquier instante de la existencia del objeto. En 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]
32 Unión Discriminada Extensión del producto cartesiano.Permite, en cualquier instante de la ejecución del código al que pertenece, la elección de una entre diferentes estructuras alternativas : Variante : estructura alternativa Discriminante: Campo selector
33 Unión Discriminada Parte Variante Parte Fija
34 Ejemplo Pascal : type reg_var = record Campo1 : integer;case atomo : boolean of true : info1 : real; false : info2 : char end;
35 Conjunto Potencia Permite definir variables cuyo valor puede ser cualquier subconjunto de un conjunto de elementos de un determinado tipo T. El tipo de las variables, tipo base, es: El conjunto de todos los subconjuntos de elementos de tipo T Si T = {a, b, c} P (T) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} #(P (T)) = 2#(T) = 23 = 8
36 Modelos de ConstrucciónCriterios a considerar en la elección de representaciones de almacenamiento : Selección eficiente de componentes de una estructura de datos. Gestión global eficiente del almacenamiento para la implementación del lenguaje.
37 Modelos de ConstrucciónConstituyen una técnica de representación interna de objetos de dato. Formado por un par consistente en : Descriptor (Conjunto de atributos de la estructura) Objeto (almacenamiento para los componentes)
38 Tipos Elementales EnterosConstituyen una abstracción de una implementación Hw. No tienen otros atributos, además de su tipo. Su implementación más común, es usar una representación definida por el Hw, y un conjunto de aritmética de Hw y operaciones primitivas relacionales sobre enteros. Normalmente, esta representación usa una palabra de memoria (o serie de bytes) completa para guardar un entero.
39 Representación Sin descriptor. (C – FORTRAN) Sólo se guarda el valorRepresentación posible si el lenguaje provee declaraciones y verificación estática de tipos. 110111 Entero binario Bit de signo
40 Representación Descriptor guardado en una palabra independiente. ( Lisp) Lo guarda en una localidad de memoria separada, con un puntero al valor entero de la “palabra completa”. Desventaja: puede duplicar el almacenamiento requerido para un objeto de datos entero individual. Ventaja: el valor se guarda usando la representación dada por el Hw; esto permite usar operaciones aritméticas de Hw.
41 Representación Gráficamente: : I Descriptor Bit de signoEntero binario : Objeto
42 Representación Descriptor guardado en la misma palabra.Guarda el descriptor y el valor en una localidad de memoria. Acorta el tamaño del entero para dar espacio para el descriptor. Se conserva el almacenamiento, pero las operaciones aritméticas del Hw no se pueden usar, sin antes: despejar el descriptor del objeto de datos entero, ejecutar la aritmética y reinsertar luego el descriptor.
43 Representación Gráficamente: Bit de signo Descriptor de tipoEntero binario I Ejecutar una serie de instrucciones de Hw para una operación aritmética ==> aritmética ineficiente. Forma práctica sólo para descriptores de tipo implementados por el Hw, no son comunes actualmente.
44 Representación T=1 T=1 T=2 a : a : Cantidad de direccionesde memoria que requiere un objeto para su almacenamiento. a : Word = 4 byte T=1 Objeto Word = 2 byte T=1 Objeto a : Objeto Word = 1 byte T=2
45 Representación Posibles representaciones para un entero int a;Ejemplo: Entero (2 bytes) int a; Descriptor Dir. Base entero Tipo a Nombre Objeto a Signo Magnitud 15
46 Tipos Elementales Reales (punto flotante)Tamaño: 4 Byte; norma 754 IEEE Este modelo emula la notación científica: cualquier número se puede expresar como N = m * 2k; < m < 1; k Z Para reales de doble precisión en punto flotante, se usa una palabra adicional de memoria para guardar una mantisa extendida.
47 Dígitos significativos del númeroRepresentación Gráficamente: Signo exponente mantisa Dígitos significativos del número S E M
48 Representación Los números se componen de 3 campos :S un campo de signo de un bit ( 0 es positivo) E un exponente en notación de exceso. Los valores (8 bits) varían entre 0 y 255, correspondientes a exponentes de 2 que van de –127 a 128. M una mantisa de 23 bits. Con esto se obtiene un intervalo de a 1038. En formato de 64 bits, el exponente se amplía a 11 bits, para dar un intervalo de –1022 a +1023, lo que da números en el intervalo de a
49 Representación Representación del real 1.5 : 000001 11000000Bit de signo de exponente Exponente Bit de signo Mantisa Punto raíz implícito 000001
50 Representación Dados E y M, el valor de representación es : ParámetrosNúmero no válido. E = 255 y M = 0 0 < E < 255 2E-127 (1.M) E = 0 y M 0 2-126.M E = 0 y M = 0
51 Ejemplos 32 bits +1 = 20 x 1 = 2127-127 x (1).0 (binario) +1.5 = 20 x 1.5 = x (1).1 (binario) -5 = -22 x 1.25 = x (1).01 (binario)
52 Representación float x; Ejemplo: Real (4 Byte; norma 754 IEEE)Descriptor Objeto
53 Representación Cantidad de direcciones de memoria que requiereun objeto para su almacenamiento. Word = 1B T=4 Objeto Objeto Word = 4B T=1 Objeto Word = 2B T=2
54 Tipos Estructurados Secuencial. La estructura de datos se guarda en un bloque contiguo de almacenamiento, que incluye el descriptor y los componentes. Vinculado. La estructura de datos se guarda en varios bloques no contiguos, con los bloques vinculados entre sí a través de apuntadores. Un apuntador del bloque A al bloque B, “vínculo”, se representa guardando la dirección de la primera localidad del bloque B en una localidad reservada para ese fin en el bloque A.
55 Tipos Estructurados Vinculada Secuencial Descriptor Componente vínculo...... Componente . vínculo Vinculada Secuencial
56 Tipos Estructurados Secuencial:Se usan para estructuras de tamaño fijo. Ocasionalmente en estructuras homogéneas de tamaño variable. Ejemplo : registros, vectores, strings, etc. Vinculada: Se usan para estructuras de tamaño variable. Ejemplo : listas enlazadas.
57 Tipos Estructurados Las memorias se estructuran como una serie de bytes. Ausencia de operaciones de hardware para acceso a componentes. Simular a través de software las estructuras de datos y las operaciones que trabajan con estructuras de datos. Tipos elementales de datos, representación de almacenamiento y operaciones son manejadas por hardware.
58 Representación Cantidad de direcciones de memoria que requiere un objeto para su almacenamiento. El tamaño de un Objeto de Dato dependerá de: Tipo de dato del objeto Tamaño de la palabra
59 Representación Los modelos de representación deben considerar fórmulas de acceso para alcanzar las componentes de tipos agregados de datos. Una fórmula de acceso es una función que transforma, a partir de los atributos contenidos en el descriptor: referencias lógicas direcciones relativas direcciones absolutas referencias físicas
60 Tipos Estructurados de DatosModelos de Representación
61 Producto Cartesiano Modalidad Pascal Var reg : record a : integer;b : real end;
62 Producto Cartesiano Descriptor Objeto Nombre reg Constructor recordSelector 1 a Tipo Selector 1 integer Tamaño Selector 1 t1 Dirección relativa Selector 1 K1 = 0 Selector 2 b Tipo Selector 2 real Tamaño Selector 2 t2 Dirección relativa Selector 2 K2 Dirección Base Objeto a b
63 Producto Cartesiano Fórmula de acceso Dirección absoluta de memoria donde se encuentra el i-ésimo selector del registro R. Objeto donde es la dirección base de R, resuelta en tiempo de carga, y tk el tamaño del k-ésimo selector.
64 å å Producto Cartesiano a + tk a + tk Sin embargo, la expresiónse resuelve en tiempo de traducción. Luego, con i - 1 tk å a + k = 1 = y = 0, constantes
65 Ejercicio Dada la siguiente estructura: a b c d e f g h j r: int floatchar boolean puntero a b c d e f g h j r: Defina las declarativas en Pascal y en C. b) Describa una fómula de acceso a una componente del registro r c) Determine la dirección absoluta del campo g del registro r, si la dirección base es 1000 y la word =1
66 Ejercicio Solución a) Pascal : type puntero = ^real;estructura = record a, d, j : integer; b, f, g : real; c : char ; e : boolean ; h : puntero end; a) C : typedef real * puntero; typedef struct { int a, d, j; float b, f, g; char c ; int e ; puntero h; } estructura ;
67 Dir(r.x)= + (tsel_1+ …+tsel_k)Solución b) Aplicando la fórmula, se tiene : Dir(r.x)= + tsel_i sel_i =a x-1 Dir(r.x)= + (tsel_1+ …+tsel_k) en que, tsel_k = techo(tamaño del tipo(sel_k) / tamaño de la palabra) Con : a k < x
68 Dir(r.g) = + ta+tb+tc+td +te +tfSolución a b c d e f g h j c) Aplicando la fórmula, se tiene : Dir(r.g) = + ta+tb+tc+td +te +tf Dado que el tamaño de la palabra es 1, word=1 se tiene que : ta= techo(2/1)=2; tb= techo(4/1)=4; tc= techo(1/1)=1; td= techo(2/1)=2; te= techo(1/1)=1; tf= techo(4/1)=4 Luego, Dir(r.g) = = + 14; pero: = 1000, Dir(r.g) = 1014
69 Ejercicio Realice implementaciones para : Números complejos (a+bi)Números racionales (a/b) Enumeraciones Booleanos Caracteres
70 Var A : array[0 .. 4] of integer;Aplicación Finita Después de una declaración de variable Var A : array[0 .. 4] of integer; Los elementos del arreglo A aparecen en localidades consecutivas de memoria: A[0] A[1] A[2] A[3] A[4]
71 La dirección base + El desplazamientoAplicación Finita Dada una representación secuencial, en la selección directa de un componente, intervienen el cálculo de : La dirección base + El desplazamiento A través de una fórmula de acceso. Localidad inicial del bloque completo. Localidad relativa del componente seleccionado dentro del bloque secuencial.
72 Aplicación Finita La fórmula de acceso, dado el nombre o subíndice del componente deseado, especifica cómo calcular el desplazamiento del componente. Este desplazamiento se suma a la dirección base para obtener la localidad real del componente seleccionado en la memoria.
73 Aplicación Finita Observación:Este cálculo será muy eficiente, si se usan subíndices constantes, ya que el traductor puede calcular la fórmula de acceso durante el tiempo de compilación y generar código para tener acceso directo al componente.
74 Aplicación Finita Ejemplo : Sea el arreglo en C : char A[10];El almacenamiento para A, se dispone en forma secuencial como A[0], A[1], ..., A[9]. La dirección de A[1] será la dirección base del arreglo A más 1 En general, para arreglos de char en C, la dirección de A[I] será Dir(A[i]) = l-value(A[0]) + I
75 Aplicación Finita Dirección base = localidad de A[0] A[0] A[1] A[2]Desplazamiento = i * tamaño del componente = 5 * 1 = 5 Dirección base + desplazamiento = l-valor( A[0] ) + 5 = l-valor( A[5] ) 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: A[5] A[0] A[1] A[2] A[3] A[4] A[6] A[7] A[8] A[9]
76 Aplicación Finita Dirección base = localidad de A[0] A[0] A[1] A[2]Desplazamiento = i * tamaño del componente = 5 * 1 = 5 Dirección base + desplazamiento = l-valor( A[0] ) + 5 = l-valor( A[5] ) 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: A[5] A[0] A[1] A[2] A[3] A[4] A[6] A[7] A[8] A[9]
77 Aplicación Finita Acceso a los componentes de una estructura homogénea: Para seleccionar la primera componente de la serie: A[i] Usar el cálculo de dirección base más el desplazamiento. 2. Para avanzar a la próxima componente: A[i+1] Sumar el tamaño de la componente actual a la localidad (dirección) del mismo.
78 Aplicación Finita Dirección base Tipo de datosLímite Inferior de subíndices Límite Superior de subíndices Tipo de Datos Componentes Tamaño del componente A[LI] A[LI] + 1 A[LS] Vector Entero E LS LI Dirección base Descriptor (vector de arreglos) Representación de almacenamiento para componentes
79 Aplicación Finita Vectores : Pascal Descriptor Objeto typevector = array [1..10] of real; Var V : vector; Vectores : Pascal Descriptor V[1] V[2] V[3] V[10] Objeto
80 Dir(V[i]) = a + ( i – li ) * TAplicación Finita Fórmula de acceso El acceso al i-ésimo elemento de V, durante ejecución: Dir(V[i]) = a + ( i – li ) * T donde: li y T se determinan en tiempo de traducción. a ,la dirección base, en tiempo de carga
81 Ejercicio V: Real a) Declarativas en Pascal b) Fómula de acceso a una componente i del vector V c) Dirección absoluta de la componente 4 del vector V, si la dirección base es 1000 y la word =2
82 Solución a) Type vector = array[-2..8] of real; Var V : vector;b) Dir(V[i]) = a + ( i – -2 ) * T Dir(V[i]) = a + ( i +2 ) * T T=4/word c) Dir(V[4]) = ( 4 +2 ) * 2 = * 2 = 1012 T=4/2=2
83 Aplicación Finita Linealizar!! A: ... ... Matrices Modalidad PascalVar A : array [1..10,1..5] of real; A: 1 2 3 4 5 6 7 8 9 10 ... 1, ,2 1,3 1,4 1,5 2,1 2, ,5 Por filas: 1,1 2,1 3, , ,1 1,2 2,2 3, ,5 ... Por columnas: Linealizar!!
84 Aplicación Finita : Var Matrices Modalidad PascalA : array [1..10,1..5] of real; Matrices Modalidad Pascal Descriptor A[1,1] A[1,2] A[1,3] A[10,5] Objeto A[1,4] A[1,5] A[2,1] A[2,2] A[2,3] :
85 Aplicación Finita Dir( A[i,j] ) = a + ( i – if ) * TF + ( j – ic ) * TEl acceso al elemento A[i, j], durante ejecución, se expresa mediante la fórmula: Límite inferior de la fila Límite inferior de la columna Dir( A[i,j] ) = a + ( i – if ) * TF + ( j – ic ) * T la dirección base, en tiempo de carga se determinan en tiempo de traducción Tamaño de la fila (sc-ic+1)*T Tamaño de la componente Límite superior de la columna Límite inferior de la columna
86 Ejercicio A: Para el arreglo : Para el arreglo : 1 2 3 4 5 6 7 8 9 10 A: Realizar la declarativa en Pascal y en C. Asuma como tipo de las componentes los reales. Determinar la dirección del elemento A[4,3].
87 Solución Pascal : Type matriz = array[1 .. 5,1..10] of float; VarA : matriz; C : typedef float matriz[5][10]; Matriz A;
88 Fórmula de acceso Dir(A[i,j]) = a + ( i – if ) * TF + (j – ic) * TEl acceso al elemento A[i, j], durante ejecución, se expresa mediante la fórmula: Dir(A[i,j]) = a + ( i – if ) * TF + (j – ic) * T Tamaño de los elementos Tamaño de la fila Para el ejemplo anterior, se tiene : Dir(A[4,3] )= a + (4 -1) * TF + (3 – 1) * T TF = (sc-ic+1)*T T = 4 / 2 2; word = 2 byte TF = (5 – 1 + 1) * 2 10 Dir(A[4,3] )= a + (4 -1) * TF + (3 – 1) * T a + (4 -1) * 10 + (3 – 1) * 2 a + 3 * * 2 Dir(A[4,3] )= a +34
89 Fórmula de acceso Linealizar!! 4 Cubo:Var A : array [1..4,1..10,1..5] of real; 4 1 10 i j k C[k,i,j] ... Vector de matrices Linealizar!!
90 Fórmula de acceso k i j j i i 4 j i 4 j k k kVar A : array [1..4,1..10,1..5] of Real; k i j Formas posibles de linealizar : Por planos j 1 10 i k Por filas i 4 1 k j Por columnas 1 10 i 4 k j
91 Fórmula de acceso donde: Var A : array [1..4,1..10,1..5] of Real;TP Tamaño del plano (sf-if+1)*(sc-ic+1)*T TF Tamaño de la fila (sc-ic+1)*T if, ic, T, TF y TP se determinan en tiempo de traducción. a ,la dirección base, en tiempo de carga
92 Ejemplo Se tiene una estructura de datos que consiste en un arreglo, cuyos componentes son registros. Realizar las declarativas correspondientes en C y Pascal. Representarlos gráficamente. Determinar la fórmula de acceso para una componente cualquiera.
93 Unión Discriminada Si los objetos de un conjunto A pueden ser clasificados en subconjuntos disjuntos B1, B2, ..., Bk, con k > 1 Tales objetos pueden representarse por medio de un registro variante, con la información común almacenada en campos fijos y la información de cada objeto en partes variantes opcionales.
94 Unión Discriminada Ejemplos :Todos los aviones tienen un fabricante y un precio; sin embargo, una avioneta tiene un motor y algunos aviones tienen 4 motores. Sea el siguiente árbol de expresión : and not x p Todos los nodos tienen un tipo; sin embargo, pueden tener un número diferente de hijos. Estos nodos pueden clasificarse en nodos para variables, constantes, operadores binarios y unarioos, con 0, 2 o 1 hijo respectivamente.
95 Unión Discriminada Se representa el árbol anterior : Typeclase = (unario, binario); nodo = record c1 :T1; c2 : T2; case k : clase of unario : (hijo : T3); binario : (hijoizq, hijoder : T4); end end; Campo discriminante Parte variante
96 Unión Discriminada Localización en memoria: c1 c2 k hijo Campomarcador Parte variante Parte fija hijoder c1 c2 k hijoizq hijoder
97 Unión Discriminada Var Z : record a : integer; case b : boolean ofTrue: (c : integer); False: (d : integer; e : real); end; Variante 1: a b c T Consta de: Un descriptor y Del espacio necesario para sus componentes, considerando el tamaño de la mayor variante definida. Variante 2: a b d e F
98 Unión Discriminada b: d: g: Descriptor ObjetoTabla de selección de variantes b: Descriptor Objeto d: g:
99 Fórmula de acceso El acceso al i-ésimo selector, durante la ejecución, se expresa mediante la fórmula: donde Sj es el selector discriminante (tag field)
100 Fórmula de acceso selector discriminante Ord(false) = 0 O bien :Ord(true) = 1 O bien : selector discriminante
101 Ejercicio Sea la siguiente multilista:Realizar las declarativas correspondientes en Pascal y C. Representar gráficamente. Definir descriptor y objeto correspondiente. Determinar la dirección real del selector 3. Sea la siguiente multilista: L 1 4 3 2 átomo next link info
102 Solución Type base = integer; Enlace=^Nodo; Nodo = Recordlink :Enlace; case atomo : boolean of true : (info : base;) false : (next : Enlace;) end; Var L : Enlace;
103 Solución typedef int base; typedef struct Nodo { Nodo *link;int atomo; union {base info; Nodo *next; }X; } *Enlace; Enlace L; Selector 1 Selector2 Selector 3 link atomo X
104 Solución Gráficamente, se tiene un arreglo de nodos : No ocupado
105 Solución b d g Descriptor Objeto a Tabla de selección True False Nombre L Constructor Union Selector 1 link Tamaño 1 T1 Dirección relativa 1 K1 = 0 Selector 2 atomo Tamaño 2 T2 Dirección relativa 2 K2 Dir.Tabla de selección Dirección Base d info Selector 3 T2 Tamaño 3 K2 Dirección relativa 3 g Selector 3 next Tamaño 3 T3 Dirección relativa 3 K3
106 Solución Fórmula de Acceso al campo X.info: Selector ( Si ) = 3Discriminante ( Sj ) = 2 i = 3; j = 2 Dir(Z.x) = + Ord( 3 2 )* ti + Ord( 3 > 2)* (T1 + T2 ) + Ord(Z.S2 = true) * (T3 ) + Ord(Z.S2 = false) * (T3 ) Dir(Z.S3) = + Ord( true)* (T1 + T2) + Ord( true)* (T3 ) = + 1* (T1 + T2) + 1* T3
107 Conjunto Potencia La representación interna de un conjunto potencia está restringida a los conjuntos definidos por extensión. Se sustenta en la estructura conocida como: string de bits
108 presencia del i-ésimo valor del tipo T en C,Conjunto Potencia C es una variable de tipo conjunto potencia #(T) = n, Si: un string de n bits C se representa donde: el i-ésimo bit en 1 presencia del i-ésimo valor del tipo T en C, C = Los n bits en cero
109 Conjunto Potencia Q = {b, c}Un string de bits coincide conceptualmente con la estructura packed array of boolean Ejemplo: Sea T = {a, b, c} y las variables: P = {a, c} Representación Q = {b, c} R = PQ = {c}