Aller au contenu

Pointeurs, structures

Les structures

Présentation

Il est possible de définir ses propres structures en C qui agrègent d'autres types. Ainsi, on pourra définir une structure point permettant de représenter des points du plan :

struct point {
    double x;
    double y;
};

On peut alors définir un élément de cette structure avec le type struct point et on peut accéder à ses champs par l'utilisation de .. Pour obtenir le point \((3,4)\) on écrit :

struct point p;
p.x = 3;
p.y = 4;

On peut passer en paramètre une telle structure et la renvoyer en valeur de retour comme ici :

struct point cree_point(double x, double y)
{
    struct point p;
    p.x = x;
    p.y = y;
    return p;
}

void affiche_point(struct point p)
{
    printf("(%f,%f)\n", p.x, p.y);
}

struct point milieu(struct point a, struct point b)
{
    struct point m;
    m.x = (a.x + b.x)/2;
    m.y = (a.y + b.y)/2;
    return m;
}

// exemple, dans main
struct point p1 = cree_point(0, 10);
struct point p2 = cree_point(6, 4);
affiche_point(milieu(p1, p2)); // (3.000000,7.000000)

Lors de ces passages et de ces retours, la structure est copiée champ par champ, comme le serait un int.

On remarque que c'est un peu pénible d'écrire struct point partout ; il est possible d'utiliser un typedef pour définir un type synonyme. Si jamais on a une structure struct t_s, on peut écrire typedef struct t_s t; pour pouvoir utiliser t à la place. On peut même avoir le même nom, comme ici :

typedef struct point point;

point p;
p.x = 2;
p.y = 3;
affiche_point(p);

Quand on sépare en .c et .h, il faut mettre les types et les déclarations (ou prototypes) dans le .h et les définitions dans le .c. Par exemple, on pourrait écrire un fichier point.h contenant

#ifndef POINT_H
#define POINT_H

struct point {
    double x;
    double y;
};

typedef struct point point;

point cree_point(double x, double y);

#endif

puis un fichier point.c contenant

#include "point.h"

point cree_point(double x, double y)
{
    point p;
    p.x = x;
    p.y = y;
    return p;
}

Remarque

Les trois lignes #ifndef POINT_H, #define POINT_H et #endif sont une garde d'inclusion : si le fichier est inclus deux fois dans un même .c (par exemple directement et via un autre .h qui l'inclut), son contenu n'est pris en compte que la première fois. Sans elle, la structure serait définie deux fois, ce qui est une erreur de compilation.

Dans les questions qui suivent, on vous demande d'écrire dans des fichiers. Votre programme sera donc réparti sur plusieurs fichiers. On suppose que votre fonction main ainsi que les tests de bon fonctionnement de vos fonctions se trouvent dans le fichier main.c. Pour compiler la prochaine question, on pourra donc écrire :

gcc -o main main.c vecteur.c -lm

Note : le -lm est nécessaire pour les fonctions mathématiques.

Attention : si on compile avec plusieurs fichiers .c comme ici, il faut placer les bibliothèques à la fin.

Sur le modèle précédent, on va définir une structure vecteur qui contient les trois coordonnées d'un vecteur dans l'espace sous la forme de nombres double.

Remarque

Pour travailler avec plusieurs fichiers, le plus simple est de créer un répertoire tp_structures sur votre ordinateur où vous avez accès à un compilateur C et à l'invite de commande. Vous placez vos fichiers dans ce répertoire et vous compilez.

Cependant, si vous n'avez pas installé ça ou si vous êtes sur l'ordinateur de l'établissement, vous pouvez créer des fichiers différents sur repl.it.

Question 1

Écrire un fichier vecteur.h qui contient la déclaration de la structure et le typedef correspondant. Ce fichier contiendra également tous les prototypes des fonctions définies dans vecteur.c.

Rappel : le prototype, c'est la ligne comme au-dessus dans point.h avec le nom de la fonction et les types de retour et de ses paramètres.

Indication

Il s'agit juste de copier-coller ce qui a été fait dans point.h en rajoutant double z et en changeant le nom de la structure.

Corrigé 
#ifndef VECTEUR_H
#define VECTEUR_H

struct vecteur {
    double x;
    double y;
    double z;
};

typedef struct vecteur vecteur;

vecteur vecteur_cree(double x, double y, double z);
vecteur vecteur_nul(void);
double vecteur_norme(vecteur v);
vecteur vecteur_ajoute(vecteur v1, vecteur v2);

#endif

En C, une fonction sans paramètre se déclare avec (void) : avant C23, vecteur vecteur_nul(); signifie « nombre de paramètres non précisé ».

Question 2

Écrire un fichier vecteur.c qui contient les fonctions suivantes :

  1. vecteur vecteur_cree(double x, double y, double z); qui renvoie un nouveau vecteur ;
  2. vecteur vecteur_nul(void); qui renvoie le vecteur nul ;

  3. double vecteur_norme(vecteur v); qui renvoie la norme du vecteur v.

    Note : la fonction sqrt se trouve dans math.h et il faut compiler en rajoutant le paramètre -lm ;

  4. vecteur vecteur_ajoute(vecteur v1, vecteur v2); qui renvoie un nouveau vecteur, somme des vecteurs v1 et v2.

