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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279 | #!/usr/bin/env python3
"""Opérations de haut niveau sur des listes simplement chaînées."""
class Cellule:
"""Une cellule d'une liste simplement chaînée."""
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
def __str__(self):
"""Renvoie la valeur en chaîne de caractères."""
return str(self.valeur)
class ListeSimplementChainee:
"""Une liste simplement chaînée."""
def __init__(self, valeurs):
self.tete = None
self.queue = None
self.taille = 0
# On rajoute toutes les valeurs en queue.
# `valeurs` est un itérable, on peut donc
# faire un `for` dessus.
for valeur in valeurs:
# Création d'une nouvelle cellule
cell = Cellule(valeur)
# Ajout dans liste vide
if self.tete is None:
self.tete = cell
self.queue = cell
# Sinon ajout en queue
else:
self.queue.suivant = cell
self.queue = cell
# Ne pas oublier de mettre la taille à jour
self.taille += 1
def __str__(self):
"""Renvoie taille = X, val1 --> val2 --> val3 ...
On implémente cette méthode spéciale `__str__` pour
pouvoir afficher nos listes simplement chaînées
avec de simples appels à `print`.
"""
# La liste chaînée vide
if self.tete is None:
return 'liste chaînée vide'
# On parcourt la liste chaînée pour
# construire la chaîne de caractères
cell = self.tete
first = True
res = 'taille = ' + str(self.taille) + ', '
while cell is not None:
if not first:
res += ' --> '
first = False
# Possible car __str__ est définie dans la
# classe Cellule ci-dessus
res += str(cell)
cell = cell.suivant
return res
def recupere_celllules(liste_chainee):
"""Renvoie un itérateur sur toutes les cellules."""
cell = liste_chainee.tete
while cell is not None:
yield cell
cell = cell.suivant
def remplace_valeurs(liste_chainee, transforme):
"""Remplace les valeurs des cellules en appliquant la fonction transforme."""
# Ici on utilise le générateur pour parcourir la liste chaînée.
# Il n'y a pas de surcoût en calcul ni en mémoire, et le code
# de parcours de liste est découplé du code de transformation.
cellules_it = recupere_celllules(liste_chainee)
for cell in cellules_it:
cell.valeur = transforme(cell.valeur)
def filtre_cellules(liste_chainee, filtre):
"""Renvoie un itérateur sur les cellules filtrées."""
# On utilise encore le générateur pour parcourir la liste chaînée.
cellules_it = recupere_celllules(liste_chainee)
for cell in cellules_it:
filtree = filtre(cell.valeur)
if not isinstance(filtree, bool):
raise TypeError("la fonction filtre a renvoyé autre chose qu'un booléen")
if filtree:
yield cell
def supprime_cellules(liste_chainee, filtre):
"""Supprime tous les cellules de liste pour lesquelles le filtre renvoie False.
Coût = O(n) avec n qui est la taille de la liste chainée.
"""
# Là encore, on va utiliser notre générateur.
# ATTENTION, il ne faut pas modifier la liste
# chaînée pendant que nous utilisons l'itérateur
# renvoyé par le générateur !
gardees_it = filtre_cellules(liste_chainee, filtre)
tete = None
queue = None
taille = 0
prec = None
for cell in gardees_it:
if tete is None:
tete = cell
if prec is not None:
prec.suivant = cell
queue = cell
prec = cell
taille += 1
# Les modifications sur la liste chaînée
# sont fait à la fin.
liste_chainee.tete = tete
liste_chainee.queue = queue
liste_chainee.taille = taille
def concatene(liste_chainee_1, liste_chainee_2):
"""Concatène liste_chainee_2 à liste_chainee_1 et vide liste_chainee_2.
Ici c'est du temps constant, la preuve y a pas de boucle !
C'est cool les listes chaînées :-)
"""
# Si la liste 1 est vide, on change la tête
if liste_chainee_1.tete is None:
liste_chainee_1.tete = liste_chainee_2.tete
# Sinon on lie les deux listes
else:
liste_chainee_1.queue.suivant = liste_chainee_2.tete
# Si la liste 2 n'est pas vide, on change la queue
if liste_chainee_2.tete is not None:
liste_chainee_1.queue = liste_chainee_2.queue
# On met à jour la taille
liste_chainee_1.taille += liste_chainee_2.taille
# On vide la liste 2
liste_chainee_2.tete = None
liste_chainee_2.queue = None
def ajoute_en_queue(liste_chainee, valeur):
"""Ajoute une valeur dans une nouvelle cellule en queue.
Coût = O(1) grâce au pointeur de queue.
"""
cellule = Cellule(valeur)
if liste_chainee.queue:
liste_chainee.queue.suivant = cellule
else:
liste_chainee.tete = cellule
liste_chainee.queue = cellule
liste_chainee.taille += 1
def decoupe(liste_chainee, fonction):
"""Crée et retourne deux listes : les cellules ne validant pas la fonction et les autres.
Coût = O(n) avec n qui est la taille de la liste chainée.
"""
# On crée les deux nouvelles listes
non = ListeSimplementChainee(range(0))
oui = ListeSimplementChainee(range(0))
# Là encore, on va utiliser notre générateur pour
# rajouter chacune des cellules dans la bonne liste
# en fonction du résultat de l'appel à la fonction
# `fonction`
for cellule in recupere_celllules(liste_chainee):
if fonction(cellule.valeur):
ajoute_en_queue(oui, cellule)
else:
ajoute_en_queue(non, cellule)
# Il n'y a rien apres la fin de chacune des listes.
# Il faut donc "casser" le suivant de la queue
# pour chacune des deux listes.
for liste in (non, oui):
if liste.queue is not None:
liste.queue.suivant = None
return (non, oui)
def multiplie_par_deux(val):
"""Multiplie val par deux et renvoie le résultat"""
return val * 2
def est_multiple_de_trois(val):
"""Renvoie True si val est multiple de 3, et False sinon"""
return val % 3 == 0
def teste_fonctions():
"""Teste les fonctions ci-dessus"""
# Teste le constructeur
liste_chainee_vide = ListeSimplementChainee(range(1, 1))
print("une liste vide :", liste_chainee_vide)
liste_chainee = ListeSimplementChainee(range(42, 42 + 7))
print("une liste à 7 éléments :", liste_chainee)
# Teste la transformation
remplace_valeurs(liste_chainee_vide, multiplie_par_deux)
print("une liste vide après remplacement des valeurs par multiplication par deux :",
liste_chainee_vide)
remplace_valeurs(liste_chainee, multiplie_par_deux)
print("une liste à 7 éléments après remplacement des valeurs par multiplication par deux :",
liste_chainee)
# Teste le filtre
filtrees = filtre_cellules(liste_chainee_vide, est_multiple_de_trois)
print("filtrage multiple de trois sur liste vide :", *filtrees)
filtrees = filtre_cellules(liste_chainee, est_multiple_de_trois)
# l'étoile ici est nécessaire pour que les cellules soient passées
# en argument à `print` et non pas l'itérateur `filtrees`
print("filtrage multiple de trois sur liste à 7 éléments :", *filtrees)
# Teste de l'exception
# filtrees = filtre_cellules(liste_chainee, multiplie_par_deux)
# print(*filtrees)
# Teste la suppression
supprime_cellules(liste_chainee_vide, est_multiple_de_trois)
print("supression sur liste vide :", liste_chainee_vide)
supprime_cellules(liste_chainee, est_multiple_de_trois)
print("supression des non-multiple de trois sur liste à 7 éléments :", liste_chainee)
# On teste tous les cas "limites" pour la concaténation
liste_chainee_1 = ListeSimplementChainee(range(0))
liste_chainee_2 = ListeSimplementChainee(range(0))
print("résultat concaténation", liste_chainee_1, "avec",
liste_chainee_2, ":", end=" ")
concatene(liste_chainee_1, liste_chainee_2)
print(liste_chainee_1, "et", liste_chainee_2)
liste_chainee_1 = ListeSimplementChainee(range(5))
liste_chainee_2 = ListeSimplementChainee(range(0))
print("résultat concaténation", liste_chainee_1, "avec",
liste_chainee_2, ":", end=" ")
concatene(liste_chainee_1, liste_chainee_2)
print(liste_chainee_1, "et", liste_chainee_2)
liste_chainee_1 = ListeSimplementChainee(range(0))
liste_chainee_2 = ListeSimplementChainee(range(5))
print("résultat concaténation", liste_chainee_1, "avec",
liste_chainee_2, ":", end=" ")
concatene(liste_chainee_1, liste_chainee_2)
print(liste_chainee_1, "et", liste_chainee_2)
liste_chainee_1 = ListeSimplementChainee(range(5))
liste_chainee_2 = ListeSimplementChainee(range(5))
print("résultat concaténation", liste_chainee_1, "avec",
liste_chainee_2, ":", end=" ")
concatene(liste_chainee_1, liste_chainee_2)
print(liste_chainee_1, "et", liste_chainee_2)
# Teste trie pairs / impairs
# Ici on utilise des lambdas : c'est à dire
# des fonctions anonyme créées directement
# dans un appel de fonction.
liste_chainee = ListeSimplementChainee(range(0))
print("résultat découpe pairs/impairs sur", liste_chainee, ":", end=" ")
impairs, pairs = decoupe(liste_chainee, lambda x: x % 2 == 0)
print(pairs, "et", impairs)
liste_chainee = ListeSimplementChainee(range(11))
print("résultat découpe pairs/impairs sur", liste_chainee, ":", end=" ")
impairs, pairs = decoupe(liste_chainee, lambda x: x % 2 == 0)
print(pairs, "et", impairs)
if __name__ == "__main__":
teste_fonctions()
|
