Chapitre 16 — Introduction aux listes, piles et files
Choisir et manipuler des structures de données adaptées aux traitements
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- expliquer les principales limites d’un tableau de taille fixe ;
- distinguer une structure statique d’une structure dynamique ;
- décrire le principe d’une liste chaînée et le rôle de ses cellules ;
- parcourir, rechercher, ajouter et supprimer un élément dans une liste ;
- expliquer le principe LIFO d’une pile et utiliser ses opérations fondamentales ;
- expliquer le principe FIFO d’une file et utiliser ses opérations fondamentales ;
- reconnaître les situations qui relèvent naturellement d’une liste, d’une pile ou d’une file ;
- analyser les cas d’erreur tels que la pile vide, la file vide ou une référence invalide ;
- comparer le coût des opérations selon la structure de données choisie ;
- concevoir un petit algorithme combinant plusieurs structures de données.
Prérequis
- variables, constantes et types simples ;
- conditions et boucles ;
- tableaux à une dimension ;
- fonctions, procédures et paramètres ;
- enregistrements et tableaux d’enregistrements ;
- notions élémentaires de complexité : coût constant et coût linéaire.
Plan du chapitre
Section | Contenu principal |
|---|---|
| 16.1 | Limites des tableaux et besoin de structures dynamiques |
| 16.2 | Listes : principe, ajout, suppression, parcours et recherche |
| 16.3 | Piles : principe LIFO, empiler, dépiler, sommet et applications |
| 16.4 | Files : principe FIFO, enfiler, défiler, tête, fin et applications |
| Applications | Historique, annulation, contrôle d’expressions, attente et traitement de tâches |
| TD | Exercices progressifs avec corrigés indicatifs |
Organisation pédagogique indicative
Activité | Durée indicative | Contenu |
|---|---|---|
| Cours | 3 h | Principes, représentations et opérations fondamentales |
| Travaux dirigés | 3 h | Traces, choix de structure et conception d’algorithmes |
| Travaux pratiques | 3 h | Implémentation dans un langage de programmation |
| Évaluation | 1 h | Questions de compréhension et problème de synthèse |
| Idée centrale : une structure de données n’est pas seulement un conteneur. Elle impose une manière d’organiser les éléments et détermine le coût des opérations de consultation, d’ajout et de suppression. |
Introduction aux structures de données dynamiques
Les tableaux constituent une première solution efficace pour stocker plusieurs valeurs de même type. Ils sont simples à parcourir et permettent un accès direct à un élément à partir de son indice. Cependant, leur taille est généralement fixée lors de la déclaration. Cette contrainte devient gênante lorsque le nombre d’éléments varie pendant l’exécution.
Les listes, les piles et les files proposent d’autres manières d’organiser les données. Une liste facilite l’ajout et la suppression d’éléments. Une pile impose que le dernier élément ajouté soit le premier retiré. Une file impose au contraire que le premier élément ajouté soit le premier retiré.
Ces structures sont souvent étudiées comme des types abstraits de données. On s’intéresse d’abord aux opérations disponibles et à leur comportement, puis à la manière de les représenter en mémoire à l’aide d’un tableau, d’enregistrements chaînés ou de mécanismes fournis par un langage de programmation.
| Vocabulaire : dans ce chapitre, le mot référence désigne un moyen d’identifier une cellule ou un objet en mémoire. La valeur NIL représente l’absence de cellule suivante. Selon le langage, on pourra rencontrer les termes pointeur, adresse, référence ou null. |
16.1 Limites des tableaux
16.1.1 Taille fixe
Dans un tableau classique, la capacité maximale est déterminée au moment de la déclaration. Si un tableau est déclaré avec 100 cases, il ne peut pas stocker directement un 101e élément sans créer un nouveau tableau plus grand et recopier les données.
Exemple de déclaration
| Constante CAPACITE_MAX ← 100 Variables valeurs : Tableau[0..CAPACITE_MAX - 1] d’Entiers n : Entier |
Il faut distinguer deux notions :
- la capacité, qui correspond au nombre total de cases réservées ;
- la taille logique, qui correspond au nombre de cases réellement utilisées.
Capacité | Taille logique | Interprétation |
|---|---|---|
| 100 | 0 | Le tableau est vide mais 100 cases sont disponibles. |
| 100 | 37 | Trente-sept éléments sont présents. |
| 100 | 100 | Le tableau est plein. Aucun ajout direct n’est possible. |
| Attention : un tableau de grande capacité évite certains dépassements, mais peut gaspiller de la mémoire. Un tableau trop petit oblige à interrompre les ajouts ou à effectuer un redimensionnement. |
16.1.2 Insertion coûteuse
Insérer un élément au milieu d’un tableau exige de libérer une case. Les éléments situés après la position d’insertion doivent être décalés vers la droite. Dans le pire cas, presque tout le tableau est déplacé.
Insertion de x à la position p
| Si n = capacite Alors Écrire("Tableau plein") Sinon Pour i allant de n - 1 à p avec un pas de -1 Faire T[i + 1] ← T[i] FinPour T[p] ← x n ← n + 1 FinSi |
Avant | Insertion | Après |
|---|---|---|
| [12, 18, 25, 31] | Insérer 20 à la position 2 | [12, 18, 20, 25, 31] |
| Déplacements | 31 puis 25 | Deux affectations de décalage |
16.1.3 Suppression coûteuse
Supprimer un élément d’un tableau crée un vide. Pour conserver les éléments de manière contiguë, il faut décaler vers la gauche tous les éléments placés après la position supprimée.
Suppression de la position p
| Si p < 0 OU p ≥ n Alors Écrire("Position invalide") Sinon Pour i allant de p à n - 2 Faire T[i] ← T[i + 1] FinPour n ← n - 1 FinSi |
L’accès par indice reste très rapide dans un tableau, mais les insertions et suppressions au début ou au milieu peuvent nécessiter un nombre de déplacements proportionnel au nombre d’éléments.
16.1.4 Besoin de structures dynamiques
Une structure dynamique peut évoluer pendant l’exécution. Elle réserve de l’espace lorsqu’un nouvel élément est ajouté et libère cet espace lorsqu’un élément est supprimé. Elle n’exige pas nécessairement de connaître à l’avance le nombre maximal d’éléments.
- une liste convient lorsque des éléments doivent être ajoutés ou supprimés fréquemment ;
- une pile convient lorsque l’ordre de retrait doit être l’inverse de l’ordre d’ajout ;
- une file convient lorsque les éléments doivent être traités dans leur ordre d’arrivée.
Structure | Accès direct par indice | Ajout/suppression | Ordre imposé |
|---|---|---|---|
| Tableau | Oui | Peut nécessiter des décalages | Aucun |
| Liste chaînée | Non, parcours nécessaire | Rapide si la position est connue | Aucun |
| Pile | Non | Au sommet | LIFO |
| File | Non | En fin et en tête | FIFO |
| Choix raisonné : une structure dynamique n’est pas toujours meilleure qu’un tableau. Le choix dépend des opérations les plus fréquentes : accès aléatoire, parcours, insertion, suppression ou respect d’un ordre particulier. |
16.2 Listes
16.2.1 Principe d’une liste
Une liste est une collection ordonnée d’éléments dont la taille peut varier. Dans une liste chaînée simple, chaque élément est stocké dans une cellule. Une cellule contient une valeur et une référence vers la cellule suivante.
Type d’une cellule
| Type Cellule = Enregistrement valeur : Entier suivant : Référence vers Cellule FinEnregistrement Variables tete : Référence vers Cellule |
La variable tete désigne la première cellule. Si la liste est vide, tete vaut NIL. La dernière cellule contient NIL dans son champ suivant.
Élément | Valeur | Référence suivante |
|---|---|---|
| Cellule 1 | 12 | Cellule 2 |
| Cellule 2 | 25 | Cellule 3 |
| Cellule 3 | 41 | NIL |
Représentation logique : tete → [12] → [25] → [41] → NIL
16.2.2 Création et liste vide
Initialisation
| tete ← NIL |
Tester si une liste est vide revient à comparer sa tête à NIL.
Test de vacuité
| Fonction EstVide(tete) : Booléen Retourner tete = NIL FinFonction |
16.2.3 Ajout en tête
L’ajout en tête est l’opération la plus simple. La nouvelle cellule pointe vers l’ancienne première cellule, puis la tête est mise à jour.
Ajouter une valeur au début
| Procédure AjouterEnTete(E/S tete, x) nouvelle ← Allouer(Cellule) nouvelle.valeur ← x nouvelle.suivant ← tete tete ← nouvelle FinProcédure |
Étape | tete | nouvelle.suivant | Liste obtenue |
|---|---|---|---|
| Avant | Cellule contenant 12 | — | 12 → 25 → NIL |
| Création de 7 | 12 | 12 | Nouvelle cellule prête |
| Mise à jour | 7 | 12 | 7 → 12 → 25 → NIL |
16.2.4 Ajout en fin
Pour ajouter en fin dans une liste simplement chaînée, il faut atteindre la dernière cellule, sauf si une référence vers la fin est maintenue séparément.
Ajouter une valeur à la fin
| Procédure AjouterEnFin(E/S tete, x) nouvelle ← Allouer(Cellule) nouvelle.valeur ← x nouvelle.suivant ← NIL Si tete = NIL Alors tete ← nouvelle Sinon courant ← tete TantQue courant.suivant ≠ NIL Faire courant ← courant.suivant FinTantQue courant.suivant ← nouvelle FinSi FinProcédure |
| Complexité : sans référence vers la dernière cellule, l’ajout en fin nécessite un parcours complet. Avec une référence fin correctement maintenue, l’ajout peut devenir constant. |
16.2.5 Ajout à une position donnée
L’insertion à une position exige de trouver la cellule qui précède la position demandée. Les cas particuliers sont la liste vide, l’insertion en tête et une position située après la fin de la liste.
Insérer après une cellule connue
| Procédure InsererApres(precedent, x) Si precedent = NIL Alors Écrire("Cellule précédente invalide") Sinon nouvelle ← Allouer(Cellule) nouvelle.valeur ← x nouvelle.suivant ← precedent.suivant precedent.suivant ← nouvelle FinSi FinProcédure |
16.2.6 Suppression en tête
La première cellule est retirée en déplaçant la tête vers la cellule suivante. La cellule supprimée doit ensuite être libérée lorsque le modèle mémoire le demande.
Supprimer le premier élément
| Procédure SupprimerTete(E/S tete) Si tete = NIL Alors Écrire("Liste vide") Sinon ancienne ← tete tete ← tete.suivant Libérer(ancienne) FinSi FinProcédure |
16.2.7 Suppression d’une valeur
Pour supprimer la première occurrence d’une valeur, il faut conserver deux références : courant pour la cellule examinée et precedent pour celle qui la précède.
Supprimer la première occurrence de x
| Fonction SupprimerValeur(E/S tete, x) : Booléen precedent ← NIL courant ← tete TantQue courant ≠ NIL ET courant.valeur ≠ x Faire precedent ← courant courant ← courant.suivant FinTantQue Si courant = NIL Alors Retourner Faux FinSi Si precedent = NIL Alors tete ← courant.suivant Sinon precedent.suivant ← courant.suivant FinSi Libérer(courant) Retourner Vrai FinFonction |
| Point important : le traitement de la première cellule est particulier, car sa suppression modifie directement la variable tete. |
16.2.8 Parcours d’une liste
Contrairement à un tableau, une liste chaînée ne permet pas d’accéder directement au troisième ou au dixième élément. Il faut partir de la tête et suivre successivement les références suivant.
Afficher tous les éléments
| courant ← tete TantQue courant ≠ NIL Faire Écrire(courant.valeur) courant ← courant.suivant FinTantQue |
Itération | courant.valeur | Action | courant après mise à jour |
|---|---|---|---|
| 1 | 12 | Afficher 12 | Cellule 25 |
| 2 | 25 | Afficher 25 | Cellule 41 |
| 3 | 41 | Afficher 41 | NIL |
| Fin | — | Condition fausse | NIL |
16.2.9 Recherche dans une liste
Recherche de la première occurrence
| Fonction Rechercher(tete, x) : Référence vers Cellule courant ← tete TantQue courant ≠ NIL ET courant.valeur ≠ x Faire courant ← courant.suivant FinTantQue Retourner courant FinFonction |
La fonction retourne la cellule trouvée ou NIL si la valeur est absente. Dans le pire cas, toutes les cellules sont examinées.
16.2.10 Autres formes de listes
Type de liste | Caractéristique | Intérêt principal |
|---|---|---|
| Simplement chaînée | Chaque cellule connaît la suivante | Structure minimale et parcours vers l’avant |
| Doublement chaînée | Chaque cellule connaît la précédente et la suivante | Parcours dans les deux sens et suppressions facilitées |
| Circulaire | La dernière cellule renvoie vers la première | Traitements cycliques et ordonnancement circulaire |
| Avec sentinelle | Une cellule spéciale encadre la liste | Réduction du nombre de cas particuliers |
16.2.11 Coût indicatif des opérations
Opération | Liste simplement chaînée | Commentaire |
|---|---|---|
| Accès au premier élément | O(1) | La tête est directement disponible. |
| Accès au iᵉ élément | O(n) | Un parcours est nécessaire. |
| Ajout en tête | O(1) | Aucun parcours. |
| Ajout en fin | O(n) ou O(1) | O(1) si une référence fin est conservée. |
| Recherche d’une valeur | O(n) | Examen séquentiel. |
| Suppression après une cellule connue | O(1) | La cellule précédente est déjà connue. |
16.3 Piles
16.3.1 Principe LIFO
Une pile est une structure dans laquelle les ajouts et les retraits s’effectuent du même côté, appelé sommet. Elle suit la règle LIFO : Last In, First Out, c’est-à-dire « dernier entré, premier sorti ».
L’image classique est celle d’une pile d’assiettes : on pose une nouvelle assiette au-dessus et on retire d’abord celle qui se trouve au sommet.
Opération | Nom usuel | Effet |
|---|---|---|
| Ajouter un élément | Empiler / Push | L’élément devient le nouveau sommet. |
| Retirer un élément | Dépiler / Pop | Le sommet est retiré et retourné. |
| Consulter le sommet | Sommet / Peek | Le sommet est lu sans être retiré. |
| Tester le contenu | EstVide | Indique si la pile ne contient aucun élément. |
16.3.2 Représentation d’une pile
Une pile peut être représentée par un tableau et un indice sommet, ou par une liste chaînée dont la tête joue le rôle de sommet. Le type abstrait reste identique : l’utilisateur de la pile manipule les opérations sans dépendre de la représentation interne.
Interface abstraite
| Initialiser(P) EstVide(P) Empiler(P, x) Depiler(P) : Élément Sommet(P) : Élément |
16.3.3 Empiler
Version avec tableau
| Procédure Empiler(E/S P, x) Si P.sommet = CAPACITE - 1 Alors Écrire("Débordement de pile") Sinon P.sommet ← P.sommet + 1 P.elements[P.sommet] ← x FinSi FinProcédure |
Version avec liste chaînée
| Procédure Empiler(E/S sommet, x) nouvelle ← Allouer(Cellule) nouvelle.valeur ← x nouvelle.suivant ← sommet sommet ← nouvelle FinProcédure |
16.3.4 Dépiler
Version avec tableau
| Fonction Depiler(E/S P) : Élément Si P.sommet = -1 Alors Erreur("Pile vide") FinSi x ← P.elements[P.sommet] P.sommet ← P.sommet - 1 Retourner x FinFonction |
| Sous-débordement : dépiler une pile vide est une erreur. Toute opération Depiler ou Sommet doit être précédée d’un test, sauf si la fonction signale elle-même l’erreur. |
16.3.5 Consulter le sommet
| Fonction Sommet(P) : Élément Si EstVide(P) Alors Erreur("Pile vide") FinSi Retourner P.elements[P.sommet] FinFonction |
L’opération Sommet ne modifie pas la pile. Elle permet seulement d’observer le prochain élément qui serait retiré.
16.3.6 Trace des opérations
Opération | Pile, du bas vers le sommet | Valeur retournée |
|---|---|---|
| Initialiser | [] | — |
| Empiler(4) | [4] | — |
| Empiler(9) | [4, 9] | — |
| Empiler(2) | [4, 9, 2] | — |
| Sommet() | [4, 9, 2] | 2 |
| Dépiler() | [4, 9] | 2 |
| Dépiler() | [4] | 9 |
16.3.7 Application : historique
Dans un navigateur ou un éditeur, une pile peut mémoriser les états précédents. L’état le plus récent est placé au sommet et sera le premier restauré.
Historique simplifié
| Procédure VisiterPage(E/S historique, pageCourante, nouvellePage) Empiler(historique, pageCourante) pageCourante ← nouvellePage FinProcédure Procédure Retour(E/S historique, E/S pageCourante) Si NON EstVide(historique) Alors pageCourante ← Depiler(historique) FinSi FinProcédure |
16.3.8 Application : annulation
Une commande d’édition peut être enregistrée avant son exécution. L’action Annuler dépile la dernière commande et applique son opération inverse. Une seconde pile peut conserver les commandes annulées pour permettre Rétablir.
Pile | Rôle |
|---|---|
| Pile Annuler | Contient les commandes exécutées, la plus récente au sommet. |
| Pile Rétablir | Contient les commandes annulées, la plus récente au sommet. |
16.3.9 Application : appels de fonctions
Lorsqu’une fonction appelle une autre fonction, le système mémorise le point de retour, les paramètres et les variables locales dans une pile d’appels. Le dernier appel effectué doit se terminer avant que l’appel précédent puisse reprendre.
Ce mécanisme explique le fonctionnement de la récursivité : chaque appel récursif crée un nouveau contexte au sommet de la pile. Une récursion sans cas de base peut provoquer un débordement de pile.
16.3.10 Application : vérifier des parenthèses
Parenthèses correctement équilibrées
| Fonction ParenthesesValides(texte) : Booléen Initialiser(P) Pour chaque caractere c de texte Faire Si c = '(' Alors Empiler(P, c) SinonSi c = ')' Alors Si EstVide(P) Alors Retourner Faux FinSi Depiler(P) FinSi FinPour Retourner EstVide(P) FinFonction |
| Généralisation : pour traiter plusieurs types de symboles — (), [] et {} — on empile les symboles ouvrants et on vérifie que chaque symbole fermant correspond au sommet de la pile. |
16.4 Files
16.4.1 Principe FIFO
Une file est une structure dans laquelle les éléments sont ajoutés à une extrémité, appelée fin, et retirés à l’autre extrémité, appelée tête. Elle suit la règle FIFO : First In, First Out, c’est-à-dire « premier entré, premier sorti ».
L’exemple classique est une file d’attente : la première personne arrivée est normalement la première servie.
Opération | Nom usuel | Effet |
|---|---|---|
| Ajouter un élément | Enfiler / Enqueue | Ajout à la fin de la file. |
| Retirer un élément | Défiler / Dequeue | Retrait de l’élément situé en tête. |
| Consulter la tête | Tête / Front | Lecture sans retrait. |
| Tester le contenu | EstVide | Indique si la file est vide. |
16.4.2 Tête et fin
La tête désigne le prochain élément qui sera traité. La fin désigne la position où le prochain élément sera ajouté. Une bonne représentation permet d’effectuer Enfiler et Défiler sans décaler tous les éléments.
Représentation logique : tête → [A] [B] [C] ← fin
16.4.3 Représentation par liste chaînée
Une file chaînée conserve généralement deux références : tete vers la première cellule et fin vers la dernière. Ainsi, l’ajout et le retrait peuvent être réalisés en temps constant.
Structure abstraite
| Type File = Enregistrement tete : Référence vers Cellule fin : Référence vers Cellule FinEnregistrement |
Initialisation
| F.tete ← NIL F.fin ← NIL |
16.4.4 Enfiler
Ajouter à la fin
| Procédure Enfiler(E/S F, x) nouvelle ← Allouer(Cellule) nouvelle.valeur ← x nouvelle.suivant ← NIL Si F.fin = NIL Alors F.tete ← nouvelle F.fin ← nouvelle Sinon F.fin.suivant ← nouvelle F.fin ← nouvelle FinSi FinProcédure |
| Cas particulier : lorsque la file était vide, la nouvelle cellule est à la fois la tête et la fin. |
16.4.5 Défiler
Retirer la tête
| Fonction Defiler(E/S F) : Élément Si F.tete = NIL Alors Erreur("File vide") FinSi ancienne ← F.tete x ← ancienne.valeur F.tete ← F.tete.suivant Si F.tete = NIL Alors F.fin ← NIL FinSi Libérer(ancienne) Retourner x FinFonction |
| Mise à jour indispensable : après le retrait du dernier élément, tete et fin doivent toutes les deux valoir NIL. Sinon, la file contient une référence incohérente. |
16.4.6 Trace des opérations
Opération | File de la tête vers la fin | Valeur retournée |
|---|---|---|
| Initialiser | [] | — |
| Enfiler(A) | [A] | — |
| Enfiler(B) | [A, B] | — |
| Enfiler(C) | [A, B, C] | — |
| Tête() | [A, B, C] | A |
| Défiler() | [B, C] | A |
| Enfiler(D) | [B, C, D] | — |
| Défiler() | [C, D] | B |
16.4.7 File circulaire avec tableau
Une file peut également être représentée par un tableau circulaire. Les indices de tête et de fin reviennent au début du tableau grâce à l’opérateur modulo. Cette technique réutilise les cases libérées sans déplacer les éléments.
Avancement circulaire
| indiceSuivant ← (indiceActuel + 1) MOD capacite |
Avantage | Difficulté |
|---|---|
| Pas de décalage lors de Défiler | Il faut distinguer correctement file vide et file pleine. |
| Mémoire contiguë et accès efficace | La capacité reste limitée si le tableau n’est pas redimensionné. |
16.4.8 Application : gestion d’attente
Dans un guichet, une plateforme de rendez-vous ou un système de support, chaque demande est placée en fin de file. L’agent traite la demande située en tête.
Traitement simple
| TantQue serviceOuvert Faire Si nouvelleDemande Alors Enfiler(attente, demande) FinSi Si agentDisponible ET NON EstVide(attente) Alors demandeCourante ← Defiler(attente) Traiter(demandeCourante) FinSi FinTantQue |
16.4.9 Application : impression
Un serveur d’impression peut conserver les travaux dans une file. Le premier document reçu est envoyé en premier à l’imprimante. Chaque travail peut être un enregistrement contenant le nom du fichier, l’utilisateur, le nombre de pages et l’heure de réception.
Type d’un travail d’impression
| Type TravailImpression = Enregistrement identifiant : Entier fichier : Chaîne utilisateur : Chaîne nbPages : Entier FinEnregistrement |
16.4.10 Application : traitement de tâches
Les systèmes informatiques utilisent des files pour répartir des tâches entre plusieurs travailleurs. Les producteurs ajoutent des tâches et les consommateurs les retirent. Cette organisation sépare la création du travail de son exécution.
| Nuance : une file FIFO respecte l’ordre d’arrivée. Une file de priorité choisit l’élément selon un niveau d’urgence ou une priorité, et non uniquement selon son ancienneté. |
Comparaison générale des structures
Critère | Tableau | Liste | Pile | File |
|---|---|---|---|---|
| Taille | Fixe ou redimensionnée | Dynamique | Dynamique ou fixe | Dynamique ou fixe |
| Accès direct | Oui | Non | Sommet seulement | Tête seulement |
| Ajout principal | Selon indice | Selon position | Sommet | Fin |
| Retrait principal | Selon indice | Selon position | Sommet | Tête |
| Ordre | Libre | Libre | LIFO | FIFO |
| Exemple | Notes | Catalogue évolutif | Annulation | Attente |
Méthode de choix
1. Identifier les opérations les plus fréquentes : accès, ajout, suppression ou retrait.
2. Déterminer si un ordre de traitement est imposé.
3. Vérifier si le nombre maximal d’éléments est connu.
4. Évaluer le coût acceptable des parcours et des déplacements.
5. Choisir la représentation interne : tableau, liste chaînée ou structure native du langage.
6. Définir les cas d’erreur et les invariants avant d’écrire les opérations.
Applications guidées
Application 1 — Inverser une suite avec une pile
Une pile restitue les éléments dans l’ordre inverse de leur insertion.
| Initialiser(P) Pour i allant de 0 à n - 1 Faire Empiler(P, T[i]) FinPour Pour i allant de 0 à n - 1 Faire T[i] ← Depiler(P) FinPour |
Entrée | Empilement | Dépilement | Résultat |
|---|---|---|---|
| [3, 8, 5, 1] | 3, 8, 5, 1 | 1, 5, 8, 3 | [1, 5, 8, 3] |
Application 2 — File d’attente d’un service
| Enfiler(attente, "Client A") Enfiler(attente, "Client B") Enfiler(attente, "Client C") premier ← Defiler(attente) // Client A Enfiler(attente, "Client D") second ← Defiler(attente) // Client B |
L’ordre final de traitement est A, B, C, D, sauf si une règle de priorité est ajoutée.
Application 3 — Supprimer les valeurs négatives d’une liste
| precedent ← NIL courant ← tete TantQue courant ≠ NIL Faire Si courant.valeur < 0 Alors aSupprimer ← courant Si precedent = NIL Alors tete ← courant.suivant courant ← tete Sinon precedent.suivant ← courant.suivant courant ← precedent.suivant FinSi Libérer(aSupprimer) Sinon precedent ← courant courant ← courant.suivant FinSi FinTantQue |
| Difficulté : après une suppression, courant ne doit pas être avancé une seconde fois. Il doit déjà désigner l’élément qui suit la cellule supprimée. |
Application 4 — Simulation d’une liste de tâches
Une application simple peut utiliser une liste pour conserver toutes les tâches, une file pour les tâches à exécuter dans l’ordre d’arrivée et une pile pour mémoriser les tâches terminées récemment.
Structure | Contenu | Opération principale |
|---|---|---|
| Liste | Catalogue complet des tâches | Rechercher et modifier |
| File | Tâches en attente | Enfiler puis défiler |
| Pile | Historique récent | Empiler puis dépiler pour annuler |
Erreurs fréquentes et bonnes pratiques
Erreur ou risque | Conséquence | Bonne pratique |
|---|---|---|
| Oublier d’initialiser tete, sommet ou fin | Références incohérentes | Initialiser explicitement à NIL ou -1. |
| Perdre la tête d’une liste | La liste devient inaccessible | Conserver l’ancienne référence avant toute modification. |
| Dépiler ou défiler une structure vide | Erreur d’exécution | Tester EstVide ou signaler proprement l’erreur. |
| Oublier de libérer une cellule | Fuite de mémoire dans certains langages | Libérer les cellules supprimées lorsque nécessaire. |
| Libérer une cellule encore utilisée | Référence invalide | Modifier les liens avant la libération. |
| Oublier de mettre fin à NIL | File incohérente après le dernier retrait | Traiter explicitement le passage à une file vide. |
| Parcourir une liste sans avancer courant | Boucle infinie | Mettre courant à courant.suivant à chaque étape appropriée. |
| Accéder à une liste comme à un tableau | Hypothèse incorrecte de coût constant | Prévoir un parcours pour atteindre une position. |
| Mélanger LIFO et FIFO | Ordre de traitement erroné | Nommer clairement la structure et ses opérations. |
Invariants utiles
- liste vide : tete = NIL ;
- dernière cellule d’une liste simple : suivant = NIL ;
- pile vide avec tableau : sommet = -1 ;
- file vide chaînée : tete = NIL ET fin = NIL ;
- file non vide : tete ≠ NIL ET fin ≠ NIL ;
- dans une file chaînée non vide : fin.suivant = NIL.
| Définition : un invariant est une propriété qui doit rester vraie avant et après chaque opération. Les invariants facilitent la conception, la preuve et le débogage des structures de données. |
Travaux dirigés
Exercice 1 — Tableau ou liste ?
Pour chacun des cas suivants, proposer un tableau ou une liste et justifier : relevés de 24 températures horaires ; catalogue de produits dont le nombre varie ; dix notes fixes ; liste de contacts fréquemment modifiée.
Exercice 2 — Trace d’une liste
On part de la liste 4 → 9 → 12 → NIL. Ajouter 2 en tête, ajouter 20 en fin, puis supprimer la valeur 9. Donner la liste après chaque opération.
Exercice 3 — Longueur d’une liste
Écrire une fonction qui retourne le nombre de cellules d’une liste simplement chaînée.
Exercice 4 — Somme et maximum
Écrire deux fonctions calculant respectivement la somme et le maximum des valeurs d’une liste d’entiers. Préciser le comportement pour une liste vide.
Exercice 5 — Insertion triée
Écrire une procédure qui insère un entier x dans une liste déjà triée par ordre croissant, tout en conservant l’ordre.
Exercice 6 — Trace d’une pile
Exécuter les opérations Empiler(5), Empiler(8), Dépiler(), Empiler(3), Empiler(7), Sommet(), Dépiler(). Donner l’état de la pile et les valeurs retournées.
Exercice 7 — Mot inversé
Utiliser une pile pour inverser une chaîne de caractères.
Exercice 8 — Parenthèses
Déterminer si les expressions (a+b)*(c-d), ((a+b), et a+b) sont valides selon les parenthèses. Proposer un algorithme.
Exercice 9 — Trace d’une file
Exécuter Enfiler(10), Enfiler(20), Défiler(), Enfiler(30), Enfiler(40), Défiler(). Donner l’état de la file et les valeurs retirées.
Exercice 10 — File d’impression
Définir un enregistrement TravailImpression et écrire les opérations d’ajout, de consultation du prochain travail et de traitement du prochain travail.
Exercice 11 — Comparaison
Comparer le coût d’un ajout en tête, d’une recherche et d’un accès au iᵉ élément dans un tableau et une liste chaînée.
Exercice 12 — Mini-projet
Concevoir un gestionnaire de demandes : une file pour les demandes en attente, une pile pour les demandes traitées et une opération permettant d’annuler le dernier traitement.
Corrigés indicatifs des travaux dirigés
Correction 1 — Tableau ou liste ?
Cas | Choix proposé | Justification |
|---|---|---|
| 24 températures horaires | Tableau | Taille connue et accès direct par heure. |
| Catalogue variable | Liste | Ajouts et suppressions fréquents. |
| Dix notes fixes | Tableau | Taille stable et parcours simple. |
| Contacts modifiés | Liste | Collection évolutive. |
Correction 2 — Trace d’une liste
Étape | Liste |
|---|---|
| Initiale | 4 → 9 → 12 → NIL |
| Ajouter 2 en tête | 2 → 4 → 9 → 12 → NIL |
| Ajouter 20 en fin | 2 → 4 → 9 → 12 → 20 → NIL |
| Supprimer 9 | 2 → 4 → 12 → 20 → NIL |
Correction 3 — Longueur d’une liste
| Fonction Longueur(tete) : Entier n ← 0 courant ← tete TantQue courant ≠ NIL Faire n ← n + 1 courant ← courant.suivant FinTantQue Retourner n FinFonction |
Correction 4 — Somme et maximum
Somme
| Fonction SommeListe(tete) : Entier somme ← 0 courant ← tete TantQue courant ≠ NIL Faire somme ← somme + courant.valeur courant ← courant.suivant FinTantQue Retourner somme FinFonction |
Maximum
| Fonction MaximumListe(tete) : Entier Si tete = NIL Alors Erreur("Liste vide") FinSi maximum ← tete.valeur courant ← tete.suivant TantQue courant ≠ NIL Faire Si courant.valeur > maximum Alors maximum ← courant.valeur FinSi courant ← courant.suivant FinTantQue Retourner maximum FinFonction |
Correction 5 — Insertion triée
| Procédure InsererTrie(E/S tete, x) nouvelle ← Allouer(Cellule) nouvelle.valeur ← x Si tete = NIL OU x ≤ tete.valeur Alors nouvelle.suivant ← tete tete ← nouvelle Retourner FinSi courant ← tete TantQue courant.suivant ≠ NIL ET courant.suivant.valeur < x Faire courant ← courant.suivant FinTantQue nouvelle.suivant ← courant.suivant courant.suivant ← nouvelle FinProcédure |
Correction 6 — Trace d’une pile
Opération | Pile | Retour |
|---|---|---|
| Empiler(5) | [5] | — |
| Empiler(8) | [5, 8] | — |
| Dépiler() | [5] | 8 |
| Empiler(3) | [5, 3] | — |
| Empiler(7) | [5, 3, 7] | — |
| Sommet() | [5, 3, 7] | 7 |
| Dépiler() | [5, 3] | 7 |
Correction 7 — Mot inversé
| Fonction Inverser(texte) : Chaîne Initialiser(P) resultat ← "" Pour chaque caractere c de texte Faire Empiler(P, c) FinPour TantQue NON EstVide(P) Faire resultat ← resultat + Depiler(P) FinTantQue Retourner resultat FinFonction |
Correction 8 — Parenthèses
Expression | Résultat | Cause |
|---|---|---|
| (a+b)*(c-d) | Valide | Chaque parenthèse ouverte est fermée. |
| ((a+b) | Invalide | Une parenthèse reste dans la pile. |
| a+b) | Invalide | Une fermeture apparaît lorsque la pile est vide. |
L’algorithme est celui présenté dans la section 16.3.10 : empiler les ouvertures, dépiler lors des fermetures et vérifier que la pile est vide à la fin.
Correction 9 — Trace d’une file
Opération | File | Retour |
|---|---|---|
| Enfiler(10) | [10] | — |
| Enfiler(20) | [10, 20] | — |
| Défiler() | [20] | 10 |
| Enfiler(30) | [20, 30] | — |
| Enfiler(40) | [20, 30, 40] | — |
| Défiler() | [30, 40] | 20 |
Correction 10 — File d’impression
| Type TravailImpression = Enregistrement id : Entier fichier : Chaîne utilisateur : Chaîne nbPages : Entier FinEnregistrement Procédure AjouterTravail(E/S file, travail) Enfiler(file, travail) FinProcédure Fonction ProchainTravail(file) : TravailImpression Retourner Tete(file) FinFonction Procédure TraiterProchain(E/S file) Si EstVide(file) Alors Écrire("Aucun travail") Sinon travail ← Defiler(file) Imprimer(travail) FinSi FinProcédure |
Correction 11 — Comparaison
Opération | Tableau | Liste chaînée |
|---|---|---|
| Ajout en tête | O(n) avec décalages | O(1) |
| Recherche d’une valeur | O(n) | O(n) |
| Accès au iᵉ élément | O(1) | O(n) |
Correction 12 — Mini-projet
| Procédure AjouterDemande(E/S attente, demande) Enfiler(attente, demande) FinProcédure Procédure TraiterDemande(E/S attente, E/S historique) Si EstVide(attente) Alors Écrire("Aucune demande en attente") Sinon demande ← Defiler(attente) ExecuterTraitement(demande) Empiler(historique, demande) FinSi FinProcédure Procédure AnnulerDernierTraitement(E/S attente, E/S historique) Si EstVide(historique) Alors Écrire("Aucun traitement à annuler") Sinon demande ← Depiler(historique) AnnulerTraitement(demande) Enfiler(attente, demande) FinSi FinProcédure |
| Remarque : réenfiler la demande annulée la place à la fin de l’attente. Une autre règle peut la replacer en tête selon les besoins de l’application. |
Synthèse du chapitre
Notion | À retenir |
|---|---|
| Tableau | Accès direct rapide, mais taille souvent fixe et décalages lors des insertions. |
| Liste | Suite de cellules reliées ; taille évolutive et parcours séquentiel. |
| Pile | Structure LIFO : ajout et retrait au sommet. |
| File | Structure FIFO : ajout en fin et retrait en tête. |
| Tête | Première cellule d’une liste ou prochain élément d’une file. |
| Sommet | Dernier élément ajouté dans une pile. |
| NIL | Absence de cellule ou de référence. |
| Invariant | Propriété qui doit rester vraie après chaque opération. |
Méthode de résolution
1. Décrire précisément l’ordre dans lequel les éléments doivent être consultés ou retirés.
2. Choisir le type abstrait : liste, pile ou file.
3. Définir l’état vide et les invariants de la structure.
4. Écrire les opérations élémentaires avant l’algorithme principal.
5. Traiter explicitement les cas limites : structure vide, un seul élément et suppression du dernier élément.
6. Construire une table de trace pour vérifier les références, la tête, la fin ou le sommet.
7. Tester plusieurs scénarios, dont les opérations sur une structure vide.
8. Évaluer le coût des parcours et des modifications.
Glossaire
Terme | Définition |
|---|---|
| Structure dynamique | Structure dont la taille peut évoluer pendant l’exécution. |
| Cellule ou maillon | Élément d’une liste contenant une valeur et une ou plusieurs références. |
| Référence | Moyen de désigner une cellule ou un objet en mémoire. |
| Tête | Première cellule d’une liste ou premier élément d’une file. |
| Fin | Dernier élément d’une file et position des nouveaux ajouts. |
| Sommet | Extrémité d’une pile où ont lieu les ajouts et retraits. |
| LIFO | Dernier entré, premier sorti. |
| FIFO | Premier entré, premier sorti. |
| Empiler | Ajouter un élément au sommet d’une pile. |
| Dépiler | Retirer et retourner le sommet d’une pile. |
| Enfiler | Ajouter un élément à la fin d’une file. |
| Défiler | Retirer et retourner l’élément en tête d’une file. |
| NIL | Valeur indiquant qu’aucune cellule n’est référencée. |
| Sous-débordement | Tentative de retrait dans une structure vide. |
Auto-évaluation
Je suis capable de… | Oui | À revoir |
|---|---|---|
| expliquer les limites principales d’un tableau de taille fixe ; | ☐ | ☐ |
| décrire une cellule et le rôle du champ suivant ; | ☐ | ☐ |
| parcourir une liste jusqu’à NIL ; | ☐ | ☐ |
| ajouter et supprimer une cellule en tête ; | ☐ | ☐ |
| rechercher une valeur dans une liste ; | ☐ | ☐ |
| expliquer le principe LIFO ; | ☐ | ☐ |
| utiliser Empiler, Depiler et Sommet ; | ☐ | ☐ |
| expliquer le principe FIFO ; | ☐ | ☐ |
| utiliser Enfiler, Defiler, Tete et Fin ; | ☐ | ☐ |
| choisir entre tableau, liste, pile et file ; | ☐ | ☐ |
| traiter correctement les structures vides ; | ☐ | ☐ |
| construire une table de trace des opérations. | ☐ | ☐ |
| Conclusion : les listes, piles et files montrent que le choix d’une structure de données doit suivre la logique du problème. Leur maîtrise prépare à l’étude des arbres, des graphes, des systèmes d’exploitation, des compilateurs et des applications distribuées. |