Aller au contenu principal

TP2 - Pile/File programmation Objet

Objectifs
  1. Représenter des structures de données en objet ;
  2. Créer un ensemble de méthodes manipulant ces objets.
Au préalable
  1. Se créer un dossier Terminale NSI sur votre ordinateur ou clé USB
  2. Dans ce dossier, créer un dossier Structures Linéaires

Sur EduPython ou autre instance python, faire :

  1. Créer un nouveau fichier en cliquant sur l'icône 📄, ou en appuyant sur CTRL+N
  2. Enregistrer le fichier sous le nom TP2_Pile_File_POO en cliquant sur l'icône 💾, ou en appuyant sur CTRL+S
TP

L'ensemble des exercices se fait sur python.
Dans ce TP, les piles et les files contiennent les mêmes 2 attributs :

  • tete : None ou valeur passée en paramètre ;
  • reste : None s’il n’y en a pas, une Pile/File s’il y en a un, passé en paramètre.

Files​

Rappel

L’élément en tête de file est le premier à partir, enfiler rajoute à chaque fois un élément à la fin.

Soit le modèle de la classe File suivant :

class File :
    def __init__(self, ..., ...):
        ...
    def __str__(self):
        ...
    def estVide(self):
        ...
    def enfiler(self, ...):
        ...
    def defiler(self):
        ...
    def taille(self):
        ...
✏️Exercices
  1. 1
    Compléter le constructeur de la classe.
  2. 2
    Dans le main, définir une première file contenant l'élément 3, puis une seconde file contenant les éléments 4 puis 2.
  3. 3
    Compléter la méthode __str__. Celle-ci doit afficher la tête de chaque élément de la file.
  4. 4
    Afficher le contenu de la première file, puis de la seconde.
  5. 5
    Compléter la méthode estVide.
  6. 6
    Compléter la méthode enfiler. L'élément en paramètre est ajouté au dernier objet de la file.
  7. 7
    Tester la méthode : enfiler l'entier 6 dans la première file, puis l'afficher.
  8. 8
    Compléter la méthode defiler. Celle-ci supprime le premier élément de la file, et le retourne.
  9. 9
    Tester la méthode : défiler la seconde file.
  10. 10
    Compléter la méthode taille, retournant la taille de la file.
  11. 11
    Écrire la méthode passerPremier(self, i) qui va placer l’élément à la i-ème position en première place.
  12. 12
    Écrire la méthode changerPlace(self, i, j) qui va échanger de place l'élément à la i-ème place avec celui à la j-ème place.

Piles​

Rappel

L’élément en tête de pile est le premier à partir, empiler rajoute à chaque fois un élément au début de la pile.

Soit le code suivant :

class Pile :
    def __init__(self, ..., ...):
        ...
    def __str__(self):
        ...
    def estVide(self):
        ...
    def empiler(self, ...):
        ...
    def depiler(self):
        ...
    def taille(self):
        ...
✏️Exercices
  1. 1
    Compléter le constructeur de la classe.
  2. 2
    Dans le main, définir une première pile contenant l'élément 12, puis une seconde pile contenant les éléments 5 puis 8.
  3. 3
    Compléter la méthode __str__. Celle-ci doit afficher la tête de chaque élément de la pile.
  4. 4
    Afficher le contenu de la première pile, puis de la seconde.
  5. 5
    Compléter la méthode estVide.
  6. 6
    Compléter la méthode empiler. L'élément en paramètre est ajouté au premier objet de la pile.
  7. 7
    Tester la méthode : empiler l'entier 6 dans la première pile, puis l'afficher.
  8. 8
    Compléter la méthode depiler. Celle-ci supprime le premier élément de la pile, et le retourne.
  9. 9
    Tester la méthode : dépiler la seconde pile.
  10. 10
    Compléter la méthode taille, retournant la taille de la pile.
  11. 11
    Écrire une méthode recherche(self,x) qui vérifie si l’élément x est bien présent dans la pile.

Aller plus loin​

✏️Exercices
  1. 1
    Créer une fonction maxPile(P, i) ayant pour paramètres une pile P et un entier i. Cette fonction retourne la position du plus grand élément parmi les i premiers éléments empilés de la pile P.
    Après appel de cette fonction, la pile P devra avoir retrouvé son état d’origine.
    La position du sommet de la pile est 1.
  2. 2
    Créer une fonction retourner(P,j) ayant pour paramètres une pile P et un entier j. Cette fonction inverse l’ordre des j premiers éléments empilés, et ne renvoie rien.
    On pourra utiliser deux piles temporaires.

On souhaite modéliser une pile de crêpes, chacune représentée par un numéro modélisant leur taille. Ainsi la "crêpe 1" sera plus petite que la "crêpe 2", elle-même plus petite que la "crêpe 3" et ainsi de suite.

Le but : on souhaite trier les crêpes par ordre croissant, c’est-à-dire que la plus grosse crêpe soit tout en dessous de la pile, la plus petite tout en haut.

On définit l’algorithme suivant :

  • On recherche la plus grande crêpe ;
  • On retourne la pile à partir de cette crêpe de façon à mettre cette plus grande crêpe tout en haut de la pile ;
  • On retourne l’ensemble de la pile de façon à ce que cette plus grande crêpe se retrouve tout en bas ;
  • La plus grande crêpe étant à sa place, on recommence l'algorithme avec le reste de la pile.
  1. 3
    Créer la fonction tri_crepes(P) ayant pour paramètre une pile P. Cette fonction trie la pile P selon la méthode du tri crêpes et ne renvoie rien.
    On utilisera les fonctions créées dans les questions précédentes.
    Vous pourrez faire un schéma pour expliciter le fonctionnement du tri crêpe.