ARREGlOS EN INFORMATICA

ARREGlOS EN INFORMATICA

Un arreglo puede definirse como un grupo o una colección finita, homogénea y ordenada de elementos. Los arreglos pueden ser de los siguientes tipos:

• De una dimensión.
• De dos dimensiones.
• De tres o más dimensiones.

Tipos de arreglos

• Arreglos unidimensionales.
• Arreglos multidimensionales.
• Arreglo con múltiple subíndices.

Arreglos unidimensionales

Es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales. Están formados por un conjunto de elementos de un mismo tipo de datos que se almacenan bajo un mismo nombre, y se diferencian por la posición que tiene cada elemento dentro del arreglo de datos. Al declarar un arreglo, se debe inicializar sus elementos antes de utilizarlos. Para declarar un arreglo tiene que indicar su tipo, un nombre único y la cantidad de elementos que va a contener.

Arreglos multidimensionales

Es un tipo de dato estructurado, que está compuesto por dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión. El término dimensión representa el número de índices utilizados para referirse a un elemento particular en el arreglo. Los arreglos de más de una dimensión se llaman arreglos multidimensionales.

Arreglos con múltiple subíndices

Es la representación de tablas de valores, consistiendo de información arreglada en renglones y columnas. Para identificar un elemento particular de la tabla, deberemos de especificar dos subíndices; el primero identifica el renglón del elemento y el segundo identifica la columna del elemento. A los arreglos que requieren dos subíndices para identificar un elemento en particular se conocen como arreglo de doble subíndice. Note que los arreglos de múltiples subíndices pueden tener más de dos subíndices. El estándar ANSI indica que un sistema ANSI C debe soportar por lo menos 12 subíndices de arreglo.

Operaciones con arreglos

Las operaciones en arreglos pueden clasificarse de la siguiente forma:

• Lectura: este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes
• Escritura: Consiste en asignarle un valor a cada elemento del arreglo.
• Asignación: No es posible asignar directamente un valor a todo el arreglo
• Actualización: Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.
• Ordenación.
• Búsqueda.
• Insertar.
• Borrar.
• Modificar.

Ordenaciones en Arreglos

La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener acceso a un dato en un arreglo ordenado que en uno desordenado.

Existen muchos algoritmos para la ordenación de elementos en arreglos, algunos de ellos son:

Selección directa

Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y así excluirlo de la lista. Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.

Ordenación por burbuja

Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es importante señalar que es el más ineficiente de todos los métodos. Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.

Ordenación por mezcla

Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el siguiente hueco.

Algoritmos de búsqueda que existen

• Búsquedas en Arreglos: Una búsqueda es el proceso mediante el cual podemos localizar un elemento con un valor especifico dentro de un conjunto de datos. Terminamos con éxito la búsqueda cuando el elemento es encontrado.

• Búsqueda secuencial: A este método también se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir a través de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo. Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.

• Búsqueda binaria: Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos. Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor. La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.

• Búsqueda por hash: La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.

EJEMPLO DE ALGORITMO CON ARRREGLOS

Estructuras de datos

Hasta ahora se han usado datos que representan valores de tipo simple como un número entero, real ó carácter.

Sin embargo, en muchas situaciones se necesita procesar un conjunto de valores que están relacionados entre sí por algún método, por ejemplo, una lista de calificaciones, una serie de temperaturas.

En este caso, el procesamiento con datos simples se hace muy difícil, por lo que la mayoría de los lenguajes de programación incluyen características deestructuras de datos

En computación, una estructura de datos es una manera de almacenar información (datos) en un computador de manera que puedan ser usados de una manera eficiente. Una selección cuidadosa de la estructura permitirá usar un algoritmo más eficiente. Una estructura bien diseñada permitirá efectuar una variedad de operaciones, usando un mínimo de tiempo de ejecución y espacio de memoria.

Los tipos de datos mas utilizados son:

Datos SIMPLES			Entero Real Carácter Lógico
Datos ESTRUCTURADOS			Arreglos Registros Archivos

Las estructuras de datos estáticas son aquellas en las que 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.

Las estructuras dinámicas pueden ser definidas en tiempo de ejecución y la limitación seria el tamaño de la memoria disponible.

1.1. Arreglos Unidimensionales - NDimensionales.

Un arreglo es una secuencia de posiciones consecutivas de memoria que almacenan datos del mismo tipo.Estos datos comparten un nombre común.

En cuanto a su dimensión ,los arreglos se pueden clasificar como :

Unidimensionales:

Vector, lista, matriz de una dimensión.

Ej : Un vector denominado ventas, de 10 elementos, se puede representar como :

ventas[1]

ventas[2]

ventas[3]

………

ventas[10]

El subíndice de cada elemento designa su posición en la ordenación del vector. Se observa que todos los elementos comparten el nombre y que cada elemento se referencia por su subíndice o sea su posición relativa en el vector.

Declaración de un arreglo Unidimensional :

Estático :

tipo nombre [dimensión]

Ej : la instrucción entero x[8] declara un arreglo de nombre x, de 8 elementos de tipo entero.

Bidimensionales (Tabla, Matriz ) :

Se pueden considerar como un vector de vectores. En este caso se necesita especificar dos subíndices para identificar cada elemento del arreglo : El primer subíndice se refiere a las filas ( i ) y el segundo a las columnas ( j ) .

Declaración de un arreglo de dos dimensiones :

Estático :

tipo nombre [filas, coumnas]

Ej : entero A [3,3] declara un arreglo de datos tipo entero de 3 filas y tres columnas.

Almacenamiento de arreglos en memoria

Arreglos de Una y dos dimensiones se representan como se muestra:

A[1]

A[2]

A[3]

A[4]

...

A[n]

A[1,1]	A[1,2]	A[1,3]	A[1,4]	...	A[1,n]
A[2,1]	A[2,2]	A[2,3]	A[2,4]	...	A[2,n]
A[3,1]	A[3,2]	A[3,3]	A[3,4]	...	A[3,n]
:	:	:	:	:	:
A[m,1]	A[m,2]	A[m,3]	A[m,4]		A[m,n]

La memoria de la computadora es unidimensional, por lo que el almacenamiento de los arreglos de más de una dimensión requiere que la posición de los elementos del arreglo sea "linealizada".

La forma mas común de almacenamiento de vectores de dos dimensiones es por filas, así un vector A[3,4] se almacenaría de la manera siguiente:

1	2	3	4	5	6	7	8	9
A[1,1]	A[1,2]	A[1,3]	A[1,4]	A[2,1]	A[2,2]	A[2,3]	A[2,4]	A[3,1]	……

La posición de un elemento A[i,j] del arreglo A[3,4] de dimensiones [m,n] con relación al primer elemento es: Posición = n*(i -1) + j

Así la posición dentro del arreglo del elemento A[2,3] del ejemplo anterior sería:

m = 3, n = 4, i = 2, j = 3 Posición = 4 * (2 - 1) + 3 = 7

Operaciones sobre arreglos

Las operaciones que se pueden realizar con arreglos durante el proceso de resolución de un problema son:

• Asignación
• Lectura / Escritura
• Recorrido
• Búsqueda
• Ordenamiento.

Asignación :

La asignación de valores a un elemento de un arreglo se representa con la instrucción:

A[10] = 3 / asigna el valor 3 al elemento 10 del vector A

ventas[2,2] = 1500

Si se desea asignar valores a todos los elementos de un vector, se debe usar estructuras de repetición.

• Caso Unidimensional: Asignar el valor 6 a todos los elementos de un vector A[5]

repetir_desde ( i = 1; i <= 5 ; i=i+1)

A[i] = 6

fin_repetir_desde

• Caso Bidimensional: Inicializar un vector B[2,3] con el valor cero.

