Structures de données

Les structures

Regrouper des champs

Une structure regroupe plusieurs valeurs, de types éventuellement différents, sous un même nom. Chacune est un champ.

#include <stdio.h>

struct point
{
    int x;
    int y;
};

typedef struct point t_point;

void translater(t_point *p, int dx, int dy)
{
    p->x += dx;
    p->y += dy;
}

int main(void)
{
    t_point a = { 1, 2 };
    t_point b = a;          /* copie champ à champ */
    translater(&a, 10, 10);
    printf("a = (%d, %d), b = (%d, %d)\n", a.x, a.y, b.x, b.y);
    printf("sizeof (t_point) = %zu\n", sizeof (t_point));
    return 0;
}

a = (11, 12), b = (1, 2)
sizeof (t_point) = 8

• struct point est le nom du type. On peut lui donner un nom plus court avec typedef : typedef struct point t_point; fait de t_point un synonyme de struct point. Le préfixe t_ n'est qu'une convention, pour reconnaître un nom de type au premier coup d'œil.
• a.x désigne le champ x de la structure a.
• Quand on a un pointeur p sur une structure, p->x désigne le champ x de la structure pointée. C'est une abréviation de (*p).x ; les parenthèses sont nécessaires, car . est prioritaire sur *.
• L'affectation b = a copie toute la structure. Modifier a ensuite ne change pas b. Il en va de même quand on passe une structure à une fonction : elle reçoit une copie. Pour que translater modifie le point de l'appelant, il faut lui donner son adresse (chapitre 2).

Les structures récursives

Une liste chaînée est faite de maillons ; chaque maillon contient une valeur et l'adresse du maillon suivant. Une structure ne peut pas se contenir elle-même (elle serait de taille infinie), mais elle peut contenir un pointeur sur une structure de son type :

typedef struct s_liste *t_liste;

struct s_liste
{
    int     val;
    t_liste suivant;
};

Le typedef peut venir avant la définition de la structure : pour déclarer un pointeur sur struct s_liste, le compilateur n'a pas besoin de connaître ses champs, puisque tous les pointeurs ont la même taille.

Ici, le typedef ne nomme pas la structure, mais un pointeur sur elle. Une liste, c'est l'adresse de son premier maillon, et la liste vide est le pointeur NULL. C'est exactement la liste de Caml : NULL joue le rôle de [], et un maillon celui de x :: reste.

Les types abstraits

Cacher la représentation

On range chaque structure de données dans son propre module, comme au chapitre 1 : un en-tête qui annonce les opérations, un fichier source qui les définit. Le point important est ce qu'on met dans l'en-tête.

liste.h :

#ifndef LISTE_H
#define LISTE_H

#include <stddef.h>

typedef struct s_liste *t_liste;

#define liste_vide() (NULL)
#define est_vide(l) ((l) == NULL)

t_liste ajouter(int x, t_liste l);
int     tete(t_liste l);
t_liste queue(t_liste l);
size_t  longueur(t_liste l);
t_liste chercher(int x, t_liste l);
void    inserer(int x, t_liste *l);
void    detruire(t_liste l);

#endif

L'en-tête dit que t_liste est un pointeur sur une struct s_liste, mais pas ce que contient cette structure. Sa définition est dans liste.c, et nulle part ailleurs. Un fichier qui inclut liste.h peut déclarer des listes, les passer aux fonctions du module, mais ne peut pas écrire l->val : le compilateur refuse, il ne connaît pas les champs.

L'intérêt est le même que celui des modules de Caml : on peut changer la représentation (ajouter un champ, passer d'une liste à un tableau) sans toucher au code qui s'en sert. Et personne ne peut casser les invariants de la structure en allant modifier un champ à la main.

liste.c :

#include <stdio.h>
#include <stdlib.h>
#include "liste.h"

struct s_liste
{
    int     val;
    t_liste suivant;
};

t_liste ajouter(int x, t_liste l)
{
    t_liste t = malloc(sizeof (struct s_liste));
    if (t == NULL)
    {
        perror("ajouter");
        exit(1);
    }
    t->val = x;
    t->suivant = l;
    return t;
}

int tete(t_liste l)
{
    return l->val;
}

t_liste queue(t_liste l)
{
    return l->suivant;
}

size_t longueur(t_liste l)
{
    size_t n = 0;
    for (; l != NULL; l = l->suivant)
        n++;
    return n;
}

t_liste chercher(int x, t_liste l)
{
    while (l != NULL && l->val != x)
        l = l->suivant;
    return l;
}

