Estructura de Datos Estructura y Representación de Datos: Primer departamental: examen y programas Segundo departamental: examen y programas Tercer departamental: Hechos ➔ datos programas  se almacena en un sistema computacional (vida real) Procesamiento de datos ➔ Información ➔ Toma de decisiones Información = datos procesados Operaciones con los datos a) Almacenar d) Encriptar b) Recuperar, Actualizar e) Codificar c) calcular f) Clasificar, Ordenar Memoria: almacenamiento, dispositivo o medio capaz de aceptar datos, almacenarlos y proporcionarlos cuando se utilizan. Memoria principal es temporal: lugar donde los datos se guardan temporalmente, durante el procesamiento. Memoria secundaria es permanente: son las cintas, discos, etc. y son permanentes. La cantidad de memoria que dispone una maquina se mide en bytes. KBytes, MB, GB, TB Estructura de Datos La memoria principal de una computadora es costosa El C.P.U. (unidad central de procesamiento), contiene la memoria. Datos organizados dentro de un sistema computacional: *las computadoras almacenan datos como 0 y 1 llamados bits (dígitos binarios) Bit ↓ Byte ↓ Data item ↓ Registro (struct) ↓ Archivo ↓ Base de datos Entrada Datos ➔ 0 ,1 0101 1101 0101 1101 0011 1110 1111……. 0101 1101 0011 1110 1111……. 0101 1101 0011 1110 1111……. 0101 1101 0011 1110 1111……. RAM ROM Salida = Información Almacenamiento secundario Unidad de control Unidad aritmética Estructura de Datos Tipos de datos • Datos numéricos: se representan en dos formas: • enteros: *datos completos *pueden ser positivos o negativos *representación binaria *el rango varia según el lenguaje 00100110 = 38 Signo →1 0100110 = - 38 Numero 128 64 32 16 8 4 2 2^0 Para eliminar el -0 utilizamos el complemento a 2 Ejemplo: Si consideramos 4 bits cual será el rango de números enteros que podemos representar: Binario 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000 Decimal → +7 → +6 → +5 → +4 → +3 → +2 → +1 →0 → -1 → -2 → -3 → -4 → -5 → -6 → -7 → -8 • Reales: tienen siempre un punto decimal, las fracciones se almacenan en las computadoras como números reales. Estructura de Datos Los números reales se representan mediante la notación del punto flotante mantisa * be. Ejemplo: 387.53 = 38753 * 10 ^ -2 Un número real esta representado por una hilera de 32 bits formado por un mantisa de 24 bits seguida por un exponente de 8 bits , la base se fija como 10, la mantisa y el exponente son enteros de complemento doble. Ejemplo: 38753 * 10^ -2 0000 0000 1001 0111 0110 0001 | 1111 1110 00000010 11111101 + 1 ---------------11111110 complemento a 2 Ejercicio: representar los siguientes números en binario No. Real Punto flotante 0.0 100.0 .5 .000005 12000.0 -12000.0 -.000005 Representación binaria con mantisa 16 bits y 8 bits para el exponente Estructura de Datos Datos tipo lógico: valores true o false → 0 ó 1 Strings o cadenas de caracteres utilizando códigos como el ASCII ´A´ = 11010010 ´B´ = 11010011 ´A B´ = 1101001011010011 El número de bits para representar un carácter se denomina tamaño del byte, si son 8 bits se pueden representar 256 caracteres. El método para interpretar un patrón de bits se denomina tipo de datos. Pascal c Var x, y: int; a, b: real; nomb: char; int x, y; double a, b; char[45] nomb; La RAM es un conjunto de bits. Un bit es direccionable. Estructura de Datos Las Estructuras de Datos. Una Estructura de datos es una colección de elementos o ítems de datos. El medio en el que se relacionan unos elementos con otros determina el tipo de estructura de datos. El valor de una estructura se determina por: a) Valor de los elementos: ver de que tipo son. b) La disposición de los elementos : como están guardados los elementos. Los valores de los datos pueden ser cambiados. La disposición cambia menos frecuente. La estructura raramente cambia. Ejemplo: Guía_telef = { nombre, dirección, teléfono } Los nombres, dirección, teléfono cambian, pero la disposición no, salvo si se ordenan en orden alfabético. Juan, Direc x, 5544332 Ana, Direc y, 5232510 Pedro, Direc z, 5188170 Ana, Direcy, 5232510 Juan, Direc x, 5544332 Pedro, Direc z, 5188170 } Disposición Definición de Variable: Se denomina variable cuando la cantidad o valor de un elemento varía de cuando en cuando. Estructura de Datos Clasificación de las Estructuras de Datos Las estructuras de datos se pueden clasificar en: Estáticas { + arreglos (vectores, matrices ,etc.), + Registros, + Archivos } Dinámicas { + lineales (pilas, colas, listas enlazadas) + no lineales ( arboles, grafos) } Arreglos: almacenan un conjunto de datos del mismo tipo, relacionados unos con otros por el orden en el que están definidos, se almacenan en posiciones adyacentes. Si se tiene el arreglo k[5] int se representaría así en la memoria: Dirección Valor Ítem Referencia 210 20 K[0] 211 28 K[1] 212 10 K[2] 213 7 K[3] 214 3 K[4] Estructura de Datos Los arreglos se clasifican en: Unidimensionales (vectores, listas) Bidimensionales (matrices, tabla) Multidimensionales (cubo) Un vector es una secuencia de elementos en la que todos los elementos son del mismo tipo , el orden es significativo y esta dado por el subíndice. Vector K[6] int K[0] K[1] . . . K[5] O puede verse de esta forma: K[0] K[1] *Ejercicio: . . . K[5] Estructura de Datos hacer un algoritmo que combine 2 vectores L y K en un tercer vector M. K= L= 1 3 2 8 3 10 1 11 Algoritmo: *Ejercicio: Hacer dos algoritmos uno que haga la diferencia de dos vectores K-L Estructura de Datos M=K–L 8 10 Y otro que haga M=L–K 2 Algoritmo: 11 Estructura de Datos Arreglos bidimensionales: + Es un vector de vectores + Elementos del mismo tipo + El orden es significativo + Se utilizan subíndices: (i, j) i = fila j = columna Representación de una matriz A de 4x4 en la Memoria A[4][4]: 0 1 2 3 0 6 8 3 4 1 3 1 2 30 2 4 2 50 60 3 70 31 26 28 La matriz identidad es aquella donde la diagonal principal contiene 1´s y los demás elementos 0´s Ejercicio: Hacer un algoritmo para crear una matriz identidad de A[4,4] 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 Estructura de Datos Algoritmo: Multiplicación de Matrices A= 1 2 3 3 2 1 B=1 2 3 Orden de la Matriz n=2 m=3 n=3 3 2 1 n = filas m = columnas m=2 Número de columnas (m) de A = al numero de filas (n) de B Orden de la Matriz Resultante n=A m=B, X[2][2] X= X[1,1] X[1,2] X[2,1] X[2,2] m de A X(i,j) = ∑ [ a[i,c] * b[c,j] ] c=1 X[1,1]=(1*1)+(2*2)+(3*3)=14 X[1,2]=(1*3)+(2*2)+(3*1)=10 X[2,1]=(3*1)+(2*2)+(1*3)=10 X[2,2]=(3*3)+(2*2)+(1*1|)=14 X = 14 10 10 14 Estructura de Datos Tarea: Resolver la sig: multiplicación de matrices: A= 1 2 3 5 10 5 2 2 2 B= 2 2 2 4 4 4 3 3 3 X = 19 65 . . . . . . . Tarea: hacer un algoritmo para la multiplicación de matrices Estructura de Datos Arreglos multidimensionales Pueden existir arreglos de tres o mas dimensiones , según el lenguaje (C, Java, etc.) o Aplicación (Data warehouse, B.I.) Fila Plano Columna Arreglo tridimensional A [3][3][3] Donde se ubica el elemento: A[2,2,1] = 20; y el A[0,2,2] = 7; Estructura de Datos Estructura de datos físicas { datos simples ( int, real, char, ..) vectores, arreglos } Estructura de datos lógicos { arreglos multidimensionales registros ,archivos listas ,pilas ,colas } Listas lineales: es un conjunto o secuencia ordenada de elementos de un tipo de dato. Representación: Lista L: L1, L2…,Ln notación: Li o L(i) + Cada elemento tiene un predecesor excepto el primero + Cada elemento tiene un sucesor excepto el ultimo sucesor L(i+1) N = Tamaño de la Lista (Número de Localidades) n = numero de elementos en lista, conocido con longitud de la lista. Si n = 0 then ”lista vacia”; Si n >= N then ”lista llena” + Cada elemento de la lista puede ser una estructura Operaciones con las Listas: Insertar un Elemento Buscar un elemento Borrar un elemento Actualizar un elemento Insertar un elemento en determinada Posición Ordenar una Lista Etc.