viernes, 23 de octubre de 2015

Introducción

Con frecuencia podemos encontrar problemas cuya solución es muy difícil de implementar si utilizamos tipos  de datos que sean simple. Por otra parte, podemos encontrar una buena solución al porblema utilizando técnicas de programacion como lo hemos presentado en este blog, en el cual solo describimos una técnica muy conocia "Los arreglos o vectores" .

Qué son los arreglos?  

Un arreglo es un conjunto de datos o una estructura de datos homogéneos que se encuentran ubicados en forma consecutiva en la memoria RAM (sirve para almacenar datos en forma temporal).  

 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.

Arreglos Unidimensionales

 

      


Un arreglo se define como una colección finita, homogénea y ordenada de elementos.


Finita: todo arreglo tiene un límite, es decir se debe determinar cuál será el número máximo de elementos que podrán formar parte del arreglo.
Homogéneas: todos los elementos de un arreglo son del mismo tipo (todos enteros, todos reales, etc., pero nunca una combinación de distintos tipos).
Ordenadas: se puede determinar cuál es el primer elemento, el segundo el tercero,… y el n-esimo elemento.

Un arreglo puede representarse gráficamente como se muestra en la siguiente imagen:




Un arreglo tiene la característica de que puede almacenar a N elementos del mismo tipo y además permite el acceso a cada uno de esos elementos. Así, se distinguen dos partes en los arreglos.
  •             Los componentes.
  •         Los índices.

Los componentes hacen referencia a los elementos que componen o forman el arreglo. Es decir, son los valores que se almacenan en cada una de sus casillas.
Los índices, por otra parte, son los que permiten accesar a los componentes del arreglo en forma individual. Para hacer referencia a un componente de un arreglo se necesita:
  •         El nombre del arreglo.
  •         El índice del elemento.

En la siguiente imagen se muestra la representación de un arreglo y se indican sus componentes y su índice:

Como los arreglos son datos estructurados, muchas de estas operaciones no pueden llevarse a cabo de manera global, sino que deben trabajar sobre cada elemento.
A continuación cada una de estas operaciones.

Lectura/Escritura

  • Lectura: Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes. La lectura se realiza de la siguiente manera: para i desde 1 hasta N haz x<--arreglo[i]
  • Escritura: Consiste en asignarle un valor a cada elemento del arreglo. La escritura se realiza de la siguiente manera: para i desde 1 hasta N haz arreglo[i] <x. 





Asignación
En general no es posible asignar directamente un valor a todo arreglo, sino que se debe asignar el valor deseado a cada componente.


Actualización

En un arreglo se pueden insertar, eliminar y/o modificar elementos. Para llevar a cabo estas operaciones eficientemente se debe tener en  cuenta si el arreglo esta ordenado o desordenado.

 Es decir, si sus componentes respetan  algún orden entre si.

Arreglos desordenados:

  •     Inserción: para insertar un elemento Y en un arreglo A desordenado debe verificarse que exista espacio. Si se cumple esta condición, entonces se asignara a la posición N+1 el nuevo elemento.
  •     Eliminación: para eliminar un elemento X de un arreglo A desordenado debe verificarse que el arreglo no esté vacío y que X se encuentre en el arreglo.

 Si se cumplen estas condiciones entonces se procederá a  recorrer todos los         elementos que están a su derecha una posición a la izquierda, decrementando finalmente el número de componentes del arreglo.
  •        Modificación: para modificar un elemento X por un elemento Y, de un arreglo A que se encuentra desordenado debe verificarse que el arreglo no esté vacío y que X se encuentre en el arreglo.

Si se cumplen estas tres condiciones entonces se puede proceder a la actualización.

Igualdad: La única forma para poder entonces verificar la igualdad de dos arreglos es realizando una función lógica en la que mediante una estructura interactiva se comparen todos y cada uno de los elementos de ambos arreglos que tengan el mismo valor de índice.



  • Recorrido: Se puede acceder a los elementos de un vector para introducir datos (leer) en él, para visualizar su contenido (escribir), para verificar su igualdad o para realizar un tratamiento sobre sus componentes. A la operación de efectuar una acción general sobre todos los elementos de un vector se la denomina recorrido del vector.

Ejemplos.



Ejemplo 1
Programa en el que el usuario ingresa 10 alturas, guardadas en un vector; calcule la suma y el promedio. 

 #include <stdio.h>