repetir_desde ( i = 1; i <= 2 ; i=i+1)

repetir_desde ( j = 1; j <= 3 ; j=j+1)

B[i,j] = 0

fin_repetir_desde

fin_repetir_desde

Lectura / Escritura :

La lectura/escritura de datos en arreglos u operaciones de entrada/salida, normalmente se realizan con estructuras repetitivas o selectivas. Las instrucciones simples de lectura/escritura se representan como:

leer(Nombre_del_arreglo[Indice])

mostrar(Nombre_del_arreglo[Indice])

Ej : leer(X[3]) / Lee el elemento 3 del vector X

Recorrido :

A la operación de efectuar alguna acción sobre todos los elementos del vector se le llama recorrido. Estas operaciones se realizan usando estructuras de repetición, cuyas variables de control se usan como índices del vector. Se puede realizar esta operación para introducir datos al vector (leer) o para ver su contenido (mostrar).

Ejemplo 1: Lectura de los 10 valores de un vector P.

Ejemplo 2: El siguiente algoritmo lee las notas del primer examen de Computación de una sección de 40 alumnos , a fin de calcular el promedio.

Si se deseara mostrar la cantidad de alumnos con notas superiores al promedio se agregan las siguientes líneas al algoritmo anterior:

Ejemplo 3: Leer una matriz de dos dimensiones A[5,4].

Dado que es una matriz de dos dimensiones, se necesitan dos bucles anidados para recorrer todos sus elementos.

Ejemplo 4: Inicializar una matriz de dos dimensiones con valor constante 0.

El algoritmo debe asignar la constante 0 a todos los elementos de la matriz A[5,4].

Dado que es una matriz de dos dimensiones, se necesitan dos bucles anidados para recorrer todos sus elementos:

Ejemplo 5: Realizar la suma de dos matrices bidimensionales.

Para sumar dos matrices es preciso que las dos matrices tengan las mismas dimensiones. La matriz suma[I,J] tendrá las mismas dimensiones de las matrices sumandos y cada elemento será la suma de los mismos elementos correspondientes en las matrices sumandos: suma[I,J] = A[I,J] + B[I,J].

Dado que las matrices son de dos dimensiones se requieren dos bucles anidados:

Ejemplo 6: Diseñar un algoritmo que genere una matriz identidad de orden n.

• La matriz identidad tiene todos los elementos de la diagonal principal igual a uno (1), todos los demás elementos son igual a cero (0).
• En los elementos de la diagonal principal I = J.

Algoritmos Básicos de Búsqueda y Ordenamiento

Búsqueda :

La operación de búsqueda es una de las tareas más comunes en computación y básicamente consiste en encontrar la posición de un elemento específico en un conjunto de elementos dados.

Búsqueda secuencial :

Suponemos una lista (vector) de elementos, donde no hay elementos repetidos ; la forma mas sencilla de buscar un elemento específico es recorriendo la lista y verificando si existe alguna coincidencia entre los elementos de la lista y el elemento buscado.

Ejemplo: Suponemos se desea buscar un nombre en una lista de n elementos. El algoritmo debe mostrar los mensajes :

- nombre encontrado, si el nombre está en la lista.

- nombre no existe, si no se encuentra el nombre.

Se supone que no hay elementos repetidos.

Análisis : Se requiere leer el número de elementos ( n ) y el elemento a buscar. Se debe recorrer toda la lista y preguntar si cada elemento de la lista es el que estamos buscando, para lo cual se requiere un ciclo con contador (i - desde 1 hasta n) y una estructura de decisión para confirmar la condición del elemento buscado.

Se usa además una variable tipo interruptor (sw) , la cual se incializa en cero antes de comenzar el ciclo de búsqueda y se cambia a uno cuando se encuentra el nombre buscado.

Diseño del algoritmo :

Búsqueda Menor / Mayor :

