Aller au contenu

TP - Implémenter une File

Ce TP doit conduire à créer de A à Z un module utilisable tout le reste de l'année.

Téléchargez le fichier « à trous » files.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier intitulé [Mes_modules].

Ce TP a pour but de définir une structure de données implémentant des files.

Remarque importante

La partie 1 a pour but d'implémenter une structure de file correspondant à l'interface vue en cours.
La partie 2 va compléter cette implémentation par de nouvelles méthodes, ce qui pourra permettre de modifier l'interface.

Partie 1 - Interface de base

La classe File sera munie d'un seul attribut nommé elements. Cet attribut est un tableau dynamique, c'est-à-dire de type list en Python et vide par défaut.

Le premier élément de la File est le premier élement du tableau, le dernier élément de la File est le dernier élément du tableau.

important

Les méthodes .append() et .pop() sont autorisées.

Pour la méthode .defiler(), il est demandé de réaliser un test de validité sous forme d'assertion (cf. le plan de test).

Le code à compléter
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class File:
    """Implémentation d'une File à partir d'un tableau (type list) Python"""

    def __init__(self):
        """
        Initialisation de la File
        """
        pass

    def est_vide(self):
        """
        Booléen indiquant si la File est vide
        """
        pass

    def enfiler(self, element):
        """
        Sortie: None - Place un élément en queue de file
                Cet élément est le dernier élément du tableau.
        """
        pass

    def defiler(self):
        """
        Sortie: Valeur du premier élément de la file.
                Cet élément est défilé, c'est-à-dire retiré du tableau.
        """
        pass

    def __repr__(self):
        """
        Sortie: str - Chaîne de caractères constituées des éléments
                de la file, séparés par des ->,
                le dernier à gauche, le premier à droite.
        """
        pass

Plan de test

>>> f = File()    
>>> f.defiler()
AssertionError: La file est vide.

>>> f.enfiler(7)    
>>> f.enfiler(3)    
>>> f.enfiler(0)    
>>> f
0 -> 3 -> 7

>>> f.defiler()
7

>>> f
0 -> 3

>>> f2 = File()
>>> f2

>>>

Vous pourrez tester votre interface en y faisant appel avec les programmes réalisés dans la page d'exercices.

Partie 2 - Interface améliorée

  1. Modifiez l'initialisation de la classe de sorte qu'elle accepte un paramètre supplémentaire de type list afin de « remplir « la file dès l'initialisation.

    Plan de test

    >>> f1 = File([2, 4, 1, 5])        
    >>> f1
    5 -> 1 -> 4 -> 2
    
    >>> f2 = File()
    >>> f3 = File()        
    >>> f2.enfiler(2)        
    >>> f2
    2
    
    >>> f3.enfiler(5)        
    >>> f3
    5
    

    Remarque

    Si vous n'obtenez pas les mêmes réponses pour f2 et f3 que dans le plan de test ci-dessus, alors appelez l'enseignant : il vous mettra sur la voie.

  2. Ajoutez une méthode .premier() qui renvoie la valeur du premier élément sans défiler celui-ci. Un test de validité de cette demande doit être réalisé sous forme d'assertion.

    Plan de test

    >>> f1 = File([2, 4, 1, 5])        
    >>> f1.premier()
    2
    
    >>> f1
    5 -> 1 -> 4 -> 2
    
    >>> f2 = File()        
    >>> f2.premier()
    AssertionError: La file est vide.
    
  3. Ajoutez une méthode .vider() qui « vide » entièrement la file.

    Plan de test

    >>> f1 = File([2, 4, 1, 5])        
    >>> f1.vider()        
    >>> f1
    
  4. Ajoutez une méthode .longueur() qui renvoie le nombre d'éléments contenus dans la file.

    Plan de test

    >>> f1 = File([2, 4, 1, 5])        
    >>> f1.longueur()
    4