Indication

On rappelle qu'on peut renvoyer une valeur vecteur directement et que tout va bien se passer. En fait, on va avoir des copies automatiques.

Corrigé 
#include <math.h>
#include "vecteur.h"

vecteur vecteur_cree(double x, double y, double z)
{
    vecteur v;

    v.x = x;
    v.y = y;
    v.z = z;

    return v;
}

vecteur vecteur_nul(void)
{
    return vecteur_cree(0., 0., 0.);
}

double vecteur_norme(vecteur v)
{
    return sqrt(v.x*v.x + v.y*v.y + v.z*v.z);
}

vecteur vecteur_ajoute(vecteur v1, vecteur v2)
{
    return vecteur_cree(
        v1.x+v2.x,
        v1.y+v2.y,
        v1.z+v2.z);
}

On va maintenant définir des pavés droits ; on parle d'axis aligned bounding boxes en anglais, ce qui est communément abrégé en AABB. Un pavé droit est l'extension naturelle à l'espace des rectangles alignés sur les axes ; on peut les définir par les coordonnées \((x_{min},y_{min},z_{min})\) et \((x_{max},y_{max},z_{max})\) et ce sont les points de coordonnées \((x,y,z)\) où \(x_{min} \le x \le x_{max}\), \(y_{min} \le y \le y_{max}\) et \(z_{min} \le z \le z_{max}\).

On peut ainsi définir la structure :

struct aabb {
    vecteur v_min;
    vecteur v_max;
};

Question 3

Définir sur le modèle précédent des fichiers aabb.h et aabb.c, avec :

  1. aabb aabb_create(vecteur v_min, vecteur v_max); qui crée une aabb ;
  2. aabb aabb_union(aabb b1, aabb b2); qui renvoie la plus petite boîte contenant les deux boîtes.
Indication

Pour 2, il faudra prendre les maximums des maximums et les minimums des minimums. Faites un dessin.

Corrigé

aabb.h :

#ifndef AABB_H
#define AABB_H

#include "vecteur.h"

struct aabb {
    vecteur v_min;
    vecteur v_max;
};

typedef struct aabb aabb;

aabb aabb_create(vecteur v_min, vecteur v_max);
aabb aabb_union(aabb b1, aabb b2);

#endif

aabb.c :

#include "aabb.h"

aabb aabb_create(vecteur v_min, vecteur v_max)
{
    aabb box;
    box.v_min = v_min;
    box.v_max = v_max;
    return box;
}

static double min(double a, double b)
{
    if (a < b)
        return a;
    else
        return b;
}

static double max(double a, double b)
{
    if (a > b)
        return a;
    else
        return b;
}

aabb aabb_union(aabb b1, aabb b2)
{
    return aabb_create(
        vecteur_cree(
            min(b1.v_min.x, b2.v_min.x),
            min(b1.v_min.y, b2.v_min.y),
            min(b1.v_min.z, b2.v_min.z)),
        vecteur_cree(
            max(b1.v_max.x, b2.v_max.x),
            max(b1.v_max.y, b2.v_max.y),
            max(b1.v_max.z, b2.v_max.z)));
}

Le mot-clé static rend min et max locales au fichier aabb.c : elles n'entrent pas en conflit avec d'autres fonctions de même nom dans le programme. Le programme se compile avec gcc -o main main.c vecteur.c aabb.c -lm.

Au sens strict, la réunion de deux pavés n'est pas un pavé : on renvoie ici la plus petite boîte englobante, ce qui est l'usage (en lancer de rayons par exemple).

Remarque

On pourrait continuer en faisant la différence, qui est complexe car elle va créer plusieurs boîtes. Cela pose pas mal de questions sur le prototype d'une telle fonction. On pourrait par exemple définir :

aabb *aabb_difference(aabb b1, aabb b2, int *nb_boites);

qui renvoie un tableau alloué dynamiquement de boîtes et place dans l'entier nb_boites, passé par pointeur, le nombre de boîtes.

Structure plus riche

La structure suivante permet de définir une structure eleve permettant de contenir un nom, qui est une chaîne de longueur au plus 9, et un âge :

struct eleve {
    char nom[10]; // prend donc 10 octets en mémoire
    int age; // prend 4 octets sur 64 bits
}; // donc prend au moins 14 octets
typedef struct eleve eleve;

Remarque

En pratique, sizeof(eleve) vaut 16 et pas 14 : le compilateur ajoute du remplissage (padding) pour que le champ age commence à une adresse multiple de 4.

On aura besoin de comparer deux chaînes ; on utilise pour cela

int strncmp(const char *s1, const char *s2, size_t n);