void detruire(t_liste l)
{
    while (l != NULL)
    {
        t_liste t = l;
        l = l->suivant;
        free(t);
    }
}

ajouter fabrique un nouveau maillon sur le tas avec malloc (chapitre 3), et vérifie qu'il l'a obtenu. chercher rend le maillon qui contient x, ou NULL. detruire libère les maillons un par un ; il faut garder l'adresse du suivant avant de libérer le maillon courant, car après free(t), lire t->suivant est interdit.

tete et queue ne vérifient pas que la liste est non vide : c'est à l'appelant de le faire, avec est_vide. On l'écrit dans le commentaire de l'en-tête, ou on ajoute un test qui arrête le programme.

Un programme qui s'en sert

essai_liste.c :

#include <stdio.h>
#include "liste.h"

void afficher(t_liste l)
{
    for (; !est_vide(l); l = queue(l))
        printf("%d ", tete(l));
    printf("\n");
}

int main(void)
{
    t_liste l = liste_vide();
    int valeurs[] = { 5, 1, 4, 1, 9, 2, 6 };

    for (size_t i = 0; i < sizeof valeurs / sizeof valeurs[0]; i++)
        inserer(valeurs[i], &l);
    afficher(l);
    printf("longueur : %zu\n", longueur(l));
    printf("9 %s\n", chercher(9, l) != NULL ? "trouvé" : "absent");
    printf("3 %s\n", chercher(3, l) != NULL ? "trouvé" : "absent");
    detruire(l);
    return 0;
}

afficher n'utilise que les opérations de l'en-tête. sizeof valeurs / sizeof valeurs[0] est le nombre de cases du tableau : sa taille totale divisée par celle d'une case (cela ne marche que sur un vrai tableau, pas sur un pointeur, chapitre 2).

Le Makefile peut s'appuyer sur les règles implicites de make, qui sait déjà fabriquer un .o à partir d'un .c : il suffit de donner les dépendances. $@ est la cible, $^ la liste de ses dépendances.

CC = gcc
CFLAGS = -std=c11 -Wall -Wextra -Werror -O2

essai_liste: essai_liste.o liste.o
	$(CC) -o $@ $^

essai_liste.o: essai_liste.c liste.h
liste.o: liste.c liste.h

clean:
	rm -f essai_liste *.o

$ make
gcc -std=c11 -Wall -Wextra -Werror -O2   -c -o essai_liste.o essai_liste.c
gcc -std=c11 -Wall -Wextra -Werror -O2   -c -o liste.o liste.c
gcc -o essai_liste essai_liste.o liste.o
$ ./essai_liste
1 1 2 4 5 6 9
longueur : 7
9 trouvé
3 absent

Passer une liste à une fonction

Par valeur, ou par adresse

En C, tous les paramètres sont passés par valeur : la fonction reçoit une copie. Pour un pointeur, c'est une copie du pointeur, qui désigne les mêmes maillons. La fonction peut donc modifier les maillons ; elle ne peut pas modifier la variable de l'appelant qui contient le pointeur.

void vider_rate(t_liste l)
{
    detruire(l);
    l = liste_vide();       /* ne change que la copie */
}

void vider(t_liste *l)
{
    detruire(*l);
    *l = liste_vide();      /* change la variable de l'appelant */
}

Après vider_rate(l), les maillons sont libérés, mais la variable l de l'appelant contient toujours l'adresse de l'ancien premier maillon : c'est un pointeur pendant, qu'il ne faut plus jamais suivre. Après vider(&l), l vaut NULL.

Les langages d'algorithmique distinguent souvent les paramètres en entrée (passés par valeur) des paramètres en entrée-sortie (passés par référence, que la procédure peut modifier). Le C n'a pas de passage par référence : on le simule en passant l'adresse de la variable, comme pour echange au chapitre 2. Une fonction qui doit changer quel maillon est en tête de liste reçoit donc un t_liste *.

On a deux façons de rendre un nouveau début de liste :

• le rendre comme résultat : t_liste ajouter(int x, t_liste l), qu'on appelle par l = ajouter(x, l); ;
• recevoir la liste par adresse : void inserer(int x, t_liste *l), qu'on appelle par inserer(x, &l);. C'est la seule solution quand le résultat sert déjà à autre chose, ou pour que l'appelant ne puisse pas oublier l'affectation.

Insérer dans une liste triée

inserer ajoute x à sa place dans une liste triée par ordre croissant. La première idée distingue deux cas : l'insertion en tête, qui change la variable de l'appelant, et l'insertion plus loin, qui change le champ suivant du maillon précédent.

