TRABAJO DE INVESTIGACIÓN ARREGLOS, MATRICES Y ARCHIVOS 1. ARREGLOS Y MATRICES Un array (matriz o vector) es un conjunto finito y ordenado de elementos homogéneos. La propiedad ordenado significa que el elemento primero, segundo y tercero,, enésimo de un array puede ser identificado. Los elementos del array son homogéneos, es decir, del mismo tipo de datos. Los array también se conocen como matrices−en matemáticas− y tablas− en cálculos financieros. En otras palabras un arreglo es una especie de variable que contiene muchos valores pero cada uno con una posición diferente. Un arreglo puede ser unidimensional o vectorial, bidimensional o matricial, o multidimencional. • Array Unidimensionales: Los Vectores El array unidimensional (matriz de una dimensión) es el tipo más simple. Un vector de una dimensión denominado NOTAS que consta de n elementos se puede representar así: 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. Como ejemplo de un vector o array unidimensional, se puede considerar el vector temperatura que contiene las temperaturas horarias registradas en una ciudad durante las veinticuatro horas del día. Este vector constará de veinticuatro elementos de tipo real, ya que las temperaturas normales no serán enteras siempre. El valor mínimo 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 éste ejemplo el límite inferior es 1 y el superior 24. TEMPERATURA (I) donde 1 <= I <=24 Un ejemplo en seudo lenguaje podría ser: Inicio Suma, const. Limite= 40 Tipo array [1limite] de real : puntuación var puntuación: puntos real: suma, media entero: i 1

1 el seudo código sería: inicio suma 0 escribir (`datos de array') desde i 1 hasta limite hacer leer (puntos [i]) suma suma + puntos [i] fin_desde media suma/limite escribir ( ` la media es' , media ) fin Este programa sirve para procesar un array puntos, realizando las siguientes operaciones; a) lectura del array, b) cálculo de la suma de los vectores del array, c) cálculo de la media de los valores. 1.2. Array Bidimensionales (Tablas/ Matrices) El array bidimensional se puede considerar como un vector de vectores. Por consiguiente, 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 los subíndices para identificar cada elemento del array. Si se visualiza un array unidimensional, se puede considerar como una columna de datos, un array bidimensional es un grupo de columna.

1.3. Array Multidimensionales Un array puede ser definido de res dimensiones, cuatro dimensiones, hasta de n−dimensiones. En general, un array de n− dimensiones requiere que los valores de n−índices puedan ser especificados a fin de identificar un elemento individual del array. Si cada componente de un array tiene n−índices, el array se dice que es solo de n−dimensiones. Ejemplo: Mediciones diarias de temperatura . Punto Tiempo 1 2 3 1 65.5 68.7 62.0 2

2 3 4

68.8 68.9 64.5 70.4 69.4 66.3 68.5 69.1 65.8

1.4. Ordenamientos La ordenación o clasificación es el proceso de organizar datos en algún orden o secuencia específica, tal como creciente o decreciente, para datos numéricos, o alfabéticos, para datos de caracteres. Los métodos de ordenación más directos son los que se realizan en el espacio ocupado por el array. Los más populares son: 1.4.1. Método De Intercambio O De Burbuja: Se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre si hasta que estén todos ordenados. Supongamos que se desea clasificar en orden ascendente el vector o lista, 50 15 56 14 35 1 12 9 A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] Los pasos a dar son: −Comparar A[1] y A[2] si están en orden, se mantienen como están, en caso contrario se intercambian entre si. −A continuación se comparan los elementos 2 y 3; de nuevo se intercambian si es necesario. −El proceso continua hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios. Un ejemplo en seudo código es: desde I 1 hasta 7 hacer si elemento [I]
Por ejemplo, supóngase que se tiene la lista desordenada; 5

14

24

39

43

65

84

45

Para insertar el elemento 45, habrá que insertar entre 43 y 65, lo que supone desplazar a la derecha todos aquellos números de valor superior a 45, es decir, saltar sobre 65 y 84. 5

