Arrays de Estructuras de Datos

Palabras clave: Datos estructurados, Registros, Arrays.

Preguntas de repaso

¿Qué es un array?
¿Qué es un índice y qué es un término?
Haz el código que imprima todos los elementos de un array de reales.

No sigas si no conoces las respuestas.

1. Listas complejas

Hemos definido los arrays como listas de valores, todos del mismo tipo ya sea simple o estructurado, aunque todos los ejemplos que se desarrollaron fueron con tipos de dato simple.

Recuerda que un array se declara e inicializa en Processing como:

TipoDeDato[] var = new TipoDeDato[n];

En el lado izquierdo de = se declara la variable var, y en el lado derecho de = se hacen estas acciones:

se reserva memoria para n-valores de tipo TipoDeDato, y
se asigna a var la referencia de la dirección de memoria donde su ubicarán dichos valores.

Gráficamente esta es la situación:

Si TipoDeDato es un tipo de dato simple, la instrucción new reserva la memoria exacta de memoria. Por ejemplo, si el array es de enteros, como los enteros se guardan en el Stack y se sabe que un entero ocupa 32-bit, se reserva una memoria de \(n\times 32\)-bits. Una vez reservada la memoria exacta ya se puede trabajar con la variable var para modificar cada una de sus "casillas".

Gráficamente, para un array de enteros esta es la situación después de un new; en la que basta hacer var[i] para asignar o recuperar el valor de la posición i.

Pero si TipoDeDato es un dato estructurado un new no es suficiente para saber cuánta memoria se tendrá que reservar para almacenar los valores. Si el tipo de dato es estructurado cada término del array almacenará una referencia al Heap.

Gráficamente esta es la situación.

Después de un new, hemos creado una lista de referencias a localizaciones a la memoria en el Heap. Pero cada término var[i] no sabe aún a qué referenciar por lo que adopta el valor null (no referencia a nada). Como en estos casos recae en nosotros el control de la memoria: habrá que hacer un new para cada elemento de la lista. Mientras que no hagamos el correspondiente new para cada uno de los elementos de la lista no tendremos reservada la memoria exacta necesaria y por tanto no podremos trabajar adecuadamente con las variables var[i].

En esta lectura se explica esta última situación; en concreto, cómo debes de actuar cuando se trabaje con una lista de listas y una lista de registros.

2. Array de registros

2.1. Declaración

Para la declaración de una lista de registros primero tendremos que declarar un nuevo tipo de dato, el de cada uno de los elementos de la lista y que responde a un registro. Después se declara una variable, que llamaremos lista como un array de dichos registros.

class TipoRegistro {
    <tipo_de_dato> campo1;
    <tipo_de_dato> campo2;
    ...
}

TipoRegistro[] lista;

2.2. Inicialización

Para la inicialización de un array de registros primero tendremos que reservar memoria para la lista (para indicar cuántos elementos habrá) y después para cada uno de los elementos de la lista.

lista = new TipoRegistro[n]; // Reserva memoria para la lista, pero cada término referencia null.

for (int i=0; i<array.length; i++) {
    lista[i] = new TipoRegistro();  // Reserva memoria para el elemento i de la lista
}

Esta es su representación gráfica. La variable lista, después del new, almacena una referencia al lugar de la memoria donde de guardan n datos y cada uno de esos datos almacena, después del preceptivo new, una referencia al lugar de la memoria donde se guarda un registro.

Failed to generate image: dot failed: Error: <stdin>: syntax error in line 1 near 'º'

º

2.3. Asignación y recuperación de valores de los campos

Una vez reservados los espacios de memoria para la lista y cada uno de sus elementos podemos tratar lista[i] como una variable de tipo registro, y como para acceder a los campos de una variable de tipo registro se usa la notación punto, la expresión lista[i].campo permite acceder al campo campo del registro lista[i].

Mencionar a lista[i].campo en una expresión permite recuperar el valor de dicho campo y la instrucción de asignación lista[i].campo=valor; permite asignar un valor al campo campo del registro lista[i].

Lee las expresiones de derecha a izquierda: lista[i].campo hace referencia al campo campo del i-ésimo elemento de la lista lista.

Observa que puedes aprovechar el bucle de inicialización de los elementos de la lista, para inicializar los campos de cada registro.

for (int i=0; i<array.length; i++) {
    array[i] = new TipoRegistro();  // Reserva memoria para el elemento i de la lista
    array[i].campo1 = valor1;   // Asigna valor al primer campo del elemento i de la lista.
    array[i].campo1 = valor1;   // Asigna valor al segundo campo del elemento i de la lista.
    ...
}

Ejemplo 1. Un cielo estrellado con registros

Imagina que queremos realizar un cielo estrellado en la pantalla gráfica de Processing pero guardando las coordendas de cada punto luminoso. Es decir, queremos una lista de estrellas y de cada estrella conocemos su coordenada en la pantalla gráfica.

Aplicando los pasos anteriores, en primer lugar definimos "el tipo de dato" estrella

1
2
3
4 class Estrella {
    float x;
    float y;
}