depuis string.h, qui permet de comparer au plus n caractères pour décider si les chaînes sont égales et renvoie 0 à ce moment-là :

  • strncmp("toto", "toti", 4); ne renvoie pas 0 ;
  • strncmp("toto", "toto", 5); renvoie 0 (pas de problème de dépassement, la comparaison s'arrête au '\0') ;
  • strncmp("toto", "toti", 3); renvoie 0.

Le qualificatif const présent ici signifie que strncmp ne modifiera pas les chaînes (ce qui est assez rassurant pour une fonction de comparaison).

Ici, on va donc utiliser 10 pour n pour ne pas sortir du nom.

On va considérer une classe qui est un tableau d'eleve et on pourra directement accéder aux champs des cases avec t[i].nom ou t[i].age.

Question 4

Écrire une fonction :

/*
 * age : renvoie l'âge d'un élève dans une classe en fonction de son nom
 *       s'il n'est pas présent dans la classe, renvoie -1
 *
 * classe est un tableau d'eleve
 * nb_eleves est le nombre d'éléments du tableau
 * nom est le nom de l'élève dont on cherche l'âge
 */
int age(eleve classe[], int nb_eleves, char *nom);
Indication

Il s'agit juste de parcourir le tableau et de faire le test avec strncmp. C'est exactement comme la recherche d'un élément dans un tableau.

Du code pour tester votre fonction :

eleve classe[4];
strcpy(classe[0].nom, "Riri");
classe[0].age = 9;
strcpy(classe[1].nom, "Fifi");
classe[1].age = 10;
strcpy(classe[2].nom, "Loulou");
classe[2].age = 11; // le premier qui dit que ce sont des triplés a un devoir supplémentaire
strcpy(classe[3].nom, "Donald");
classe[3].age =  42; // il est en 43/2

if (age(classe, 4, "Donald") != 42)
    printf("Erreur 1\n");
if (age(classe, 3, "Donald") != -1)
    printf("Erreur 2\n");
if (age(classe, 4, "Loulou") != 11)
    printf("Erreur 3\n");
Corrigé 
int age(eleve classe[], int nb_eleves, char *nom)
{
    for(int i = 0; i < nb_eleves; i++) {
        if (strncmp(classe[i].nom, nom, 10) == 0)
            return classe[i].age;
    }

    return -1;
}

Retours d'arguments avec des pointeurs

Question 5

On a vu jusqu'ici comment renvoyer le minimum d'un tableau, comment renvoyer son indice, mais pas encore comment renvoyer les deux en même temps. Pour cela, on va écrire une fonction qui renvoie le minimum directement mais utilise un pointeur pour renvoyer son indice (voir le passage par adresse). On suppose que nb \(\ge 1\).

int cherche_minimum(int *t, int nb, int *indice);

Remarque

Ici * est utilisé de deux façons différentes :

  • dans int *t, t est l'adresse de la première case d'un tableau d'entiers (un tableau passé en paramètre est converti en un tel pointeur, voir Pointeurs et tableaux) ;
  • dans int *indice, il s'agit d'un passage par adresse de la variable indice de l'appelant.

C'est vrai qu'il peut être plus clair d'utiliser int t[] dans ce cadre-là pour distinguer les deux usages : pour un paramètre, les deux écritures sont équivalentes.

Indication

On rappelle qu'il suffit d'écrire *indice = 4; pour changer cette valeur.

Exemple d'utilisation :

int t[] = { 1, 3, 0, 2, 4 };
int indice;
int min = cherche_minimum(t, 5, &indice); // on passe un pointeur sur indice
printf("Le minimum est %d et il est à l'indice %d\n", min, indice);
Corrigé 
int cherche_minimum(int *t, int nb, int *indice)
{
    int mini = 0;

    for(int i = 1; i < nb; i++) {
        if(t[i] < t[mini])
            mini = i;
    }

    *indice = mini;
    return t[mini];
}

Question 6

Pour la fonction suivante, on vous demande de calculer, pour un tableau t contenant au moins deux éléments, le couple \((i,j)\) où \(i < j\) et pour lequel \(|t[i]-t[j]|\) est minimal. C'est-à-dire la plus petite distance entre deux éléments d'indices distincts dans le tableau. On pourra utiliser int abs(int x); pour calculer \(|x|\) (qui se trouve dans stdlib.h).

/*
 * t : tableau d'entiers
 * nb : nombre d'éléments du tableau
 *
 * i, j : valeurs de retour passées par pointeurs
 *
 * Renvoie dans (i,j) le couple tel que |t[i]-t[j]| soit minimal
 * et i < j. En cas de plusieurs couples valides, renvoie le couple
 * dont la première coordonnée est minimale.
 */
void plus_petite_distance(int *t, int nb, int *i, int *j);
Indication

C'est un calcul de minimum mais avec deux indices au lieu d'un. C'est sûrement plus clair ici de placer la distance minimale courante dans une variable plutôt que de la calculer à la volée.

Pour les indices du minimum courant, vous avez le choix entre utiliser *i et *j ou passer par des variables locales et attendre la fin de la fonction pour affecter *i et *j. La deuxième version est sûrement plus claire.

// Exemple de test (il faut #include <assert.h>)
int t[] = { 5, 2, 7, 10 };
int i, j;
plus_petite_distance(t, 4, &i, &j);
assert( i == 0 && j == 2 );
Corrigé 
void plus_petite_distance(int *t, int nb, int *i, int *j)
{
    int mini = 0;
    int minj = 1;

    for(int k = 0; k < nb; k++) {
        for(int l = k+1; l < nb; l++) {
            if(abs(t[k]-t[l]) < abs(t[mini]-t[minj])) {
                mini = k;
                minj = l;
            }
        }
    }

    *i = mini;
    *j = minj;
}

Les couples sont parcourus dans l'ordre lexicographique et la comparaison est stricte : en cas d'égalité, on garde le premier couple rencontré, de première coordonnée minimale (puis de seconde coordonnée minimale). Cette solution est en \(O(n^2)\) ; en triant une copie du tableau, on pourrait trouver la plus petite distance en \(O(n \log n)\).

Tableaux redimensionnables

On va utiliser ici une structure pour emballer les tableaux, qui permet de transmettre directement le tableau et sa taille :

struct array_t {
    int *elements;
    int nelements;
};
typedef struct array_t *array;

Le pointeur elements va être alloué dynamiquement. Ici, array est un pointeur sur la structure. C'est très important car cela va permettre de modifier les valeurs elements ou nelements dans les fonctions.

Si on a un array a, c'est un pointeur struct array_t *a, donc pour accéder à ses membres, il faut écrire par exemple (*a).elements. Ce n'est pas très agréable et comme ce cas est très présent, il y a un raccourci : a->elements.

Remarque

En résumé :

  • x.v si x est une valeur de type struct t ;
  • x->v si x est une valeur de type struct t *.

Note : compilez avec -g -fsanitize=address pour être sûr de ne pas faire n'importe quoi avec la mémoire (voir Erreurs classiques).

Question 7

Écrire une fonction

array array_alloc(int n);

qui alloue et renvoie un tableau de n entiers.

Indication

Il faut faire deux malloc ici (un pour le array et un pour son champ elements), et il faut bien faire attention à ne pas oublier de changer la valeur du champ nelements aussi.

Corrigé 
array array_alloc(int n)
{
    array t = malloc(sizeof(struct array_t));
    t->elements = malloc(n * sizeof(int));
    t->nelements = n;
    return t;
}

Attention à sizeof(struct array_t) : sizeof(array) ne serait que la taille d'un pointeur.

Question 8

Écrire une fonction

void array_free(array t);

qui libère le tableau d'éléments.

Indication

Attention à bien libérer à la fois t->elements et t lui-même.

Corrigé 
void array_free(array t)
{
    free(t->elements);
    free(t);
}

L'ordre compte : après free(t), on n'a plus le droit de lire t->elements.

Question 9

Écrire une fonction

int array_get(array t, int i);

qui renvoie l'entier à l'indice i si c'est un indice valide et fait une erreur, en déclenchant un assert, sinon.

Indication

Il faut inclure assert.h pour avoir assert.

Corrigé 
int array_get(array t, int i)
{
    assert(0 <= i && i < t->nelements);
    return t->elements[i];
}

Question 10

Écrire une fonction

void array_set(array t, int i, int v);

qui place la valeur v à l'indice i. On gérera les erreurs comme dans la fonction précédente.

Corrigé 
void array_set(array t, int i, int v)
{
    assert(0 <= i && i < t->nelements);
    t->elements[i] = v;
}

Question 11

Écrire une fonction

void array_append(array t, int v);

qui va :

  • allouer un tableau nt de t->nelements + 1 éléments ;
  • recopier t->elements dans nt->elements (avec une boucle for) ;
  • placer v à la fin du nouveau tableau ;
  • libérer t->elements ;
  • changer t->elements et t->nelements avec les valeurs dans nt ;
  • libérer nt (attention, ça ne va pas libérer nt->elements et c'est ce qu'on veut).
Corrigé 
void array_append(array t, int v)
{
    array nt = array_alloc(t->nelements + 1);
    for(int i = 0; i < t->nelements; i++) {
        nt->elements[i] = t->elements[i];
    }
    nt->elements[t->nelements] = v;
    free(t->elements);
    t->elements = nt->elements;
    t->nelements += 1;
    free(nt);
}

Question 12

Écrire une fonction

int array_pop(array t);

qui va, pour un tableau t non vide :

  • allouer un tableau nt de t->nelements - 1 éléments ;
  • recopier t->elements, sauf son dernier élément, dans ce tableau ;
  • stocker le dernier élément de t->elements ;
  • libérer t->elements ;
  • changer t->elements et t->nelements ;
  • libérer nt (attention, ça ne va pas libérer nt->elements et c'est ce qu'on veut) ;
  • renvoyer le dernier élément.
Corrigé 
int array_pop(array t)
{
    assert(t->nelements > 0);
    array nt = array_alloc(t->nelements - 1);
    for(int i = 0; i < t->nelements-1; i++) {
        nt->elements[i] = t->elements[i];
    }
    int v = t->elements[t->nelements-1];
    free(t->elements);
    t->elements = nt->elements;
    t->nelements -= 1;
    free(nt);
    return v;
}

Exemple d'utilisation, qui affiche 3, 2 puis 1 :

array l = array_alloc(0);
array_append(l, 1);
array_append(l, 2);
array_append(l, 3);
for(int i = 0; i < 3; i++)
    printf("%d\n", array_pop(l));
array_free(l);

Chaque ajout ou retrait recopie tout le tableau : \(n\) ajouts successifs coûtent \(\sum_{k=0}^{n-1} k = O(n^2)\) copies. C'est l'objet de la partie suivante.

Tableaux dynamiques plus efficaces

Question 13

Reprendre ce qui a été fait en OCaml avec des tableaux dynamiques qui doublent de taille en cas d'ajout.

Corrigé

On distingue le nombre de cases utilisées (nelements) du nombre de cases allouées (capacite). On ne réalloue que lorsque le tableau est plein, en doublant sa capacité : \(n\) ajouts coûtent alors \(O(n)\) copies au total, donc \(O(1)\) en coût amorti par ajout.

struct tabdyn_t {
    int *elements;
    int nelements; // nombre de cases utilisées
    int capacite;  // nombre de cases allouées
};
typedef struct tabdyn_t *tabdyn;

tabdyn tabdyn_vide(void)
{
    tabdyn t = malloc(sizeof(struct tabdyn_t));
    t->capacite = 1;
    t->nelements = 0;
    t->elements = malloc(t->capacite * sizeof(int));
    return t;
}

void tabdyn_free(tabdyn t)
{
    free(t->elements);
    free(t);
}

int tabdyn_get(tabdyn t, int i)
{
    assert(0 <= i && i < t->nelements);
    return t->elements[i];
}

void tabdyn_set(tabdyn t, int i, int v)
{
    assert(0 <= i && i < t->nelements);
    t->elements[i] = v;
}

void tabdyn_append(tabdyn t, int v)
{
    if (t->nelements == t->capacite)
    {
        // plein : on double la capacité
        int *nouveau = malloc(2 * t->capacite * sizeof(int));
        for (int i = 0; i < t->nelements; i++)
        {
            nouveau[i] = t->elements[i];
        }
        free(t->elements);
        t->elements = nouveau;
        t->capacite = 2 * t->capacite;
    }
    t->elements[t->nelements] = v;
    t->nelements += 1;
}

int tabdyn_pop(tabdyn t)
{
    assert(t->nelements > 0);
    t->nelements -= 1;
    return t->elements[t->nelements];
}

La fonction realloc de stdlib.h permet d'agrandir une zone allouée en évitant d'écrire la boucle de recopie.

Listes chaînées

Listes simplement chaînées

Remarque

Il faut compiler tout ce TP avec -fsanitize=address -Wall pour ne pas rater d'erreurs de gestion de la mémoire. Il faudra aussi effectuer des tests de vos fonctions.

Voici un exemple de script de test :

int main(void)
{
    liste *l = liste_vide();
    liste_affiche(l);
    liste_ajout_en_tete(l, 3);
    liste_ajout_en_tete(l, 2);
    liste_ajout_en_tete(l, 1);
    liste_affiche(l);
    liste_ajout_en_fin(l, 5);
    liste_affiche(l);
    maillon *m = liste_cherche_maillon(l, 3);
    liste_ajout_maillon_apres(l, m, 4);
    liste_affiche(l);
    liste_suppr_maillon(l, m);
    liste_affiche(l);
    liste_detruire(l);
}

qui doit afficher [], [1,2,3], [1,2,3,5], [1,2,3,4,5] puis [1,2,4,5]. Pensez aussi à tester les cas limites : liste vide, liste à un seul maillon, opérations sur le premier ou le dernier maillon.

On pourra également faire des tests dans PythonTutor pour s'assurer que la mémoire correspond à ce que l'on a en tête.

On va définir des fonctions sur les listes chaînées en utilisant le type suivant :

struct maillon {
    int valeur;
    struct maillon *suivant;
};
typedef struct maillon maillon;

struct liste {
    maillon *premier;
    maillon *dernier;
};
typedef struct liste liste;

Remarque

Invariants à maintenir

  • Dans un maillon, suivant est soit NULL si c'est le dernier maillon de la chaîne, soit un pointeur vers le maillon qui le suit.
  • Si la liste est vide, alors premier et dernier valent NULL. Sinon, ils pointent respectivement sur le premier et le dernier maillon de la chaîne.

Chaque fonction qui modifie la liste doit rétablir ces invariants, en particulier le champ dernier, qu'on oublie facilement.

Question 14

Écrire une fonction de prototype

liste *liste_creer(maillon *premier, maillon *dernier);

qui alloue et renvoie une liste dont les maillons sont donnés en arguments.

Question 15

Écrire une fonction de prototype

liste *liste_vide(void);

qui alloue et renvoie une liste vide.

Ici, on dit une car chaque appel va renvoyer une nouvelle liste vide.

Corrigé (questions 14 et 15) 
liste *liste_creer(maillon *premier, maillon *dernier)
{
    liste *l = malloc(sizeof(liste));
    l->premier = premier;
    l->dernier = dernier;
    return l;
}

liste *liste_vide(void)
{
    return liste_creer(NULL, NULL);
}

Question 16

Écrire une fonction de prototype

void liste_affiche(liste *l);

qui affiche le contenu de la liste sous la forme [1,2,3].

Note : on pourra utiliser putchar(c); pour afficher le caractère c.

Corrigé 
void liste_affiche(liste *l)
{
    putchar('[');
    maillon *m = l->premier;
    while(m != NULL)
    {
        printf("%d", m->valeur);
        if(m->suivant != NULL)
            putchar(',');
        m = m->suivant;
    }
    putchar(']');
    putchar('\n');
}

Question 17

Écrire une fonction de prototype

maillon *maillon_creer(int valeur, maillon *suivant);

qui alloue et initialise un nouveau maillon.

Corrigé 
maillon *maillon_creer(int valeur, maillon *suivant)
{
    maillon *m = malloc(sizeof(maillon));
    m->valeur = valeur;
    m->suivant = suivant;
    return m;
}

Question 18

Écrire une fonction de prototype

void maillon_detruire(maillon *m);

qui détruit, c'est-à-dire libère, la mémoire associée à un maillon.

Écrire une fonction de prototype

void chaine_detruire(maillon *m);

qui détruit la chaîne de maillons accessible depuis le maillon m.

En déduire une fonction de prototype

void liste_detruire(liste *l);

qui détruit la chaîne pointée par une liste, ainsi que la liste elle-même.

Corrigé 
void maillon_detruire(maillon *m)
{
    free(m);
}

// en impératif
void chaine_detruire(maillon *m)
{
    while(m != NULL)
    {
        maillon *suivant = m->suivant; // à lire AVANT de libérer m
        maillon_detruire(m);
        m = suivant;
    }
}

// en récursif
void chaine_detruire_rec(maillon *m)
{
    if (m != NULL) {
        chaine_detruire_rec(m->suivant);
        maillon_detruire(m);
    }
}

void liste_detruire(liste *l)
{
    chaine_detruire(l->premier);
    free(l);
}

La version récursive utilise une profondeur de pile égale à la longueur de la chaîne : sur une très longue liste, elle peut provoquer un dépassement de pile, contrairement à la version impérative.

Question 19

Écrire une fonction de prototype

int liste_longueur(liste *l);

qui renvoie la longueur de la liste l.

Corrigé 
int liste_longueur(liste *l)
{
    int longueur = 0;
    maillon *m = l->premier;
    while(m != NULL)
    {
        longueur += 1;
        m = m->suivant;
    }
    return longueur;
}

Question 20

Écrire des fonctions de prototype

int liste_tete(liste *l);
liste *liste_queue(liste *l);

qui renvoient respectivement la tête et la queue d'une liste non vide. Attention : ici, contrairement au type des listes d'OCaml, le maillon suivant n'est pas une liste.

Corrigé 
int liste_tete(liste *l)
{
    assert(l->premier != NULL);
    return l->premier->valeur;
}

liste *liste_queue(liste *l)
{
    assert(l->premier != NULL);
    if (l->premier->suivant == NULL) // la queue est vide
        return liste_vide();
    return liste_creer(l->premier->suivant, l->dernier);
}

La queue partage ses maillons avec l : on la libère avec un simple free, et pas avec liste_detruire, sinon les maillons seraient libérés deux fois. De plus, toute modification de l peut rendre la queue incohérente. Il faut traiter à part la liste à un élément pour respecter l'invariant de la liste vide.

Question 21

Écrire une fonction de prototype

void liste_ajout_en_tete(liste *l, int valeur);

qui ajoute un maillon en tête de la liste pointée par l en \(O(1)\). On fera attention au cas où l pointe la liste vide.

Corrigé 
void liste_ajout_en_tete(liste *l, int valeur)
{
    l->premier = maillon_creer(valeur, l->premier);
    if(l->dernier == NULL) // la liste était vide
        l->dernier = l->premier;
}

Question 22

Écrire une fonction de prototype

void liste_suppr_en_tete(liste *l);

qui supprime un maillon en tête de la liste l supposée non vide en \(O(1)\).

On fera attention au cas où on supprime l'unique maillon de la liste.

Corrigé 
void liste_suppr_en_tete(liste *l)
{
    assert(l->premier != NULL);
    maillon *m = l->premier;
    l->premier = m->suivant;
    maillon_detruire(m); // on libère la mémoire
    if(l->premier == NULL) // on a vidé la liste
        l->dernier = NULL;
}

Question 23

Écrire une fonction de prototype

void liste_ajout_en_fin(liste *l, int valeur);

qui ajoute un maillon en fin de la liste l en \(O(1)\).

Corrigé 
void liste_ajout_en_fin(liste *l, int valeur)
{
    maillon *m = maillon_creer(valeur, NULL);
    if(l->dernier == NULL) // la liste était vide
        l->premier = m;
    else
        l->dernier->suivant = m;
    l->dernier = m;
}

Dans le cas de la liste vide, il n'y a pas d'ancien dernier maillon à chaîner : écrire l->dernier->suivant serait un déréférencement de NULL.

Question 24

Écrire une fonction de prototype

maillon *liste_cherche_maillon(liste *l, int valeur);

qui renvoie un pointeur sur le premier maillon de valeur valeur ou renvoie NULL s'il n'y en a pas.

Corrigé 
maillon *liste_cherche_maillon(liste *l, int valeur)
{
    maillon *m = l->premier;
    while(m != NULL && m->valeur != valeur)
    {
        m = m->suivant;
    }
    return m;
}

L'évaluation paresseuse de && garantit qu'on ne lit pas m->valeur quand m vaut NULL.

Question 25

Écrire une fonction de prototype

void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur);

