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-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
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