para a continuación declarar una lista de ellas:

1 Estrella[] listaEstrellas;

Vamo a generar, por ejemplo, un total de 100 estrellas cada una colocada de forma aleatoria en la pantalla:

1
2
3
4
5
6
7 listaEstrellas = new Estrella[100];  // Reservamos espacio para 100 referencias de memoria.

for (int i=0; i<listaEstrellas.length; i++) {
    listaEstrellas[i] = new Estrella();  // Reserva memoria para el elemento i de la lista
    listaEstrellas[i].x = random(0,width);   // Asigna valor al campo x del elemnto i de la lista.
    listaEstrellas[i].y = random(0,height);   // Asigna valor al campo y del elemento i de la lista.
}

Por último mostramos las estrellas en la pantalla como un punto:

1
2
3 for (int i=0; i<listaEstrellas.length; i++) {
    point(listaEstrellas[i].x, listaEstrellas[i].y);
}

Basándote en el código anterior construye las siguientes funciones:

Añade a las estrellas un nuevo campo que se corresponda con la intensidad de luz que emite.
Una función que cree y reserve memoria para una lista de n-estrellas y para cada uno de sus elementos, donde n viene dado por el usuario (es parámetro de entrada).

Recuerda que una función que crea listas es una función que retorna una array.
Una función que asigne valores a una lista de estrellas creada. Sus valores serán aleatorios.

Recuerda que una función que asigne valores a una estructura de datos que ya existe es una función que modifica valores y, por tanto, la estructura de datos será un parámetro en la función.
Una función que muestre las estrellas en la ventana gráfica como puntos más o menos "gruesos" y luminosos en función de su intensidad.
Una función principal que invoque a las funciones anteriores, según el orden expuesto.

Compara tu solución con la mía. Este es mi programa completo:

Recuerda que no debes pulsar el icono hasta que tengas en firme una respuesta con la que comparar mi resultado.

Modifica el programa anterior para tener una versión animada donde las estrellas vayan en la misma dirección pero donde las estrellas más cercanas (las más intensas) vayan a una velocidad mayor.

Compara tu solución con la mía. Este es mi programa completo:

Recuerda que no debes pulsar el icono hasta que tengas en firme una respuesta con la que comparar mi resultado.

3. Array de array

3.1. Declaración

Para la declaración de una lista cuyos elementos son a su vez listas nos basamos en que un tipo de dato array es aquel que responde al patrón TipoDeDato[].

Así, si la declaración de una lista es

TipoDeDato[] lista;

y queremos que el TipoDeDato sea un array, es decir, responda al patrón TipoDeDato[], la declaración de una lista de listas será:

TipoDeDato[][] lista;

En la expresión TipoDeDato[][] lista distinguimos dos partes que coloreamos: TipoDeDato[] [] lista.

[] lista establece que lista es una variable de tipo array de algo,
y ese algo es una lista, pues TipoDeDato[] responde al patrón de un array.

3.2. Inicialización

Para la inicialización de una lista de listas primero tendremos que reservar memoria para la lista (para indicar cuántos elementos habrá en ella) y después habrá que reservar memoria para cada uno de los elementos de dicha lista (pues son listas).

Según el párrafo anterior, si se deseara una lista de n-elementos en una lista, y que cada uno de esos elementos contuvieran una lista de m-valores, en total se necesitaría memoria para \(n\times m\) valores. Dicha reserva se realizan con una sola instrucción:

lista = new TipoDeDato[n][m]; // Reserva memoria para nxm-valores

Esta es su representación gráfica. La variable lista, después del new, almacena una referencia al lugar de la memoria donde de guardan n datos y cada uno de esos datos almacena una referencia al lugar de la memoria donde se guarda otra lista de m datos.

Uno podría desear que cada uno de los n-elementos de la lista esté formado por otra lista cada cual con una longitud diferente. Por ejemplo, que el primer elemento esté formado por una lista de 2 elementos, que el segundo elemento esté formado por una lista de 13 elementos, que el tercer elemento esté formado por una lista de 7 elementos, y así sucesivamente. Este tipo de estructura de datos se puede realizar también utilizando solo arrays. Para ellos se deberá de realizar estos dos pasos:

establecer el número de lista que contendrá mediante la instrucción new TipoDeDato[n][].
indicar para cada uno de los términos de la lista de que longitud será la lista que "almacenará".

Ejemplo 2. Un array escalonado

Observa cómo se pueden construir una lista de listas de distinta longitud. En este caso es una lista de 2 elementos y cada uno es una lista. El primer elemento es una lista de 4 enteros y el segundo de 2 enteros.

1
2
3
4 int[][] arrayEscalonado = new int[3][];
arrayEscalonado[0] = new int[4];
arrayEscalonado[1] = new int[2];
arrayEscalonado[2] = new int[8];

Su representación gráfica es esta:

3.3. Asignación y recuperación de valores de los elementos

Una vez reservados los espacios de memoria para todos los elementos que componen las listas de la lista, utilizaremos el sistema de índices ya estudiado.