qui insère en \(O(1)\) un maillon après le maillon m. On fera en sorte que l'insertion soit valide même si m est le dernier maillon de la liste.

Corrigé 
void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur)
{
    m->suivant = maillon_creer(valeur, m->suivant);
    if (m == l->dernier)
        l->dernier = m->suivant;
}

Remarque

Dans les fonctions suivantes, on suppose qu'on va aller chercher naïvement le maillon précédent pour faire les chaînages.

Cependant, on peut se contenter de faire des échanges de valeurs pour ne pas avoir ce problème.

Question 26

Écrire une fonction de prototype

void liste_ajout_maillon_avant(liste *l, maillon *m, int valeur);

qui ajoute un maillon avant m. Dans le cas où m est le premier maillon, l'insertion sera en \(O(1)\).

Note : on peut rendre cela en \(O(1)\) dans tous les cas en tenant compte de la remarque précédente.

Corrigé 
// version naïve où on recherche le maillon précédent
void liste_ajout_maillon_avant(liste *l, maillon *m, int valeur)
{
    if (m == l->premier)
        liste_ajout_en_tete(l, valeur);
    else
    {
        maillon *prec = l->premier;
        while(prec->suivant != m)
        {
            prec = prec->suivant;
        }
        prec->suivant = maillon_creer(valeur, m);
    }
}

