Skip to content

Fictif en tête

Énoncé

Dans cet exercice, nous allons étudier une technique très classique pour simplifier les codes manipulant des listes chaînées : la technique de l'élément fictif en tête.

Un élément fictif est tout simplement une Cellule dont le champ val n'est pas significatif et ne fait pas formellement partie de la liste chaînée. Comme il n'est pas possible de mettre "rien" comme valeur d'une cellule, on pourra par exemple utiliser le caractère ?, ce qui permettra de détecter visuellement d'éventuelles erreurs (si une trace affiche le caractère ? à l'écran). En effet, on ne devra jamais accéder au champ val d'une cellule fictive, car ce champ est considéré comme « non initialisé ».

On créera donc un élément fictif en tête en allouant une cellule qu'on chaînera simplement en tête de la liste : fictif = Cellule('?', liste).

Cette technique est utile quand on doit parcourir une liste chaînée avec un coup de retard : par exemple quand on veut supprimer la cellule contenant la première occurrence d'une valeur et qu'on doit s'arrêter sur la cellule précédant celle contenant cette valeur, pour pouvoir modifier le chaînage. Dans une telle fonction, le cas de la liste chaînée vide et celui de la liste contenant la valeur cherchée dans sa première cellule sont des cas particuliers qu'on doit traiter séparément du cas général. L'utilisation de l'élément fictif en tête permet souvent d'homogénéiser le code en ramenant les cas particuliers au cas général.

Pour vous en convaincre, ajoutez la fonction supprime suivante à votre programme manipulant les listes basiques de l'exercice précédent :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def supprime(lsc, val):
    """
    Supprime la premiere occurrence de val dans lsc (version naive sans fictif).
    La fonction renvoie la liste chaînée (éventuellement) modifiée et un booléen supp qui vaut True
      ssi il y a bien eu une suppression (c'est à dire si la liste chaînée initiale contenait au
      moins une occurrence de val).
    """
    supp = False
    if est_vide(lsc):
        pass
    elif lsc.val == val:
        lsc = lsc.suiv
        supp = True
    else:
        prec = lsc
        while prec.suiv is not None and prec.suiv.val != val:
            prec = prec.suiv
        if prec.suiv is not None:
            prec.suiv = prec.suiv.suiv
            supp = True
    return lsc, supp
ainsi que le bout de code de test ci-dessous à la fin de la fonction main : 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    # Ajouter ce bout de code à la fin de la fonction main de l'exercice précédent
    print("\nListe initiale   : ", end="")
    affiche(lsc)
    while not est_vide(lsc):
        val = randint(0, 5)
        print(f"Suppression de {val} : ", end="")
        lsc, supp = supprime(lsc, val)
        if supp:
            affiche(lsc)
        else:
            print("valeur absente")

Testez cette fonction (volontairement non commentée !) et essayez de comprendre son fonctionnement, en faisant particulièrement attention aux deux cas particuliers au début de la fonction.

Créez une fonction supprimer_fictif qui utilise la technique de l'élément fictif en tête pour écrire un code équivalent à celui de supprimer, mais sans avoir à dissocier les cas particuliers. Autrement dit, la fonction supprimer_fictif ajoutera un élément fictif en tête de liste avant de faire la suppression. Il suffira de changer l'appel à supprimer en appel à supprimer_fictif dans le code de test pour vérifier votre fonction.

Correction

Cliquez ici pour révéler la correction.

fictif_en_tete.py :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#!/usr/bin/env python3
"""
  Programme pour tester des listes simplement chaînées avec technique du fictif.
"""

from random import randint

class Cellule:
    """
    Une cellule est composée d'une valeur et d'une référence vers la
      cellule suivante (ou None s'il n'y a pas de suivant)
    """

    # pylint: disable=too-few-public-methods

    def __init__(self, val, suiv):
        """
        Constructeur
        """
        self.val = val
        self.suiv = suiv

    def __str__(self):
        """
        Afficheur
        """
        return f"{self.val} -> "


def est_vide(lsc):
    """
    Teste si la liste chaînée est vide
    """
    return lsc is None


def insere_tete(lsc, val):
    """
    Insère une cellule de valeur val en tête de la liste chaînée.
    Renvoie la nouvelle cellule insérée en tête.
    """
    return Cellule(val, lsc)


def insere_queue(lsc, val):
    """
    Insère une cellule de valeur val en queue de la liste chaînée
    """
    cell = Cellule(val, None)
    if est_vide(lsc):
        return cell
    cour = lsc
    while cour.suiv is not None:
        cour = cour.suiv
    cour.suiv = cell
    return lsc

def affiche(lsc):
    """
    Affiche la liste chaînée
    """
    cour = lsc
    while cour is not None:
        print(cour, end="")
        cour = cour.suiv
    print("FIN")

def supprime(lsc, val):
    """
    Supprime la premiere occurrence de val dans lsc (version naive sans fictif).
    La fonction renvoie la liste chaînée (éventuellement) modifiée et un booléen supp qui vaut True
      ssi il y a bien eu une suppression (c'est à dire si la liste chaînée initiale contenait au
      moins une occurrence de val).
    """
    supp = False
    if est_vide(lsc):
        pass
    elif lsc.val == val:
        lsc = lsc.suiv
        supp = True
    else:
        prec = lsc
        while prec.suiv is not None and prec.suiv.val != val:
            prec = prec.suiv
        if prec.suiv is not None:
            prec.suiv = prec.suiv.suiv
            supp = True
    return lsc, supp

def supprime_fictif(lsc, val):
    """
    Supprime la premiere occurrence de val (version avec fictif)
    """
    supp = False
    fictif = Cellule("?", lsc)
    prec = fictif
    while prec.suiv is not None and prec.suiv.val != val:
        prec = prec.suiv
    if prec.suiv is not None:
        prec.suiv = prec.suiv.suiv
        lsc = fictif.suiv
        supp = True
    return lsc, supp

def main():
    """
    Fonction principale
    """
    lsc = None  # creation d'une liste chaînée vide
    print("Liste initiale vide     : ", end="")
    affiche(lsc)
    for _ in range(10):
        ins_en_tete = randint(0, 1) == 1
        val = randint(0, 5)
        if ins_en_tete:
            print(f"Insertion en tête de {val}  : ", end="")
            lsc = insere_tete(lsc, val)
        else:
            print(f"Insertion en queue de {val} : ", end="")
            lsc = insere_queue(lsc, val)
        affiche(lsc)
    # Ajouter ce bout de code à la fin de la fonction main de l'exercice précédent
    print("\nListe initiale   : ", end="")
    affiche(lsc)
    while not est_vide(lsc):
        val = randint(0, 5)
        print(f"Suppression de {val} : ", end="")
        lsc, supp = supprime(lsc, val)
        if supp:
            affiche(lsc)
        else:
            print("valeur absente")

main()