|
|
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.
Para ello se usan los punteros a punteros, y los arrays construidos de este modo se denominan arrays dinámicos.
Veamos la declaración de un puntero a puntero:
int **tabla;
"tabla" es un puntero que apunta a una variable 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;
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.h>
int main() {
int **tabla;
int n = 134;
int m = 231;
// Array de punteros a int:
tabla = new (*int)[n];
// n arrays de m ints
for(int i = 0; i < n; i++)
tabla[i] = new int[m];
tabla[21][33] = 123;
cout << tabla[21][33] << endl;
// Liberar memoria:
for(int 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:
| Ciudad A | 0 | ||||
| Ciudad B | 154 | 0 | |||
| Ciudad C | 254 | 354 | 0 | ||
| Ciudad D | 54 | 125 | 152 | 0 | |
| Ciudad E | 452 | 133 | 232 | 110 | 0 |
| Distancias | Ciudad A | Ciudad B | Ciudad C | Ciudad D | Ciudad E |
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 implemetar esta tabla:
#include <iostream.h>
#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() {
// 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(int 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(int 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.
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.
Usando como base el ejemplo anterior, separar dos nuevas funciones:
© Septiembre de 2.000 Salvador Pozo, salvador@c-con-clase.every1.net