Estructura de Datos Arreglos

Unidad 5:

*Conocer las estructuras de datos

*Trabajar con arreglos unidimensionales o vectores.

*Realizar operaciones con arreglos unidimensionales o vectores.

*Trabajar con arreglos bidimensionales o matrices

*Conocer los arreglos multidimensionales.

*Entender el almacenamiento e arreglos en memoria.

Arreglos Unidimensionales:

Un arreglo unidimensional o vector, es un conjunto finito, consecutivo  y organizado de elementos homogéneos, es decir, elementos pertenecientes en un mismo tipo de dato.

*Finito: El arreglo tiene un número determinado de elementos.

*Homogéneo: Todos los elementos del arreglo son del mismo tipo.

*Organizado: Existe una forma de referenciar cada elemento del arreglo y de acceder a cada uno de sus elementos de manera independiente.

*Consecutivo: Por la parte en que e almacena o representa un vector en la memoria del computador, en posiciones consecutivas de la memoria.

Para referenciar cada elemento de un arreglo se usa el índice, que es un valor que directa o indirectamente referencia la posición del elemento dentro del arreglo.

Los índices deben ser de cualquier tipo de datos escalar, porque en un escalar se puede definir un orden y entre dos elementos consecutivos no puede haber infinitos elementos. Un ejemplo de datos escalares son los enteros y caracteres. Normalmente, como índices se van a utilizar números enteros.

Par referenciar un elemento de un arreglo se usa el nombre del arreglo y entre corchetes ([]) el índice que determina la posición de ese elementos en el arreglo.

El rango o longitud de un vector o arreglo lineal es la diferencia entre el índice de valor máximo en el arreglo y el índice de valor mínimo +1. Normalmente, los índices comienzan a enumerarse desde 0 o 1 , como el valor mínimo del índice. Dependiendo del lenguaje de programación.

Los arreglos se almacenan siempre en posiciones consecutivas de memoria y se puede acceder a cada elemento del arreglo de manera independiente, a través de los índices. Un índice no tiene porqué ser un valor constante, puede ser también una variable o una expresión que al ser evaluada devuelva un valor escalar que se encuentre entre índice menor y el índice mayor del arreglo o ambos inclusive.

Definición de un Arreglo o Vector:

Para definir un arreglo, se da el nombre del arreglo, el rango de sus índices y el tipo de los datos que contiene, Esto es:

<nom_arreglo>: arreglo [rango] de <tipo>

Ejemplo:

sueldo: arreglo[8] de real

i:entero

i=2

sueldo[i]=23.5

Operaciones con Vectores:

Se usa la declaración del vector

Ventas: arreglo [12] entero

Gráficamente se representa:

1

2

3

4

5

6

7

8

9

10

11

12

 

Asignar datos a una posición del arreglo dada por un índice. La sintaxis de esta operación es:

<nom_arreglo> [indice] = valor

Ejemplo: asignar el valor de 105 a la posición 5 del vector:

ventas[5] = 105

Lectura y escritura de datos:

Consiste en usar una posición cualquiera del arreglo definida por un indice para operaciones de entrada y salida.

La sintaxis para estas operaciones es:

Leer<nom_arreglo> [indice]

Escribir <nom_arreglo> [ indice]

Ejemplo:

Desde i =1 hasta 12

Escribir “Introduzca las ventas del mes” i

Leer ventas [i]

Fin desde

Desde i = 1 hasta 12

Escribir “ventas del mes” i “=” ventas [i]

Fin desde

Recorrido o Acceso secuencial de un arreglo:

Consiste en pasar todas las posiciones del arreglo para procesar su información usualmente, se usa el ciclo “Desde”  para recorrer el vector.

La sintaxis de esta operación es:

Desde indice =1 Hasta Rango Arreglo

<Acciones con el arreglo>

Fin Desde

Ejemplo: Sumar 300 a las ventas de cada mes.

Desde i=1 Hasta 12

Ventas [i] =Ventas [i] +300

Fin Desde

 

Actualización de un Arreglo:

Añadir Datos: Es un caso especial de una operación de inserción de un elemento de un arreglo, donde el elemento nuevo se agrega después de la última posición que contiene información valida en el arreglo. Para  hacer esta operación es necesario si el arreglo actualmente tiene k posiciones de información valida, tenga un tamaño de al menos k+1 para que se pueda añadir otro elemento a continuación del elemento en la posición k.

Sintaxis:

<nom_arreglo> [k+1]=valor

 Insertar Datos:

Consiste en introducir un elemento a una posición del interior del arreglo, para lo cual será necesario desplazar una posición a la derecha a todos los elementos que estén a la derecha de donde se va a insertar el elemento, esto con el fin de conservar el orden relativo entre los elementos.

Para que se pueda insertar un nuevo elemento en el arreglo si ya existen n elementos con información en el arreglo, el arreglo tendrá que tener un tamaño de al menos n+1para poder insertar el nuevo elemento.

c

r

h

j

n

o

 

Al insertar g en la cuarta posición queda:

c

r

h

g

j

n

o

 

Si k es la posición donde se va a insertar el nuevo elemento, n es el número de elementos validos en el arreglo en el momento de la inserción y suponiendo un tamaño mínimo de n+1 , el algoritmo de inserción es:

Desde i=n  hasta k con decremento 1

A [i+1] = A [i]

Fin Desde

A[k] = valor

 

Ejemplo: Insertar 300 correspondiente a las ventas del mes 5.

Desde i= 11 hasta 5 con decremento 1

Ventas [ i + 1 ]= ventas [i]

Fin Desde

Ventas [5]=300

 Eliminar Datos:

Para eliminar un elemento de un arreglo, si ese elemento está posicionado al final del arreglo, no hay ningún problema, simplemente si el tamaño del arreglo era n , ahora hay que considerar que el tamaño del arreglo es n-1.

