Arreglos

Invertir algunos números

Considera un programa que lea del teclado 8 números y los despliegue luego en orden inverso, como se ve a continuación:

La solución es bastante fácil de programar. Basta con declarar 8 variables enteras, leerlas del teclado y escribirlas en orden inverso:

  1. int v1,v2,v3,v4,v5,v6,v7,v8;

  2. printf ("Ingresa los números\n");

  3. printf ("Número 1:");

  4. scanf(“%d”,&v1);

  5. printf ("Número 2:");

  6. scanf(“%d”,&v2);

  7. printf ("Número 3:");

  8. scanf(“%d”,&v3);

  9. printf ("Número 4:");

  10. scanf(“%d”,&v4);

  11. printf ("Número 5:");

  12. scanf(“%d”,&v5);

  13. printf ("Número 6:");

  14. scanf(“%d”,&v6);

  15. printf ("Número 7:");

  16. scanf(“%d”,&v7);

  17. printf ("Número 8:");

  18. scanf(“%d”,&v8);

  19. printf ("Los números al revés son:\n");

  20. printf ("Número 8 %d\n",v8);

  21. printf ("Número 7 %d\n",v7);

  22. printf ("Número 6 %d\n",v6);

  23. printf ("Número 5 %d\n",v5);

  24. printf ("Número 4 %d\n",v4);

  25. printf ("Número 3 %d\n",v3);

  26. printf ("Número 2 %d\n",v2);

  27. printf ("Número 1 %d\n",v1);

    ¿Qué pasaría, sin embargo, si fueran 100 números en vez de sólo 8? ¿Habría que declarar 100 números enteros?

    Arreglos

    Un arreglo es un objeto que sirve para almacenar un conjunto de valores del mismo tipo. Su declaración es:

    tipoVariable nombreVariable[];

    Su creación es similar a la creación de un objeto común, pero se debe especificar además la cantidad de elementos:

    tipoVariable nombreVariable[cantidad];

    Por ejemplo, si se desea guardar en el arreglo v las votaciones de 8 candidatos la declaración debe ser hecha de la siguiente manera:

    int v[8];

    v = new int [8];

    Los arreglos tienen además una fuerte relación con los punteros, puesto que son áreas en la memoria a las cuales son “apuntados”. Por ejemplo el mismo arreglo anterior se puede declarar de la siguiente manera:

    int *v;

    v = (int *) malloc (sizeof(int) * 8);

    Lo que se traduce en la creación de un objeto de 8 elementos enteros que es apuntado (referenciado por v). Malloc se utiliza para pedir memoria, es decir, C le dice al computador “necesito x celdas de memoria”, en este caso son 8 celdas para almacenar enteros:

    Cada elemento se referencia con el nombre del arreglo y un índice entero. El rango de los índices va de 0 a cantidad-1.

    Por ejemplo, para hacer referencia al valor del cuarto elemento de v hay que escribir v[3]. El indice dentro de los paréntesis cuadrados puede ser cualquier expresión entera que este dentro del rango [0, cantidad-1].

    El siguiente código asigna valor 0 a todos los elementos de v:

  28. i=0;

  29. while (i<8) {

  30. v[i]=0;

  31. i++;

    }

    Como v[i] es un arreglo de enteros, sus elementos pueden ser colocado en cualquier contexto donde sea valido poner una variable de tipo entero. Un par de ejemplos clarifica esto:



        int a;

        scanf (“%d”,&a);

    int v[8];

        i=0;

        while (i<8) {

        scanf (“%d”,&v[i]);

        i++;

        }

    int x=a*2;

    int x=v[7]*2;

    a=a+1;

    v[2]=v[2]+1;

    Además toda la aritmética de punteros se puede utilizar sobre los arreglos, por ejemplo es válido:

    int v[10],x;

    int *pa;

    pa = &v[1]; /* pa apunta a la dirección de la celda v[1] */

    x = *pa; /* x = v[1] */

    x = *(pa+1); /* x = v[2] */

    pa = v; /* Correspondencia entre punteros y arreglos*/

    /* Es equivalente a pa = &v[0] */

    Usando arreglos, el programa para invertir los números queda:

  32. int v[8];

  33. printf ("Ingresa los números\n");

  34. for (int i=0; i<8; i++) {

  35. print ("Número %d:",i);

  36. scanf (“%d”,&v[i]);

  37. }

  38. printf ("Los números al revés son:\n");

  39. for (int i=7; i>=0; i--)

  40. println ("Número %d: %d”,i,v[i]);

    Arreglos de dos dimensiones

    En un curso de computación de 100 alumnos se han rendido 6 test a lo largo del año. Las notas podrían guardarse en 6 arreglos de 100 elementos cada uno:

    float c1[100];

    ...

    float c5100];

    float c6[100];

    o en una matriz de 100 x 6

    double notas[100][6];

    Como ejemplo, si los datos se encuentran en la matriz:

    notas

    6.7 6.5 6.3 6.1 6.8 7.0

    1.2 2.3 3.1 4.0 4.0 2.1

    4.5 4.4 4.1 4.0 4.0 3.5

    ...

    El promedio de cada alumno es simple de calcular:

  41. for (alumno=0; alumno<100; alumno++) {

  42. float suma=0.0;

  43. int test;

  44. for (test=0; test <6; test++)

  45. suma=suma+notas[alumno][test];

  46. println ("El promedio del alumno %d es %1.2f",alumno+1,suma/6);

  47. }