// version efficace : on insère une copie de m après m,
// puis on place la nouvelle valeur dans m
void liste_ajout_maillon_avant_O1(liste *l, maillon *m, int valeur)
{
    maillon *m2 = maillon_creer(m->valeur, m->suivant);
    m->valeur = valeur;
    m->suivant = m2;
    if (m == l->dernier)
        l->dernier = m2;
}

Attention, dans la version en \(O(1)\), le pointeur m désigne ensuite le maillon contenant valeur, et non plus l'ancienne valeur de m : d'éventuels pointeurs conservés ailleurs sur ce maillon changent de sens.

Question 27

Écrire une fonction de prototype

void liste_suppr_maillon(liste *l, maillon *m);

qui supprime un maillon.

Dans le cas où m est le premier maillon, la suppression sera en \(O(1)\).

Note : on peut rendre cela en \(O(1)\) sauf dans un cas, en tenant compte de la remarque précédente.

Corrigé 
// version naïve avec une recherche
void liste_suppr_maillon(liste *l, maillon *m)
{
    if (m == l->premier)
        liste_suppr_en_tete(l);
    else
    {
        maillon *prec = l->premier;
        while(prec->suivant != m)
        {
            prec = prec->suivant;
        }
        prec->suivant = m->suivant;
        if (m == l->dernier)
            l->dernier = prec;
        maillon_detruire(m);
    }
}

