Structures séquentielles : listes, piles, files

Cours complet · informatique (MP2I/MPI), chapitre 7 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

7.1 Trois contrats, deux réalisations

Ce chapitre met en pratique le précédent. Trois structures abstraites — la liste, la pile, la file — et pour chacune les deux mises en œuvre que le programme retient : « implémentation par un tableau, par des maillons chaînés ». Le programme ajoute une consigne pédagogique qu'on suivra : « on présente les structures de données construites à l'aide de pointeurs d'abord au tableau avant de guider les étudiants dans l'implémentation ».

Tout le chapitre tourne autour d'une seule question : quelle opération veut-on répéter ? Car les deux réalisations sont exactement inverses l'une de l'autre.

7.2 La liste

Définition 7.1Contrat

Une liste est une suite finie et ordonnée d'éléments, avec accès par position.

Opération	Rôle	Effet
`creer()`	constructeur	liste vide
`longueur(l)`	accesseur	nombre d'éléments
`lire(l, i)`	accesseur	l'élément de position $i$
`inserer(l, i, x)`	transformateur	insère $x$ en position $i$
`supprimer(l, i)`	transformateur	retire l'élément de position $i$

7.2.1 Par un tableau

Définition 7.2Tableau et taille effective

On fixe une capacité maximale et l'on retient combien de cases sont utilisées. Le programme le dit ainsi : « pour l'implémentation par un tableau, on se fixe une taille maximale ».


#define CAPACITE 100

typedef struct {
    int tab[CAPACITE];
    int n;                  /* nombre de cases EFFECTIVEMENT utilisées, n <= CAPACITE */
} liste_tab;


/* Insère x en position i. Précondition : 0 <= i <= l->n et l->n < CAPACITE. */
void inserer(liste_tab* l, int i, int x) {
    assert(l != NULL && 0 <= i && i <= l->n && l->n < CAPACITE);
    for (int j = l->n; j > i; j = j - 1) {   /* on décale vers la DROITE, */
        l->tab[j] = l->tab[j - 1];           /* en partant de la FIN */
    }
    l->tab[i] = x;
    l->n = l->n + 1;
}

AttentionDécaler dans le mauvais sens écrase tout

Si la boucle allait de $i$ vers $n$ en écrivant tab[j+1] = tab[j], la première écriture détruirait la valeur que la deuxième doit lire, et toutes les cases finiraient égales à tab[i]. On décale en partant du bout vers lequel on pousse. C'est un cas typique de faute qu'aucune erreur de compilation ne signale, et qu'un test sur trois éléments révèle en une seconde.

iRemarqueRedimensionner

« On peut évoquer le problème du redimensionnement d'un tableau », dit le programme. Lorsque le tableau est plein, on en alloue un de capacité double et l'on recopie : le coût amorti d'un ajout en fin reste $O (1)$ , comme démontré au chapitre chap:algo-prog.

7.2.2 Par des maillons chaînés

Définition 7.3Maillon

Chaque élément vit dans un maillon qui contient sa valeur et un pointeur vers le suivant. Le dernier pointe sur NULL.


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


(* En OCaml, le type somme récursif dit la même chose en trois lignes,
   et c'est exactement le type 'a list prédéfini. *)
type 'a liste = Vide | Cons of 'a * 'a liste


/* Insère x en tête. Renvoie la nouvelle tête, ou l'ancienne si malloc échoue. */
maillon* inserer_tete(maillon* tete, int x) {
    maillon* neuf = malloc(sizeof(maillon));
    if (neuf == NULL) { return tete; }
    neuf->valeur = x;
    neuf->suivant = tete;      /* on RACCROCHE avant de rendre */
    return neuf;
}

/* Libère toute la chaîne. */
void detruire(maillon* tete) {
    while (tete != NULL) {
        maillon* suiv = tete->suivant;   /* on RETIENT avant de libérer */
        free(tete);
        tete = suiv;
    }
}

AttentionLibérer avant d'avoir retenu le suivant

Écrire free(tete); tete = tete->suivant; lit un champ dans une mémoire déjà rendue : c'est le pointeur fou du chapitre chap:langage-c. Le programme peut fonctionner cent fois puis échouer — la mémoire libérée n'est pas effacée, elle est seulement disponible. La ligne maillon* suiv = tete->suivant; n'est pas une élégance : elle est obligatoire.

7.2.3 Le coût, et comment choisir

ImportantDeux réalisations, deux profils exactement inverses

Opération	Tableau	Maillons
Lire la position $i$	$O (1)$	$O (i)$
Insérer en tête	$O (n)$	$O (1)$
Insérer en position $i$	$O (n - i)$	$O (i)$
Supprimer en tête	$O (n)$	$O (1)$
Mémoire par élément	la valeur	la valeur et un pointeur
Voisinage en mémoire	contigu, donc lu vite	dispersé

La règle se dit en une phrase : si l'on accède par indice, tableau ; si l'on insère et supprime en tête, maillons.

Et la ligne « voisinage en mémoire » n'est pas décorative — mais elle ne dit pas ce qu'on croit. Ce n'est pas le chaînage qui coûte, c'est la dispersion. Mesuré sur ce livre, un parcours de huit millions d'éléments :

tableau	référence
chaîne dont les maillons sont contigus	$\times 1, 5$
chaîne dont les maillons sont dispersés	$\times 115$

