17 Tipos de variables VI: Punteros 2

Ya hemos visto que los arrays pueden ser una potente herramienta para el almacenamiento y tratamiento de información, pero tienen un inconveniente: hay que definir su tamaño durante el diseño del programa, y después no puede ser modificado.

La gran similitud de comportamiento de los punteros y los arrays nos permiten crear arrays durante la ejecución, y en este caso además el tamaño puede ser variable. Usaremos un puntero normal para crear vectores dinámicos, uno doble para tablas, etc.

Por ejemplo, crearemos una tabla dinámicamente. Para ello se usan los punteros a punteros.

Veamos la declaración de un puntero a puntero:

int **tabla;

"tabla" es un puntero que apunta a un objeto de tipo puntero a int.

Sabemos que un puntero se comporta casi igual que un array, por lo tanto nada nos impide que "tabla" apunte al primer elemento de un array de punteros:

int n = 134;
tabla = new int*[n];

Ahora estamos en un caso similar, "tabla" apunta a un array de punteros a int, cada elemento de este array puede ser a su vez un puntero al primer elemento de otro array:

int m = 231;
for(int i = 0; i < n; i++)
   tabla[i] = new int[m];

Ahora tabla apunta a un array de dos dimensiones de n * m, podemos acceder a cada elemento igual que accedemos a los elementos de los arrays normales:

tabla[21][33] = 123;

Otra diferencia con los arrays normales es que antes de abandonar el programa hay que liberar la memoria dinámica usada, primero la asociada a cada uno de los punteros de "tabla[i]":

for(int i = 0; i < n; i++) delete[] tabla[i];

Y después la del array de punteros a int, "tabla":

delete[] tabla;

Veamos el código de un ejemplo completo:

#include <iostream>
using namespace std;

int main() {
   int **tabla;
   int n = 134;
   int m = 231;
   int i;

   // Array de punteros a int:
   tabla = new int*[n];
   // n arrays de m ints
   for(i = 0; i < n; i++)
      tabla[i] = new int[m];
   tabla[21][33] = 123;
   cout << tabla[21][33] << endl;
   // Liberar memoria:
   for(i = 0; i < n; i++) delete[] tabla[i];
   delete[] tabla;

   return 0;
}

Pero no tenemos por qué limitarnos a arrays de dos dimensiones, con un puntero de este tipo:

int ***array;

Podemos crear un array dinámico de tres dimensiones, usando un método análogo.

Y generalizando, podemos crear arrays de cualquier dimensión.

Tampoco tenemos que limitarnos a arrays regulares.

Veamos un ejemplo de tabla triangular:

Crear una tabla para almacenar las distancias entre un conjunto de ciudades, igual que hacen los mapas de carreteras.

Para que sea más sencillo usaremos sólo cinco ciudades:

Evidentemente, la distancia de la Ciudad A a la Ciudad B es la misma que la de la Ciudad B a la Ciudad A, así que no hace falta almacenar ambas. Igualmente, la distancia de una ciudad a sí misma es siempre 0, otro valor que no necesitamos.

Si tenemos n ciudades y usamos un array para almacenar las distancias necesitamos:

n*n = 5*5 = 25 casillas.

Sin embargo, si usamos un array triangular:

n*(n-1)/2 = 5*4/2 = 10 casillas.

Veamos cómo implementar esta tabla:

#include <iostream>
using namespace std;

#define NCIUDADES 5
#define CIUDAD_A 0
#define CIUDAD_B 1
#define CIUDAD_C 2
#define CIUDAD_D 3
#define CIUDAD_E 4

// Variable global para tabla de distancias:
int **tabla;
// Prototipo para  calcular la distancia entre dos ciudades:
int Distancia(int A, int B);

