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
| '''MODULE implémentant une Liste Chaînée MUABLE sous forme d'un objet stockant Tête
Description
-----------
* Une Liste VIDE est un objet dont l'attribut tete contient None
* Une Liste NON VIDE est un objet qui possède un attribut : tete
* Une Cellule est un objet qui possède deux attributs : v et s
'''
class Cellule:
'''Cellule (valeur, successeur)'''
def __init__(self, valeur:'Element', successeur:'Cellule|None'):
self.v = valeur # Valeur ne peut pas être None si File homogène
self.s = successeur # successeur vaut None si Cellule de Fin
def nb_cellules(self:'Cellule') -> int: #Coût Linéaire O(n)
'''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule'''
if self.s is None: # si il n'y a pas de successeur
return 1 # il y a au moins la fin
else:
return 1 + self.s.nb_cellules() # on demande au successeur...
def contenu(self:'Cellule') -> 'Element': # Coût constant
'''Renvoie le contenu de la Cellule'''
return self.v
def successeur(self:'Cellule NON FIN') -> 'Cellule': # Coût constant
'''Renvoie la Cellule qui succède à une cellule NON FIN'''
return self.s
class Liste:
'''Liste chaînée MUABLE Tete'''
def __init__(self):
self.tete = None
def est_liste_vide(self:'Liste') -> bool: # Coût constant
'''Prédicat qui renvoie True si la liste est vide'''
pass
def acces_tete(self:'Liste NON VIDE') -> Cellule: # Coût constant
'''Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE'''
pass
def acces_fin(self:'Liste NON VIDE') -> Cellule: # Coût linéaire 𝞗(n)
'''Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE'''
c = self.tete
while ...: # TANT QUE la cellule ne mène pas à None (n'est pas la fin donc)
... # on passe à la cellule suivante
return ... # on renvoie la cellule c qui est donc la fin
def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule: # Coût Linéaire O(n)
'''Renvoie l'adresse de la cellule i dans la liste NON VIDE'''
c = self.tete # récupère la cellule de tête
for _ in range(...): # Faire i fois
c = ... # passe au successeur
return ...
def inserer_tete(self:'Liste', elt:'Element') -> None: # coût constant
'''Rajoute une nouvelle cellule contenant elt en tête de liste'''
... # Etape 1 : création de la cellule
... # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête
... # Etape 3 : modification de la liste
def inserer_fin(self:'Liste', elt:'Element') -> None: # Coût constant
'''Rajoute une nouvelle cellule de Fin contenant elt dans la liste'''
if ...: # Si la liste est vide, on fait appel
... # à inserer_tete()
else:
... # Etape 1 : on crée la nouvelle Cellule
...
...
def inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None:
"""Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste"""
if i == 0:
...
else:
... # Etape 1 : recherche de la cellule i-1
... # Etape 2 : création de la cellule
... # Etape 3 : liaison nouvelle i vers ancienne i
... # Etape 4 : liaison i-1 vers nouvelle i
def supprimer_tete(self:'Liste NON VIDE') -> 'Elt': # coût constant
"""Supprime la tête et renvoie son contenu"""
... # Etape 1 : on mémorise l'ancienne valeur
... # Etape 2 : la tête devient le successeur de l'ancienne tête
...
def supprimer_fin(self:'Liste NON VIDE') -> 'Element': # Coût Linéaire θ(n)
'''Supprime la cellule de fin d'une liste NON VIDE et renvoie l'élément qui y était stocké'''
if ...: # si la liste ne possède qu'une seule cellule
... # on demande à l'autre fonction de faire le travail
else :
# Etape 1 : on cherche le prédécesseur c de la Fin
... # on part de la tête
while ...: # tant que c n'est pas le prédécesseur de la Fin
... # on passe à la cellule suivante
... # Etape 2 : on mémorise la valeur de Fin actuelle
... # Etape 3 : on fait pointer le prédécesseur sur None
... # Etape 4 : on renvoie la valeur mémorisée
def supprimer(self:'Liste NON VIDE', i:'int VALIDE') -> 'Element': # Coût linéaire θ(i) O(n)
"""Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké"""
if i == 0: # En réalité, on veut supprimer la Tête
return ...
else:
... # Etape 1 : recherche de la cellule i-1
... # Etape 2 : on mémorise la valeur en position i actuellement
... # Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeur
... # Etape 4 : on renvoie la valeur mémorisée
def longueur(self:'Liste') -> int: # Coût Linéaire θ(n)
'''Renvoie la longueur de la liste'''
if ...:
return 0
else:
return ...
def premier(self:'Liste NON VIDE') -> 'Element': # Coût constant
'''Renvoie l'élément stocké en Tête de liste NON VIDE'''
return ...
def dernier(self:'Liste NON VIDE') -> 'Element': # Coût linéaire
'''Renvoie l'élément stocké en Fin de liste NON VIDE'''
return ...
def ieme(self:'Liste NON VIDE', i:'int VALIDE') -> 'Element': # Coût Linéaire O(n)
'''Renvoie l'élément stocké en position i de la liste NON VIDE'''
return ...
if __name__ == '__main__':
def tester_inserer_tete():
print("Tests de inserer_tete())...", end="")
lst = Liste()
lst.inserer_tete(5)
assert lst.tete.v == 5
lst.inserer_tete(10)
assert lst.tete.v == 10
assert lst.tete.s.v == 5
lst.inserer_tete(20)
assert lst.tete.v == 20
assert lst.tete.s.v == 10
assert lst.tete.s.s.v == 5
print("ok")
def tester_supprimer_tete():
print("Tests de supprimer_tete())...", end="")
lst = Liste()
lst.inserer_tete(5)
lst.inserer_tete(10)
lst.inserer_tete(20)
lst.supprimer_tete()
assert lst.tete.v == 10
lst.supprimer_tete()
assert lst.tete.v == 5
lst.supprimer_tete()
assert lst.tete is None
print("ok")
def tester_inserer_fin():
print("Tests de inserer_fin())...", end="")
lst = Liste()
lst.inserer_fin(5)
assert lst.tete.v == 5
lst.inserer_fin(10)
assert lst.tete.v == 5
assert lst.tete.s.v == 10
lst.inserer_fin(20)
assert lst.tete.v == 5
assert lst.tete.s.s.v == 20
lst.inserer_tete(200)
assert lst.tete.v == 200
assert lst.tete.s.v == 5
assert lst.tete.s.s.v == 10
assert lst.tete.s.s.s.v == 20
print("ok")
def tester_inserer():
print("Tests de inserer())...", end="")
lst = Liste()
lst.inserer(5, 0)
lst.inserer(10, 1)
assert lst.tete.v == 5
assert lst.acces_fin().v == 10
lst.inserer(500, 1)
assert lst.tete.v == 5
assert lst.tete.s.v == 500
assert lst.acces_fin().v == 10
print("ok")
def tester_supprimer_fin():
print("Tests de supprimer_fin())...", end="")
lst = Liste()
lst.inserer_tete(5)
lst.inserer_tete(10)
lst.inserer_tete(20)
lst.inserer_tete(200)
lst.supprimer_fin()
assert lst.tete.v == 200
assert lst.acces_fin().v == 10
lst.supprimer_tete()
assert lst.tete.v == 20
assert lst.acces_fin().v == 10
lst.supprimer_fin()
assert lst.acces_fin().v == 20
lst.supprimer_fin()
assert lst.tete is None
print("ok")
def tester_supprimer():
print("Tests de inserer())...", end="")
lst = Liste()
lst.inserer(5, 0)
lst.inserer(10, 1)
lst.inserer(500, 1)
lst.supprimer(1)
assert lst.tete.v == 5
assert lst.acces_fin().v == 10
lst.supprimer(0)
assert lst.tete.v == 10
assert lst.acces_fin().v == 10
lst.supprimer(0)
assert lst.tete == None
print("ok")
def tester_ieme_premier_dernier():
print("Tests ieme() premier() dernier()...", end="")
lst = Liste()
lst.inserer_tete(5)
lst.inserer_tete(10)
lst.inserer_tete(20)
lst.inserer_fin(30)
assert lst.premier() == 20
assert lst.ieme(0) == 20
assert lst.ieme(1) == 10
assert lst.ieme(2) == 5
assert lst.ieme(3) == 30
assert lst.dernier() == 30
lst.supprimer(1)
assert lst.premier() == 20
assert lst.ieme(0) == 20
assert lst.ieme(1) == 5
assert lst.ieme(2) == 30
assert lst.dernier() == 30
lst.supprimer(0)
assert lst.premier() == 5
assert lst.ieme(0) == 5
assert lst.ieme(1) == 30
assert lst.dernier() == 30
lst.supprimer_tete()
assert lst.premier() == 30
assert lst.ieme(0) == 30
assert lst.dernier() == 30
lst.supprimer_fin()
assert lst.est_liste_vide()
print("ok")
#tester_inserer_tete()
#tester_supprimer_tete()
#tester_inserer_fin()
#tester_supprimer_fin()
#tester_inserer()
#tester_supprimer()
#tester_ieme_premier_dernier()
|