ARREGLOS

ARREGLOS

Las variables que hemos utilizado hasta ahora nos permiten el almacenamiento de un solo valor a la vez.

Para resolver cierto tipo de problemas con datos múltiples en forma eficiente, se requiere almacenamiento en conjunto. A esta organización de elementos se le conoce con el nombre de arreglo.

Otra definición de arreglo más completa (Luis Joyanes A.), es un conjunto finito y ordenado de elementos homogéneos. La propiedad "ordenado" significa que el elemento primero, segundo, tercero…n-ésimo de un arreglo puede ser identificado. Los elementos de una arreglo deberán ser homogéneos, es decir, del mismo tipo de datos. Por ejemplo un arreglo puede estar compuesto de todos sus elementos de tipo cadena, otro puede tener sus elementos de tipo entero, etc.

Al tratar el tema de arreglos es necesario conocer el término de dimensión.

Dimensión
Descripción
0
Un solo punto.
1
(vector o lista) Una recta. Contiene largo.
2
(matriz o tabla) Contiene largo y ancho.
3
(cubo) Tiene largo, ancho y fondo.

Declaración de un Arreglo

Nom_variable : Arreglo [dimensión] de Nom_tipo

Ø En donde dimensión especifica :

…

En el orden : Fila, Columna, Fondo.

Ø Ejemplo de una declaración :

0 Dimensión :

x 20 donde x, es de tipo Entero.

1 Dimensión:


5



1 2 3 4
x[2] 5
x : arreglo [1..4] de Enteros.

2 Dimensiones:

1 2 3 4







8









x[2,4] 8
x : arreglo [1..3, 1..4] de Enteros.

3 Dimensiones:

x[1,4,2] 3
x : arreglo[1..3, 1..4, 1..2] de Enteros.

Las operaciones que se pueden realizar con arreglos 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

VECTORES

Son aquéllos de una sola dimensión, por lo que también son llamados arreglos Unidimensionales.

Ejemplo:

Un vector de una dimensión llamado CALIF, que consta de n elementos.

calif(1)
calif(2)
…
calif(n-2)
calif(n-1)
calif(n)

El subíndice o índice de un elemento (1, 2 …n) designa su posición en la ordenación del vector. Otras posibles notaciones del vector son:

a1, a2,…,an En matemáticas y algunos lenguajes(BASIC)

A(1), A(2),…A(n)

A[1], A[2],…A[n] En programación (Pascal)

Los vectores se almacenan en memoria central de la computadora en un orden adyacente. Así, un vector de 50 elementos denominado NUMEROS se representa gráficamente por 50 posiciones de memoria sucesivas.

Memoria

NUMEROS(1) Dirección x
NUMEROS(2) Dirección x+1
NUMEROS(3) Dirección x+2
:
:
NUMEROS(50) 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) 75 (almacena el valor 75 en la posición 25a del vector
NUMEROS y la instrucción de salida : escribir
NUMEROS(25).

Declaración

nom _arreglo = arreglo[liminf..limsup] de tipo

donde:

nom_arreglo: nombre válido del arreglo.
liminf..limsup: límites inferior y superior del rango del arreglo.
tipo: tipo de datos de los elementos del arreglo : entero, real, carácter.

NOMBRES= arreglo [1..10] de carácter

Significa que NOMBRES es un arreglo (array) unidimensional de 10 elementos (1 a 10) de tipo carácter.

Asignación

NOMBRES(8) ‘Ana’

Asigna el valor ‘Ana’ al elemento 8 del vector NOMBRES

Lectura/Escritura de Datos

La Lectura/Escritura de datos en un arreglo u operaciones de entrada/salida normalmente se realizan con estructuras repetitivas, aunque puede también hacerse con estructuras selectivas. Las instrucciones simples de lectura/escritura se representarán como:
leer A Lectura del vector A
escribir A Escritura del vector A
leer V(5) Leer el elemento V(5) del vector V

Acceso Secuencial al Vector (recorrido)

Se puede acceder a los elementos de un vector para introducir datos (escribir) en el o bien para visualizar su contenido (leer). Estas operaciones se realizan utilizando estructuras repetitivas, cuyas variables de control (por ejemplo I) se utilizan como subíndices del vector (por ejemplo, X(I). El incremento del contador del bucle producirá el tratamiento sucesivo de los elementos del vector.

Ejemplo:

Lectura de 15 valores enteros de un vector denominado TOTAL.

TOTAL= array [1..15] de entero
desde i1 hasta 15 hacer
leer TOTAL(i)
fin _desde

Si se cambian el límite inferior y superior, por ejemplo, 5 y 12, el bucle de lectura sería:

desde i 5 hasta 12 hacer
leer TOTAL(i)
fin_desde

La salida o escritura de vectores se representa de un modo similar.

desde i1 hasta 15 hacer
escribir TOTAL(i)
fin_desde

Visualiza todo el vector completo (un elemento en cada línea independiente).

Actualización de un Vector

Puede constar de tres operaciones más elementales:

a) Añadir elementos (añade un nuevo elemento al final del vector)

Un arreglo A se ha dimensionado a 6 elementos, pero solo se han asignado 4 valores a los elementos A(1), A(2), A(3), A(4), se podrán añadir dos elementos más con una simple acción de asignación.

A(5) 15
A(6) 9

b) Insertar elementos (introduce un elemento en el interior de un vector)

