TP - Piles et Files

Dans le dossier [NSI], créez le dossier [A03-Structures_Lineaires].

Téléchargez le module TAD_ListesChaineesCirc.py qui contient une implémentation de Liste sous la forme d'une liste chaînée circulaire et placez ce module dans le dossier [A03-Structures_Lineaires].

Cette implémentation est réalisée sous la forme d'objets de la classe Liste. On récapitule les instructions à votre disposition dans le tableau ci-dessous :

Méthode/Opérations	Description
L = Liste()	Initialisation d'une liste vide
L.est_vide()	Renvoie True si la liste est vide, False sinon.
L.inserer_en_tete(elt)	Ajoute un nouvel élément au début de la liste L
L.inserer_en_dernier(elt)	Ajoute un nouvel élément à la fin de la liste L
elt = L.tete()	Renvoie la valeur du premier élément de la liste L
L.queue()	Remplace la liste L par la liste située en queue

On ajoute une méthode de conversion de Liste en chaîne de caractères (fonction str()).

Exemple d'affichage

>>> L = Liste()
>>> for i in range(5):
...     L.inserer_en_tete(i)
>>> str(L)
'4, 3, 2, 1, 0'

Consignes

Les deux parties de TP sont indépendantes les unes des autres. Elles doivent être programmées dans des fichiers distincts.

TPA03.11 - Programmer une Pile avec une Liste

Ce TP a pour but de vous faire programmer, en POO, une structure de Pile en utilisant uniquement les méthodes proposées dans l'interface du module TAD_ListesChaineesCirc.py.

Téléchargez puis complétez le fichier « à trous » TPA03.11.py (clic droit -> [Enregistrer sous]).

Vous ferez les tests de vérification nécessaires en ajoutant une méthode d'affichage des piles (en colonne) à partir de la méthode de conversion de Liste en chaîne de caractères (fonction str()).

Exemple d'affichage

>>> P = Pile()
>>> for i in range(5):
...     P.empiler(i)
>>> P 
4
3
2
1
0

Exemple de tests

>>> P = Pile()
>>> for i in range(5):
...     P.empiler(i)
>>> P 
4
3
2
1
0
>>> P.depiler()
4
>>> P 
3
2
1
0
>>> P.empiler(5)
>>> P 
5
3
2
1
0
>>> while not P.est_vide():
...     P.depiler()
...     print(P)
...     print(P.est_vide())
3
2
1
0
False
2
1
0
False
1
0
False
0
False

True

Rappel des méthodes « de base » pour les piles

Méthode/Opérations	Description
P = Pile()	Initialisation d'une pile vide.
P.est_vide()	Renvoie True si la pile est vide, False sinon.
P.empiler(elt)	Empile un nouvel élément au sommet de la pile.
elt = P.depiler()	Lorsque la pile n'est pas vide, supprime le sommet de la pile et renvoie la valeur de ce sommet.

TPA03.12 - Programmer une File avec une Liste

Ce TP a pour but de vous faire programmer, en POO, une structure de File en utilisant uniquement les méthodes proposées dans l'interface du module TAD_ListesChaineesCirc.py.

Téléchargez puis complétez le fichier « à trous » TPA03.12.py (clic droit -> [Enregistrer sous]).

Vous ferez les tests de vérification nécessaires en ajoutant une méthode d'affichage des files (en ligne) à partir de la méthode de conversion de Liste en chaîne de caractères (fonction str()).

Exemple d'affichage

>>> F = File()
>>> for i in range(5):
...     F.enfiler(i)
>>> F 
4 -> 3 -> 2 -> 1 -> 0

Exemple de tests

>>> F = File()
>>> for i in range(5):
...     F.enfiler(i)
>>> F 
4 -> 3 -> 2 -> 1 -> 0
>>> F.defiler()
0
>>> F 
4 -> 3 -> 2 -> 1
>>> F.enfiler(5)
>>> F 
5 -> 4 -> 3 -> 2 -> 1
>>> while not F.est_vide():
...     F.defiler()
...     print(F)
...     print(F.est_vide())
5 -> 4 -> 3 -> 2
False
5 -> 4 -> 3
False
5 -> 4
False
5
False

True

Rappel des méthodes « de base » pour les files

Méthode/Opérations	Description
F = File()	Initialisation d'une file vide.
F.est_vide()	Renvoie True si la file est vide, False sinon.
F.enfiler(elt)	Enfile un nouvel élément en queue de la file.
elt = F.defiler()	Lorsque la file n'est pas vide, supprime le premier élément de la file et renvoie la valeur de cet élément.