14

24

39

43

65

84

45

El método se basa en comparaciones y desplazamientos sucesivos. El algoritmo de clasificaciones de un vector X para N elementos se realiza con un recorrido de todo el vector y la inserción del elemento correspondiente en el lugar adecuado. El recorrido se realeza desde el segundo elemento al n−ésimo. desde i 2 hasta N hacer insertar X[ i ] en el lugar adecuado entre x [ 1 ] . . x [ i − 1 ] fin_desde Esta acción repetitiva − insertar− se realiza más fácilmente con la inclusión de un valor centinela o bandera. (SW). Seudocódigo: algoritmo Clas_insercion1 //declaraciones inicio ... //ordenación desde I 2 hasta N hacer AUXI X [ I ] KI−1 SW falso mientras no (SW) y (k >= 1) hacer si AUXI < X [ ] entonces X[K+1]X[K] KK−1

4

si_no SW verdad fin_si fin_mientras X [ K + 1 ] AUXI fin_desde fin 1.4.3. Ordenación Por Selección Este método se basa en buscar el elemento menor del vector y colocarlo en primera posición. Luego se busca el segundo elemento más pequeño y se coloca en la segunda posición, y así sucesivamente. Los pasos sucesivos a dar son: • Seleccionar el electo menor del vector de n elementos. • Intercambiar dicho elemento con el primero. • Repetir estas operaciones con los n − 1 elementos restantes, seleccionando el segundo elemento; continuar con los n − 2 elementos restantes hasta que solo quede el mayor. Para la comprensión del método usaremos un ejemplo: El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e']. Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'. Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e']. El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'. El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r']. De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo. El número de comparaciones que realiza este algoritmo es : Para el primer elemento se comparan n−1 datos, en general para el elemento i−ésimo se hacen n−i comparaciones, por lo tanto, el total de comparaciones es: la sumatoria para i de 1 a n−1 (n−i) = 1/2 n (n−1). Seudo código: Inicio 5

desde I 1 hasta n − 1 hacer buscar elemento menor de X [ I], X [ I + 1 ], . . . , X [N ] e intercambiar con X [ I ] fin_desde fin. 1.4.4. Método De Shell Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. Nombrado así debido a su inventor Donald Shell. Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento. Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1."Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos." Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa. El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1. Un ejemplo de su algoritmo es: const MAXINC = _____; incrementos = array[1..MAXINC] of integer; var j,p,num,incre,k:integer; begin for incre := 1 to MAXINC do begin /* para cada uno de los incrementos */ k := inc[incre]; /* k recibe un tipo de incremento */ for p := k+1 to MAXREG do begin /* inserción directa para el grupo que se encuentra cada K posiciones */ num := reg[p]; 6

j := p−k; while (j>0) AND (num < reg[j]) begin reg[j+k] := reg[j]; j := j − k; end; reg[j+k] := num; end end end; Ejemplo: Para el arreglo a = [6, 1, 5, 2, 3, 4, 0] Tenemos el siguiente recorrido: Recorrido 1 2 3 4 5

Salto 3 3 3 1 1

Lista Ordenada 2,1,4,0,3,5,6 0,1,4,2,3,5,6 0,1,4,2,3,5,6 0,1,2,3,4,5,6 0,1,2,3,4,5,6

Intercambio (6,2), (5,4), (6,0) (2,0) Ninguno (4,2), (4,3) Ninguno

1.4.5. Ordenación Rápida (Quicksort) El método de ordenación rápida sirve para ordenar o clasificar un vector o lista de elementos (array). Desarrollada por C.A.R. Hoare en 1960, se basa en el hecho de que es más rápido y fácil ordenar dos listas pequeñas que una lista grande. Se denomina así, ya que en general, puede ordenar una lista de datos mucho más rápidamente que cualquiera de los métodos de ordenación anteriores. El algoritmo fundamental es el siguiente: • Eliges un elemento de la lista. Puede ser cualquiera, lo llamaremos elemento de división. • Buscas la posición que le corresponde en la lista ordenada (explicado más abajo). • Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre). • Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados. • Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos 7

elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste: • Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento). • Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias. • Repites esto hasta que se crucen los índices. • El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados). Al finalizar este procedimiento el elemento de división queda en una posición en que todos los elementos a su izquierda son menores que él, y los que están a su derecha son mayores. Un seudo código en C sería: Tabla de variables Nombre Tipo lista Cualquiera inf Entero sup Entero El mismo que los elementos de la elem_div lista El mismo que los elementos de la temp lista i Entero j Entero cont

Entero

Uso Lista a ordenar Elemento inferior de la lista Elemento superior de la lista El elemento divisor Para realizar los intercambios Contador por la izquierda Contador por la derecha El ciclo continua mientras cont tenga el valor 1

Nombre Procedimiento: OrdRap Parámetros: lista a ordenar (lista) índice inferior (inf) índice superior (sup) // Inicialización de variables 1. elem_div = lista[sup]; 2. i = inf − 1; 3. j = sup; 4. cont = 1; 8

// Verificamos que no se crucen los límites 5. if (inf >= sup) 6. retornar; // Clasificamos la sublista 7. while (cont) 8. while (lista[++i] < elem_div); 9. while (lista[−−j] > elem_div); 10. if (i < j) 11. temp = lista[i]; 12. lista[i] = lista[j]; 13. lista[j] = temp; 14. else 15. cont = 0; // Copiamos el elemento de división // en su posición final 16. temp = lista[i]; 17. lista[i] = lista[sup]; 18. lista[sup] = temp; // Aplicamos el procedimiento // recursivamente a cada sublista 19. OrdRap (lista, inf, i − 1); 20. OrdRap (lista, i + 1, sup); 2. ARCHIVOS Los archivos también denominados ficheros (file); es una colección de información (datos relacionados entre sí), localizada o almacenada como una unidad en alguna parte de la computadora. Los archivos son el conjunto organizado de informaciones del mismo tipo, que pueden utilizarse en un mismo tratamiento; como soporte material de estas informaciones.

9

Las principales características de esta estructura son: independencia de las informaciones respecto de los programas, la información almacenada es permanente, un archivo puede ser accedido por distintos programas en distintos momentos, gran capacidad de almacenamiento. 2.1. Tipos De Archivos Los elementos de un archivo pueden ser de cualquier tipo, simples o estructurados o según su función. 2.1.1 Según Su Función Se define por: 2.1.1.1 Archivos Permanentes: Son aquellos cuyos registros sufren pocas o ninguna variación a lo largo del tiempo, se dividen en: a. Constantes: Están formados por registros que contienen campos fijos y campos de baja frecuencia de variación en el tiempo. b. De Situación: Son los que en cada momento contienen información actualizada. Históricos: Contienen información acumulada a lo largo del tiempo de archivos que han sufridos procesos de actualización o bien acumulan datos de variación periódica en el tiempo. 2.1.1.2. Archivos de Movimiento: Son aquellos que se utilizan conjuntamente con los maestros (constantes), y contienen algún campo común en sus registros con aquellos, para el procesamiento de las modificaciones experimentados por los mismos. 2.1.1.3. Archivo de Maniobra o Transitorio: Son los archivos creados auxiliares creados durante la ejecución del programa y borrados habitualmente al terminar el mismo.

2.1.2. Según Sus Elementos Los principales archivos de este tipo son: 2.1.2.1. Archivo de Entrada: Una colección de datos localizados en un dispositivo de entrada. 2.1.2.2. Archivo de Salida: Una colección de información visualizada por la computadora. 2.1.2.3. Archivo de Programa: Un programa codificado en un lenguaje especifico y localizado o almacenado en un dispositivo de almacenamiento. 2.1.2.4. Archivo de Texto: Una colección de caracteres almacenados como una unidad en un dispositivo de almacenamiento. 2.2. Operaciones Generales Que Se Realizan Sobre Un Archivo Las operaciones generales que se realizan son: 2.2.1. Creación: Escritura de todos sus registros.

