Listes simplement chaînées
Énoncé
On cherche à implanter des listes simplement chaînées un peu plus complexes que les listes basiques vues dans les exercices précédents.
Pour cela, on va utiliser un type Cellule et un type ListeSimplementChainee : une liste simplement chaînée comprendra donc ici :
- une référence vers la première cellule de la liste ;
- une référence vers la dernière cellule de la liste ;
- un entier qui correspond au nombre de cellules dans la liste.
Une liste composée des entiers 4, 2, 5 et 3 ressemble à :
Analyser le schéma ci-dessus pour bien comprendre quels doivent êtres les attributs de chacune des deux classes.
Important : dans le schéma, on attire votre attention sur la case mémoire contenant la valeur 4, qui est utilisée à la fois pour représenter la valeur 4 de la liste chaînée, mais aussi pour le compteur de cellules. À votre avis, quel peut-être l'intérêt de cette factorisation ? Pour information, la version de Python que l'on utilise effectue la factorisation pour tout entier compris entre -5 et 256 inclus.
Compléter ensuite le fichier liste_simplement_chainee.py disponible ici et affiché ci-dessous.
Le code fourni contient des appels au traceur dans la fonction de test du code fourni, qui sont commentés par défaut : vous pouvez les décommenter si vous souhaitez utiliser le module traceur pour mettre au point votre code (il faut évidemment avoir un module traceur opérationnel pour ça).
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
77
78 | #!/usr/bin/env python3
"""Listes simplement chaînées + quelques operations."""
#import traceur
class Cellule:
"""Une cellule d'une liste."""
# TODO
...
class ListeSimplementChainee:
"""Une liste simplement chaînée."""
# TODO
...
def ajoute_en_tete(liste_chainee, valeur):
"""Ajoute une cellule en tête."""
# TODO
...
def ajoute_en_queue(liste_chainee, valeur):
"""Ajoute une cellule en queue."""
# TODO
...
def recherche(liste_chainee, valeur):
"""Recherche une valeur dans la liste_chainee donnée.
Renvoie la première cellule contenant la valeur donnée ou
None si la valeur n'est pas trouvée dans la liste_chainee.
"""
# TODO
...
def supprime(liste_chainee, valeur):
"""Supprime la premiere cellule contenant la valeur donnée."""
# TODO
...
def teste_listes():
"""On teste les operations de base, dans différentes 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"
# )
teste_listes()
|
Correction
Cliquez ici pour révéler la correction.
Voici les quatre images correspondant aux appels au traceur que l'on doit obtenir :
liste_chainee_0.svg :
liste_chainee_1.svg :
liste_chainee_2.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
125
126
127
128
129
130
131
132
133
134
135
136
137 | #!/usr/bin/env python3
"""Listes simplement chaînées + 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 chaînée."""
def __init__(self):
self.tete = None
self.queue = None
self.taille = 0
def __str__(self):
"""Renvoie val1 --> val2 --> val3 ..."""
str_repr = ""
cellule_courante = self.tete
while cellule_courante is not None:
if str_repr:
str_repr += " --> "
str_repr += str(cellule_courante.valeur)
cellule_courante = cellule_courante.suivant
return str_repr
def ajoute_en_tete(liste_chainee, valeur):
"""Ajoute une cellule en tête."""
# 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 recherche(liste_chainee, valeur):
"""Recherche une valeur dans la liste_chainee donnée.
Renvoie la première cellule contenant la valeur donnée ou
None si la valeur n'est pas trouvée dans la liste_chainee.
"""
cellule_courante = liste_chainee.tete
while cellule_courante is not None:
if cellule_courante.valeur == valeur:
return cellule_courante
cellule_courante = cellule_courante.suivant
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):
"""Supprime la premiere cellule contenant la valeur donnée."""
cellule_precedente = None
cellule_courante = liste_chainee.tete
while cellule_courante is not None:
if cellule_courante.valeur == valeur:
supprime_suivant(liste_chainee, cellule_precedente)
return liste_chainee
cellule_precedente = cellule_courante
cellule_courante = cellule_courante.suivant
return liste_chainee
def teste_listes():
"""On teste les operations de base, dans différentes 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"
# )
teste_listes()
|
Exercices