Si el elemento a eliminar ocupa cualquier otra posición entonces se tendrá que desplazar una posición a la izquierda, todos los elementos situados a la derecha del elemento a borrar, para que el arreglo quede organizado.

c

e

f

k

m

p

Al borrar el elemento k queda

c

e

f

m

p

 

Suponiendo que el número de elementos validos actualmente es “n” y que se desea borrar el elemento de la posición k.

Desde i = k hasta n-1

A [i] = A [i+1]

Fin Desde

Ejemplo: Eliminar ventas registradas en el mes 4 y desplazar las de los mese subsiguientes hacia la izquierda.

Desde i=4 Hasta 11

Ventas[i]= ventas [i+1]

Fin Desde

El número de los elementos validos  n es ahora n=n-1

 

 Arreglos Bidimensionales:

En un arreglo unidimensional o vector cada elemento es referenciado por un indice, en un arreglo bidimensional cada elemento se va a referenciar por dos índices.

La representación lógica de un arreglo bidimensional es una matriz de dimensiones M XN don M es el número de filas de la matriz y N es el número de columnas, es decir la primera dimensión indica las filas y la 2 dimensión indica las columnas. Al acceder a un elemento que ocupa la fila I ,J  se está accediendo al elemento que ocupa la fila i y la columna j.

Un arreglo bidimensional  de M x N  elementos es un conjunto de M x N elementos, todos del mismo  tipo, cada uno de los cuales es referenciado a través de 2 subíndices. El primer subíndice varía entre 1 y M 0 entre  0 hasta M-1 , dependiendo desde donde comience el indice .El segundo indice varía entre 1 y N o entre 0 y N-1.

En general se puede definir un arreglo de 2 dimensiones de la siguiente manera:

<nombre_arreglo>: arreglo [rango-filas, rango-columnas] <tipo de dato>

Ejemplo: Representación de una matriz de las ventas mensuales de 5 años.

Ventas: arreglo [5,12] real

El tamaño resulta de la multiplicación de su rango de filas por su rango de columnas:

Tamaño n x m = 5x12 = 60

En memoria sin embargo todos los elementos del arreglo se almacenan en posiciones continuas.

Matriz de ventas 5x12, total de 60 elementos.

	1	2	3	4	5	6	7	8	9	10	11	12
1
2
3
4		120
5

 

Ventas [4,2] =120

En memoria se almacenan los elementos de forma consecutiva:

1,1

1,2

1,3

1,4

1,5

1,6

1,7

1,8

1,9

 

 

Manejo de Matrices:

Colocar el valor de cero a todos los elementos de una matriz

Esta es una operación útil cuando se desea inicializar todos los elementos de la matriz a un valor dado, usualmente ese valor es cero, aunque bien podría ser cualquier otro valor valido.

Sintaxis:

M : arreglo [m,n] entero

Var i ,j : entero

Desde i =1 hasta m

Desde j=1 hasta n

M [ i, j]=0

Fin Desde

Fin Desde

Ejemplo: Inicializar la matriz de ventas mensuales para 5 años

Ventas: arreglo [5,12] entero

Var i, j: entero

     Desde i =1 hasta 5

           Desde j=1 hasta 12

              Ventas [i, j]=0

            Fin Desde

    Fin Desde

Colocar el valor de cero a todos los elementos de una fila dada

En este caso se mantiene fija la fila y se recorren las columnas asignándoles un valor suministrado , usualmente ese valor es cero.

Sintaxis:

M: arreglo [m,n] entero

Var i , j : entero

I=fila

Desde j=1 Hasta n

     M [i , j] = 0

Fin Desde

 

Ejemplo: Inicializar ventas mensuales del año 3.

Ventas: arreglo [5 ,12] entero

Var i , j : entero

i=3

Desde j=1 Hasta 12

M [i ,j] =0

Fin Desde

En este caso se le asignó el valor de cero a los elemento de la tercera fila de la matriz ventas.

 

Arreglo Multidimensionales:

Un arreglo multidimensional es una matriz de 3 o más dimensiones .Si se tiene un arreglo de N dimensiones, donde cada dimensiones de tamaño  d1,d2,dn…..el número del arreglo será d1x,d2x,xdn.

Para acceder  los elementos de una arreglo se utilizan n índices, cada uno de los cuales referencia a una posición dentro de una dimensión siempre según el orden de la declaración.

En memoria, el arreglo se sigue almacenando en posiciones consecutivas

La declaración de un arreglo multidimensional será:

Nom_arreglo : arreglo[rango 1,rango 2 …..rango n] tipo

Ejemplo: Definir una matriz de ventas mensuales de 5 años para 3 vendedores y asignar a las ventas del mes 10 del cuarto año para el vendedor 2 la cantidad de 1000.5

Ventas: arreglo [3, 5, 12] real

Ventas [2, 4, 10] =1000.5

Almacenamiento de arreglo en Memoria:

Un arreglo en memoria siempre se almacena en posiciones continuas a partir de la dirección base de comienzo del arreglo, la cual se asigna cuando se declara una variable del tipo arreglo.

El tamaño que ocupa el arreglo en memoria es el producto del producto de sus elementos

Ventas: arreglo [5,12] real

Tamaño n x m = 5x12 = 60

 

En el caso de un arreglo multidimensional, también se almacena en posiciones continuas de memoria. Su tamaño será el producto de sus elementos por el tamaño requerido para representar cada elemento en memoria.

Ejemplo:

 

Arreglo [3, 5, 12] enteros

Si se asume que cada entero necesita 2 byte para ser almacenados y se tiene un total de 3x5x12=180 elementos , entonces 180x2=360 bytes de memoria.

2 bytes x (3x5x12) elementos=360 bytes