Si array[k] es el patrón básico para acceder el elemento k-ésimo de una array:

lista[i], responde al acceso del elemento i-ésimo de la lista (el cuál es otro array);
lista[i][j], responde al acceso del elemento j-ésimo de la lista lista[i].

Necesitamos dos índice para acceder a cada uno de los elementos en un array de arrays.

Recuerda que para recorrer los elementos de una lista se hacía:

for (int i=0; i<lista.length; i++) {
    acciones sobre lista[i]
}

pero como ahora lista[i] es otra lista, actuaremos sobre cada elemento utilizando este patrón:

for (int i=0; i<lista.length; i++) {
    for (int j=0; j<lista[i].length; j++) {
        acciones sobre lista[i][j]
    }
}

Cuando uses dos índices necesitarás 2 bucles, uno anidado en el otro. Por extensión, cuando uses k-índices necesitarás k-bucles anidados.

Cuando se conocen los elementos exactos que tendrá un array de arrays se puede realizar la reserva de memoria y asignación en una única instrucción:

TipoDeDato[][] variable = {
    {dato1, dato2, ..., datoN}
    {dato1, dato2, ..., datoM}
    ...
};

Ejemplo 3. Un cielo estrellado con lista de listas

Si contemplamos al información de una estrella como una lista de dos valores {x,y} cada estrella se puede modelar mediante una array de reales float[]. Desde esta perspectiva, una lista de estrellas es un array de float[]:

1 float[][] listaEstrellas;

Vamos a generar, por ejemplo, un total de 100 estrellas y cada una colocada de forma aleatoria en la pantalla. Empezamos reservando la memoria para todos los datos.

1 listaEstrellas = new float[100][2];

El primer corchete representa el número de elementos que contendrá la lista (100 estrellas), y el segundo corchete representa el número de elementos que contendrá cada uno de los elementos de la lista (2 valores reales).

Para asignar valores recurrimos a una estructura repetitiva anidada:

1
2
3
4
5 for (int i=0; i<listaEstrellas.length; i++) {
    for (int j=0; j<listaEstrellas[i].length; j++) {
        listaEstrellas[i][j] = random(0, min(width, height));
    }
}

Por último las mostramos las estrellas como puntos en la pantalla:

1
2
3 for (int i=0; i<listaEstrellas.length; i++) {
    point(listaEstrellas[i][0], listaEstrellas[i][1]);
}

Basándote e el código anterior construye las siguientes funciones utilizando únicamente lista de listas:

Una función que cree y reserve memoria para una lista de n-estrellas, donde n viene dado por el usuario.
Una función que coloque las estrellas de forma aleatoria en la pantalla gráfica, para una lista de estrellas dada.
Una función que muestre las estrellas en la ventana gráfica.
Una función principal que invoque a las funciones anteriores, según el orden expuesto.

Compara tu solución con la mía. Este es mi programa completo:

Recuerda que no debes pulsar el icono hasta que tengas en firme una respuesta con la que comparar mi resultado.

3.4. Extendiendo la dimensión

Todo lo explicado en los apartados anteriores sobre lista de listas se puede extender a "más dimensiones". Por ejemplo, podemos trabajar con una lista que contenga lista y éstas a su vez contengan otras listas.

Para añadir una nueva "dimensión" (o lista) en el array basta añadir un nuevo conjunto de corchetes, [], y su índice correspondiente. Continuando con el ejemplo, se necesitará una variable "3-dimensional", en el sentido de que se requerirán 3 índices para poder acceder a un elemento. Una variable "3-D" se declarará como TipoDato[][][] variable;.

Para acceder a cada uno de los elementos se necesitarán tantos índices como corchetes se utilicen y tantos bucles (anidados) como índices para poder recorrer todos los elementos del array.

En el caso de conocer todos los elementos literales que contendrá el array existen algunos atajos. Por ejemplo,

int[][][] array3D =
{
    { {1,3}, {5,7,8} },
    { {0,2}, {4,6}, {8,10} },
    { {11,22}, {99,88,4}, {0,9}, {3,6,2} }
};

define un array cuyos elementos son listas de listas de enteros (de distinta longitud).

¿Cuál es el valor del elemento array3D[2][1][0]?

4. Repaso

Un array es una estructura formada por una lista de valores, todos del mismo tipo.
Antes de usar una variable de tipo array siempre hay que usar la instrucción new TipoDato[n], siendo n el número de elementos que contendrá la lista.
Si TipoDato es una estructura de datos, será necesiario realizar la correspondiente reserva de memoria para cada elemento de la lista.
- Si TipoDato es un registro, será: lista[i] = new TipoRegisto().
- Si TipoDato es un array se deberá de hacer un new para cada array; pero si se desea que todas tengan la mima longitud será: lista = new Tipo[n][m].
El acceso de cada elemento de lista[i] será acorde al tipo de dato:
- Si TipoDato es un registro, lista[i].campo permite acceder al campo campo del registro i-ésimo.
- Si TipoDato es un array, lista[i][j] permite acceder al elemento k-ésimo de la lista lista[i].