Complex data containers

01Why group data

Storing the 1000 samples of an oscilloscope in a thousand separate variables is impossible to manage. Storing a measurement in three separate variables —voltage, current and time instant— forces you to always pass them together and never mix them up. Data containers solve both problems: the array groups many data of the same type and the structure groups different data that describe one and the same thing.

02Arrays: data in a row

An array occupies contiguous positions. If it starts at address base and each element takes up sizeof(T) bytes, element i is at:

The calculation is one multiplication and one addition, regardless of the size of the array: accessing v[999] takes the same time as accessing v[0]. And C does not check that the index is within the array: v[10] in a 10-element array calculates the address and reads or writes whatever is there, which is another variable.

Matrices are also stored in a row, row by row (row-major order). For an R × C matrix:

03Character strings

C has no string type: a string is an array of char that ends with the null character '\0' (value 0). All the functions in <string.h> scan until they find it; that is why char s[6] is enough for "Hello" but not for "Hello!".

char s[8] = "R1=4k7";   // 'R' '1' '=' '4' 'k' '7' '\0' and one spare byte
strlen(s);                  // 6: it does not count the '\0'
sizeof(s);                  // 8: the whole array
strcpy(s, "R10=100k");     // 9 bytes into 8! overflow
snprintf(s, sizeof s, "%s", "R10=100k");  // copies 7 and terminates with '\0'

04Pointers: variables that store addresses

A pointer is a variable whose contents are a memory address. Two operators handle everything: &x gives the address of x and *p gives what is at the address stored in p.

int x = 10;
int *p = &x;     // p stores the address of x
*p = 25;          // writes to x: now x is 25
int v[4] = {3, 1, 4, 1};
int *q = v;        // the array name is the address of v[0]
*(q + 2) == v[2]    // true: v[i] is defined as *(v + i)

Pointer arithmetic counts in elements, not in bytes: q + 2 advances 2 · sizeof(int) bytes. It is exactly the formula from section 2, and that is why in C arrays and pointers are used almost interchangeably. A pointer that points to nothing is set to NULL, and before using *p you must be sure that p points to something valid.

05Structures: different data that belong together

typedef struct {
    float    voltage;   // V
    float    current;   // A
    uint32_t timestamp; // ms since startup
} Measurement;

Measurement m = { 4.98f, 0.021f, 1500 };
Measurement table[100];         // array of structures
table[3].voltage = 5.01f;
Measurement *pm = &table[3];
pm->current = 0.02f;        // -> is (*pm).current

A structure can be copied with =, passed to a function and returned. Since it is passed by value, with large structures it is better to pass a pointer, and const if the function does not modify it.

There is a detail that comes as a surprise: padding. Many processors read a 4-byte item faster, or can only read it, if its address is a multiple of 4. The compiler adds empty bytes between fields to align them. struct { char a; int32_t b; } takes up 8 bytes, not 5. In the lab above, the Structure with padding option shows this, and it also shows that ordering the fields from largest to smallest reduces the waste.

06Dynamic memory

Local variables live on the stack and have a fixed size, decided at compile time. When the amount of data is only known at run time, memory is requested from the heap (also called the free store):

int n;
scanf("%d", &n);
double *samples = malloc(n * sizeof *samples);
if (samples == NULL) { /* out of memory: report and exit */ }
...                                 // used like an array: samples[i]
free(samples);                     // give it back when it is no longer needed
samples = NULL;

What is requested with malloc lives until it is released with free, even if the function that requested it has finished. Forgetting to release it is a memory leak; using the memory after releasing it is an error that may not show up for weeks. On small microcontrollers dynamic memory is avoided: with only a few KiB, fragmentation makes it unpredictable.

07Linked structures

An array cannot grow or insert in the middle without shifting everything that follows. A linked list stores each item in a separate node, requested with malloc, and each node has a pointer to the next:

typedef struct node {
    int value;
    struct node *next;       // NULL in the last one
} Node;

/* insert at the beginning: O(1), no other data is moved */
Node *insert(Node *head, int v)
{
    Node *n = malloc(sizeof *n);
    if (!n) return head;
    n->value = v;
    n->next = head;
    return n;
}

Stacks, queues, trees and graphs are built with the same idea. No structure is better in general: you choose according to which operation is performed most often.

08Files: the container that outlives the program

Everything above disappears when the program ends. To save data, files are used, through a pointer to FILE:

FILE *f = fopen("measurements.csv", "w");
if (f == NULL) { perror("measurements.csv"); return 1; }
for (int i = 0; i < n; i++)
    fprintf(f, "%u;%.3f;%.4f\n", table[i].timestamp, table[i].voltage, table[i].current);
fclose(f);

A text file like that can be opened with any spreadsheet. A binary one, written with fwrite(table, sizeof(Measurement), n, f), takes less space and is read faster, but depends on the size of the types, on padding and on the byte order of the machine that wrote it.

09In the lab

10Common mistakes

• Traversing with i <= n an array of n elements: the last valid index is n − 1.
• Forgetting the space for the '\0' when sizing a string.
• Comparing strings with ==: it compares addresses. Use strcmp, which returns 0 if they are equal.
• Using an uninitialized pointer or one after free.
• Computing the size of an array with sizeof inside a function that received it as a parameter.
• Assuming that the sizeof of a structure is the sum of its fields.

11Self-assessment

12Further reading

• Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language. 2nd ed. (Spanish edition, “El lenguaje de programación C”), Prentice Hall Hispanoamericana, 1991. Chapters 5 (pointers and arrays) and 6 (structures) are still the best short explanation.
• Luis Joyanes Aguilar and Ignacio Zahonero Martínez. Programación en C. Metodología, algoritmos y estructura de datos. 2nd ed., McGraw-Hill, 2005 (in Spanish). Lists, stacks, queues and files implemented in C, in Spanish.
• Niklaus Wirth. Algorithms + Data Structures = Programs. Spanish edition (“Algoritmos + estructuras de datos = programas”), Ediciones del Castillo, 1980. The choice of data structure as part of algorithm design.
• Robert Sedgewick. Algorithms in C. 3rd ed., Addison-Wesley, 1998. Data structures and algorithms implemented in C, with cost analysis.