#include <windows.h>
main()
{
int altura[10],suma=0,promedio,i,c;
printf("*** Bienvenido al Programa ***\n");
printf(" introduce 10 alturas\n");
for(i=1;i<=10;i++)
{
scanf("%d",&altura[i]);
suma=suma+altura[i];
}
promedio=suma/10;
printf("la suma es %d",suma);
printf(" el promedio es %d\n",promedio);
system("pause");





Ejemplo 2
Programa que guarda 15 números ingresados por el usuario e indica cuantos números son positivos, negativos y nulos.



Arreglos Multidimensional

Concepto


Los arrays multidimensionales son una estructura de datos que almacenan los valores en más de una dimensión. Los arrays que hemos visto hasta ahora almacenan valores en una dimensión, por eso para acceder a las posiciones utilizamos tan solo un índice. Los arrays de 2 dimensiones guardan sus valores, por decirlo de alguna manera, en filas y columnas y por ello necesitaremos dos índices para acceder a cada una de sus posiciones. 

Dicho de otro modo, un array multidimensional es como un contenedor que guardara más valores para cada posición, es decir, como si los elementos del array fueran a su vez otros arrays. 

La declaración de los arreglos bidimensionales, caso particular de los arreglos multidimensionales, se hace como en el siguiente ejemplo:

En la primera línea se reserva espacio para 3 × 4 = 12 elementos doble precisión. El primer subíndice varía entre 0 y 2, y el segundo varía entre 0 y 3. Usualmente, de manera análoga a las matrices, se dice que el primer subíndice indica la fila y el segundo subíndice indica la columna.



Ejemplos de arreglos multidimensional 

Ejemplo#1
“Este programa imprimirá las fila y las columna del vector  multidimensional  3x4”





Ejemplo #2 

En el siguiente ejemplo, el programa sirve para leer matrices, escribirlas y calcular el producto. Lo hace mediante la utilización de funciones que tienen como parámetros arreglos bidimensionales:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void lect_ao(double a[][40], int m, int n, char c );
void escra_ao(double a[][40], int m, int n );
int prodAB0(double a[][40], int m, int n, double b[][40],
int p, int q, double c[][40]);
main()
{
double a[50][40], b[20][40], c[60][40];
int m, n, p, q;
printf("\n Producto de dos matrices.\n");
printf(" num. de filas de A : ");
scanf( "%d", &m);
printf(" num. de columnas de A : ");
scanf( "%d", &n);
// Es necesario controlar que m, n no son muy grandes
// Ni negativos
printf(" num. de filas de B : ");
scanf( "%d", &p);
printf(" num. de columnas de B : ");
scanf( "%d", &q);
if( n != p ){
printf(" Producto imposible\n");
exit(1);
// En el lenguaje C para terminar una aplicación desde la función main
}
Lect_ao(a, m, n, 'A');
printf(" A : \n");
escr_ao(a, m, n);
lect_ao(b, n, q, 'B');
printf(" B : \n");
escr_ao(b, n, q);
if( prodAB0(a,m,n, b,p,q, c) )
{
printf(" C : \n");
escrA0(c, m, q);
}
else printf("\ ERROR\n");
return 0;

//------------------------------------------------

void lect_ao(double a[][40], int m, int n, char c )
{
// lectura de los elementos de una matriz.
int i, j;
for( i = 0; i < m; i++){
for( j=0; j < n; j++){
printf(" %c[%d][%d] = ", c, i+1, j+1);
scanf("%lf", &a[i][j] );
}
}
}
//------------------------------------------------
void escr_ao(double a[][40], int m, int n )
{
// escritura de los elementos de una matriz
int i, j;
int nEltosLin = 5; // numero de elementos por linea
for( i = 0; i < m; i++){
for( j = 0; j < n; j++){
printf("%15.8lf", a[i][j]);
if((j+1)%nEltosLin == 0 || j==n-1)printf("\n");
}
}
}
//------------------------------------------------
int prodAB0(double a[][40], int m, int n, double b[][40],int p, int q, double c[][40])
{
// producto de dos matrices, a mxn, b pxq
// devuelve 1 si se puede hacer el producto
// devuelve 0 si no se puede
int i, j, k;
double s;
if(m<0||n<0||p<0||q<0 || n!= p ) return 0;
for( i=0; i < m; i++){
for( j=0; j < q; j++){
s = 0.0;
for( k=0; k<n; k++) s += a[i][k]*b[k][j];
c[i][j] = s;
}
}
return 1;

En el ejemplo, en la función lect_ao, antes de la lectura del elemento a[i][j], el programa escribe los valores i+1 y j+1, entonces para el usuario el primer subíndice empieza en 1 y acaba en m; el segundo empieza en 1 y acaba en n.

ARREGLOS BIDIMENSIONALES



  • Conceptos Básicos:

{ clrscr();
printf("\n\n");
for(i=1;i<=n;i++)Los arreglos bidimensionales son tablas de valores. Cada uno de sus elementos tiene una posición que se identifica mediante dos índices: el de su fila y el de su columna.
Ejemplo:
P= [4] [3]; que se interpreta como el elemento en la cuarta fila y tercera columna.
Son estructuras de datos que agrupan muchos datos del mismo tipo, en donde cada elemento se puede trabajar individualmente y se puede referenciar con un mismo nombre.
Un arreglo bidimensional está compuesto, por un conjunto de elementos homogéneos y se puede acceder a los datos utilizando dos subíndices, este tipo de arreglo es también conocido como matriz.
El uso de arrays con más de 2 dimensiones no es muy común.



matriz[0][0]
matriz[0][1]
matriz[0][2]
matriz[1][0]
matriz[1][1]
matriz[1][2]
matriz[2][0]
matriz[2][1]
matriz[2][2]
Estructura de un arreglo bidimensional de 3x3








  • Operaciones

Para manejar un arreglo, las operaciones a efectuarse son:
 DECLARACIÓN:
 La declaración de un arreglo consiste en establecer las características del arreglo y sus elementos por medio de la siguiente sintaxis:

<tipo_de_dato> <identificador_del_arreglo> [Dimensión_fila] [Dimensión_columna]

Donde:
Tipo de dato indica el tipo correspondiente a los elementos del arreglo.
Identificador del arreglo es el nombre del arreglo.
El par de corchetes ([  ]) representan las dimensiones del arreglo y encierra dos números enteros, cuyo producto corresponde al número de elementos del arreglo.

Por ejemplo:
1) int arreglo[10][10];
2) float matriz[10][10];
También podemos utilizar constantes para definir la dimensión del arreglo de dos dimensiones:
3) const int N = 10;
4) int arreglo[N][N];


