Skip to content

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

Énoncé

On s'intéresse dans cet exercice aux listes simplement chaînées circulaires, triées, et avec sentinelle.

La tête de liste est une sentinelle contenant une valeur fictive. Elle nous permet de garantir que toute cellule a toujours une cellule suivante et une cellule précédente. Cela permet de simplifier le code de suppression par exemple.

Comme la liste est circulaire, la cellule suivant la dernière est la sentinelle et aucun attribut suivant des cellules ne vaut donc None.

Les valeurs des cellules sont triées par ordre croissant. La valeur de la sentinelle peut être librement choisie pour vous arranger.

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

liste 0 à 7

Une des opérations demandées est d'implémenter une fonction découpe 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

On vous demande de compléter le code suivant du fichier circulaire.py affiché ci-dessous et disponible ici :

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

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

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, sentinelle, nombres=None):
        """Construit la liste avec le range de nombres donné.

        `sentinelle` precise la valeur de la cellule sentinelle.
        pre-condition: le range de nombres donné est trié.
        """
        # TODO
        ...

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

def ajoute(liste_chainee, valeur):
    """Ajoute la valeur donné à 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
    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
    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()

Difficulté

star star star star

Exercices associés