// version efficace : on recopie le maillon suivant dans m
// et on supprime ce suivant
void liste_suppr_maillon_O1(liste *l, maillon *m)
{
    if (m == l->dernier)
    {
        // seul cas en O(n) : il faut trouver le précédent
        liste_suppr_maillon(l, m);
    } else {
        maillon *m2 = m->suivant;
        m->valeur = m2->valeur;
        m->suivant = m2->suivant;
        if (m2 == l->dernier)
            l->dernier = m;
        maillon_detruire(m2);
    }
}

Le cas exceptionnel est celui du dernier maillon, qui n'a pas de suivant à recopier.

Listes doublement chaînées

Pour les listes doublement chaînées, on va adapter le type précédent en rajoutant juste un pointeur precedent dans les maillons :

struct maillon {
    int valeur;
    struct maillon *suivant;
    struct maillon *precedent;
};
typedef struct maillon maillon;

struct liste {
    maillon *premier;
    maillon *dernier;
};
typedef struct liste liste;

Remarque

Invariants à maintenir

  • Dans un maillon, suivant est soit NULL si c'est le dernier maillon de la chaîne, soit un pointeur vers le maillon qui le suit.
  • Dans un maillon, precedent est soit NULL si c'est le premier maillon de la chaîne, soit un pointeur vers le maillon qui le précède.
  • Si la liste est vide, alors premier et dernier valent NULL. Sinon, ils pointent respectivement sur le premier et le dernier maillon de la chaîne.