5) int a [4] [3];

a[0][0]
a[0][1]
a[0][2]
a[1][0]
a[1][1]
a[1][2]
a[2][0]
a[2][1]
a[2][2]
a[3][0]
a[3][1]
a[3][2]






      CREACIÓN:

Consiste en reservar espacio en la memoria para todos sus elementos, utilizando la siguiente sintaxis:

< identificador > = new <tipo> [ dim1, dim2 ] ;

Donde:
new es el operador para gestionar espacio de memoria, en tiempo de ejecución,
dim1 y dim2 son valores enteros que representan las dimensiones del arreglo.

El tamaño del arreglo es el resultado de multiplicar los valores de las dimensiones y representa el número de elementos del arreglo.

Por ejemplo:
matriz = new double [2, 3] ; 

// Se crea el arreglo matriz, con 6 elementos de tipo
// Punto flotante y precisión doble.

  INICIALIZACIÓN:
Una matriz o arreglo bidimensional se puede inicializar de este modo:
int matriz[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
Con la anterior asignación se crea en memoria una matriz igual a la de abajo:

0
1
2
0
1
2
3
1
4
5
6
2
7
8
9
Fig. 8.1

A las matrices se le asignan automáticamente valores iniciales
predeterminados a cada uno de sus elementos, de acuerdo a los
siguientes criterios:
Si el tipo del arreglo es numérico, a sus elementos se les asigna el valor cero.
Si el tipo del arreglo es char, a sus elementos se les asigna el valor '\u0000'.
Si el tipo del arreglo es bool, a sus elementos se les asigna el valor false.
Si el tipo del arreglo es una clase, a sus elementos se les asigna el valor null.
Por ejemplo:

Leer, desde el teclado, una matriz de números enteros de dimensión 3x3.

#include <iostream.h>
void main()
{
const int TAM=3;
int matriz[TAM][TAM];
for( int i=0; i<TAM ; i++)
{
for( int j=0; j<TAM; j++)
{
cout<<”Ingrese el elemento [“<<i<<”,“<<j<<”] “;
cin>>matriz[I][j];
}
}
 ACCESO A LOS ELEMENTOS DE UN ARREGLO BIDIMENSIONAL:

En un arreglo de dos dimensiones necesitamos también dos índices para acceder a sus elementos.
Si utilizamos: matriz[i] [j], entonces i se refiere a la fila y j a la columna.
Para acceder al elemento de la segunda fila y segunda columna de la matriz de la Fig. 8.1 hacemos:
int nro = matriz[1][1];
En la variable nro se guardara el número 5.
Las matrices o arreglos bidimensionales se suelen utilizar en cálculos matemáticos, operaciones con matrices, recorridos por matrices, y cualquier uso que nosotros le podamos dar.

Se pueden definir arreglos de más de 2 dimensiones, pero su manejo se dificultaría enormemente.
-Inserción Directa de Elementos en un Arreglo Bidimensional:
<Nombre del arreglo> [índice de fila] [índice de columna]= valor
del elemento;
<Nombre del arreglo> [<m>] [<n>]= valor del elemento
Por ejemplo:
M [3] [2]=9        M [3,2]=9
- Extracción Directa de Elementos en un Arreglo Bidimensional:
<Identificador variable>=<nombre del arreglo> [índice de fila][índice de columna]

Por ejemplo:


x =M [3] [2]            x= M [3,2]

Aplicaciones
¿Cómo realizar un programa con arreglos bidimensionales?
Para el desarrollo de esta práctica, se lleva a cabo el siguiente algoritmo:
1.- Se da el número de renglones (n) y columnas (m).
2.- n*m, es la dimensión de la matriz
3.- Repetir con i desde 1 hasta
Repetir con j desde 1 hasta m
Leer matriz [i, j]
Continúa con j
Continúa con i

4.- Para insertar: es necesario verificar si hay espacio; si no, primero eliminar. Si hay espacio, se pide el elemento a insertar, se busca la nueva posición y se inserta el nuevo elemento.

5.- Para eliminar: se pide el elemento a eliminar, si se encuentra, se elimina.

6.- Para modificar: se busca el elemento a modificar, se da el elemento por el que se va a reemplazar, si se encuentra se reemplaza, si no se despliega un mensaje notificando al usuario.

Por lo tanto el código fuente quedaría:

En el caso de INSERCIÓN de un elemento
{
for(j=1;j<=m;j++)
{
printf("\b\bELEMENTO[%d][%d]=%d\n ",i,j,mat[i][j]);
}
}
gotoxy(5,8);
cprintf("ELEMENTO A INSERTAR:");scanf("%d",&ei);
if (nae<nte)
{
nae++;
b=0;
while(b!=1)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(b==1)
break;
if(mat[i][j]=='\0')
{
b=1;
mat[i][j]=ei;
break;
}  
}
}
printf("\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("\b\bELEMENTO[%d][%d]=%d\n ",i,j,mat[i][j]);
}
}
}
else
{
gotoxy(3,9);
cprintf(" LA MATRIZ ESTA LLENA ");
}
getch();
} break;




