Aller au contenu

Exercices pour s'entraîner☘

Prenez l'habitude de revenir vous entraîner régulièrement avec ces exercices tout au long de l'année. Ils sont généralement accompagnés de pistes et de leur solution pour vous permettre de progresser.

Préambule☘

Utilisez le module TAD_listes_chainees.py développé en Travaux Pratiques qui contient une implémentation orientée objet de liste et placez ce module dans votre répertoire de travail.
L'interface est (presque) celle donnée dans le cours :

Méthode/Opérations Description
L = ListeChainee() Initialisation d'une liste chaînée vide
L.est_vide() Renvoie True si la liste L est vide, False sinon.
L.inserer_en_tete(elt) Ajoute un nouveau maillon au début de la liste.
L.tete() Renvoie la valeur du premier maillon de la liste
L.queue() Renvoie la liste située en queue
Attention aux effets de bord !

Pour faciliter les tests dans les exercices, on ajoute à cette implémentation :

  • une méthode d'affichage __repr__() ;
  • une méthode pour vider entièrement vider() ;
  • une méthode de remplissage rapide à partir d'un tableau tab_to_liste().
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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 !).
        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}"

    def vider(self):
        """"
        Supprime tous les éléments de la liste.
        Ne renvoie rien.
        """
        while not self.est_vide():
            temp = self.premier
            self.premier = temp.suivant
            del temp

    def tab_to_liste(self, tab):
        """
        Insère les éléments de tab dans l'objet ListeChainee
        """
        self.vider()
        for i in range(len(tab)-1, -1, -1):
            self.inserer_en_tete(tab[i])
Enregistrez le fichier TAD_listes_chainees.py sous le nom ProgA02.60.py.
Ce fichier sera complété au fur et à mesure des exercices de cette page.

ProgA02.61 - Renverser☘

  1. Ajoutez une méthode renverser() qui renverse en place la liste (méthode à effet de bord).

    84
85
86
87
        def renverser(self):
        """
        Renverse les éléments de la liste (le premier devient dernier, etc...)
        """

    Plan de test

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

>>> L1.renverser()
>>> L1
(3, (4, (1, (2, (5, None)))))
    Une solution
    84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
        def renverser(self):
        """
        Renverse les éléments de la liste (le premier devient dernier, etc...)
        """
        temp = ListeChainee()
        while not self.est_vide():
            temp.inserer_en_tete(self.tete())
            self.premier = self.premier.suivant
        temp2 = ListeChainee()
        while not temp.est_vide():
            temp2.inserer_en_tete(temp.tete())
            temp.premier = temp.premier.suivant
        while not temp2.est_vide():
            self.inserer_en_tete(temp2.tete())
            temp2.premier = temp2.premier.suivant

  2. Même si vous n'êtes pas autorisé à utiliser ces structures dans ce TP, posez-vous la question suivante (et essayez d'y répondre) :
    Pour programmer cette méthode, est-il plus efficace d'utiliser une structure de Pile ou bien une structure de File ?

    Une solution

    Une structure de Pile est bien évidemment le plus efficace ici.
    Si vous n'en êtes pas convaincu, étudiez de nouveau le chapitre sur les Piles et les Files

ProgA02.62 - Liste triée ?☘

Ajoutez une méthode est_triee() qui renvoie True si les éléments de la liste sont triés par ordre croissant et False sinon.

100
101
102
103
104
    def est_triee(self):
        """
        Sortie: bool - True si les éléments de la liste sont triés par
                ordre croissant, False sinon
        """

Plan de test

>>> L1 = ListeChainee()
>>> L1.tab_to_liste([5, 2, 1, 4, 3])
>>> L1.est_triee()
False

>>> L2 = ListeChainee()
>>> L2.tab_to_liste([2*x for x in range(5)])
>>> L2
(0, (2, (4, (6, (8, None)))))

>>> L2.est_triee()
True
Une solution
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
    def est_triee(self):
        """
        Sortie: bool - True si les éléments de la liste sont triés par
                ordre croissant, False sinon
        """
        if self.est_vide():
            return True
        elif self.premier.suivant is None:
            return True
        else:
            temp = self.premier
            while temp.suivant is not None:
                if temp.valeur > temp.suivant.valeur:
                    return False
                else:
                    temp = temp.suivant
            return True

ProgA02.63 - Insérer dans une liste triée☘

Ajoutez une méthode inserer() qui insère l'élément passé en paramètre à sa bonne place dans une liste déjà triée (la liste doit rester triée : méthode à effet de bord).

119
120
121
122
123
    def inserer(self, elt):
        """
        Précondition : la liste est triée
        Sortie: None - Insère elt à sa bonne place dans la liste
        """

Plan de test

>>> L2 = ListeChainee()
>>> L2.tab_to_liste([2*x for x in range(5)])
>>> L2
(0, (2, (4, (6, (8, None)))))

>>> L2.inserer(3)
>>> L2.inserer(-1)
>>> L2.inserer(11)
>>> L2
(-1, (0, (2, (3, (4, (6, (8, (11, None))))))))
Une solution
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
    def inserer(self, elt):
        """
        Précondition : la liste est triée
        Sortie: None - Insère elt à sa bonne place dans la liste
        """
        if self.est_vide():
            self.inserer_en_tete(elt)
        elif elt < self.premier.valeur:
            self.inserer_en_tete(elt)
        else:
            preced = self.premier
            temp = self.premier.suivant
            while temp is not None and temp.valeur < elt:
                preced = temp
                temp = temp.suivant
            new = Maillon(elt, temp)
            preced.suivant = new

ProgA02.64 - Tri par insertion☘

Ajoutez une méthode tri_insertion() qui renvoie une nouvelle liste triée par insertion.

138
139
140
141
    def tri_insertion(self):
        """
        Sortie: ListeChainee - Une liste triée de mêmes éléments que self
        """

Plan de test

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

>>> L3 = L1.tri_insertion()
>>> L3
(1, (2, (3, (4, (5, None)))))
Une solution
138
139
140
141
142
143
144
145
146
147
148
149
    def tri_insertion(self):
        """
        Sortie: ListeChainee - Une liste triée de mêmes éléments que self
        """
        result = ListeChainee()
        if not self.est_vide():
            temp = self.premier
            while temp is not None:
                elt = temp.valeur
                result.inserer(elt)
                temp = temp.suivant
        return result