Question 28

Reprendre les questions précédentes avec ce nouveau type.

Corrigé

Peu de modifications à faire. On fait en sorte que maillon_creer effectue le double chaînage avec ses voisins.

liste *liste_creer(maillon *premier, maillon *dernier)
{
    liste *l = malloc(sizeof(liste));
    l->premier = premier;
    l->dernier = dernier;
    return l;
}

liste *liste_vide(void)
{
    return liste_creer(NULL, NULL);
}

void liste_affiche(liste *l)
{
    putchar('[');
    maillon *m = l->premier;
    while(m != NULL)
    {
        printf("%d", m->valeur);
        if(m->suivant != NULL)
            putchar(',');
        m = m->suivant;
    }
    putchar(']');
    putchar(' ');
    // pour tester, on remonte dans l'autre sens
    putchar('[');
    m = l->dernier;
    while(m != NULL)
    {
        printf("%d", m->valeur);
        if(m->precedent != NULL)
            putchar(',');
        m = m->precedent;
    }
    putchar(']');
    putchar('\n');
}

// crée un maillon et le chaîne à precedent et à suivant (s'ils existent)
maillon *maillon_creer(int valeur,
        maillon *precedent, maillon *suivant)
{
    maillon *m = malloc(sizeof(maillon));
    m->valeur = valeur;
    m->suivant = suivant;
    m->precedent = precedent;
    if (precedent != NULL)
        precedent->suivant = m;
    if (suivant != NULL)
        suivant->precedent = m;
    return m;
}

