Nom = ""
Prénom = ""
Python 6 - Listes chainées encapsulées¶
1 - Encapsulation¶
Dans Python07, une liste chainée était définie par son chainon de tête. Cette approche a l'avantage d'être simple, mais le rajout d'un maillon change obligatoirement la référence de la liste chainée. C'est un problème.
Un autre problème de cette approche est qu'il est impossible d'avoir une liste chainée vide.
Un solution à ces problèmes est d'encapsuler les maillons dans un objet qui référence le maillon de tête et représente alors la liste chainée :
class Chaine:
"""
Représente une liste chainée
"""
def __init__(self):
"""
Défini une liste chainée, de chainon de tête 'tete'
"""
self.tete = None
On rappelle la classe Maillon, telle que définie dans l'activité précédente :
class Maillon:
"""
Un maillon d'une liste simplement chainée
"""
def __init__(self, valeur, suivant):
"""
:param valeur: (type quelconque) la valeur du maillon
:param suivant: (instance Maillon) le maillon suivant ou None pour le dernier
"""
self.suivant = suivant
self.valeur = valeur
def __repr__(self):
if self.suivant is None:
return str(self.valeur)
return str(self.valeur) + '->' + str(self.suivant)
def __len__(self):
if self.suivant is None:
return 1
return 1 + len(self.suivant)
Par exemple, la variable lc1 est une liste chainée contenant les nombres 1, 2, 3 et 4 dans cet ordre :
lc1 = Chaine()
lc1.tete = Maillon(1, Maillon(2, Maillon(3, Maillon(4, None))))
2 - Longueur¶
Ajouter une méthode __len__ à la classe Chaine afin de pouvoir utiliser la fonction len avec les instances de la classe Chaine.
Rappel : si a est un objet, len(a) est équivalent à a.__len__().
Remarque : On utilisera évidemment la fonction len sur le maillon de tête : le travail a déjà été fait dans Python 7 !
class Chaine:
"""
Représente une liste chainée
"""
def __init__(self):
"""
Défini une liste chainée, de chainon de tête 'tete'
"""
self.tete = None
def __len__(self):
# Insérez votre code ici
lc = Chaine()
assert len(lc) == 0
lc.tete = Maillon(1, Maillon(2, Maillon(3, Maillon(4, None))))
assert len(lc) == 4
3 - Affichage¶
Définir une méthode __repr__ dans la classe Chaine afin de pouvoir afficher une liste chainée comme dans Python26 :
>>> print(lc)
'1->2->3->4'Rappel : Outre la fonction print, les fonctions de conversion (objet Chaine -> chaine de caractère) str et repr utilisent la méthode __repr__.
# Insérez votre code ici
lc = Chaine()
assert str(lc) == '-'
lc.tete = Maillon(1, Maillon(2, Maillon(3, Maillon(4, None))))
assert repr(lc) == '1->2->3->4'
assert str(lc) == '1->2->3->4'
4 - Ajout d'éléments¶
Avec une liste chainée, la manière naturelle d'ajouter un élément est au début de la liste (au contraire des listes Python).
a - Méthode append¶
Rajouter une méthode append à la classe Chaine qui rajoute un nouvel élément à la liste chainée.
Remarque : A partir d'ici, l'attribut tete devient privé : pensez à rajouter un underscore devant.
# Insérez votre code ici
lc = Chaine()
lc.append(4)
lc.append(5)
assert str(lc) == '5->4'
test = False
try:
lc.tete
except AttributeError:
test = True
assert test, "L'attribut tete n'est pas privé"
b - Méthode extend¶
Rajouter une méthode extend qui rajoute les éléments d'un itérable (comme une liste ou un tuple) à une liste chainée encapsulée.
Rappel : pour parcourir un itérable à l'envers, utiliser un for avec reversed.
# Insérez votre code ici
lc = Chaine()
lc.extend([2, 3])
lc.extend(range(2))
assert str(lc) == '0->1->2->3'
c - Argument de Chaine¶
Modifier le constructeur de la classe Chaine afin qu'il prenne en argument optionnel un itérable, dont les valeurs initialiseront la liste chainée.
# Insérez votre code ici
lc = Chaine(range(5))
assert str(lc) == '0->1->2->3->4'
5 - Copie d'une liste chainée¶
Ajouter une méthode copie qui renvoie une copie d'une liste chainée (tous les objets formant la liste doivent être dupliqués).
# Insérez votre code ici
vide = Chaine()
copie_vide = vide.copie()
assert vide is not copie_vide
assert str(vide) == str(copie_vide)
lc = Chaine(('a', 'b', 'c', 'd'))
copie = lc.copie()
assert lc is not copie
assert str(lc) == str(copie)
6 - Accès aux éléments¶
Le seul élément auquel il est facile d'accèder est celui qui est dans le maillon de tête. Pour les autres, il faut parcourir la liste en partant du début jusqu'à atteindre l'élément voulu.
a - Méthode pop¶
Rajouter à la classe Chaine une méthode pop qui enlève le maillon de tête et renvoie sa valeur.
# Insérez votre code ici
lc = Chaine([2, 3])
r = lc.pop()
assert r == 2
assert str(lc) == '3'
assert lc.pop() == 3
b = False
try:
lc.pop()
except IndexError:
b = True
assert b
b - Méthode __getitem__¶
La méthode __getitem__ permet d'utiliser avec un objet la notation qui permet d'accèder aux éléments d'une liste Python : si a est un objet, a[i] renverra la même chose que a.__getitem__(i).
Nous allons donc ajouter cette méthode à la classe Chaine pour accèder à la valeur du maillon d'indice i (le maillon de tête est celui d'indice 0).
# Insérez votre code ici
it = range(10)
lc = Chaine(it)
for i in it:
assert lc[i] == i
# IndexError si i == 10 :
test = False
try:
lc[10]
except IndexError:
test = True
assert test, "Il faut lever IndexError si l'indice est trop grand"
# IndexError si la liste est vide :
lc = Chaine()
test = False
try:
lc[0]
except IndexError:
test = True
assert test, "Il faut lever IndexError si la liste est vide"
7 - Suppression d'un maillon¶
Ajouter une méthode supprime à la classe Chaine qui prend en argument un entier i et supprime le maillon d'indice i.
Dans le cas où i ne serait pas entier, une erreur TypeError doit avoir lieu.
Dans le cas où i ne serait pas dans le bon intervalle, une erreur IndexError doit avoir lieu.
# Insérez votre code ici
lc = Chaine(range(10))
lc.supprime(0)
assert str(lc) == '1->2->3->4->5->6->7->8->9'
lc.supprime(2)
assert str(lc) == '1->2->4->5->6->7->8->9'
lc.supprime(len(lc) - 1)
assert str(lc) == '1->2->4->5->6->7->8'
typeerror_ok = False
try:
lc.supprime(0.5)
except TypeError:
typeerror_ok = True
assert typeerror_ok
indexerror_ok = False
try:
lc.supprime(10)
except IndexError:
indexerror_ok = True
assert indexerror_ok
8 - Insertion d'un élément¶
Ajouter une méthode insert à la classe Chaine qui prend en premier argument un indice i et en deuxième argument la valeur v à insérer à l'indice i.
# Insérez votre code ici
lc = Chaine(range(4))
lc.insert(0, 'a')
assert str(lc) == 'a->0->1->2->3'
lc.insert(2, 'b')
assert str(lc) == 'a->0->b->1->2->3'
lc.insert(len(lc), 'c')
assert str(lc) == 'a->0->b->1->2->3->c'
typeerror_ok = False
try:
lc.insert(0.5, 'd')
except TypeError:
typeerror_ok = True
assert typeerror_ok
indexerror_ok = False
try:
lc.insert(20, 'd')
except IndexError:
indexerror_ok = True
assert indexerror_ok
9 - Somme de deux listes chainées¶
Python permet de calculer la somme de deux listes :
>>> [0, 1] + [2, 3, 4]
[0, 1, 2, 3, 4]Nous voulons pouvoir faire la même chose avec deux liste chainées.
Un point important est que les deux listes initiales ne sont pas modifiées lors de la somme.
Nous allons rajouter une méthode __add__ à la classe Chaine, qui fonctionne de la manière suivante : si a est un objet, a.__add__(x) est équivalent à a + x.
# Insérez votre code ici
a = Chaine(range(5))
b = Chaine(range(3))
assert str(a + b) == '0->1->2->3->4->0->1->2'
assert str(a) == '0->1->2->3->4'
assert str(b) == '0->1->2'
c = Chaine()
assert str(b + c) == '0->1->2'
assert str(c + b) == '0->1->2'
test = False
try:
a + 3
except TypeError:
test = True
assert test
10 - Itération¶
En vous documentant sur internet, faites de vos listes chainées des itérables.
# Insérez votre code ici
lc = Chaine(range(10))
s = 0
for v in lc:
s += v
assert s == 45
s = 0
for x in lc:
for y in lc:
s += x*y
assert s == 2025
11 - Générateur¶
Ajouter à la classe Chaine une méthode get_generatorqui renvoie un
générateur renvoyant successivement les valeurs de la liste chainée.
def get_gen_temp(self):
m = self._tete
while m is not None:
yield m.valeur
m = m.suivant
Chaine.get_generator = get_gen_temp
lc = Chaine(range(10))
g = lc.get_generator()
#assert type(g) == generator
j = 0
for i in g:
assert i == j
j += 1