¿Filas o columnas?

    Una de las preguntas más comunes en arreglos bidimensionales es cuál indice representa las columnas y cuál las filas. Por ejemplo, si se te pide crear un arreglo para guardar las notas de 100 alumnos a lo largo de 5 pruebas, ¿cuál de las siguientes declaraciones es la correcta?

    float nota[100][5];

    o

    float nota[5][100];

    En realidad da lo mismo, sólo importa ser consecuente (aunque ser consecuente no es una virtud) después de la declaración y respetar la convención que uno mismo se da.

    El código de la figura 1 es correcto, a diferencia del de la figura 2, que no respeta el sentido de la declaración:

  1. float nota[100][5];

  2. for (i=0; i<100;i++)

  3. for (j=0; j<5; i++) {

  4. print ("Ingresa la nota %d del Alumno %d”,j,i);

  5. scanf (“%f",&nota[i][j]);

  6. }

    Figura 1

  7. float nota[5][100];

  8. for (int i=0; i<100;i++)

  9. for (int j=0; j<5; i++) {

  10. print ("Ingresa la nota %d del Alumno %d”,j,i);

  11. scanf (“%f",&nota[i][j]);

  12. }

    Figura 2

    El código de la figura 2 corregido es

  13. float nota[5][100];

  14. for (int i=0; i<100;i++)

  15. for (int j=0; j<5; i++) {

  16. print ("Ingresa la nota %d del Alumno %d”,j,i);

  17. scanf (“%f",&nota[j][i]);

  18. }

    Asignacion de arreglos

    Imagina que tienes un arreglo A de 100 números de tipo entero y quieres copiarlo en un arreglo B. El código que escribiría un alumno de pocas luces es:

  19. int A[100], B[100];

  20. /* leer A de el teclado, o calcularo */

  21. ...

  22. B=A;

    Este código compila, ¿pero qué es lo que hace? . En este caso estamos creando un objeto que consiste de 100 elementos enteros y guardamos una referencia a él en A.

    En la segunda declaración se le dice a C que en B se guardará una referencia a un arreglo de enteros. En la línea 22 se hace que B haga referencia al mismo objeto (arreglo de enteros) que A:

    En todo caso, el compilador de C reclamará porque dirá que B es estático y no dinámico (averigue la diferencia... investigue, no sea flojo), lo cual se “mejoraría” si se declara B como int *B , sin embargo la solución aún no es correcta. El siguiente es un ejemplo erroneo de querer usar B para guardar una "copia" de A para luego reestablecer los valores originales:

  23. int A[100], *B;

  24. ....

  25. B=A; /* guardamos copia de A */

  26. /* se modifica A */

  27. for (int i=0; i<100;i++)

  28. A[i]=...;

  29. /* reestablecemos los valores de A */

  30. A=B;

    Cualquier cambio hecho en el arreglo en la línea 28 es permanente, en el sentido que la linea 30 no tiene ningún efecto, pues A y B ya hacen referencia al mismo objeto a partir de la línea 25.

    El código correcto es

  31. int A[100], B[100];

  32. /* o bien: int *B; B = (int *) malloc (100*sizeof(int));*/

  33. ...

  34. for (int i=0;i<100;i++)

  35. B[i]=A[i];

  36. // se modifica A

  37. for (int i=0; i<100;i++)

  38. A[i]=...;

  39. // reestablecemos los valores de A

  40. for (int i=0;i<100;i++)

  41. A[i]=B[i];

    El siguiente diagrama muestra la situación después de la línea 31:

Patrónes en arreglos

El patrón más común es el de recorrer un arreglo:

Similar es el patrón de recorrido de un arreglo en orden inverso:

El patrón de búsqueda de un elemento es un caso particular del recorrido:

El patrón de búsqueda del índice de un elemento es muy usado:



Recorrido de una matriz

Existen varias formas de recorrer un arreglo, dependiendo de la forma en que se incrementen los índices. Hay veces en las que la forma del recorrido no tiene ninguna importancia (sumar todos los datos de la matriz), pero en problemas como resolver un sistema de ecuaciones lineales sí importa:

for (fila=0;fila<n; fila++)

for (col=0; col<m; col++)

... A[fila][col];

for (fila=0;fila<n; fila++)

for (col=m-1; col>=0; col--)

... A[fila][col];

 

Pon tus conocimientos a prueba

  • ¿Cómo harías para almacenar una matriz de m x n elementos en un arreglo de una sola dimensión?

  • Escribe un programa que multiplique matrices

Problemas resueltos

Problema 1: Matriz simétrica

Muchos problemas de algebra lineal son simplificables si las matrices involucradas cumplen ciertas propiedades. Dentro de las tantas propiedades que puede tener una matriz, es ser simétrica.



Un ejemplo de matriz simétrica es éste:

Es decir, si A es matriz de n x n, entonces A es simétrica si:

Escriba un programa en Java que determine si una matriz es simétrica o no. Suponga que ya tiene una matriz A de tamaño n x n. Tenga cuidado con la solución, aproveche las propiedades de la matriz para resolver el problema eficientemente.

  1. /* En este caso, es solo un TROZO de código

  2. Se tienen la matriz A de tamano nxn y los indices que sean

  3. necesarios. Usaremos una variable flag, que registra un

  4. estado como interruptor */

  5. int A[n][n];

  6. int i,j,flag=true;

  7. for(i=0; i<n; i++)

  8. for(j=0; j<i; j++)

  9. if (A[i][j] != A[j][i])

  10. flag=false;

  11. if (flag) /* Es simetrica, no cambio nunca */

  12. printf("Matriz simetrica\n");

  13. else

  14. printf("Matriz no simetrica\n");

Problema 2: Consultoría sentimental

Una empresa de consultoría sentimental se encarga de poner en contacto personas que podrían tener afinidad para que se conozcan.

Para esto tienen un programa en C (de miles de líneas de código) que se encarga de procesar toda la información sobre los clientes para encontrar quienes podrían entablar una buena relación.

El programa entrega como resultado, un arreglo de tamaño NPERSONAS (que es un int) de enteros (compatible[ ]) que es un índice para el arreglo de personas que indica la persona con que tiene afinidad (No se almacena el nombre para mantener el anonimato). Por ejemplo, si compatible[10]=25 quiere decir que la persona 10 le agradaria la persona 25, pero no necesariamente al revés.

Para terminar el programa, falta escribir las partes que permitan hacer ciertas consultas:

  1. Escribe la parte del programa que permita encontrar todas las parejas mutuamente compatibles. No importa que la pareja aparezca repetida.

  2. Escribe la parte del programa que encuentre la persona con quien mas personas son compatibles. Sin es más de una imprima cualquiera.

  3. Escribe la parte del programa que encuentre aquellas personas con quienes nadie es compatible (snif).

Indicacion: Suponga que los arreglos nombre[ ] y compatible[ ] existen y ya tienen la información.

Solución a)

  1. /* Revisamos todas las personas */

  2. int i;

  3. for(i=0; i<NPERSONAS; i++)

  4. /* Si una persona es comptible con otra que es

  5. compatible con la primera, son mutuamente compatibles */

  6. if( i==compatible[compatible[i]]) {

  7. printf("%d y %d son compatibles y hacen pareja\n"i,compatible[i]);

  8. }

    Solución b)

  9. int maxcomp=0; /* Guarda la compatibilidades del maximo */

  10. int ncomp; /* Guarda el No. de compat. de la persona actual */

  11. int indmaxcomp=0; /* Indice del mas compatible */

  12. /* Recorremos todas las personas */

  13. int i;

  14. for(i=0; i<NPERSONAS; i++)

  15. {

  16. int j;

  17. ncomp=0;

  18. for(j=0; j<NPERSONAS; j++)

  19. /* Chequeamos si es compatible */

  20. if (compatible[j]==i)

  21. ncomp++;

  22. /* Si tenemos un nuevo maximo */

  23. if(ncomp>maxcomp)

  24. {

  25. maxcomp=ncomp;

  26. indmaxcomp=i;

  27. }

  28. }

  29. printf("Con %d son compatibles %d personas",indmaxcomp,maxcomp);

    Solución c)

  30. /* Chequeamos todas las personas */

  31. int i;

  32. for(int i=0; i<NPERSONAS; i++)

  33. {

  34. ncomp=0;

  35. /* Revisamos si tiene alguien compatible */

  36. int j;

  37. for(j=0; j<NPERSONAS; j++)

  38. // Si tiene alguien compatible terminamos

  39. if(compatible[j]==i)

  40. {

  41. ncomp=1;

  42. break;

  43. }

  44. if (ncomp==0)

  45. printf("Nadie es compatible con %d\n",i);

  46. }

Memoria Dinámica

La función básica es malloc, que reserva unr espacio de memoria del tamaño que se le indique (en bytes) y retorna un puntero. Siempre hay que anteponerle un cast a la llamada, para que el tipo del puntero retornado se adapte a lo que se espera.


        #include <stdlib.h>
        
        char *s;
        
        s = (char *)malloc(100); /* reserva un área de 100 bytes */

Para pedir espacio para un arreglo hay dos alternativas. Una es usar malloc y calcular "a mano" el espacio total requerido. Por ejemplo,


        p = (int *)malloc(100*sizeof(int)); /* p apunta a un arreglo de 100 int's */

La otra forma es usar otra función, calloc, que tiene dos parámetros (número de celdas y tamaño de cada celda):


        p = (int *)calloc(100, sizeof(int)); /* p apunta a un arreglo de 100 int's */

Un efecto lateral de calloc es que inicializa en cero la memoria que entrega.

Al terminar de usar un área de memoria pedida dinámicamente, se le debe retornar al sistema usando


        free(p);

donde p apunta al principio del área que se libera.

En C no hay recolección automática de basura, es responsabilidad del programador liberar la memoria que ya no use. Los programas que funcionan durante mucho tiempo y que van olvidando liberar memoria se dice que tienen un error de tipo "memory leak", el cual puede ser muy difícil de investigar.