Pour chaque question, une seule réponse est correcte.
1. Dans une liste chaînée, chaque nœud contient :
Correction publiée après la séance.
2. Pour représenter une liste vide, on utilise :
NoneListeChainee dont l’attribut premier vaut None[]Correction publiée après la séance.
3. Quelle est la complexité de l’ajout en tête d’une liste chaînée ?
Correction publiée après la séance.
4. On considère la liste chaînée 5 → 3 → 8 → None. Quelle expression Python permet d’accéder à la valeur 8 ?
ma_liste.premier.elementma_liste.premier.suivant.elementma_liste.premier.suivant.suivant.elementma_liste.ieme_element(3)Correction publiée après la séance.
5. Par rapport au type list de Python (tableau dynamique), la liste chaînée est plus performante pour :
Correction publiée après la séance.
On rappelle les classes vues en cours :
class Noeud:
def __init__(self, element, suivant=None):
self.element = element
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.premier = None
def ajout_en_tete(self, element):
nouveau = Noeud(element)
nouveau.suivant = self.premier
self.premier = nouveau
def ajout_en_queue(self, element):
"""Insère element en queue de liste"""
if self.premier == None:
self.ajout_en_tete(element)
else:
courant = self.premier
while courant.suivant != None:
courant = courant.suivant
dernier = Noeud(element)
courant.suivant = dernier
On exécute les instructions suivantes :
ma_liste = ListeChainee()
ma_liste.ajout_en_tete(7)
ma_liste.ajout_en_tete(3)
ma_liste.ajout_en_tete(9)
Dessiner l’état de la liste chaînée après chaque instruction ajout_en_tete. On représentera chaque nœud par une case contenant la valeur et une flèche vers le suivant.
ajout_en_tete crée un nœud dont le suivant est l’ancien premier nœud, puis en fait le nouveau premier : chaque nouvelle valeur se place devant les autres.
Quelle est la valeur de ma_liste.premier.element ?
premier désigne le nœud de tête, celui du dernier ajout en tête.
Quelle est la valeur de ma_liste.premier.suivant.suivant.element ?
Chaque .suivant avance d’un nœud : partir de la tête du dessin et avancer deux fois.
On ajoute maintenant ma_liste.ajout_en_tete(1). Dessiner le nouvel état de la liste.
Correction publiée après la séance.
On reprend les classes Noeud et ListeChainee. Compléter les méthodes suivantes en remplaçant les ... par le code approprié.
a) Méthode __len__ qui renvoie le nombre d’éléments de la liste :
def __len__(self):
courant = ... # partir du premier nœud
cpt = 0
while courant:
courant = ... # passer au nœud suivant
cpt += 1
return ... # renvoyer le compteur
self.premier est le premier nœud et courant.suivant le nœud qui suit courant. La boucle s’arrête quand courant vaut None, c’est-à-dire après le dernier nœud.
b) Méthode __repr__ qui renvoie une représentation sous la forme "9 → 3 → 7" :
def __repr__(self):
elements = []
courant = self.premier
while courant:
elements.append(str(...)) # ajouter la valeur du nœud
courant = ... # passer au suivant
return " → ".join(elements)
La valeur d’un nœud est son attribut element ; on avance de nœud en nœud comme dans __len__.
c) Méthode contient qui renvoie True si element est dans la liste, False sinon :
def contient(self, element):
courant = self.premier
while courant:
if ... == element: # comparer avec la valeur du nœud
return True
courant = ... # passer au suivant
return ... # élément non trouvé
Comparer courant.element à element. Si la boucle se termine sans l’avoir trouvé, l’élément n’est pas dans la liste.
Correction publiée après la séance.
Écrire la méthode supprime_en_tete(self) qui supprime le premier élément de la liste et renvoie sa valeur. Si la liste est vide, la méthode doit lever une exception ValueError("liste vide").
Si self.premier vaut None, la liste est vide : lever l’exception avec raise ValueError("liste vide"). Sinon, garder la valeur du premier nœud, faire du nœud suivant la nouvelle tête, puis renvoyer la valeur gardée.
def supprime_en_tete(self):
if self.premier == None:
raise ValueError("liste vide")
valeur = self.premier.element
self.premier = ...
return ...
Tester votre méthode sur la liste 9 → 3 → 7 :
supprime_en_tete() une première fois : quelle valeur est renvoyée ? Quel est l’état de la liste ?supprime_en_tete() deux fois de plus : quelles valeurs sont renvoyées ?Construire la liste avec trois appels à ajout_en_tete, en ajoutant 7, puis 3, puis 9, et afficher la liste après chaque suppression. Le dernier appel porte sur une liste vide : relire ce que la méthode doit faire dans ce cas.
Correction publiée après la séance.
Écrire la méthode inserer(self, element, i) qui insère element en position i dans la liste (les positions sont comptées à partir de 0).
Indications :
i == 0, il suffit d’utiliser ajout_en_tete ;i - 1 (le futur prédécesseur) ;i ;i - 1.Tester avec la liste 9 → 3 → 7 :
inserer(5, 0) doit donner 5 → 9 → 3 → 7 ;inserer(1, 2) doit donner 5 → 9 → 1 → 3 → 7.Les indications donnent la marche à suivre. Pour atteindre le nœud de position i - 1, partir de self.premier et avancer i - 1 fois avec courant = courant.suivant.
def inserer(self, element, i):
if i == 0:
self.ajout_en_tete(element)
else:
courant = self.premier
for _ in range(i - 1):
courant = ...
courant.suivant = Noeud(element, ...)
Correction publiée après la séance.
Compléter le tableau suivant en indiquant la complexité de chaque opération pour les deux structures :
| Opération | list Python (tableau) |
Liste chaînée |
|---|---|---|
Accès à l’élément d’indice i |
||
| Ajout en tête | ||
| Ajout en queue | ||
| Suppression en tête | ||
| Suppression en queue | ||
| Recherche d’un élément |
Le tableau Python accède directement à la case d’indice i, mais doit décaler tous les éléments quand on insère ou supprime au début. La liste chaînée n’accède directement qu’à son premier nœud : atteindre un autre nœud demande de parcourir la liste depuis la tête.
Correction publiée après la séance.
Dans la classe ListeChainee de l’exercice 2, la méthode ajout_en_queue parcourt toute la liste pour atteindre le dernier nœud. On écrit une nouvelle classe, ListeAvecDernier, qui garde en plus une référence dernier vers le dernier nœud. Quand la liste est vide, premier et dernier valent tous les deux None.
a) Quelle est la complexité de la méthode ajout_en_queue de la classe ListeChainee ? Pourquoi ?
Que fait la boucle while avant d’accrocher le nouveau nœud ? Combien de tours fait-elle pour une liste de \(n\) éléments ?
b) Compléter les méthodes de la classe ListeAvecDernier, pour que ajout_en_queue s’exécute en temps constant et que dernier désigne toujours le dernier nœud :
class ListeAvecDernier:
def __init__(self):
self.premier = None
self.dernier = None
def ajout_en_queue(self, element):
nouveau = Noeud(element)
if self.dernier == None:
self.premier = ...
else:
self.dernier.suivant = ...
self.dernier = ...
def ajout_en_tete(self, element):
nouveau = Noeud(element, self.premier)
self.premier = nouveau
if ...:
self.dernier = ...
def supprime_en_tete(self):
"""Retire le premier nœud d'une liste non vide et renvoie son élément."""
element = self.premier.element
self.premier = ...
if ...:
self.dernier = ...
return element
Si la liste n’a pas de dernier nœud, elle est vide : un nœud ajouté, en tête comme en queue, est alors à la fois le premier et le dernier. Après une suppression en tête, la liste est devenue vide quand premier vaut None : il n’y a plus de dernier nœud non plus.
c) Dans supprime_en_tete, que se passerait-il si l’on ne remettait pas dernier à None quand la liste devient vide ? Dérouler la suite d’opérations suivante.
l = ListeAvecDernier()
l.ajout_en_queue(5)
l.supprime_en_tete()
l.ajout_en_queue(8)
Après la suppression du seul nœud, premier vaut None. Vers quel nœud dernier pointe-t-il encore ? Que fait alors ajout_en_queue(8) ?
d) Garder une référence vers le dernier nœud ne rend pas la suppression en queue plus rapide. Pourquoi ?
Pour retirer le dernier nœud, quel nœud faut-il modifier ? Peut-on l’atteindre depuis dernier ?
Correction publiée après la séance.