Arreglos Y Registros

Transcript

Introducción a la Informática 2009 Tema 7 Arreglos y Registros 1. Introducción a las estructuras de datos Una estructura de datos es una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen en ella. Las estructuras de datos son muy importantes en los sistemas de computadora. Los tipos de datos más frecuentes utilizados en los diferentes lenguajes de programación son: entero(integer) estándar real (real) carácter (char) Datos Simples o Primitivos lógico (boolean) definido por el programador (no estándar) subrango (subrange) Enumerativo (enumerated) Arreglos (vectores/matrices) registro (record) estáticos Datos Estructurados o ficheros (archivos) conjuntos (set) Datos compuestos cadenas (string) listas (pilas/colas) dinámicos listas enlazadas Árboles y grafos Los tipos de datos simples o primitivos: son aquellos que no están compuestos de otras estructuras de datos. Los tipos de datos compuestos están construidos en base a los tipos de datos primitivos, un ejemplo, es la cadena o string de caracteres. A su vez, las estructuras compuestas pueden ser: Estáticas: cuando el tamaño ocupado en memoria se define antes de que el programa se ejecute y no puede modificarse dicho tamaño durante la ejecución del programa. Dinámicas: no tienen limitaciones o restricciones en el tamaño de memoria ocupada (este tipo de estructura no se contempla en esta asignatura). Diferencia entre los tipos de datos Los tipos de datos simples tienen como característica común que cada variable representa un elemento. Los tipos de datos estructurados tienen como característica común que un identificador (nombre) puede representar múltiples datos individuales, pudiendo cada uno de éstos ser referenciado independientemente. Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 1 Introducción a la Informática 2009 Tema 7 2. Arreglos unidimensionales: los vectores Un arreglo (matriz o vector) es un conjunto finito y ordenado de elementos homogéneos. La propiedad ordenado, significa que el elemento primero, segundo,.., enésimo de un arreglo puede ser identificado. La propiedad homogéneo, quiere decir que los elementos son del mismo tipo de datos. Por ejemplo, un arreglo puede tener todos sus elementos de tipo entero, o todos sus elementos de tipo char. El tipo más simple de arreglo es el arreglo unidimensional o vector. Ejemplo: Un vector de una dimensión, denominado NOTAS, que consta de n elementos se puede representar de la siguiente manera: NOTAS(1) NOTAS(2) …. NOTAS (i) … NOTAS(n) EL subíndice o índice de un elemento (1,2,…,i,n) designa su posición en la ordenación del vector. Otras posibles notaciones del vector son: a1, a 2,....., an en matemática y algunos lenguajes (V.B 6.0 y VB.Net) A(1), A(2),………,A(I),…..A(N) A[1], A[2],………,A[I],…..A[N] en programación (C y Pascal) En el ejemplo de las notas, observe que sólo el vector global, el dato compuesto, tiene nombre (NOTAS). Los elementos del vector se referencian por su subíndice ó índice, es decir, por su posición relativa en el vector. Otra forma de Notación: A (L:U) = {A (I)} Para I = L, L+1,…,U-1, U donde cada elemento A (I) es de tipo de datos T A es el vector unidimensional con elementos de datos tipo T, cuyos subíndices varían en el rango L a U, que significa que el índice no tiene porqué comenzar en 0 o en 1. El número de elementos de un vector se denomina rango del vector. El rango del vector A (L: U) es U – L+1. El rango del vector B (1: n) es n. Un ejemplo de un vector pueden ser los nombres de los alumnos de una clase. El vector se denomina ALUMNOS y tiene 30 elementos de rango. 1 Luis 2 Francisco 3 José … i Martín … 30 Graciela Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 2 Introducción a la Informática 2009 Tema 7 Otro ejemplo de un vector unidimensional, es el vector TEMPERATURA que contiene las temperaturas horarias registradas en una ciudad durante las 24 horas del día. Este vector constará de 24 elementos del tipo real, ya que las temperaturas no serán enteras siempre. El valor mínimo del índice permitido de un vector se denomina límite inferior del vector (L) y el valor máximo permitido se denomina límite superior (U). En este ejemplo el límite inferior es 1 y el superior 24. TEMPERATURA (I) donde 1 <= I <= 24 Los vectores se almacenan en memoria central de la computadora en un orden adyacente. Así, un vector de cincuenta números denominado NUMEROS se representa físicamente por cincuenta posiciones de memoria sucesivas. Memoria 1 Dirección x 2 Dirección x + 1 3 Dirección x + 2 30 Dirección x + 49 Cada elemento de un vector se puede procesar como si fuese una variable simple al ocupar una posición de memoria. Así: NUMEROS[25] = 72 almacena el valor entero o real 72 en la posición 25ª del vector NUMEROS y la instrucción de salida ESCRIBIR NUMERO [25] visualiza el valor almacenado en la posición 25ª, en este caso 72. Esta propiedad significa que cada elemento de un vector y posteriormente una tabla o matriz, es accesible directamente y es una de las ventajas más importantes de usar un vector. Ejemplo 1: Vector X de ocho elementos X[1] X[2] X[3] X[4] X[5] X[6] X[7] X[8] 14.0 12.0 8.0 7.0 6.41 5.23 6.15 7.25 Elemento 1° Elemento 2° Elemento 8° Ejemplo 2: Algunas instrucciones que manipulan el vector X del ejemplo 1. Acciones Resultados ESCRIBIR X[1] Visualiza el valor X[1] o 14.0 X[4] = 45 Almacena el valor 45 en X[4] SUMA = X[1]+X[3] Almacena la suma de X[1] y X[3] o bien 22.0 en la variable SUMA SUMA = SUMA+X[4] Añade en la variable SUMA el valor de X[4], o sea, SUMA= 67.0 X[5] = X[5] + 3.5 Suma 3.5 a X [5]; el nuevo valor será 9.91 X[6] = X[1] + X[2] Almacena la suma de X[1] y X[2] en X[6]; el nuevo valor será 26.5 Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 3 Introducción a la Informática 2009 Tema 7 Los arreglos unidimensionales y multidimensionales necesitan ser dimensionados previamente a su uso dentro del programa. Ejemplo 3: Un vector V de ocho elementos V[1] V[2] V[3] V[4] V[5] V[6] V[7] V[8] 12 5 -7 14.5 20 1.5 2.5 -10 I= 4 V [I+1] representa el elemento V (5) de valor 20 V [I+2] representa el elemento V (6) de valor 1.5 V [I-2] representa el elemento V (2) de valor 5 V [I+3] representa el elemento V (7) de valor 2.5 Los subíndices de un vector pueden ser enteros, variables o expresiones enteras. 3. Operaciones con vectores: Las operaciones que se pueden realizar con vectores durante el proceso de resolución de un problema son: • Asignación • Lectura/escritura • Recorrido (acceso secuencial) • Actualizar (añadir, borrar, insertar) • Ordenación • Búsqueda En general, las operaciones implican el procesamiento o tratamiento de los elementos individuales del vector. La notación algorítmica es: TIPO ARRAY [liminf…limsup] DE tipo:nombre_array nombre_array: nombre válido del arreglo liminf . . limisup: límites inferior y superior del rango del arreglo tipo: tipo de datos de los elementos del array: entero, real, carácter Ejemplo: TIPO ARRAY [1..10] DE carácter: NOMBRES VARIABLES NOMBRES: N Significa que NOMBRES es un array unidimensional de diez elementos (1 a 10) de tipo carácter. Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 4 Introducción a la Informática 2009 Tema 7 3.1. Asignación La asignación de valores a un elemento del vector se realizará con la instrucción de asignación: A[20] = 5 asigna el valor 5 al elemento 20 del vector A Para asignar valores a todos los elementos de un vector, se debe recurrir a estructuras repetitivas (PARA, MIENTRAS o ITERAR) e incluso selectivas (SI-ENTONCES). Ejemplo 1: Introducir los valores 5, 7, 8, 14 y 12 mediante asignaciones a cada elemento del vector A. LEER A [ i ] A [1] = 5 A [2] = 7 A [3] = 8 A [4] = 14 A [5] = 12 Ejemplo 2: Para dar el mismo valor a todos los elementos, la notación algorítmica se simplifica con el formato: PARA i DESDE 1 HASTA 5 A [i] = 8 FIN-PARA Donde A[i] tomará los valores numéricos: A[1] = 8, A[2] = 8, ……. , A[5] = 8 3.2. Lectura/escritura de datos La lectura/escritura de datos en arreglos u operaciones de entrada/salida normalmente se realizan con estructuras repetitivas, o con estructuras selectivas. Las instrucciones simples de lectura/escritura se representarán como: LEER V [5] // leer el elemento V [5] del vector V 3.3. Acceso secuencial al vector (recorrido) Se puede acceder a los elementos de un vector para introducir datos (escribir) en él o bien para visualizar su contenido (leer). A la operación de efectuar una acción general sobre todos los elementos de un vector se la denomina recorrido del vector. Estas operaciones se realizan utilizando estructuras repetitivas, cuyas variables de control (ej. i) se utilizan como subíndice del vector (ej. S [i]). El incremento del contador del bucle producirá el tratamiento sucesivo de los elementos del vector. Ejemplo 1: Lectura de veinte valores enteros de un vector denominado F. Procedimiento 1 ALGORITMO leer_vector TIPO ARRAY[1..20] DE entero: FINAL VARIABLES FINAL: F INICIO PARA i DESDE 1 HASTA 20 LEER (F [i]) FIN-PARA FIN Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 5 Introducción a la Informática 2009 Tema 7 La lectura de veinte valores sucesivos desde el teclado rellenará de valores el vector F, comenzando con el elemento F [1] y terminando en F [20]. Procedimiento 2 Los elementos del vector se pueden leer también con bucles MIENTRAS o HACER-HASTA. i= 1 I= 1 MIENTRAS i <= 20 HACER LEER F [i] o bien i = i+1 FIN-MIENTRAS LEER F [i] i = i+1 HASTA i > 20 La salida o escritura de vectores se representa de un modo similar. La estructura visualiza todo el vector completo (un elemento en cada línea independiente). Ejemplo 2: Procesamiento de un arreglo PUNTOS, realiza las operaciones: lectura del array, cálculo de la suma de los valores del arreglo, cálculo de la media de los valores. El arreglo se denomina PUNTOS, el límite superior del rango se introduce por teclado y el límite inferior se considera 1. Amplíe el ejemplo permitiendo la visualización de los elementos del arreglo, cuyo valor es superior a la media. (Ejercite) ALGORITMO media_puntos CONST limite = 40 TIPO ARRAY [1 . . limite] DE real: puntuacion VARIABLES puntuacion: puntos real: suma , media entero: i INICIO suma = 0 ESCRIBIR ‘datos del array’ PARA I DESDE 1 HASTA limite LEER puntos [i] suma = suma + puntos [i] FIN-PARA media = suma/limite ESCRIBIR ‘La media es’, media FIN 3.4 Actualización de un vector La operación de actualizar un vector puede constar a su vez de tres operaciones elementales: - añadir elementos - insertar elementos - borrar elementos Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 6 Introducción a la Informática 2009 Tema 7 Se denomina añadir datos a un vector a la operación de añadir un nuevo elemento al final del vector. La única condición necesaria para esta operación es la comprobación de espacio de memoria suficiente para el nuevo vector. Ejemplo 1: Un arreglo TOTAL se ha dimensionado a seis elementos, pero sólo se le han asignado cuatro valores a los elementos TOTAL[1], TOTAL[2], TOTAL[3] y TOTAL[4]. Se podrán añadir dos elementos más con una simple acción de asignación. TOTAL [5] = 14 TOTAL [6] = 12 La operación insertar un elemento consiste en introducir dicho elemento en el interior del vector. En este caso se necesita un desplazamiento previo hacia abajo para colocar el elemento nuevo en su posición relativa. Ejemplo 2 Se tiene un array COCHES de nueve elementos que contiene siete marcas de automóviles en orden alfabético y se desea insertar dos nuevas marcas: OPEL y CITROËN Como Opel está comprendido entre Lancia y Renault, se deberá desplazar hacia abajo los elementos 5 y 6, que pasaran a ocupar la posición relativa 6 y 7. Posteriormente debe realizarse la operación con Citroën, que ocupará la posición 2. El algoritmo que realiza esta operación para un vector de n elementos, suponiendo que haya suficiente espacio en el vector, es: 1. // Calcular la posición ocupada por el elemento a insertar (ej. P) 2. // Inicializar contador de inserciones i = n 3. MIENTRAS i >= P // transferir el elemento actual i-ésimo a la posición i+1 COCHES [i+1] = COCHES [i] i = i-1 // decrementar contador FIN_MIENTRAS 4. // insertar el elemento en la posición P COCHES [P] = ’nuevo elemento’ 5. // actualizar el contador de elementos del vector 6. n = n+1 7. FIN a) COCHES b) Insertar OPEL c) Insertar Citroën 1 Alfa Romeo 1 Alfa Romeo 1 Alfa Romeo 2 Fiat 2 Fiat 2 Citroën 3 Ford 3 Ford 3 Fiat 4 Lancia 4 Lancia 4 Ford 5 Renault 5 Opel 5 Lancia 6 Seat 6 Renault 6 Opel 7 7 Seat 7 Renault 8 8 8 Seat 9 9 9 Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 7 Introducción a la Informática 2009 Tema 7 La operación de borrar un elemento al final del vector no presenta ningún problema; el borrado de un elemento del interior del vector provoca el movimiento hacia arriba de los elementos inferiores a él para reorganizar el vector. Ejemplo 3: El algoritmo de borrado del elemento j-ésimo del vector COCHES INICIO // Se utilizará una variable auxiliar –AUX- que contendrá el valor del elemento que se desea borrar AUX = COCHES [j] PARA i DESDE i= j HASTA N-1 COCHES [i] = COCHES [i+1] // llevar elemento j+1 hacia arriba FIN_PARA // actualizar contador de elementos // ahora tendrá un elemento menos, N-1 N = N-1 FIN 4. Arreglos de varias dimensiones Se pueden definir tablas o matrices como arreglos multidimensionales, cuyos elementos se pueden referenciar por dos, tres o más subíndices. Ejemplos típicos de tablas o matrices son: - tablas de distancias kilométricas entre ciudades. - cuadros horarios de trenes o aviones. Los arreglos no unidimensionales se dividen en dos grandes grupos: - arreglos bidimensionales (2 dimensiones) - arreglos multidimensionales (3 o más dimensiones) En esta materia se tratarán arreglos de 2 dimensiones solamente. 4.1. Arreglos bidimensionales (tablas/matrices) El arreglo bidimensional se puede considerar como un vector de vectores. Es un conjunto de elementos, todos del mismo tipo, en el cual el orden de los componentes es significativo y en el que se necesita especificar dos subíndices para poder identificar cada elemento del arreglo. Ejemplo: El diagrama representa una tabla o matriz de 30 elementos (5 x 6) con 5 filas y 6 columnas. El primer subíndice se refiere a la fila y el segundo subíndice se refiere a la columna. Ej. M [2 ,3 ] se refiere al elemento de la segunda fila, tercer columna, que contiene el valor 18. Fila 1 Fila 2 18 Fila 3 Fila 4 Fila 5 Col. 1 Col. 2 Col. 3 Licenciatura en Sistemas de Información –FACENA-UNNE Col. 4 Col. 5 Col. 6 Pág. 8 Introducción a la Informática 2009 Tema 7 En notación estándar, B [i , j ] es el elemento de B que ocupa la iª (i-ésima) fila y la jª (j-ésima)columna. 1 2 3 4 . J . N 1 2 . I B[I,J] . M El elemento B [i , j ] , se puede representar en notación algorítmica, el array B con elementos del tipo T (numéricos, alfanuméricos) con subíndice fila que varían en el rango de 1 a M y subíndice columna en el rango de 1 a N es: B (1 : M, 1: N) = B [I, J] Donde I = 1, ….. , M o 1 <=I<= M Donde J = 1, ….. , N 1 <=J<= N Cada elemento B [I , J] es de tipo T. En general, el arreglo bidimensional B con su primer subíndice, variando desde un límite inferior L a un límite superior U. En notación algorítmica: B (L1 : U1, L2: U2) = B [I , J] Donde L1 <= I <==6) and (alumno.notaParcial2>=6) THEN BEGIN promedio := (alumno.notaParcial1 + alumno.notaParcial2)/2; WRITE('Promedio: ', promedio:3:2); END; WRITELN; WRITE(' para continuar ');READLN; END; END; (* cerrando archivo *) CLOSE(archivo); END. Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 13 Introducción a la Informática 2009 Tema 7 PLANIFICACION INTRODUCCION A LA INFORMATICA 2009 a) Planificación de las clases e.1.) Clases teóricas: Sem. Lunes Módulo/Tema 1 09/03/2008 Tema 1 (Conceptos Básicos) 11/03/2008 Dapozo 2 16/03/2008 Tema 2 (Rep. De información) 18/03/2008 Godoy 3 23/03/2008 Tema 2 (Rep. de información) 25/03/2008 Godoy 4 30/03/2008 Tema 2 (Rep. de información) 01/04/2008 Dapozo 5 06/04/2008 Tema 3 (Algoritmos) 08/04/2008 Dapozo 6 13/04/2008 Tema 4 (Estructura Programa) 15/04/2008 Dapozo 7 20/04/2008 Tema 5 y 6(Estructura Selectivas y Repetitivas) 22/04/2008 Dapozo 8 27/04/2008 Tema 7 (Registros y Arreglos) 29/04/2008 Godoy 9 04/05/2008 Tema 8 (Hardware) 06/05/2008 Godoy 11/05/2008 4º Turno de exámenes 10 18/05/2008 Tema 8 (Hardware) 20/05/2008 Dapozo 11 25/05/2008 (*) Entrega trabajo hardware 27/05/2008 Dapozo 12 01/06/2008 Tema 9 (Software) 03/06/2008 Dapozo 13 08/06/2008 Tema 10 (Redes e Internet) 10/06/2008 Godoy 14 15/06/2008 (**) Entrega trabajo software 17/06/2008 Dapozo 15 22/06/2008 Tema 11 (Sist. de Información) 24/06/2008 Dapozo 16 29/06/2008 Repaso relevantes 17 01/07/2009 Tercer parcial teórico 1 2 temas Miércoles sobre sobre teóricos Docente/s Dapozo (*) Feriado: 25 de mayo (**) Feriado: 20 de junio e.2.) Clases Prácticas: Clase Semana/Fecha Módulo/Tema Docente/s 1 1 (10 al 13/3) Práctico 1 A cargo del grupo 2 1 (10 al 13/03) Práctico 1 A cargo del grupo 3 2 (17 al 20/03) Práctico 2 (Sistemas numéricos) A cargo del grupo 4 2 (17 al 20/03) Práctico 2 (Sistemas numéricos) A cargo del grupo Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 14 Introducción a la Informática 2009 Tema 7 5 3 (24 al 27/03) (*) Práctico 2 (Rep. de información) A cargo del grupo 6 3 (24 al 27/03) Práctico 2 (Rep. de información) A cargo del grupo 7 4 (30/3 al 03/04) Practico 3 (Algoritmos) A cargo del grupo 8 4 (30/3 al 03/04) Practico 3 (Algoritmos) A cargo del grupo 9 5 (7 al 8/04) (**) Practico 4 (Datos y asignaciones) A cargo del grupo 10 6 (14 al 17/04) Practico 4 (Datos y asignaciones) A cargo del grupo 11 6 (14 al 17/04) Practico 5 (Estructura Selectiva) A cargo del grupo 12 7 (21 al 25/04) Practico 5 (Estructura Selectiva) A cargo del grupo 13 7 (21 al 25/04) Practico 6 (Estructura Repetitiva) A cargo del grupo 14 8 (25 (**) al 29/04 Practico 6 (Estructura Repetitiva) A cargo del grupo 15 8 (25 (**) al 29/04 Practico 6 (Estructura Repetitiva) A cargo del grupo 16 9 (4 al 8/05) Repaso para el parcial A cargo del grupo 9 (08/05/2009) Primer parcial A cargo del grupo 10 (12 al 15//05) Receso 4to turno exámenes 10 (15/05/09 Recuperatorio primer parcial A cargo del grupo 18 11 (19 al 22/05) Practico 6 (Archivos) A cargo del grupo 19 11 (19 al 22/05) Práctico 6 (Archivos) A cargo del grupo 11 (19 al 22/05) Taller de Pascal 20 12 (26 al 29/05) Práctico 7 (Arreglos y Registros) A cargo del grupo 21 12 (26 al 29/05) Práctico 7 (Arreglos y Registros) A cargo del grupo 12 (26 al 29/05) Taller de Pascal 22 13 (2 al 5/06) Práctico 8 (Ejercicios integrales) A cargo del grupo 23 13 (2 al 5/06) Práctico 8 (Ejercicios integrales) A cargo del grupo 13 (2 al 5/06) Taller de Pascal A cargo del grupo 24 14 (9 al 12/6) Práctico 8 (Ejercicios integrales) A cargo del grupo 25 14 (9 al 12/6) Práctico 8 (Ejercicios integrales) A cargo del grupo 14 (9 al 12/6) Taller de Pascal 15 (16 al 17/6) Repaso segundo parcial A cargo del grupo 15 (19/06/09) Segundo parcial A cargo del grupo 16 (23 al 24/6) Repaso Recuperatorio A cargo del grupo 26 27 Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 15 Introducción a la Informática 2009 16 (26/06/09) 28 Tema 7 Recuperatorio Segundo parcial A cargo del grupo Repaso Exámenes Extraordinarios A cargo del grupo 03/07/09 Recuperatorios Extraordinarios A cargo del grupo 07/07/2009 Entrega de notas y consultas A cargo del grupo 17 ((30/06 01/07) y (*) Feriado el martes 24 de marzo; (**) Semana Santa 8 y 9 de abril, (***) Feriado 1 de mayo b) Exámenes parciales: Actividad Fecha Primer parcial 08 de Mayo Rec. Primer Parcial 15 de Mayo Segundo parcial 19 junio Rec. Segundo Parcial 26 de junio Extraordinario 03 de julio Extraordinario Ingreso 08 de julio c) Información de contacto: introducció[email protected] d) Exámenes Finales para el presente ciclo lectivo: Normalmente los exámenes se toman en la fecha del final a las 16 hs., a los alumnos libres y regulares. Cualquier cambio de horario se publicará en el sitio de Introducción: http://exa.unne.edu.ar/depar/areas/informatica/introduccion/public_html/i ndex.html Turno Mes Fecha 4 Mayo 13/05/2009 5 Julio 08/07/2009 6 Julio 29/07/2009 7 Agosto 26/08/2009 8 Septiembre 30/09/2008 9 Noviembre 24/11/2009 10 Diciembre 16/12/2009 Licenciatura en Sistemas de Información –FACENA-UNNE Pág. 16