Structures séquentielles : listes, piles, files
Cours · informatique (MP2I/MPI), chapitre 7 · MP2I et MPI · le début du chapitre, la suite sur Adloun
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
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 |
inserer(l, i, x) | transformateur | insère en position |
supprimer(l, i) | transformateur | retire l'élément de position |
7.2.1 Par un tableau
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;
}Si la boucle allait de vers 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.
« 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 , comme démontré au chapitre chap:algo-prog.