Skip to content

Listes simplement chaînées triées circulaires avec sentinelle

Énoncé

On s'intéresse dans ce mini-projet aux listes simplement chaînées circulaires, triées, et avec sentinelle.

La tête de liste est une cellule contenant une valeur particulière permettant d'identifier la cellule comme étant la sentinelle. La valeur de la cellule sentinelle peut être librement choisie pour vous arranger.

Comme la liste est circulaire, la cellule suivant la dernière est la sentinelle. Cette circularité nous permet donc de garantir que toute cellule a toujours une cellule suivante. De plus la sentinelle permet de garantir que toute cellule a toujours une cellule précédente.

Grâce à ces propriétés sur notre liste chaînée, certaines opérations comme la suppression sont simplifiées.

Dans ce TP, lorsque ne nous ajouterons une valeur dans la liste, celle si sera insérée au "bon endroit" afin de toujours avoir un chaînage de cellules qui sont triées selon leur valeur, par ordre croissant.

L'image ci-dessous illustre la représentation de la liste 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7

liste 0 à 7

On vous demande de compléter le code du fichier circulaire.py affiché ci-dessous et disponible ici (vous pouvez décommenter les appels au traceur si vous souhaitez vous en servir) :

  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
#!/usr/bin/env python3

"""Listes simplement chaînées, triées, circulaires et avec sentinelle."""

# Décommentez si vous souhaitez utiliser le traceur
#import traceur


class Cellule:
    """Une cellule possède une valeur et un suivant."""

    def __init__(self, valeur, suivant=None):
        # TODO
        ...


class ListeSimplementChaineeTriee:
    """Listes simplement chaînées, triées, circulaires et avec sentinelle."""

    def __init__(self, valeur_sentinelle, nombres=None):
        """Construit la liste avec le range de nombres donné.

        `valeur_sentinelle` precise la valeur de la cellule sentinelle.
        pre-condition: le range de nombres donné est trié si il est
                       différent de None.
        Si le range est différent de None, on créera directement les cellules
        ici dans le constructeur. Autrement dit, on n'utilisera pas la fonction
        ajoute.
        """
        # TODO
        ...

    def __str__(self):
        """Renvoie la chaîne de caractères "val1 --> val2 --> val3 ..." """
        # TODO
        ...


def ajoute(liste_chainee, valeur):
    """Ajoute la valeur donnée à la bonne place dans la liste chaînée.

    pre-condition : `valeur` n'est pas la valeur de la sentinelle.
    """
    # TODO
    ...

def supprime(liste_chainee, valeur):
    """Supprime la première cellule de la liste chaînée avec la valeur donnée.

    pre-condition : `valeur` n'est pas la valeur de la sentinelle.
    """
    # TODO
    ...

def decoupe(liste_chainee):
    """Découpe la liste chaînée en deux, une cellule sur 2.

    Par exemple (1,2,3,4,5) produit (1,3,5) et (2,4).
    Renvoie les deux nouvelles listes.
    Aucune nouvelle cellule n'est créée hormis les sentinelles
    des deux nouvelles listes.
    En sortie `liste_chainee` est vide.
    """
    # TODO
    ...

def test():
    """Tests simples des différentes fonctions (à compléter)"""

    # On crée une liste simplement chaînée triée circulaire et l'on affiche
    liste_chainee = ListeSimplementChaineeTriee(float("inf"), range(1, 6))
    print("liste_chainee :", liste_chainee)

    # On ajoute et on supprime puis on affiche
    ajoute(liste_chainee, 0)
    ajoute(liste_chainee, 7)
    ajoute(liste_chainee, 6)
    ajoute(liste_chainee, 5)
    supprime(liste_chainee, 5)
    ajoute(liste_chainee, 8)
    supprime(liste_chainee, 8)
    print("liste_chainee :", liste_chainee) 

    # On trace notre liste
    # Décommentez si vous souhaitez utiliser le traceur
    # liste_chainee_variable = traceur.Variable("liste_chainee", liste_chainee)
    # traceur.display_vars(
    #     liste_chainee_variable, visualize=False, image_name="liste_chainee_0_a_7"
    # )

    # On découpe notre liste
    resultat_decoupe = decoupe(liste_chainee)
    pairs, impairs = resultat_decoupe  # ce qu'on fait ici s'appelle du unpacking

    # On trace le résultat de la découpe
    # Décommentez si vous souhaitez utiliser le traceur
    # resultat_decoupe_variable = traceur.Variable("res_decoupe", resultat_decoupe)
    # traceur.display_vars(
    #     resultat_decoupe_variable, visualize=False, image_name="resultat_decoupe"
    # )

    # On affiche
    print("pairs   :", pairs)
    print("impairs :", impairs)
    print("liste_chainee :", liste_chainee)

    # On refait quelques suppressions et ajouts pour le plaisir
    # puis on affiche
    supprime(pairs, 4)
    supprime(pairs, 0)
    supprime(pairs, 2)
    supprime(pairs, 6)
    ajoute(impairs, 6)
    ajoute(impairs, 0)
    print("impairs après ajout de 6 et 0 :", impairs)
    print("pairs après suppression de tous les éléments :", pairs)

if __name__ == "__main__":
    test()

Correction

Cliquez ici pour révéler la correction.

Voici le code de correction.

  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
135
136
137
138
139
140
141
142
143
144
#!/usr/bin/env python3

"""Listes simplement chaînées, triées, circulaires et avec sentinelle."""