El problema consiste en buscar el elemento menor/mayor de un conjunto de elementos almacenados en un arreglo. Por ejemplo, buscar el elemento mayor del vector A mostrado:

Análisis :

La estrategia a seguir consiste en asignar la condición deseada (MAYOR) al primer elemento de la lista (A[1]) y se empieza a comparar con todos los elementos de la lista. Si alguno de los elementos resulta mayor que el elemento al cual se le ha asignado la condición, se cambia la condición al nuevo elemento. Al terminar de recorrer todo el vector, el valor que mantiene la condición deseada es el mayor.

Los resultados sobre el ejemplo se podrían ver como sigue:

Diseño del algoritmo:

Ordenamiento

El ordenamiento es una labor común que realizamos continuamente y es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente organizar información de una manera especificada (criterio de ordenamiento).

El ordenamiento puede ser:

Interno : La operación se realiza en memoria central. (Arreglos)

Externo: La operación se realiza sobre un soporte externo (Archivos).

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientosmás complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás.

Método de Intercambio o de burbuja:

El algoritmo se basa en el principio de comparar pares de elementos e intercambiarlos entre sí hasta que estén todos ordenados.

Para intercambiar dos elementos A[i] y A[i+1], es necesario considerar una variable auxiliar, usando el siguiente procedimiento:

aux = A[i]

A[i] = A[i+1]

A[i+1] = aux

Ejemplo:

Aplicaciones sobre Arreglos

1.- Dados tres arreglos A, B, C de n elementos enteros cada uno, generar un cuarto arreglo D de tres elementos, donde el contenido de cada elemento sea la suma de los elementos de A , B y C, es decir : D[1] = A[1]+ A[2]+ A[3]+…A[n]…..

Diseño del Algoritmo :

Algoritmo Creación de Arreglo

Inicio

2.- Un vendedor que hizo 20 ventas en el día desea calcular su comisión total sobre las ventas diarias, sabiendo que le corresponde un 5% de comisión sobre artículos cuyo precio es menor de 10000 Bs.y el 10% de comisión por artículos cuyo precio = 10000 Bs. ó mas.Además,el vendedor desea saber cuantas ventas hizo menores de 10000 y cuántas de 10000 ó mas.

El algoritmo debe permitir realizar los diferentes procesos como opciones a escoger por el usuario, como un dato de entrada.

Diseño del Algoritmo:

Algoritmo Cálculo de comisión

Inicio

entero i,cont_menor, cont_mayor, opción

real precio[20], comisión, comisión_total

caracter respuesta

cont_menor = 0, cont_mayor = 0,comisión_total = 0

respuesta = "s"

Repetir mientras (respuesta == "s")

Mostrar ("Introduzca su opción : 1.- Leer arreglo de precios

2.- Calcular comisión

3.- Mostrar resultados " )

Leer (opción)

En caso de (opcion)

caso 1 :

Repetir desde ( i= 1; i <=20) ; i=i+1)

Mostrar ( " Introduzca el precio del artículo ", i )

Leer ( precio[i] )

Fin Repetir desde

caso 2 :

Repetir desde ( i= 1; i <=20) ; i=i+1)

Si ( Precio [i]< 10000)

comisión = 0.05*precio[i]

cont_menor = cont_menor + 1

sino

comisión = 0.10*precio[i]

cont_mayor = cont_mayor + 1

Fin Si

comisión_total = comisión_total + comisión

Fin Repetir desde

caso 3 :

Mostrar ( "Artículos vendidos con precio inferior a 10000 :",

cont_menor )

Mostrar ( "Artículos vendidos con precio superior a 10000 :",

cont_mayor )

Mostrar (" Comisión total del vendedor = ", comisión_total )

Fin En caso de

Mostrar (" Desea continuar : s/n ")

Leer (respuesta )

Fin Repetir mientras

Fin

3.- Un tablero de damas se puede representar con un arreglo de 8 filas por 8 columnas, donde un 1 representa la presencia de una ficha roja en el tablero, un 2 representa la presencia de una ficha negra y un tres representa ausencia de ficha.