int main() {
   int i;

   // Primer subíndice de A a D
   tabla = new int*[NCIUDADES-1];
   // Segundo subíndice de B a E,
   // define 4 arrays de 4, 3, 2 y 1 elemento:
   for(i = 0; i < NCIUDADES-1; i++)
      tabla[i] = new int[NCIUDADES-1-i]; // 4, 3, 2, 1
   // Inicialización:
   tabla[CIUDAD_A][CIUDAD_B-CIUDAD_A-1] = 154;
   tabla[CIUDAD_A][CIUDAD_C-CIUDAD_A-1] = 245;
   tabla[CIUDAD_A][CIUDAD_D-CIUDAD_A-1] = 54;
   tabla[CIUDAD_A][CIUDAD_E-CIUDAD_A-1] = 452;
   tabla[CIUDAD_B][CIUDAD_C-CIUDAD_B-1] = 354;
   tabla[CIUDAD_B][CIUDAD_D-CIUDAD_B-1] = 125;
   tabla[CIUDAD_B][CIUDAD_E-CIUDAD_B-1] = 133;
   tabla[CIUDAD_C][CIUDAD_D-CIUDAD_C-1] = 152;
   tabla[CIUDAD_C][CIUDAD_E-CIUDAD_C-1] = 232;
   tabla[CIUDAD_D][CIUDAD_E-CIUDAD_D-1] = 110;

   // Ejemplos:
   cout << "Distancia A-D: "
        << Distancia(CIUDAD_A, CIUDAD_D) << endl;
   cout << "Distancia B-E: "
        << Distancia(CIUDAD_B, CIUDAD_E) << endl;
   cout << "Distancia D-A: "
        << Distancia(CIUDAD_D, CIUDAD_A) << endl;
   cout << "Distancia B-B: "
        << Distancia(CIUDAD_B, CIUDAD_B) << endl;
   cout << "Distancia E-D: "
        << Distancia(CIUDAD_E, CIUDAD_D) << endl;

   // Liberar memoria dinámica:
   for(i = 0; i < NCIUDADES-1; i++) delete[] tabla[i];
   delete[] tabla;

   return 0;
}

int Distancia(int A, int B) {
   int aux;

   // Si ambos subíndices son iguales, volver con cero:
   if(A == B) return 0;
   // Si el subíndice A es mayor que B, intercambiarlos:
   if(A > B) {
      aux = A;
      A = B;
      B = aux;
   }
   return tabla[A][B-A-1];
}

Notas sobre el ejemplo:

Observa el modo en que se usa la directiva #define para declarar constantes. Aunque en C++ es preferible usar variables constantes, como este tema aún no lo hemos visto, seguiremos usando macros.

Efectivamente, para este ejemplo se complica el acceso a los elementos de la tabla ya que tenemos que realizar operaciones para acceder a la segunda coordenada. Sin embargo piensa en el ahorro de memoria que supone cuando se usan muchas ciudades, por ejemplo, para 100 ciudades:

Tabla normal 100*100 = 10000 elementos.

Tabla triangular 100*99/2 = 4950 elementos.

Hemos declarado el puntero a tabla como global, de este modo será accesible desde main y desde Distancia. Si la hubiéramos declarado local en main, tendríamos que pasarla como parámetro a la función.

Observa el método usado para el intercambio de valores de dos variables. Si no se usa la variable "aux", no es posible intercambiar valores. Podríamos haber definido una función para esta acción, "Intercambio", pero lo dejaré como ejercicio.

Problemas

1. Usando como base el ejemplo anterior, realizar los siguientes cambios:
   • Modificar el código para que "tabla" sea una variable local de main.
   • Definir una función con el prototipo void AsignarDistancia(int**, int, int, int);, para asignar valores a distancias entre dos ciudades. El primer parámetro será la tabla de distancias, los dos siguientes parámetros serán identificadores de dos ciudades y el cuarto la distancia entre dichas ciudades.
     Por ejemplo AsignarDistancia(tabla, CIUDAD_E, CIUDAD_B, 123);.
   • Definir una función con el prototipo void Intercambio(int &, int &);, para intercambiar los contenidos de dos variables enteras.

   Realizar los cambios necesarios en el programa para que se usen estas nuevas funciones siempre que sea posible.

2. Ordenar un array de float aleatorios, para ello, crear un array dinámico con el mismo número de elementos que contenga valores enteros, cada uno de ellos será un índice del array de floats a ordenar.
   Ordenar los índices en este segundo array según el orden ascendente del array de números, pero sin modificar el orden ni el contenido del array de floats, que debe permanecer constante.
   Por ejemplo, si el array dado contiene los valores: 1.32, 4.21, 2.33, 0.23, 8.35, 2.32, se debe crear un segundo array de enteros dinámico, que una vez ordenado debe contener los valores: 3, 0, 5, 2, 1, 4.
   Para ordenar el array de enteros se debe usar la función qsort.
3. Modificar el programa anterior para añadir un segundo array de enteros que contenga los índices del array de floats ordenados de mayor a menor, además del que ya tenía, con los índices de los floats ordenados de menor a mayor.
4. Concatenar dos arrays de enteros ordenados en un tercero, de modo que contenga los elementos de los dos, mezclados de modo que se mantenga el orden.
   Por ejemplo:
   

       int a1[] = {1,3,4,7,8,9,12,15,16,17,21,23,25};
       int a2[] = {2,5,6,10,11,13,14,18,19,20,22,24,26,27,28};
   

   El resultado debe ser un tercer array con todos los elementos presentes en los dos arrays dados, y manteniendo el orden ascendente.