# Décommentez si vous souhaitez utiliser le traceur
#import traceur


class Cellule:
    """Une cellule possède une valeur et un suivant."""

    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant


class ListeSimplementChaineeTriee:
    """Listes simplement chaînées, triées, circulaires et avec sentinelle."""

    def __init__(self, valeur_sentinelle, nombres=None):
        """Construit la liste avec le range de nombres donné.

        `valeur_sentinelle` precise la valeur de la cellule sentinelle.
        pre-condition: le range de nombres donné est trié si il est
                       différent de None.
        Si le range est différent de None, on créera directement les cellules
        ici dans le constructeur. Autrement dit, on n'utilisera pas la fonction
        ajoute.
        """
        self.tete = Cellule(valeur_sentinelle)
        self.tete.suivant = self.tete
        derniere_cellule = self.tete
        if nombres is not None:
            for element in nombres:
                derniere_cellule.suivant = Cellule(element, self.tete)
                derniere_cellule = derniere_cellule.suivant

    def __str__(self):
        """Renvoie la chaîne de caractères "val1 --> val2 --> val3 ..." """
        chaine = ""
        cour = self.tete.suivant
        while cour is not self.tete:
            chaine = f"{'' if len(chaine) == 0 else f'{chaine} --> '}{cour.valeur}"
            cour = cour.suivant
        return chaine


def ajoute(liste_chainee, valeur):
    """Ajoute la valeur donnée à la bonne place dans la liste chaînée.

    pre-condition : `valeur` n'est pas la valeur de la sentinelle.
    """
    prec = liste_chainee.tete
    while prec.suivant is not liste_chainee.tete and prec.suivant.valeur <= valeur:
        prec = prec.suivant
    prec.suivant = Cellule(valeur, prec.suivant)

def supprime(liste_chainee, valeur):
    """Supprime la première cellule de la liste chaînée avec la valeur donnée.

    pre-condition : `valeur` n'est pas la valeur de la sentinelle.
    """
    prec = liste_chainee.tete
    while prec.suivant is not liste_chainee.tete and prec.suivant.valeur != valeur:
        prec = prec.suivant
    if prec.suivant is not liste_chainee.tete:
        prec.suivant = prec.suivant.suivant

def decoupe(liste_chainee):
    """Découpe la liste chaînée en deux, une cellule sur 2.

    Par exemple (1,2,3,4,5) produit (1,3,5) et (2,4).
    Renvoie les deux nouvelles listes.
    Aucune nouvelle cellule n'est créée hormis les sentinelles
    des deux nouvelles listes.
    En sortie `liste_chainee` est vide.
    """
    listes = (ListeSimplementChaineeTriee(liste_chainee.tete.valeur),
              ListeSimplementChaineeTriee(liste_chainee.tete.valeur))
    fins = [listes[0].tete, listes[1].tete]
    idx = 0
    cour = liste_chainee.tete.suivant
    while cour is not liste_chainee.tete:
        fins[idx].suivant = cour
        fins[idx] = cour
        idx = (idx + 1) % 2
        cour = cour.suivant
    fins[0].suivant, fins[1].suivant = listes[0].tete, listes[1].tete
    liste_chainee.tete.suivant = liste_chainee.tete
    return listes

def test():
    """Tests simples des différentes fonctions (à compléter)"""

    # On crée une liste simplement chaînée triée circulaire et l'on affiche
    liste_chainee = ListeSimplementChaineeTriee(float("inf"), range(1, 6))
    print("liste_chainee :", liste_chainee)

    # On ajoute et on supprime puis on affiche
    ajoute(liste_chainee, 0)
    ajoute(liste_chainee, 7)
    ajoute(liste_chainee, 6)
    ajoute(liste_chainee, 5)
    supprime(liste_chainee, 5)
    ajoute(liste_chainee, 8)
    supprime(liste_chainee, 8)
    print("liste_chainee :", liste_chainee) 

    # On trace notre liste
    # Décommentez si vous souhaitez utiliser le traceur
    # liste_chainee_variable = traceur.Variable("liste_chainee", liste_chainee)
    # traceur.display_vars(
    #     liste_chainee_variable, visualize=False, image_name="liste_chainee_0_a_7"
    # )

    # On découpe notre liste
    resultat_decoupe = decoupe(liste_chainee)
    pairs, impairs = resultat_decoupe  # ce qu'on fait ici s'appelle du unpacking

    # On trace le résultat de la découpe
    # Décommentez si vous souhaitez utiliser le traceur
    # resultat_decoupe_variable = traceur.Variable("res_decoupe", resultat_decoupe)
    # traceur.display_vars(
    #     resultat_decoupe_variable, visualize=False, image_name="resultat_decoupe"
    # )

    # On affiche
    print("pairs   :", pairs)
    print("impairs :", impairs)
    print("liste_chainee :", liste_chainee)

    # On refait quelques suppressions et ajouts pour le plaisir
    # puis on affiche
    supprime(pairs, 4)
    supprime(pairs, 0)
    supprime(pairs, 2)
    supprime(pairs, 6)
    ajoute(impairs, 6)
    ajoute(impairs, 0)
    print("impairs après ajout de 6 et 0 :", impairs)
    print("pairs après suppression de tous les éléments :", pairs)

if __name__ == "__main__":
    test()

Une des opérations à implémenter est un découpage construisant deux nouvelles listes en alternant les éléments d’une liste de départ. Voici le résultat attendu sur la liste 0 à 7 ci dessus :

résultat découpe

Exercices