Se requiere calcular y mostrar :

El número de fichas rojas , el número de fichas negras y el número total de fichas.

4.- Se tiene el monto de cada una de 100 ventas realizadas por una vendedora de un establecimiento comercial. Por cada venta calcule : el IVA de 15.5 %, calcule y muestre el monto a pagar incluyendo el IVA, calcule y muestre el monto total en ventas y monto total en impuesto por todas las 100 ventas.

Análisis:

• EL dato sería un vector VENTAS[100], el cual contiene los montos de las 100 ventas.
• Se debe generar un vector IVA[100],haciendo IVA[I] = VENTAS[I]*0.155.
• El monto a pagar de cada venta se guarda en un vector MONTO[100]. Este vector se calcula haciendo MONTO[I] = Ventas[I] + IVA[I].
• El monto total en ventas (T_VENTAS) se obtiene sumando los elementos del vector MONTO[100].
• El monto total de impuesto (T_IMP) se obtiene sumando los elementos del vector IVA[100].

Diseño del algoritmo:

• Se requiere calcular el vector IVA para lo cual es necesario recorrer el vector ventas y multiplicar cada elemento por el 15.5 %.
• Dentro del mismo ciclo se puede calcular el vector MONTO.

5.-Llenar un vector de n elementos con los primeros n valores enteros y primos.

Análisis:

• Un número primo es aquel que es divisible únicamente por el mismo y la unidad. Para chequear si un numero es divisible por otro se usa la función mod, la cual devuelve el resto de la división : si (A mod B = 0 ),el número A es divisible por B.
• Para verificar si un número es primo se comprueba la división del número por todos los valores enteros que están por debajo de el, excluyendo la unidad y el número mismo.
• Los números 1,2 y 3 son primos.

Diseño del algoritmo:

6.-Generar la siguientes matrices:

Análisis:

• las matrices se almacenan como se muestra:

• La matriz A se recorre por filas y se asigna a cada elemento un valor que puede ser un contador inicializado en 1.
• La matriz B se recorre por columnas y se asigna a cada elemento un valor que puede ser el contador inicializado en 1.
• La matriz C se crea utilizando un criterio (i == j) para llenarla.

Diseño del algoritmo:

Ejercicios propuestos

ESTRUCTURAS DE DATOS (ARREGLOS)

1. Escriba un algoritmo que lea una lista de N números reales y calcule el promedio de estos números.

2. Si XPR representa la media de los numero X1, X2, X3,….XN, la varianza es la media de los cuadrados de las desviaciones de los números de la media y la desviación estándar es la raíz cuadrada de la varianza:

Escriba un algoritmo que lea una secuencia de números reales y a continuación calcule y muestre su media, varianza y desviación estándar.

3. Escriba un algoritmo que lea un vector de números enteros y determine el valor máximo y el valor mínimo.

4. Diseñe un algoritmo que lea una lista de números reales y calcule la media de los números de posiciones pares y la media de los números de posiciones impares.

5. Escriba un algoritmo que lea una matriz NxN de números enteros y determine la posición de la matriz en la que se encuentra el valor máximo.

6. Escriba un algoritmo que efectúe la suma y la resta de dos matrices NxM de números reales.

7. Una agencia de ventas de vehículos distribuye 10 modelos y tiene contratados 15 vendedores. Escribir un algoritmo que calcule y muestre una tabla resumen donde se muestre:

a. Cuantos autos colocó cada vendedor.

b. Cuantos autos se vendieron, por modelo.

c. Cual modelo se vendió menos.

d. Organizar la información de manera que se muestre en forma creciente las ventas totales por vendedor.

8. Diseñe un algoritmo que lea un vector de 500 elementos enteros y a partir de ese vector genere un nuevo vector con un máximo de 30 elementos, donde cada elemento es primo.