void inserer(int x, t_liste *l)
{
    if (*l == NULL || (*l)->val >= x)
        *l = ajouter(x, *l);
    else
    {
        t_liste prec = *l;
        while (prec->suivant != NULL && prec->suivant->val < x)
            prec = prec->suivant;
        prec->suivant = ajouter(x, prec->suivant);
    }
}

On s'arrête sur le maillon précédent (celui dont le suivant est trop grand, ou n'existe pas), car c'est son champ suivant qu'il faut modifier.

Mais les deux cas font la même chose : remplacer un pointeur (la variable de l'appelant, ou un champ suivant) par l'adresse d'un nouveau maillon. Si l'on garde l'adresse de ce pointeur plutôt que le maillon, il n'y a plus qu'un cas :

void inserer(int x, t_liste *l)
{
    while (*l != NULL && (*l)->val < x)
        l = &(*l)->suivant;
    *l = ajouter(x, *l);
}

Au départ, l pointe sur la variable de l'appelant. À chaque tour, il avance sur le champ suivant du maillon courant. Quand on s'arrête, *l est le pointeur à remplacer, quel qu'il soit. &(*l)->suivant se lit &((*l)->suivant) : l'adresse du champ suivant du maillon *l.

Lire une signature

Le C utilise l'étoile pour beaucoup de choses : un passage par adresse, un tableau, une chaîne, une structure chaînée, un pointeur générique. En regardant f(int *p), on ne sait pas lequel. D'où quelques conventions, pour que la signature d'une fonction dise d'elle-même comment s'en servir :

• Structures de données : le pointeur est caché par un typedef (t_liste, t_arbre). Pas d'étoile.
• Tableaux : dans un paramètre, int t[] veut dire exactement la même chose que int *t. On écrit les crochets pour un tableau.
• Chaînes : ce sont des tableaux de caractères ; on écrit char s[], ou const char *s quand la fonction ne la modifie pas.
• Il reste l'étoile explicite : elle signale un passage par adresse, une variable de l'appelant que la fonction va modifier, ou plus rarement un pointeur générique void *.

Quelques signatures, et ce qu'elles disent :

/* t_liste est abstrait : on n'a pas à savoir que c'est un pointeur. */
t_liste ajouter(int x, t_liste l);

/* La tête de liste peut changer : la liste est passée par adresse. */
void inserer(int x, t_liste *l);

/* v est un tableau ; *somme recevra un second résultat. La fonction
 * rend sans doute le nombre d'éléments, et range leur somme dans *somme.
 * Mais comment connaît-elle la taille de v ? Il manque un paramètre. */
size_t compter_sommer(int v[], int *somme);

Reste une ambiguïté : char *t[] est-il un tableau de chaînes, ou l'adresse d'une chaîne qu'on va modifier ? La syntaxe ne le dit pas. C'est le premier (argv, dans int main(int argc, char *argv[]), est un tableau de chaînes), mais seul un commentaire, ou un typedef, peut le dire au lecteur.

Un échange générique

echange(int *a, int *b) échange deux entiers. Pour échanger deux valeurs de n'importe quel type, on passe par void *, et il faut alors donner la taille des valeurs, puisque void * ne la connaît pas. La copie se fait octet par octet, avec memcpy :

#include <stdlib.h>
#include <string.h>

void echange_gen(void *a, void *b, size_t taille)
{
    void *tmp = malloc(taille);
    if (tmp == NULL)
        abort();
    memcpy(tmp, a, taille);
    memcpy(a, b, taille);
    memcpy(b, tmp, taille);
    free(tmp);
}

double u = 1.5, v = 2.5;
echange_gen(&u, &v, sizeof u);          /* u = 2.5, v = 1.5 */

char *s = "bonjour", *t = "au revoir";
echange_gen(&s, &t, sizeof s);          /* échange les deux pointeurs */

C'est ainsi que sont écrites les fonctions génériques de la bibliothèque standard, comme qsort. On y perd la vérification des types : rien n'empêche de passer une mauvaise taille. Et pour deux entiers, c'est bien plus lent que echange.

Une file

Une file (queue) est une liste où l'on ajoute à un bout et retire à l'autre : le premier entré est le premier sorti. Pour que les deux opérations soient en temps constant, il faut accéder aux deux bouts. Une astuce le permet avec un seul pointeur : la liste est circulaire, et l'on garde l'adresse du dernier maillon. Son suivant est le premier.

flowchart LR
    F([f]) --> C
    A[premier] --> B[deuxième] --> C[dernier] --> A

On y range des void *, pour pouvoir y mettre n'importe quelle donnée : des arbres, des chaînes…

file.h :

#ifndef FILE_H
#define FILE_H

typedef struct s_file *t_file;

#define file_vide() (NULL)
#define file_est_vide(f) ((f) == NULL)

t_file enfiler(void *x, t_file f);
void  *defiler(t_file *f);

#endif

file.c :

#include <stdio.h>
#include <stdlib.h>
#include "file.h"

struct s_file
{
    void  *val;
    t_file suivant;
};

/* f pointe sur le dernier maillon ; le dernier pointe sur le premier. */
t_file enfiler(void *x, t_file f)
{
    t_file t = malloc(sizeof (struct s_file));
    if (t == NULL)
    {
        perror("enfiler");
        exit(1);
    }
    t->val = x;
    if (f == NULL)
        t->suivant = t;
    else
    {
        t->suivant = f->suivant;
        f->suivant = t;
    }
    return t;
}

void *defiler(t_file *f)
{
    t_file premier = (*f)->suivant;
    void  *x = premier->val;
    if (premier == *f)
        *f = NULL;
    else
        (*f)->suivant = premier->suivant;
    free(premier);
    return x;
}

• enfiler insère le nouveau maillon après le dernier, donc entre le dernier et le premier, et le nouveau maillon devient le dernier : on le rend. Une file d'un seul maillon pointe sur elle-même.
• defiler retire le premier maillon (le suivant du dernier). Elle rend déjà la valeur, elle reçoit donc la file par adresse pour pouvoir la modifier. Si le premier était aussi le dernier, la file devient vide.

char  *mots[] = { "un", "deux", "trois" };
t_file f = file_vide();

for (int i = 0; i < 3; i++)
    f = enfiler(mots[i], f);
while (!file_est_vide(f))
    printf("%s\n", (char *)defiler(&f));

un
deux
trois

Les arbres binaires

Le module

Un arbre binaire est vide, ou fait d'un nœud qui porte une clé et deux sous-arbres. Même principe que la liste : l'arbre vide est NULL.

arbre.h :

#ifndef ARBRE_H
#define ARBRE_H

#include <stddef.h>

typedef struct s_arbre *t_arbre;

t_arbre noeud(int cle, t_arbre g, t_arbre d);
int     hauteur(t_arbre a);
size_t  taille(t_arbre a);
void    afficher_profondeur(t_arbre a);
void    afficher_largeur(t_arbre a);
void    detruire_arbre(t_arbre a);

#endif

Le début d'arbre.c :

#include <stdio.h>
#include <stdlib.h>
#include "file.h"
#include "arbre.h"

struct s_arbre
{
    int     cle;
    t_arbre g, d;
};

t_arbre noeud(int cle, t_arbre g, t_arbre d)
{
    t_arbre a = malloc(sizeof (struct s_arbre));
    if (a == NULL)
    {
        perror("noeud");
        exit(1);
    }
    a->cle = cle;
    a->g = g;
    a->d = d;
    return a;
}

size_t taille(t_arbre a)
{
    return a == NULL ? 0 : 1 + taille(a->g) + taille(a->d);
}

void detruire_arbre(t_arbre a)
{
    if (a == NULL)
        return;
    detruire_arbre(a->g);
    detruire_arbre(a->d);
    free(a);
}

Les fonctions récursives s'écrivent comme en Caml : un cas pour l'arbre vide, un cas pour le nœud. detruire_arbre libère les deux sous-arbres avant le nœud, puisque c'est dans le nœud que sont rangées leurs adresses.

La hauteur, et un piège sur les entiers

Par convention, une feuille (un nœud sans enfant) a pour hauteur 0, et l'arbre vide -1. La hauteur est donc un entier signé :

int hauteur(t_arbre a)
{
    if (a == NULL)
        return -1;
    int hg = hauteur(a->g);
    int hd = hauteur(a->d);
    return 1 + (hg > hd ? hg : hd);
}

Deux parcours

Le parcours en profondeur visite un nœud, puis tout son sous-arbre gauche, puis tout son sous-arbre droit. On affiche chaque clé décalée selon sa profondeur :

static void profondeur(t_arbre a, int decalage)
{
    if (a == NULL)
        return;
    printf("%*s%d\n", decalage, "", a->cle);
    profondeur(a->g, decalage + 2);
    profondeur(a->d, decalage + 2);
}

void afficher_profondeur(t_arbre a)
{
    profondeur(a, 0);
}

%*s affiche une chaîne sur une largeur donnée en argument : ici la chaîne vide, complétée par decalage espaces. static rend profondeur invisible hors de arbre.c : c'est une fonction auxiliaire, qui n'a pas sa place dans l'en-tête.

Le parcours en largeur visite les nœuds niveau par niveau : la racine, puis ses enfants, puis ses petits-enfants. On s'aide de la file : on retire un nœud, on l'affiche, on ajoute ses enfants en fin de file. Pour passer à la ligne à la fin de chaque niveau, on met dans la file un marqueur, NULL : quand on le retire, tout le niveau a été affiché, et tout le niveau suivant est dans la file, derrière lui.

void afficher_largeur(t_arbre a)
{
    if (a == NULL)
        return;
    t_file f = file_vide();
    f = enfiler(a, f);
    f = enfiler(NULL, f);
    while (!file_est_vide(f))
    {
        t_arbre t = defiler(&f);
        if (t != NULL)
        {
            printf("%d ", t->cle);
            if (t->g != NULL)
                f = enfiler(t->g, f);
            if (t->d != NULL)
                f = enfiler(t->d, f);
        }
        else
        {
            printf("\n");
            if (!file_est_vide(f))
                f = enfiler(NULL, f);
        }
    }
}

t_arbre a = noeud(1,
                  noeud(2, noeud(4, NULL, NULL), NULL),
                  noeud(3, noeud(5, NULL, NULL), noeud(6, NULL, NULL)));

printf("taille %zu, hauteur %d\n", taille(a), hauteur(a));
afficher_profondeur(a);
afficher_largeur(a);
detruire_arbre(a);

taille 6, hauteur 2
1
  2
    4
  3
    5
    6
1
2 3
4 5 6

Le programme se compile avec les deux modules : gcc -std=c11 -Wall -Wextra -Werror essai_arbre.c arbre.c file.c.

Un vecteur de taille variable

Le chapitre 3 a présenté le vecteur dynamique : un tableau alloué sur le tas, agrandi avec realloc quand il est plein, en doublant sa capacité. En voici la version complète, en type abstrait.

vecteur.h :

#ifndef VECTEUR_H
#define VECTEUR_H

#include <stddef.h>

typedef struct s_vecteur *t_vecteur;

t_vecteur vecteur_nouveau(void);
void      vecteur_ajouter(t_vecteur v, int x);
int       vecteur_lire(t_vecteur v, size_t i);
size_t    vecteur_longueur(t_vecteur v);
void      vecteur_detruire(t_vecteur v);

#endif

vecteur.c :

#include <stdio.h>
#include <stdlib.h>
#include "vecteur.h"

struct s_vecteur
{
    size_t longueur;    /* cases occupées */
    size_t capacite;    /* cases allouées */
    int   *cases;
};

static void *allouer(void *p, size_t n)
{
    p = realloc(p, n);
    if (p == NULL)
    {
        perror("vecteur");
        exit(1);
    }
    return p;
}

t_vecteur vecteur_nouveau(void)
{
    t_vecteur v = allouer(NULL, sizeof (struct s_vecteur));
    v->longueur = 0;
    v->capacite = 1;
    v->cases = allouer(NULL, sizeof (int));
    return v;
}

void vecteur_ajouter(t_vecteur v, int x)
{
    if (v->longueur == v->capacite)
    {
        v->capacite *= 2;
        v->cases = allouer(v->cases, v->capacite * sizeof (int));
    }
    v->cases[v->longueur++] = x;
}

int vecteur_lire(t_vecteur v, size_t i)
{
    if (i >= v->longueur)
    {
        fprintf(stderr, "vecteur_lire : indice %zu hors limites\n", i);
        exit(1);
    }
    return v->cases[i];
}

size_t vecteur_longueur(t_vecteur v)
{
    return v->longueur;
}

void vecteur_detruire(t_vecteur v)
{
    free(v->cases);
    free(v);
}

• realloc(NULL, n) se comporte comme malloc(n) : une seule fonction allouer sert aux deux usages, et vérifie le résultat.
• Parce que le type est abstrait, vecteur_lire peut vérifier l'indice, ce que le C ne fait jamais sur un tableau. Personne ne peut contourner la vérification en lisant v->cases[i] directement.
• vecteur_detruire libère le tableau puis la structure : dans l'autre ordre, on lirait v->cases dans une zone déjà libérée.

t_vecteur v = vecteur_nouveau();
for (int i = 0; i < 1000; i++)
    vecteur_ajouter(v, i * i);
printf("%zu cases, la dernière vaut %d\n",
       vecteur_longueur(v), vecteur_lire(v, vecteur_longueur(v) - 1));
vecteur_lire(v, 1000);

1000 cases, la dernière vaut 998001
vecteur_lire : indice 1000 hors limites