Une chaîne allouée d'un bloc n'est qu'à peine plus lente qu'un tableau ; c'est la même chaîne, allouée maillon par maillon au fil d'un programme, qui s'effondre — chaque saut d'adresse manque le cache du processeur. À complexité égale, c'est la localité qui décide, et le tableau la garantit par construction.

7.3 La pile

Définition 7.4Contrat : dernier entré, premier sorti

Une pile n'autorise l'ajout et le retrait qu'à une seule extrémité, le sommet. C'est la discipline lifo — last in, first out.

Exemple 7.5Par un tableau : le sommet est la dernière case


typedef struct { int tab[CAPACITE]; int n; } pile;

void pile_empiler(pile* p, int x) {
    assert(p != NULL && p->n < CAPACITE);
    p->tab[p->n] = x;
    p->n = p->n + 1;
}

int pile_depiler(pile* p) {
    assert(p != NULL && p->n > 0);
    p->n = p->n - 1;
    return p->tab[p->n];
}

Les deux opérations sont $O (1)$ : aucun décalage, puisqu'on ne touche qu'au bout.

Exemple 7.6Par des maillons : le sommet est la tête

Empiler, c'est inserer_tete ; dépiler, c'est retirer la tête. Là encore $O (1)$ , et sans capacité maximale. En OCaml, la liste immuable est déjà une pile :


let empiler p x = x :: p
let depiler = function [] -> failwith "pile vide" | x :: r -> (x, r)

Le module Stack de la bibliothèque standard en offre une version mutable : create, is_empty, push, pop, et l'exception Empty.

Exemple 7.7Un usage : vérifier un parenthésage


(* Renvoie true si les parenthèses, crochets et accolades de s sont
   correctement imbriqués. Précondition : aucune. *)
let bien_parenthese s =
  let p = Stack.create () in
  let ouvrante = function ')' -> '(' | ']' -> '[' | '}' -> '{' | _ -> ' ' in
  try
    String.iter (fun c ->
      match c with
      | '(' | '[' | '{' -> Stack.push c p
      | ')' | ']' | '}' ->
          if Stack.is_empty p || Stack.pop p <> ouvrante c then raise Exit
      | _ -> ()) s;
    Stack.is_empty p            (* tout ce qui a été ouvert a été fermé *)
  with Exit -> false

La pile est ici le bon choix parce que la dernière parenthèse ouverte est la première à devoir se fermer : la structure du problème est exactement la discipline lifo. C'est aussi, exactement, la pile d'exécution du chapitre chap:recursivite.

7.4 La file

Définition 7.8Contrat : premier entré, premier sorti

Une file ajoute à une extrémité et retire à l'autre. C'est la discipline fifo — first in, first out, la file d'attente.

Exemple 7.9Par des maillons : deux pointeurs

On garde un pointeur de tête (d'où l'on retire) et un pointeur de queue (où l'on ajoute). Les deux opérations sont alors $O (1)$ .


typedef struct {
    maillon* tete;      /* on défile ici */
    maillon* queue;     /* on enfile ici */
} file;

Méthode : Par un tableau : le tableau circulaire

Avec un simple tableau, défiler en position $0$ obligerait à décaler tout le reste, en $O (n)$ . On garde donc deux indices, début et fin, et l'on repart au début du tableau quand on atteint la fin — d'où le modulo.


typedef struct { int tab[CAPACITE]; int debut; int n; } file_circ;

void enfiler(file_circ* f, int x) {
    assert(f != NULL && f->n < CAPACITE);
    f->tab[(f->debut + f->n) % CAPACITE] = x;
    f->n = f->n + 1;
}

int defiler(file_circ* f) {
    assert(f != NULL && f->n > 0);
    int x = f->tab[f->debut];
    f->debut = (f->debut + 1) % CAPACITE;
    f->n = f->n - 1;
    return x;
}

Les deux opérations sont $O (1)$ , et le tableau est réutilisé indéfiniment. C'est la structure qu'emploiera le parcours en largeur du chapitre chap:parcours.

AttentionPleine ou vide, il faut savoir les distinguer

Si l'on ne gardait que début et fin, l'égalité debut == fin désignerait à la fois la file vide et la file pleine : deux états contradictoires, un seul témoin. C'est pourquoi la structure ci-dessus retient $n$ , le nombre d'éléments. L'autre parade classique — laisser toujours une case libre — perd une case mais évite un champ ; les deux se défendent, à condition de choisir et de le documenter.

7.5 Ce qu'il faut retenir

ImportantLe tableau et la chaîne se répondent

Le tableau excelle à	La chaîne excelle à
lire la $i$ -ième case, en $O (1)$	insérer et supprimer en tête, en $O (1)$
parcourir vite (mémoire contiguë)	croître sans capacité maximale
ne rien coûter en mémoire de plus	partager une queue sans copie

Pile : $O (1)$ des deux côtés, quelle que soit la réalisation — c'est pourquoi elle est partout. File : $O (1)$ avec des maillons et deux pointeurs, ou avec un tableau circulaire ; jamais avec un tableau naïf. Ces deux structures reviendront au chapitre chap:parcours, où le seul remplacement d'une pile par une file transforme un parcours en profondeur en parcours en largeur.

Continuer sur Adloun : animation, QCM, fiches, exercices