Vectores, matrices y registros

Guardar la nota de un alumno se hace con una variable. Guardar las notas de cien alumnos con cien variables sueltas es inviable: habría que inventarse cien nombres y escribir cien veces cada operación. La solución es el vector, también llamado array o arreglo: una única variable capaz de contener muchos valores del mismo tipo, cada uno en su posición numerada.

La imagen que mejor lo describe es la de una fila de casilleros pegados unos a otros, con un número pintado encima de cada uno. Todos los casilleros son del mismo tamaño y guardan la misma clase de cosa, el conjunto tiene un solo nombre, y para llegar a uno concreto basta con decir el nombre de la fila y el número del casillero.

entero notas[5]                  // reserva 5 casillas para enteros

notas[0] = 7
notas[1] = 4
notas[2] = 9
notas[3] = 6
notas[4] = 8

escribir(notas[2])               // escribe 9

// Tambien se puede crear y rellenar de una vez:
entero temasPorBloque[4] = { 9, 5, 12, 7 }

• Línea 1: se declara el vector diciendo tres cosas: de qué tipo son sus elementos, cómo se llama y cuántas casillas tiene.
• Líneas 3 a 7: se asigna un valor a cada posición. El número entre corchetes es el índice, que indica a qué casilla se accede.
• Línea 9: se consulta una casilla concreta. La expresión notas[2] se comporta exactamente igual que una variable entera normal.
• Línea 12: la forma abreviada, que declara y rellena en la misma línea.

Un vector tiene dos características que lo definen y que conviene retener. Es homogéneo: todos sus elementos son del mismo tipo, y no se pueden mezclar enteros con textos. Y en los lenguajes clásicos tiene tamaño fijo: se decide cuántas casillas tendrá al crearlo y no crece después.

Un vector es una colección de elementos del mismo tipo, con un solo nombre y acceso por posición. Su ventaja es que permite tratar muchos datos con un bucle en vez de una instrucción por dato.

