Skip to content

TP14. Listes simplement chaînées

Énoncé

On cherche à implémenter des listes simplement chaînées similaires à celles vues en TD. Pour cela, on va utiliser un type Cellule et un type ListeSimplementChainee.

Une liste composée des entiers 4, 2, 5 et 3 ressemble à : liste simplement chaînée

Analyser le schéma ci-dessus pour bien comprendre quels doivent êtres les attributs de chacune des deux classes. Compléter ensuite le fichier liste_simplement_chainnees.py disponible ici et affiché ci-dessous. Des appels au traceur sont faits dans la fonction de teste du code fourni. Il faudra donc avoir un module traceur opérationnel (aller voir les exercices associés mentionnés ci-dessous si besoin). On pourra bien entendu rajouter tous les appels au traceur nécessaires afin de déboguer plus facilement notre code.

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

"""Listes simplements chainees + quelques operations"""

import traceur

class Cellule:
    """Une cellule d'une liste."""
    # TODO
    ...

class ListeSimplementChainee:
    """Une liste simplement chainee."""
    # TODO
    ...

def ajoute_en_tete(liste_chainee, valeur):
    """Ajoute une cellule en tete"""
    # TODO
    ...

def ajoute_en_queue(liste_chainee, valeur):
    """Ajoute une cellule en queue."""
    # TODO
    ...

def recupere_cellules(liste_chainee):
    """Renvoie un vecteur contenant toutes les cellules de la liste_chainee"""
    # TODO
    ...

def recherche(liste_chainee, valeur):
    """Recherche uen valeur dans la liste_chainee donnée.

    Renvoie la premiere cellule contenant la valeur donnée ou
    None si la valeur n'est pas trouvée dans la liste_chainee.
    """
    # TODO
    ...

# TODO
...

def supprime(liste_chainee, valeur):
    """Enleve la premiere cellule contenant la valeur donnée."""
    # TODO
    ...

def test_listes():
    """On teste les operations de base, dans differentes configurations."""
    liste_chainee = ListeSimplementChainee()
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_0")
    ajoute_en_tete(liste_chainee, 3)
    ajoute_en_tete(liste_chainee, 5)
    ajoute_en_tete(liste_chainee, 2)
    ajoute_en_tete(liste_chainee, 4)
    print("liste_chainee : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_1")
    print("recherche : ", recherche(liste_chainee, 3).valeur)
    supprime(liste_chainee, 5)
    print("apres suppression de 5 : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_2")
    supprime(liste_chainee, 4)
    print("apres suppression de 4 : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_3")

if __name__ == "__main__":
    test_listes()

Cliquez ici pour révéler la correction.

Correction

Voici les quatre images correspondant aux appels au traceur que l'on doit obtenir :

liste_chainee_0.svg :

liste_chainee_0.svg

liste_chainee_1.svg :

liste_chainee_1.svg

liste_chainee_2.svg :

liste_chainee_2.svg

liste_chainee_3.svg :

liste_chainee_3.svg

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

"""Listes simplements chainees + quelques operations"""

import traceur

class Cellule:
    """Une cellule d'une liste."""
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

class ListeSimplementChainee:
    """Une liste simplement chainee."""
    def __init__(self):
        self.tete = None
        self.queue = None
        self.taille = 0

    def __str__(self):
        """Renvoie val1 --> val2 --> val3 ..."""
        return " --> ".join([str(c.valeur) for c in recupere_cellules(self)])

def ajoute_en_tete(liste_chainee, valeur):
    """Ajoute une cellule en tete"""
    # Temps constant
    liste_chainee.taille += 1
    liste_chainee.tete = Cellule(valeur, liste_chainee.tete)
    if liste_chainee.queue is None:
        liste_chainee.queue = liste_chainee.tete
    return liste_chainee

def ajoute_en_queue(liste_chainee, valeur):
    """Ajoute une cellule en queue."""
    # Possible en temps constant grace au pointeur de queue.
    liste_chainee.taille += 1
    nouvelle_cellule = Cellule(valeur)
    if liste_chainee.queue:
        liste_chainee.queue.suivant = nouvelle_cellule
    else:
        liste_chainee.tete = nouvelle_cellule

    liste_chainee.queue = nouvelle_cellule
    return liste_chainee

def recupere_cellules(liste_chainee):
    """Renvoie un vecteur contenant toutes les cellules de la liste_chainee"""
    cellules = []
    cellule_courante = liste_chainee.tete
    while cellule_courante:
        cellules.append(cellule_courante)
        cellule_courante = cellule_courante.suivant
    return cellules

def recherche(liste_chainee, valeur):
    """Recherche uen valeur dans la liste_chainee donnée.

    Renvoie la premiere cellule contenant la valeur donnée ou
    None si la valeur n'est pas trouvée dans la liste_chainee.
    """
    for cellule in recupere_cellules(liste_chainee):
        if cellule.valeur == valeur:
            return cellule
    return None

def supprime_suivant(liste_chainee, cellule):
    """Supprime la cellule apres la cellule donnée.

    Si la cellule donnée est None, supprime le premier élément de la liste_chainee.
    pre-condition: il y a un element a enlever.
    """
    liste_chainee.taille -= 1
    if cellule:
        assert cellule.suivant is not None,\
            "utilisation invalide de supprimer_suivant"
        cellule_supprimee = cellule.suivant
        cellule.suivant = cellule_supprimee.suivant
    else:
        assert liste_chainee.tete is not None,\
            "utilisation invalide de supprimer_suivant"
        cellule_supprimee = liste_chainee.tete
        liste_chainee.tete = cellule_supprimee.suivant

    if cellule_supprimee == liste_chainee.queue:
        liste_chainee.queue = cellule

def supprime(liste_chainee, valeur):
    """Enleve la premiere cellule contenant la valeur donnée."""
    cellule_precedente = None
    for cellule in recupere_cellules(liste_chainee):
        if cellule.valeur == valeur:
            supprime_suivant(liste_chainee, cellule_precedente)
            return liste_chainee
        cellule_precedente = cellule
    return liste_chainee

def test_listes():
    """On teste les operations de base, dans differentes configurations."""
    liste_chainee = ListeSimplementChainee()
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_0")
    ajoute_en_tete(liste_chainee, 3)
    ajoute_en_tete(liste_chainee, 5)
    ajoute_en_tete(liste_chainee, 2)
    ajoute_en_tete(liste_chainee, 4)
    print("liste_chainee : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_1")
    print("recherche : ", recherche(liste_chainee, 3).valeur)
    supprime(liste_chainee, 5)
    print("apres suppression de 5 : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_2")
    supprime(liste_chainee, 4)
    print("apres suppression de 4 : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_3")

if __name__ == "__main__":
    test_listes()

Difficulté

star star star

Exercices associés