Contenedores de datos complejos

01Por qué agrupar datos

Guardar las 1000 muestras de un osciloscopio en mil variables sueltas es imposible de manejar. Guardar una medición en tres variables sueltas —tensión, corriente e instante— obliga a pasarlas siempre juntas y a no mezclarlas nunca. Los contenedores de datos resuelven las dos cosas: el arreglo agrupa muchos datos del mismo tipo y la estructura agrupa datos distintos que describen una misma cosa.

02Arreglos: datos en fila

Un arreglo ocupa posiciones contiguas. Si empieza en la dirección base y cada elemento ocupa sizeof(T) bytes, el elemento i está en:

La cuenta es una multiplicación y una suma, sin importar el tamaño del arreglo: acceder a v[999] tarda lo mismo que acceder a v[0]. Y C no verifica que el índice esté dentro del arreglo: v[10] en un arreglo de 10 elementos calcula la dirección y lee o escribe lo que haya ahí, que es otra variable.

Las matrices se guardan también en fila, fila por fila (orden por filas). Para una matriz de F × C:

03Cadenas de caracteres

C no tiene un tipo cadena: una cadena es un arreglo de char que termina con el carácter nulo '\0' (valor 0). Todas las funciones de <string.h> recorren hasta encontrarlo; por eso char s[6] alcanza para "Hola!" pero no para "Hola!!".

char s[8] = "R1=4k7";   // 'R' '1' '=' '4' 'k' '7' '\0' y un byte libre
strlen(s);                  // 6: no cuenta el '\0'
sizeof(s);                  // 8: el arreglo entero
strcpy(s, "R10=100k");     // ¡9 bytes en 8! desborda
snprintf(s, sizeof s, "%s", "R10=100k");  // copia 7 y cierra con '\0'

04Punteros: variables que guardan direcciones

Un puntero es una variable cuyo contenido es una dirección de memoria. Dos operadores lo manejan todo: &x da la dirección de x y *p da lo que hay en la dirección guardada en p.

int x = 10;
int *p = &x;     // p guarda la dirección de x
*p = 25;          // escribe en x: ahora x vale 25
int v[4] = {3, 1, 4, 1};
int *q = v;        // el nombre del arreglo es la dirección de v[0]
*(q + 2) == v[2]    // verdadero: v[i] se define como *(v + i)

La aritmética de punteros cuenta en elementos, no en bytes: q + 2 avanza 2 · sizeof(int) bytes. Es exactamente la fórmula de la sección 2, y por eso en C los arreglos y los punteros se usan casi indistintamente. Un puntero que no apunta a nada se iguala a NULL, y antes de usar *p hay que estar seguro de que p apunta a algo válido.

05Estructuras: datos distintos que van juntos

typedef struct {
    float    tension;    // V
    float    corriente;  // A
    uint32_t instante;   // ms desde el arranque
} Medicion;

Medicion m = { 4.98f, 0.021f, 1500 };
Medicion tabla[100];         // arreglo de estructuras
tabla[3].tension = 5.01f;
Medicion *pm = &tabla[3];
pm->corriente = 0.02f;        // -> es (*pm).corriente

Una estructura se puede copiar con =, pasar a una función y devolver. Como se pasa por valor, con estructuras grandes conviene pasar un puntero, y const si la función no la modifica.

Hay un detalle que sorprende: el relleno. Muchos procesadores leen un dato de 4 bytes más rápido, o sólo pueden leerlo, si su dirección es múltiplo de 4. El compilador agrega bytes vacíos entre campos para alinearlos. struct { char a; int32_t b; } ocupa 8 bytes, no 5. En el laboratorio de arriba, la opción Estructura con relleno lo muestra, y muestra también que ordenar los campos de mayor a menor reduce el desperdicio.

06Memoria dinámica

Las variables locales viven en la pila y tienen tamaño fijo, decidido al compilar. Cuando la cantidad de datos se conoce recién al ejecutar, se pide memoria al montículo (heap):

int n;
scanf("%d", &n);
double *muestras = malloc(n * sizeof *muestras);
if (muestras == NULL) { /* no hubo memoria: avisar y salir */ }
...                                 // se usa como un arreglo: muestras[i]
free(muestras);                     // devolverla cuando ya no hace falta
muestras = NULL;

Lo que se pide con malloc vive hasta que se libera con free, aunque la función que lo pidió haya terminado. Olvidarse de liberar es una fuga de memoria; usar la memoria después de liberarla, un error que puede no manifestarse durante semanas. En microcontroladores chicos se evita la memoria dinámica: con pocos KiB la fragmentación la vuelve impredecible.

07Estructuras enlazadas

Un arreglo no puede crecer ni insertar en el medio sin correr todo lo que sigue. Una lista enlazada guarda cada dato en un nodo aparte, pedido con malloc, y cada nodo tiene un puntero al siguiente:

typedef struct nodo {
    int valor;
    struct nodo *sig;       // NULL en el último
} Nodo;

/* insertar al principio: O(1), no se mueve ningún otro dato */
Nodo *insertar(Nodo *cabeza, int v)
{
    Nodo *n = malloc(sizeof *n);
    if (!n) return cabeza;
    n->valor = v;
    n->sig = cabeza;
    return n;
}

Pilas, colas, árboles y grafos se construyen con la misma idea. No hay estructura mejor en general: se elige según qué operación se hace más seguido.

08Archivos: el contenedor que sobrevive al programa

Todo lo anterior desaparece al terminar el programa. Para guardar datos se usan archivos, a través de un puntero a FILE:

FILE *f = fopen("mediciones.csv", "w");
if (f == NULL) { perror("mediciones.csv"); return 1; }
for (int i = 0; i < n; i++)
    fprintf(f, "%u;%.3f;%.4f\n", tabla[i].instante, tabla[i].tension, tabla[i].corriente);
fclose(f);

Un archivo de texto como ese se abre con cualquier planilla de cálculo. Uno binario, escrito con fwrite(tabla, sizeof(Medicion), n, f), ocupa menos y se lee más rápido, pero depende del tamaño de los tipos, del relleno y del orden de los bytes de la máquina que lo escribió.

09En el laboratorio

10Errores frecuentes

• Recorrer con i <= n un arreglo de n elementos: el último índice válido es n − 1.
• Olvidar el lugar del '\0' al dimensionar una cadena.
• Comparar cadenas con ==: compara direcciones. Se usa strcmp, que devuelve 0 si son iguales.
• Usar un puntero sin inicializar o después de free.
• Calcular el tamaño de un arreglo con sizeof dentro de una función que lo recibió como parámetro.
• Suponer que sizeof de una estructura es la suma de sus campos.

11Autoevaluación

12Para ampliar

• Brian W. Kernighan y Dennis M. Ritchie. El lenguaje de programación C. 2.ª ed., Prentice Hall Hispanoamericana, 1991. Los capítulos 5 (apuntadores y arreglos) y 6 (estructuras) siguen siendo la mejor explicación breve.
• Luis Joyanes Aguilar e Ignacio Zahonero Martínez. Programación en C. Metodología, algoritmos y estructura de datos. 2.ª ed., McGraw-Hill, 2005. Listas, pilas, colas y archivos implementados en C, en castellano.
• Niklaus Wirth. Algoritmos + estructuras de datos = programas. Ediciones del Castillo, 1980. La elección de la estructura de datos como parte del diseño del algoritmo.
• Robert Sedgewick. Algorithms in C. 3.ª ed., Addison-Wesley, 1998 (en inglés). Estructuras de datos y algoritmos implementados en C, con análisis de costo.