void maillon_detruire(maillon *m)
{
    free(m);
}

void chaine_detruire(maillon *m)
{
    while(m != NULL)
    {
        maillon *suivant = m->suivant;
        maillon_detruire(m);
        m = suivant;
    }
}

void liste_detruire(liste *l)
{
    chaine_detruire(l->premier);
    free(l);
}

int liste_longueur(liste *l)
{
    int longueur = 0;
    maillon *m = l->premier;
    while(m != NULL)
    {
        longueur += 1;
        m = m->suivant;
    }
    return longueur;
}

int liste_tete(liste *l)
{
    assert(l->premier != NULL);
    return l->premier->valeur;
}

void liste_ajout_en_tete(liste *l, int valeur)
{
    l->premier = maillon_creer(valeur, NULL, l->premier);
    if(l->dernier == NULL) // la liste était vide
        l->dernier = l->premier;
}

void liste_suppr_en_tete(liste *l)
{
    assert(l->premier != NULL);
    maillon *m = l->premier;
    l->premier = m->suivant;
    maillon_detruire(m); // on libère la mémoire
    if(l->premier == NULL) // on a vidé la liste
        l->dernier = NULL;
    else
        l->premier->precedent = NULL;
}

void liste_ajout_en_fin(liste *l, int valeur)
{
    // maillon_creer chaîne déjà l'ancien dernier au nouveau
    l->dernier = maillon_creer(valeur, l->dernier, NULL);
    if(l->premier == NULL) // la liste était vide
        l->premier = l->dernier;
}

maillon *liste_cherche_maillon(liste *l, int valeur)
{
    maillon *m = l->premier;
    while(m != NULL && m->valeur != valeur)
    {
        m = m->suivant;
    }
    return m;
}

void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur)
{
    maillon *mn = maillon_creer(valeur, m, m->suivant);
    if (m == l->dernier)
        l->dernier = mn;
}

La fonction liste_queue n'a pas été reprise : une queue qui partage ses maillons avec la liste aurait un premier maillon dont le champ precedent n'est pas NULL, ce qui viole l'invariant.

Question 29

Écrire une fonction de prototype

void liste_suppr_en_fin(liste *l);

qui supprime en \(O(1)\) le dernier maillon d'une liste non vide.

Corrigé 
void liste_suppr_en_fin(liste *l)
{
    assert(l->dernier != NULL);
    maillon *fin = l->dernier;
    l->dernier = fin->precedent;

    if (l->dernier == NULL)
        l->premier = NULL;
    else
        l->dernier->suivant = NULL;

    maillon_detruire(fin);
}

Question 30

Écrire une fonction de prototype

void liste_ajout_maillon_avant(liste *l, maillon *m, int valeur);

qui ajoute un maillon avant m en \(O(1)\).

Corrigé 
void liste_ajout_maillon_avant(liste *l, maillon *m, int valeur)
{
    maillon *mn = maillon_creer(valeur, m->precedent, m);
    if(m == l->premier)
        l->premier = mn;
}

Question 31

Écrire une fonction de prototype

void liste_suppr_maillon(liste *l, maillon *m);

qui supprime en \(O(1)\) le maillon m.

Corrigé 
void liste_suppr_maillon(liste *l, maillon *m)
{
    if (m == l->premier)
        liste_suppr_en_tete(l);
    else if (m == l->dernier)
        liste_suppr_en_fin(l);
    else
    {
        m->precedent->suivant = m->suivant;
        m->suivant->precedent = m->precedent;
        maillon_detruire(m);
    }
}