10

Operación de clasificación por número de empleado 2.2.2. Consulta: Lectura de todos sus registros. 2.2.3. Actualización: Inserción supresión o modificación de algunos de sus registros. 2.2.4. Clasificación: Reubicación de los registros de tal forma que queden ordenados según determinados criterios. 2.2.5. Borrado: Eliminando total del archivo, dejando libre el espacio del soporte que ocupaba.

Un ejemplo de seudo código en archivo sería: Ejemplo: La declaración de un archivo con tipo se efectúa con la ayuda de las palabras reservadas file of. Type datos = record clave : integer; nombre : string[30]; puesto : string[20]; sueldo : real; estado : boolean; {true activo,false baja lógica} end; Var archivo:file of datos; begin Assign(archivo,'empleado.dat'); 3. registros Son estructura de datos formada por uno o más elementos denominados "Campos" y estos pueden estar compuestos a su vez por "subcampos". Puede definirse también como una colección de información, normalmente relativa a una entidad particular. Un ejemplo de registro puede ser la información de un 11

determinado empleado, que contiene los campos de nombre, dirección, fecha de nacimiento, estudios, salarios, etc. N N = Longitud de registro 3.1. Tipos De Registros Los archivos se encuentran organizados lógicamente como una secuencia de registros de varias longitudes diferentes. Entre ellas tenemos: 3.1.1. Registros De Longitud Fija: son los que almacenan la información en los archivos mediante un encabezado y luego se introducen uno a uno los registros ubicados en posiciones consecutivas. 3.1.2. Registros De Longitud Variable: es el almacenamiento de registros de varios tipos en un archivo y permite uno o más campos de longitudes variables y dichos campos pueden ser repetidos. La longitud de los registros debe estar definida correctamente para poder leer y escribir de forma efectiva. 3.2. Estructura De Registro Una estructura de registro en una computadora es diseñada para obtener datos. Los datos están organizados de tal modo que pueden ser recuperados fácilmente, actualizados o borrados y almacenados de nuevo en el archivo con todos los cambios realizados. La siguiente figura recoge la estructura de un registro correspondiente a un usuario de una revista de informática: Registro 1 Registro 2 Registro 3 Registro 4 CONCLUSIÓN: En conclusión se puede decir que los arreglos pueden variar dependiendo sus dimensiones. Con respecto a los archivos no se requieren de un tamaño predeterminado; esto significa que se pueden hacer archivos de datos más grandes o pequeños, según se necesiten. Las aplicaciones pueden ser infinitas, ya que son utilizados en diferentes rutinas diarias, como por ejemplo, acceder a nuestro expediente en la universidad, para consultar el estado de cuenta bancario, etc. La elección del método de ordenamiento esta directamente relacionada con la estructura de los registros del archivo y del soporte utilizado. Un programa puede acceder directamente cualquier registro sin tener que leer los registros previos. REFERENCIAS O BIBLIOGRAFÍAS: JOYANES, Luis Fundamentos de Programación Editorial Lavel, 1996. España

12

P.p.205−321. PRIETO, Alberto Introducción a la Informática Editorial Mc. Grauhill.1999. España P.p.444−445. http://webdia.cem.itesm.mx/ac/rtrejo/CompuII/S32.html http://c.conclase.net/orden/quicksort.html UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA PARTAMENTO DE ING. ELECTRICA CATEDRA: COMPUTACIÓN II DATOS Fila 1 Fila 2 Fila 3 Fila 4 Fila 5 Columna 6 Columna 5 Columna 4 Columna 3 Columna 2 Columna 1 CREACIÓN de un archivo en disco Maestro

13

ordenado MAESTRO (desordenado) Número de empleado Proceso de consulta Proceso de actualización Clasificación Clasificación Copia Proceso de reorganización Registro de datos Nombre Profesión Dirección Teléfono Ciudad

14