Aller au contenu

TP - Implémenter une liste chaînée

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 » TAD_listes_chainees.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, en programmation orientée objet des listes sous la forme de listes chaînées.

Partie 1 - Classe Maillon

Les objets de la classe Maillon seront munis de deux attributs :

  • valeur : la valeur de l'élément ;
  • suivant : le lien qui pointe vers l'élément (le maillon) suivant.

Ces attributs seront initialisés par défaut à None.

  1. Complétez le constructeur de la classe Maillon.

    1
    2
    3
    class Maillon:
        def __init__(self, valeur=None, suivant=None):
            pass
    
  2. Testez l'instruction suivante :

    >>> n = Maillon(4)
    >>> n
    

    1. Quel est le maillon créé par cette instruction ?
    2. A quoi correspond l'affichage obtenu ?
  3. Complétez la définition de la méthode __repr__() afin d'obtenir des affichages de la forme suivante :

    >>> m = Maillon()
    >>> m
    (None, None)
    
    >>> n = Maillon(4, m)
    >>> n
    (4, (None, None))
    

Partie 2 - Classe ListeChainee

Les objets de la classe ListeChainee sont munis du seul attribut premier, initialisé à None par défaut.

Complétez les méthodes de cette classe et vérifiez votre travail à l'aide du plan de test qui suit.

Le code à compléter
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class ListeChainee:
    """
    Implémentation d'une liste chaînée
    """

    def __init__(self):
        """
        Initialisation d'une liste chaînée.
        """
        pass

    def est_vide(self):
        """
        Booléen indiquant si la liste chaînée est vide
        """
        pass

    def inserer_en_tete(self, elt):
        """
        Insère un élément en tête de liste.
        """
        pass

    def tete(self):
        """
        Renvoie la valeur de l'élément en tête de liste.
        """
        pass

    def queue(self):
        """
        Renvoie la liste située en queue (pas le maillon !)
        sous la forme d'une nouvelle liste.
        Attention aux effets de bord
        """
        pass

    def __repr__(self):
        """
        Sortie: str - Chaîne d'affichage de la liste.
        """
        pass

Plan de test

Attention à la méthode queue() qui doit doit renvoyer une liste de type ListeChainee.

>>> lst = ListeChainee()
>>> lst
None

>>> lst.inserer_en_tete(2)
>>> lst.inserer_en_tete(8)
>>> lst.inserer_en_tete(5)
>>> lst
(5, (8, (2, None)))

>>> lst.tete()
5

>>> lst2 = lst.queue()
>>> lst2
(8, (2, None))

>>> lst2.inserer_en_tete(0)
>>> lst2
(0, (8, (2, None)))