En el caso de ELIMINACIÓN de un elemento:
{ clrscr();
printf("\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("\b\bELEMENTO[%d][%d]=%d\n ",i,j,mat[i][j]);
}
}
gotoxy(5,8);
cprintf("ELEMENTO A ELIMINAR: ");scanf("%d",&e);
if (nae>1)
{
ban=0;
i=1;
j=1;
while(ban!=1)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(mat[i][j]==e)
{
ban=1;
nae--;
mat[i][j]='\0';
}
}
}
}
if (ban==0)
{
gotoxy(3,9);
cprintf("ELEMENTO %d NO EXISTE EN LA MATRIZ",e,mat[i][j]);
}
}
else
{
gotoxy(3,9);
cprintf("LA MATRIZ ESTA VACIA\n\n");
}
mat[n][m]=4;
printf("\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("\b\bELEMENTO[%d][%d]=%d\n ",i,j,mat[i][j]);
}
}
getch();
}break;


Y para la MODIFICACIÓN de un elemento el código fuente fue:

{ clrscr();
printf("\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("\b\bELEMENTO[%d][%d]=%d\n ",i,j,mat[i][j])
}
}
gotoxy(5,8);
cprintf("ELEMENTO A MODIFICAR: ");scanf("%d",&mi);
gotoxy(5,9);
cprintf("NUEVO ELEMENTO: ");scanf("%d",&ni);
if(nae>1)
{
i=1,
j=1;
b=0;
while(b!=1)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if (b==1)
break;
if (mat[i][j]==mi)
{
b=1;
mat[i][j]=ni;
break;
}
}
}
}
if (b==0)
{
gotoxy(3,10);
cprintf("ELEMENTO %d NO EXISTE EN LA MATRIZ",mi);
}
}
if (nae==0)
cprintf("LA MATRIZ ESTA VACIA");
printf("\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("\b\bELEMENTO[%d][%d]=%d\n ",i,j,mat[i][j]);
}
}
getch();
} break;