Ejemplo: Se tiene un arreglo NOM de 6 elementos de nombres de personas, en orden alfabético y se desea insertar un nuevo nombre.

{Calcular la posición ocupada por el elemento a insertar} P
{Inicializar contador de inserciones} i n.
mientras i >= P hacer
{transferir el elemento actual hacia abajo, a la posición i+1}
NOM(i+1) NOM(i)
{decrementar contador}
i i-1
fin_mientras

{Insertar el elemento en la posición P}
NOM(P) ‘nuevo elemento’
{Actualizar el contador de elementos del vector}
n n+1
fin

c) Borrar elementos (Elimina elementos de un vector)

Algoritmo de Borrado

Inicio
{se utilizará una variable auxiliar AUX, que contendrá el valor del elemento que se desea borrar}
AUX NOM(i)
desde ij hasta N-1 hacer
{llevar elemento j+1 hacia arriba}
NOM(i) NOM(i+1)
fin_desde
{actualizar contador de elementos}
{ahora tendrá un elemento menos, N-1}
N N-1
Fin

Referencia a un elemento de Arreglo
variable de arreglo [subíndice]

Ejemplo:

x x[3]9
escribir (x[2])

?
9
1 2 3

Ejercicio:

Se desea la lectura y desplegado de 5 nombres. Resuelva el problema por cada uno de los siguientes criterios:

a) Lectura y desplegado alternados.
b) Todas las lecturas, todos los desplegados.

a) variables:

string : nom
entero : x

Inicio
Para x1 hasta 5 hacer
escribir(‘Nombre ? ‘)
leer(nom)
escribir( ‘La persona número’, x, ‘ se llama : ‘,nom)
Fin

Nota: No se utilizaron arreglos porque no se requería de almacenamiento múltiple.

b) variables :

nom : Arreglo[1..5] de string
x : Entero

Inicio
para x 1 hasta 5 hacer
escribir(‘Dame el nombre número’,x,’ ?’)
leer(nom[x])
para x 1 hasta 5 hacer
escribir(‘La persona número ‘, x,’ se llama : ‘,nom[x])
Fin

Ordenación de Arreglos

Existen diversos métodos para ordenar los elementos de un arreglo. El más conocido de ellos (no el mejor) es el Método de la Burbuja.

El método consiste en hacer un recorrido por el arreglo comparando parejas de elementos; si estos no están en el orden deseado, se procede a intercambiarlos.

Al finalizar el recorrido se verifica la cantidad de intercambios, si esta es 0 se asume que el arreglo está ordenado ; en caso contrario se inicia nuevamente el recorrido.

Las parejas de elementos que se comparan deben ser contiguos (elemento1 y elemento2, elemento2 y elemento3, etc). El número total de comparaciones es n-1 (donde n es la cantidad de elementos).

Ejemplo:

Se requiere la ordenación de una lista con 5 valores enteros previamente introducidos.

Variables:

LISTA : arreglo[1..5] de entero
x, aux : entero
cambio : boleano

Inicio
Para x 1 hasta 5 hacer
escribir(‘Dame el valor’,x,’ :’)
leer( LISTA[x])
repetir
cambio falso
para x 1 hasta 4 hacer
si LISTA[x] > LISTA[x+1] entonces
aux LISTA[x]
LISTA[x] LISTA[x+1]
LISTA[x+1] aux
cambio verdadero
fin_si_entonces
hasta cambio = falso
escribir(‘Lista ordenada’)
para x 1 hasta 5 hacer
escribir(‘Elemento número’,x,’ es’,LISTA[x])
Fin