File à partir d'une liste chainée⚓︎
On veut écrire une classe pour gérer une file à l'aide d'une liste chainée. On dispose d'une classe Maillon
permettant la création d'un maillon de la chaine, celui-ci étant constitué d'une valeur et d'une référence au maillon suivant de la chaine (à sa création le maillon ne connait pas son suivant, d'où l'utilisation de l'objet None
) :
class Maillon:
def __init__(self, valeur) :
self.valeur = valeur
self.suivant = None
La file non vide est constituée de maillons avec un maillon de tete
, celui qu'on va enlever lors de l'action defile
et un maillon de fin
qui est le dernier à être arrivé par l'action enfile
. S'il n'y a qu'un seul élément dans la file, le maillon de tete
est le même que celui de fin
.
Compléter la classe File
et vérifier votre travail sur les exemples. On vous donne l'initialiseur, la méthode est_vide
qui renvoie True
si la file est vide et False
sinon, ainsi que la méthode affiche
qui permet de voir l'état de la file manipulée.
Exemples
>>> file = File()
>>> file.est_vide()
True
>>> file.enfile(2)
>>> file.affiche()
← 2 ←
>>> file.est_vide()
False
>>> file.enfile(5)
>>> file.enfile(7)
>>> file.affiche()
← 2 5 7 ←
>>> file.defile()
2
>>> file.defile()
5
>>> file.affiche()
← 7 ←
class Maillon:bksl-nl def py-undpy-undinitpy-undpy-und(self, valeur):bksl-nl self.valeur = valeurbksl-nl self.suivant = Nonebksl-nlbksl-nlclass File:bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.tete = Nonebksl-nl self.fin = Nonebksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.fin is Nonebksl-nlbksl-nl def affiche(self):bksl-nl maillon = self.tetebksl-nl print('←', end=' ')bksl-nl while maillon is not None:bksl-nl print(maillon.valeur, end=' ')bksl-nl maillon = maillon.suivantbksl-nl print('←')bksl-nlbksl-nl def enfile(self, element):bksl-nl nouveaupy-undmaillon = ...bksl-nl if self.estpy-undvide():bksl-nl self.tete = ...bksl-nl else:bksl-nl self.fin.suivant = ...bksl-nl self... = nouveaupy-undmaillonbksl-nlbksl-nl def defile(self):bksl-nl if ...:bksl-nl resultat = ...bksl-nl self.tete = ...bksl-nl if self.tete is None:bksl-nl self.fin = ...bksl-nl return ...bksl-nl else:bksl-nl return Nonebksl-nlbksl-nl# testsbksl-nlbksl-nlfile = File()bksl-nlassert file.estpy-undvide()bksl-nlfile.enfile(2)bksl-nlassert not file.estpy-undvide()bksl-nlfile.enfile(5)bksl-nlfile.enfile(7)bksl-nlassert file.defile() == 2bksl-nlassert file.defile() == 5bksl-nlbksl-nlclass Maillon:bksl-nl def py-undpy-undinitpy-undpy-und(self, valeur):bksl-nl self.valeur = valeurbksl-nl self.suivant = Nonebksl-nlbksl-nlclass File:bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.tete = Nonebksl-nl self.fin = Nonebksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.fin is Nonebksl-nlbksl-nl def affiche(self):bksl-nl maillon = self.tetebksl-nl print('←', end=' ')bksl-nl while maillon is not None:bksl-nl print(maillon.valeur, end=' ')bksl-nl maillon = maillon.suivantbksl-nl print('←')bksl-nlbksl-nl def enfile(self, element):bksl-nl nouveaupy-undmaillon = Maillon(element)bksl-nl if self.estpy-undvide():bksl-nl self.tete = nouveaupy-undmaillonbksl-nl else:bksl-nl self.fin.suivant = nouveaupy-undmaillonbksl-nl self.fin = nouveaupy-undmaillonbksl-nlbksl-nl def defile(self):bksl-nl if not self.estpy-undvide():bksl-nl resultat = self.tete.valeurbksl-nl self.tete = self.tete.suivantbksl-nl if self.tete is None:bksl-nl self.fin = Nonebksl-nl return resultatbksl-nl else:bksl-nl return Nonebksl-nlbksl-nl# testsbksl-nlbksl-nlfile = File()bksl-nlassert file.estpy-undvide()bksl-nlfile.enfile(2)bksl-nlassert not file.estpy-undvide()bksl-nlfile.enfile(5)bksl-nlfile.enfile(7)bksl-nlassert file.defile() == 2bksl-nlassert file.defile() == 5bksl-nlbksl-nl
A
Représenter une file avec une liste chainée⚓︎
Il est aussi possible d'utiliser une liste chainée classique, en n'ayant une référence qu'au premier maillon, mais dans ce cas, il faut parcourir toute la liste pour les ajouts ou les retraits, selon le sens d'insertion.
return None
⚓︎
Dans la méthode defile
, le else: return None
est inutile puisque
si un appel de fonction ne se termine pas par un return
, la valeur
None
est automatiquement renvoyée.
Z