Aquí está la peculiaridad que más desconcierta a quien empieza y que más se pregunta. En la mayoría de lenguajes (C, C++, Java, C#, Python, JavaScript), la primera casilla de un vector no es la número uno: es la número cero. Un vector de cinco elementos tiene índices 0, 1, 2, 3 y 4, y el índice 5 no existe.

          notas
       +---+---+---+---+---+
valor  | 7 | 4 | 9 | 6 | 8 |
       +---+---+---+---+---+
indice   0   1   2   3   4

  5 elementos, indices del 0 al 4.
  El primero es notas[0] y el ultimo es notas[4], no notas[5].

El motivo no es un capricho. El índice no indica el número de orden del elemento, sino cuántas casillas hay que avanzar desde el principio del vector para llegar a él. Al primer elemento no hay que avanzarle nada, así que su desplazamiento es cero. Al segundo hay que avanzarle una casilla, y de ahí su índice uno.

De ahí sale la fórmula que conviene memorizar: en un vector de n elementos, el último índice válido es n menos uno. Es la regla que evita casi todos los errores de este apartado.

No todos los lenguajes hacen lo mismo. Fortran, Lua, MATLAB y COBOL numeran desde uno, y alguno permite incluso elegir el índice inicial. Pero en examen, salvo que se diga otra cosa expresamente, se asume la numeración desde cero, que es la de la familia de C y la de los lenguajes más usados.

En un vector de n elementos los índices válidos van de 0 a n menos uno. El índice no es el número de orden, es cuántas posiciones hay que avanzar desde el principio.

El vector y el bucle for están hechos el uno para el otro, y esta es la combinación más repetida de toda la programación. La razón es que la variable de control del bucle sirve directamente como índice: si se hace que vaya tomando los valores 0, 1, 2 y así sucesivamente, el cuerpo del bucle pasa por todas las casillas sin escribir ninguna a mano.

entero notas[5] = { 7, 4, 9, 6, 8 }
entero suma = 0

for (entero i = 0; i < 5; i++) {
    suma = suma + notas[i]
}

real media = suma / 5.0
escribir(media)          // 6.8

• Línea 2: el acumulador se inicializa a cero ANTES del bucle. Dentro se reiniciaría en cada vuelta y al final solo tendría la última nota.
• Línea 4: el bucle empieza en 0, que es el índice de la primera casilla, y avanza de uno en uno.
• Línea 5: en cada vuelta, notas[i] es una casilla distinta. Con i valiendo 0 es el 7, con 1 es el 4, y así hasta el 8.
• La condición es i < 5, no i <= 5. Con cinco elementos, el último índice válido es el 4, y con i <= 5 el bucle intentaría acceder a notas[5], que no existe.
• Línea 8: al dividir se usa 5.0 y no 5, para forzar una división real. Con dos enteros el resultado se habría truncado a 6.

En lugar del número 5 escrito a mano conviene usar la longitud real del vector, que todos los lenguajes ofrecen de alguna forma. Así, si mañana el vector pasa a tener ocho elementos, el bucle sigue funcionando sin tocarlo. Escribir el tamaño a mano en la condición es una de las fuentes de error más habituales.

Muchos lenguajes ofrecen además el recorrido for-each, del estilo de «para cada nota del vector notas», que pasa por todos los elementos sin manejar índices. Es más seguro, porque hace imposible salirse de rango, pero solo sirve cuando hay que recorrer el vector entero y no importa la posición de cada elemento.

El patrón estándar para recorrer un vector de n elementos es un for que empieza en 0 y sigue mientras el índice sea MENOR que n. Con menor o igual se accede a una casilla que no existe.

Acceder a una posición que no existe es el error clásico de los vectores. Se conoce como índice fuera de rango, o desbordamiento de límites, y aparece de tres maneras: usando un índice negativo, usando uno igual o mayor que el número de elementos, o recorriendo el vector con una condición mal puesta.

entero notas[5] = { 7, 4, 9, 6, 8 }

notas[5]     // FUERA DE RANGO: el ultimo indice valido es el 4
notas[-1]    // FUERA DE RANGO: no existen indices negativos

// El caso mas frecuente, en la condicion del bucle:
for (entero i = 0; i <= 5; i++) {
    escribir(notas[i])       // en la ultima vuelta accede a notas[5]
}

// Correcto:
for (entero i = 0; i < 5; i++) {
    escribir(notas[i])
}

A ese fallo de contar uno de más o uno de menos se le llama error de desplazamiento en uno, o error off-by-one, y casi siempre nace de la misma confusión: pensar que el vector va del 1 al 5 en vez de del 0 al 4.

Lo que ocurre al salirse depende del lenguaje, y la diferencia es importante. Los lenguajes con comprobación de límites, como Java, C#, Python o JavaScript, detectan el acceso indebido y detienen el programa con un error claro. Los que no la hacen, señaladamente C y C++, no comprueban nada: leen o escriben la memoria que haya en ese punto, que pertenece a otra cosa.

Esa segunda situación es mucho peor de lo que parece. El programa no da error: sigue funcionando con un dato basura, o peor aún, machaca una variable ajena. Es además el origen de una familia entera de vulnerabilidades de seguridad conocida como desbordamiento de búfer, que consiste precisamente en escribir más allá del final de un vector para alterar memoria que no correspondía.

Salirse de rango detiene el programa en los lenguajes que comprueban límites, y en los que no lo hacen produce datos corruptos sin ningún aviso. La segunda situación es más peligrosa precisamente porque no se nota.

Un vector es una fila de casilleros. Cuando los datos se organizan de forma natural en filas y columnas, como una tabla, hace falta una dimensión más: eso es una matriz, o vector bidimensional. Ahora cada casilla se localiza con dos índices, el de la fila y el de la columna.

  resultados[3][4]   ->  3 alumnos (filas) x 4 test (columnas)

              test 0   test 1   test 2   test 3
            +--------+--------+--------+--------+
 alumno 0   |   7    |   4    |   9    |   6    |
            +--------+--------+--------+--------+
 alumno 1   |   5    |   8    |   8    |   7    |
            +--------+--------+--------+--------+
 alumno 2   |   9    |   9    |   6    |  10    |
            +--------+--------+--------+--------+

  resultados[1][2] vale 8: fila 1, columna 2.
  Las dos dimensiones empiezan tambien en cero.

Para recorrer una matriz entera hace falta un bucle dentro de otro, lo que se llama bucles anidados. El de fuera avanza por las filas y el de dentro, por las columnas de la fila actual. La consecuencia es que el bucle interior se recorre entero por cada vuelta del exterior.

entero resultados[3][4]
entero suma

for (entero fila = 0; fila < 3; fila++) {
    suma = 0
    for (entero col = 0; col < 4; col++) {
        suma = suma + resultados[fila][col]
    }
    escribir("Media del alumno " + fila + ": " + (suma / 4.0))
}

• El bucle exterior recorre los tres alumnos, uno por vuelta.
• El acumulador se pone a cero al principio de cada fila, no antes de todo: cada alumno necesita su propia suma.
• El bucle interior recorre los cuatro test de ese alumno y los va sumando.
• La línea de escribir está fuera del bucle interior pero dentro del exterior, así que se ejecuta una vez por alumno, cuando su suma ya está completa. Si estuviera dentro del interior escribiría doce veces.
• En total, el cuerpo del bucle interior se ejecuta 3 por 4, es decir, doce veces.

Una matriz necesita tantos bucles anidados como dimensiones tenga. Dónde se coloca cada instrucción respecto a las llaves de los dos bucles decide cuántas veces se ejecuta, y ahí está el error habitual.

El vector resuelve un problema: guardar muchos datos iguales. Pero hay otro problema distinto. Un alumno no es un dato: es un nombre, un correo, una fecha de alta y una nota media, cosas de tipos diferentes que describen todas al mismo elemento. Guardarlas en variables sueltas funciona hasta que hay que manejar doscientos alumnos y mantener a mano la correspondencia entre el nombre número 7 y la nota número 7.

Para eso está el registro, llamado también estructura o record. Es un tipo de dato nuevo, creado por el programador, que agrupa bajo un solo nombre varios datos de tipos distintos. Cada uno de esos datos se llama campo, y se accede a él por su nombre, no por un número de posición.

// Se define el tipo: un molde, todavia sin datos
registro Alumno {
    cadena  nombre
    entero  temasCompletados
    real    notaMedia
    booleano activo
}

// Se crea una variable de ese tipo y se rellenan sus campos
Alumno ana
ana.nombre           = "Ana"
ana.temasCompletados = 12
ana.notaMedia        = 6.8
ana.activo           = true

escribir(ana.notaMedia)      // 6.8

• Líneas 2 a 7: se define el tipo Alumno. Esto es solo un molde: describe qué campos tendrá cualquier alumno, pero no crea ningún alumno concreto ni reserva memoria para datos.
• Los cuatro campos son de cuatro tipos distintos, y eso es justamente lo que un vector no permite.
• Línea 10: aquí sí se crea una variable concreta del tipo Alumno.
• Líneas 11 a 14: se accede a cada campo con el nombre de la variable, un punto y el nombre del campo. Ese punto es el operador de acceso a campo.
• Cada campo se comporta como una variable normal de su tipo: ana.notaMedia se puede sumar, comparar o pasar a una función igual que cualquier real.

La diferencia con el vector es la clave de este apartado y se resume en una frase: un vector agrupa muchas cosas iguales y un registro agrupa cosas distintas que describen a un mismo elemento. Un vector de notas contiene cinco notas; un registro de alumno contiene un nombre, un contador y una nota.

Lo habitual es combinar los dos, y ahí es donde el conjunto empieza a ser útil de verdad: un vector de registros. Alumno curso[200] declara doscientos alumnos, cada uno con todos sus campos, y curso[7].notaMedia se lee de izquierda a derecha como «del alumno de la posición 7, su nota media». Un registro puede además contener a su vez otro registro o un vector como campo.

El vector es homogéneo y se accede por índice; el registro es heterogéneo y se accede por nombre de campo. Combinados en un vector de registros son la base de cualquier programa que maneje listas de elementos con varias propiedades.

Un vector ocupa posiciones contiguas de memoria, es decir, sus elementos están pegados unos a otros sin huecos. Esa es la razón de que el acceso por índice sea inmediato: conociendo la dirección donde empieza el vector y el tamaño de cada elemento, la dirección de cualquier casilla se obtiene con una multiplicación y una suma, sin recorrer nada.

direccion del elemento i = direccion base + (i * tamaño de cada elemento)

  Si «notas» empieza en la direccion 1000 y cada entero ocupa 4 bytes:

     notas[0] -> 1000 + (0 * 4) = 1000
     notas[1] -> 1000 + (1 * 4) = 1004
     notas[3] -> 1000 + (3 * 4) = 1012

  Aqui se ve por que el primer indice es el 0: multiplica por cero
  porque no hay que desplazarse nada desde el principio.

La memoria es lineal, así que una matriz, que es bidimensional, tiene que aplanarse para caber en ella. Hay dos formas de hacerlo: por filas, colocando una fila entera detrás de otra, que es lo que hacen C, C++, Java y Python; y por columnas, que es lo que hacen Fortran y MATLAB. La consecuencia práctica es de rendimiento: recorrer una matriz en el mismo orden en que está almacenada aprovecha mucho mejor la caché del procesador que hacerlo en el orden contrario.

En cuanto al tamaño, el vector estático fija su número de elementos al escribir el programa y no cambia nunca. El vector dinámico reserva su memoria durante la ejecución, cuando ya se sabe cuántos elementos harán falta, y algunos lenguajes ofrecen además colecciones que crecen solas conforme se les añaden elementos.

Ese crecimiento automático no es gratis: cuando la colección se queda sin sitio, reserva un bloque mayor, copia todo lo que tenía y libera el anterior. Por eso una colección que crece sola es cómoda pero más cara que un vector de tamaño conocido de antemano.

La memoria contigua es lo que da al vector su acceso directo por índice, y es también la razón de que no pueda crecer sin más: para añadir una casilla al final tendría que estar libre justo la memoria siguiente.