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 [1…limite] de real : puntuación

var

puntuación: puntos

real: suma, media

entero: i

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	68.8	68.9	64.5
3	70.4	69.4	66.3
4	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] <elemento [I + 1] entonces

intercambiar (elemento [I] , elemento [I + 1]

fin_si

fin_desde

1.4.2. Ordenamiento Por Inserción

Consiste en insertar un elemento en el vector en una parte ya ordenada de este vector y comenzar de nuevo con los elementos restantes. Por ser utilizado generalmente por los jugadores de cartas se le conoce también por el método de la baraja.

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 ]

K I - 1

SW falso

mientras no (SW) y (k >= 1) hacer

si AUXI < X [ ] entonces

X [ K + 1 ] X [ K ]

K K - 1

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

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];

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	Salto	Lista Ordenada	Intercambio
1	3	2,1,4,0,3,5,6	(6,2), (5,4), (6,0)
2	3	0,1,4,2,3,5,6	(2,0)
3	3	0,1,4,2,3,5,6	Ninguno
4	1	0,1,2,3,4,5,6	(4,2), (4,3)
5	1	0,1,2,3,4,5,6	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 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	Uso
lista	Cualquiera	Lista a ordenar
inf	Entero	Elemento inferior de la lista
sup	Entero	Elemento superior de la lista
elem_div	El mismo que los elementos de la lista	El elemento divisor
temp	El mismo que los elementos de la lista	Para realizar los intercambios
i	Entero	Contador por la izquierda
j	Entero	Contador por la derecha
cont	Entero	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;

// 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.

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.

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 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

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

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