Aller au contenu

TP - Améliorer l'interface de liste chaînée☘

Ce TP a pour but de reprogrammer une partie des fonctions sur les listes déjà étudiées dans le premier TP, cette fois-ci sous une forme « orientée objet » en poursuivant le travail réalisé dans le TP sur l'implémentation des listes chaînées.

Pour cela, reprenez le fichier TAD_listes_chainees.py. Les parties suivantes vont vous conduire à compléter cette implémentation par de nouvelles méthodes.

Rappel - L'implémentation obtenue
 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
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
62
63
64
65
class Maillon:
    """
    Implémentation d'un Maillon,
    nécessaire à l'implémentation d'une liste chaînée
    """

    def __init__(self, valeur=None, suivant=None):
        """
        Initialisation d'un maillon
        """
        self.valeur = valeur
        self.suivant = suivant

    def __repr__(self):
        """
        Sortie: str - Chaîne d'affichage du maillon.
        """
        return f"({self.valeur}, {self.suivant})"


class ListeChainee:
    """
    Implémentation d'une liste chaînée
    """

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

    def est_vide(self):
        """
        Booléen indiquant si la liste chaînée est vide
        """
        return self.premier is None

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

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

    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
        """
        result = ListeChainee()
        if self.premier.suivant is not None:
            result.premier = self.premier.suivant
        return result

    def __repr__(self):
        """
        Sortie: str - Chaîne d'affichage de la liste.
        """
        return f"{self.premier}"

Conseil général

Faites des schémas sur le modèle de ceux travaillés en TD !

Partie 1 - Vider puis remplir☘

  1. Complétez la définition à trous de la méthode vider() qui supprime tous les éléments de la liste.

    1
2
3
4
5
6
        def vider(self):
        """
        Supprime tous les éléments de la liste
        """
        while not self.est_vide():
            temp = ...

    Plan de test

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

>>> lst.vider()
>>> lst
None

  2. Ajoutez une méthode tab_to_liste() qui prend en paramètre un tableau (type list en Python) et qui remplit la liste avec les éléments du tableau.
    Attention à bien garder le même ordre pour les éléments.

    Plan de test

    >>> lst = ListeChainee()
>>> lst.tab_to_liste([1, 2, 3, 4])
>>> lst
(1, (2, (3, (4, None))))

Partie 2 - insertion, suppression☘

  1. Complétez la définition à trous de la méthode inserer_en_dernier() qui insère un élément en fin de liste.

    1
2
3
4
5
6
7
8
9
        def inserer_en_dernier(self, elt):
        """
        Insère l'élément en fin de liste chaînée
        """
        if self.est_vide():
            ...
        else:
            temp = self.premier
            while ...

    Plan de test

    >>> lst = ListeChainee()
>>> lst.tab_to_liste([1, 2, 3, 4])
>>> lst.inserer_en_dernier(5)
>>> lst
(1, (2, (3, (4, (5, None)))))

  2. Testez les instructions ci-après dans la console puis appelez l'enseignant et justifiez-lui les valeurs affichées par la console. 

    >>> lst = ListeChainee()
>>> lst.tab_to_liste([1, 2, 3, 4])
>>> lst

>>> lst2 = lst.queue()
>>> lst2

>>> lst2.inserer_en_dernier(5)
>>> lst2

>>> lst

  3. Ajoutez une méthode supprimer_premier() qui supprime le premier élément de la liste.

    1
2
3
4
        def supprimer_premier(self):
        """
        Sortie: None - Supprime le premier élément de la liste
        """

    Plan de test

    >>> lst = ListeChainee()
>>> lst.tab_to_liste([1, 2, 3, 4])      
>>> lst
(1, (2, (3, (4, None))))

>>> lst.supprimer_premier()
>>> lst
(2, (3, (4, None)))

  4. Ajoutez une méthode supprimer_dernier() qui supprime le dernier élément de la liste.

    1
2
3
4
        def supprimer_dernier(self):
        """
        Sortie: None - Supprime le dernier élément de la liste
        """
    Une piste

    Séparez les cas :

    • aucun élément
    • un élément
    • plusieurs éléments

    Plan de test

    >>> lst = ListeChainee()
>>> lst.tab_to_liste([1, 2, 3, 4])      
>>> lst
(1, (2, (3, (4, None))))

>>> lst.supprimer_dernier()
>>> lst
(1, (2, (3, None)))

Partie 3 - « Jouer » avec les indices☘

  1. Complétez la définition à trous de la méthode __len__() qui renvoie le nombre d'éléments présents dans la liste.

    1
2
3
4
5
6
7
        def __len__(self):
        """
        Sortie: int - Nombre d'éléments de la liste
        """
        nb_elt = 0
        temp = self.premier
        while ...
    Une piste

    Vous pouvez vous inspirer de cette partie du cours.

    Plan de test

    >>> lst = ListeChainee()
>>> len(lst)
0

>>> lst.tab_to_liste([1, 2, 3, 4])
>>> len(lst)
4

  2. Ajoutez une méthode elt_indice() qui renvoie l'élément d'indice k (s'il existe - on numérote à partir de 0) de la liste.
    Il faudra prendre en compte les messages d'erreurs signalés ci-dessous dans votre programme.

    1
2
3
4
5
        def elt_indice(self, k):
        """
        k - int, entier tel que 0 <= k < taille
        Sortie: élément d'indice k de la liste
        """

    Plan de test

    >>> lst = ListeChainee()
>>> lst.elt_indice(4)
AssertionError: La liste est vide

>>> lst.tab_to_liste([1, 2, 3, 4])
>>> for i in range(5):
...     print(lst.elt_indice(i))
1
2
3
4
AssertionError: Index out of range

  3. Copiez/collez/modifiez légérement la méthode précédente afin d'obtenir la méthode modifier_elt_indice() qui modifie la valeur de l'élément d'indice k (s'il existe - on numérote à partir de 0) de la liste.
    Il faudra prendre en compte les messages d'erreurs signalés ci-dessous dans votre programme.

    1
2
3
4
5
6
        def modifier_elt_indice(self, k, elt):
        """
        k - int, entier positif inférieur au nombre d'éléments de la liste
        elt - un élément de même type que ceux de la liste
        Sortie: None - Modification de la valeur d'indice k de la liste
        """

    Plan de test

    >>> lst = ListeChainee()
>>> lst.modifier_elt_indice(5, 42)
AssertionError: La liste est vide

>>> lst.tab_to_liste([1, 2, 3, 4])
>>> for i in range(4):
...     lst.modifier_elt_indice(i, 5-i)

>>> lst
(5, (4, (3, (2, None))))

>>> lst.modifier_elt_indice(5, 42)
AssertionError: Index out of range

  4. Ajoutez une méthode insere_position() qui insère dans la liste une valeur à l'indice signalé (compris entre 0 et le nombre d'éléments de la liste).
    N'utilisez pas la méthode .taille() dans ce programme et inspirez-vous du travail précédent (les messages d'erreurs sont les mêmes et ne sont pas testés ci-dessous).

    1
2
3
4
5
6
        def insere_position(self, k, elt):
        """
        k - int, entier positif inférieur au nombre d'éléments de la liste
        elt - un élément de même type que ceux de la liste
        Sortie: None - Insertion de elt à l'indice k
        """
    Une piste

    Séparez le raisonnement sur l'indice 0 des autres indices.

    Plan de test

    >>> lst = ListeChainee()
>>> lst.tab_to_liste([1, 2, 3, 4])
>>> lst
(1, (2, (3, (4, None))))

>>> lst.insere_position(2, 42)
>>> lst
(1, (2, (42, (3, (4, None)))))

>>> lst.insere_position(1, 666)
>>> lst
(1, (666, (2, (42, (3, (4, None))))))

Partie 4 - Pour aller plus loin☘

Si vous êtes arrivés à ce point, vous pouvez vous débrouillez tout seul à présent.

Programmez les méthodes suivantes :

  1. somme() qui renvoie la somme des éléments (numériques) de la liste ;

    1
2
3
4
        def somme(self):
        """
        Sortie: int - La somme des éléments de la liste
        """

  2. indice_elt() qui renvoie l'indice de l'élément passé en paramètre s'il est présent dans la liste, qui renvoie -1 sinon ;

    1
2
3
4
5
        def indice_elt(self, elt):
        """
        elt - élément de même type que les éléments de la liste
        Sortie: int - indice de elt dans la liste, -1 s'il n'est pas présent
        """

  3. supprimer_elt_indice() qui supprime l'élément d'indice k (s'il existe - on numérote à partir de 0) de la liste ;

    1
2
3
4
5
        def supprimer_elt_indice(self, k):
        """
        k - int, entier tel que 0 <= k < taille
        Sortie: None - Supprime l'élément d'indice k
        """

  4. copie() qui renvoie une liste copie de la liste sur laquelle s'applique cette méthode (attention aux effets de bord...) ;

    1
2
3
4
        def copie(self):
        """
        Sortie: ListeChainee - Copie de la liste
        """

  5. __add__() qui prend en paramètre une liste et qui renvoie la liste concaténée. Les deux listes d'origine ne doivent pas avoir été modifiées par effet de bord...

    1
2
3
4
5
        def __add__(self, autreListe):
        """
        autreListe - Objet de type ListeChainee
        Sortie: ListeChainee - Liste constituée des deux précédentes concaténées
        """

  6. queue_distincte() qui renvoie, sous la forme d'une nouvelle liste, la queue de la liste sur laquelle s'applique cette méthode (pour éviter les effets de bord).

    1
2
3
4
5
        def queue_distincte(self):
        """
        Renvoie la queue de la liste sous la forme d'une nouvelle liste
        pour éviter les effets de bord
        """