Table des matières

Mission 11 - Listes chainées

Phase de démarrage

Phase de réalisation

Mission 11 : Les listes chaînées

/syllabus/info1-exercises/assets/linkedtrain.jpg

Introduction

Le Service des sports fait appel à vous dans le cadre du développement d'un système informatique pour la gestion des résultats de la course des 24h Vélo de Louvain-la-Neuve. Vous devez réaliser un programme Python permettant d'encoder et de manipuler les différentes données nécessaires (coureurs, résultats, classements) pour tenir à jour les classements en cours de course. Par exemple, il faut pouvoir afficher en temps réel, sur des écrans disposés dans la ville et sur internet, le classement des meilleurs temps pour le tour du circuit.

Un classement par temps (Tour de France 2013)

Pour cette mission, vous allez devoir implémenter une classe Python permettant de manipuler un tel classement et de le mettre à jour avec de nouveaux résultats. Le classement doit être ordonné, et on ne désire pas refaire le tri pour chaque nouveau résultat: il faut donc une structure de liste ordonnée avec des opérations qui maintiennent cet ordre. Vous utiliserez pour cela une liste chaînée.

Objectifs

A l'issue de cette mission, chacun d'entre vous :

sera en mesure d'exploiter les listes chaînées
aura eu l'occasion d'écrire des tests unitaires pour ses programmes

Préparation, étude et apprentissage

Comment bien préparer la mission?

Assister au cours pour comprendre les notions et concepts qui seront abordés.
Lire attentivement et comprendre le chapitre sur Linked lists dans la partie Objects du syllabus théorie :
- 6 - Linked lists
  Embedded references
  
  The Node class
  
  Linked lists as collections
  
  Linked lists and recursion
  
  Infinite lists
  
  Ambiguity between lists and nodes
  
  Modifying lists
  
  Wrappers and helpers
  
  The LinkedList class
Essayer et comprendre le code développé dans le syllabus et qui se trouve aussi dans l'annexe correspondant :
- Appendix - Source code of linked lists
  LinkedList class
  
  Node class
  
  Creating and using LinkedList objects
Dans cette mission, vous devrez de nouveau utiliser le framework unittest pour produire des classes de test. Relisez la documentation si vous aviez du mal à créer des tests unitaires lors de la mission précédente.
Répondre aux questions à choix multiples et aux autres questions de démarrage.

Questionnaire de démarrage

Ces questions supposent que vous avez lu le chapitre du syllabus théorique sur les listes chaînées et que vous avez lu et testé le code des classes LinkedList et Node dans l'annexe code des classes LinkedList et Node dans l'annexe correspondante.

Questions à choix multiples

Les questions à choix multiples de cette mission sont accessibles en ligne depuis https://inginious.info.ucl.ac.be/course/LSINF1101-PYTHON/Session11_QCM.

Questions ouvertes

0. Notions théoriques

Répondez aux questions suivantes:

Qu'est-ce qu'une liste chaînée?
Qu'est-ce qu'une structure de données? Donnez un exemple.
Expliquez la différence entre un noeud (Node) et sa cargaison (cargo).
Expliquez la différence entre un noeud (Node) et une liste chainée (LinkedList).
Dans le livre et le cours magistral, la notion d'une liste chaînée a d'abord été expliqué sans la classe LinkedList, simplement en chaînant des noeuds l'un à l'autre. Pourquoi avons nous alors besoin d'une classe LinkedList?
Expliquez et donnez un exemple du caractère ambiguë d'un noeud.

1. Utilisation d'une `LinkedList`

Question 1a : Manipuler une liste vide

Cette question concerne l'utilisation de la classe LinkedList dont le code se trouve dans l'annexe suivante du syllabus : Appendix - Source code of linked lists

Utilisez la classe LinkedList pour créer une liste chaînée vide l.

Donnez une instruction Python pour imprimer le contenu de cette liste l.

Quel résultat sera affiché si on essaie d'imprimer la liste l avec l'instruction print(l)? Expliquez.

Donnez une instruction Python pour imprimer la taille de cette liste l .

Quel résultat sera affiché si on essaie d'imprimer la taille avec l'instruction print(l.__length)? Expliquez.

Question 1b : Remplir la liste

Pour ajouter des éléments à une liste vide, quelqu'un a écrit les instructions suivantes:

l = LinkedList()
l.add(3)
l.add(2)
l.add(1)
l.print()

Mais quelqu'un d'autre à écrit:

l = LinkedList()
l.add(Node(3))
l.add(Node(2))
l.add(Node(1))
l.print()

Dans les deux cas, exécuter l'instruction l.print() affichera [ 1 2 3 ].

Lequel des deux fragments de code ci-dessus vous semble correct? Pourquoi l'autre imprime quand-même le même résulat?

Indice : qu'est-ce qui se passe si on exécute l'instruction print(Node(Node(Node(1))))? Pouvez-vous expliquer?

2. Imprimer une liste chaînée

Dans le code donné dans l'annexe Appendix - Source code of linked lists la méthode print() de la classe LinkedList imprime les éléments d'une liste chaînée, séparés par une espace. Par exemple:

>>> l = LinkedList()
>>> l.add(3)
>>> l.add(2)
>>> l.add(1)

>>> l.print()
[ 1 2 3 ]

Or, normalement la convention est de séparer les éléments d'une liste par des virgules. Ajoutez une nouvelle méthode print_avec_virgule() dans la classe LinkedList qui imprime la liste comme suite:

>>> l.print_avec_virgule()
[ 1, 2, 3 ]

Attention: il n'y a pas de virgule après le dernier élément ou si on imprime une liste vide.

>>> l = LinkedList()
>>> l.print_avec_virgule()
[ ]

3. Imprimer une liste chaînée (généralisation)

Généralisez la méthode print_avec_virgule de l'exercice précédente par une méthode print_avec_separateur qui peut prendre n'importe quelle séparateur. Par exemple:

>>> l = LinkedList()
>>> l.add(3)
>>> l.add(2)
>>> l.add(1)

>>> l.print_avec_separateur(", ")
[ 1, 2, 3 ]
>>> l.print_avec_separateur(" ")
[ 1 2 3 ]
>>> l.print_avec_separateur(" - ")
[ 1 - 2 - 3 ]

4. Initialiser une liste chaînée

Changez la méthode d'initialisation __init__ de la classe LinkedList (cf. l'annexe Appendix - Source code of linked lists ), afin qu'elle prenne une liste Python comme paramètre pour initialiser la liste chaînée. Attention: le premier élément de cette liste doit devenir le premier élément de la liste chainée, et ainsi de suite. Spécifier bien cette nouvelle méthode __init__ avec des conditions pre et post.

def __init__(self, lst=[]):
    self.__length = 0
    self.__head = None
    # initialiser la liste chainêé avec les éléments de lst ...

Par exemple:

>>> l = LinkedList([1,2,3])
>>> l.print()
[ 1 2 3 ]

>>> l = LinkedList([])
>>> l.print()
[ ]

5. Supprimer un élément

Ajoutez à la classe LinkedList (cf. l'annexe Appendix - Source code of linked lists ) une méthode remove() pour supprimer le noeud en tête de la liste. Si la liste chaînée était déjà vide, cette méthode ne fait rien.

l = LinkedList()
l.add(3)
l.add(2)
l.add(1)
l.print()
# [ 1 2 3 ]
l.remove()
l.print()
# [ 2 3 ]
l.remove()
print(l.length)
# 1
l.remove()
l.print()
# [ ]
l.remove()
l.print()
# [ ]

6. Ajouter un élément à la fin

Ajoutez à la classe LinkedList une méthode add_to_end(self, cargo) pour ajouter un noeud en queue de la liste. Ajoutez d'abord un nouvel attribut last dans la méthode d'initialisation pour garder une référence vers ce dernier élément. Changez ensuite la méthode add pour assigner cette référence lors de l'ajout du premier noeud, et la méthode remove pour remettre cette référence à None lorsque la liste est de nouveau vide. Implémentez ensuite la méthode add_to_end.

7. Supprimer un élément à la fin

Est-ce facile d'implémenter une méthode remove_from_end(self, cargo) pour supprimer un élément de la queue d'une LinkedList? Expliquez en mots comment vous feriez.

8. Imbriquer une classe dans une autre

En Python il est possible d'imbriquer une classe dans une autre. Ceci peut être utile si une classe n'est utilise que par une seule autre classe. C'est le cas ici avec la classe Node. Ce n'est qu'une classe auxiliaire pour la classe LinkedList. Adapter le code de votre classe LinkedList en imbriquant le code de la classe Node dedans. Il suffit d'indenter le code de la classe Node et de changer chaque référence à la classe Node à l'interieur de la classe LinkedList par self.Node.

Quels sont les avantages et désavantages d'imbriquer la classe Node dans la classe LinkedList?

9. Insérer un élément

Considérez qu'on désire utiliser la classe LinkedList pour stocker une liste de strings. On souhaite qu'elle soit en permanence en ordre alphabétique croissant.

Dessinez complètement une telle liste chainée contenant les trois strings "abc", "def" et "xyz".
```
 
 
 
 
 
 
 
 
```
Expliquez en français et dessinez les opérations à effectuer pour ajouter un Node contenant "aaa" dans cette liste.
```
 
 
 
 
 
 
 
 
```
Même question avec un Node contenant "ghi".
```
 
 
 
 
 
 
 
 
```
Même question avec un Node contenant "def".
```
 
 
 
 
 
 
 
 
```
Même question avec un Node contenant "zzz".
```
 
 
 
 
 
 
 
 
```

Comment feriez-vous pour écrire dans la classe LinkedList cf. l'annexe Appendix - Source code of linked lists ) la méthode insert dont la spécification est la suivante:

def insert(self,s):
"""
@pre  s est un string à insérer dans la liste chainée;
      self est une liste chaînée dont les noeuds contiennent des strings;
      les noeuds de la liste sont ordonnées en ordre croissant selon les valeurs (strings)
      qu'ils contiennent.
@post Un noeud contenant le String s a été inséré dans la liste de façon
      à ce qu'après l'insertion celle-ci soit toujours en ordre croissant.
"""

Pour rappel, en Python on peut facilement comparer un string avec un autre avec l'opérateur <. Vous pouvez aussi considérez que la classe Node se trouve maintenant à l'intérieur de la classe LinkedList et possède la méthode mutateur suivante:

class Node:

    def set_next(self,node):
        self.__next = node

10. Tests unitaires

Lors de la mission précédente, les tests unitaires avec unittest ont été introduits. Pour revisiter ce concept, consultez éventuellement un tutoriel online comme https://openclassrooms.com/fr/courses/235344-apprenez-a-programmer-en-python/2235416-les-tests-unitaires-avec-unittest

Créez un test unitaire pour tester la classe LinkedList. Ce test doit contenir des tests pour les différentes méthodes de la classe LinkedList comme size(), first() ou add(valeur) (code original), remove() (question 5), add_to_end(valeur) (question 6) ou insert(valeur) (question 9). Pour vous mettre sur le bon chemin, votre classe test aura la structure suivante:

import unittest

class LinkedListTest(unittest.TestCase):
    """Classe de test utilisé pour tester la classe LinkedList"""

    def test_size(self):
        """Test de la methode size() de la classe LinkedList."""
        # ... assert*(...) ...

    def test_first(self):
        """Test de la methode first() de la classe LinkedList."""
        # ... assert*(...) ...

    def test_add(self):
        """Test de la methode add(valeur) de la classe LinkedList."""
        # ... assert*(...) ...

    def test_remove(self):
        """Test de la methode remove() de la classe LinkedList."""
        # ... assert*(...) ...

    def test_add_to_end(self):
        """Test de la methode add_to_end(valeur) de la classe LinkedList."""
        # ... assert*(...) ...

    def test_insert(self):
        """Test de la methode insert(valeur) de la classe LinkedList."""
        # ... assert*(...) ...

if __name__ == '__main__':
    unittest.main()

Mission

Cette mission est un peu différente des autres missions. En effet, vous trouverez sur INGInious une grande partie du code nécessaire, sauf l'implémentation complète de la classe Classement que vous devez produire, ainsi que la classe OrderedLinkedList qu'elle doit utiliser. Comme source d'inspiration on vous donnera également une implémentation assez complète d'une classe LinkedList sur laquelle vous pouvez vous baser, ou que pouvez étendre, pour implémenter la classe OrderedLinkedList. Vous devez également écrire des classes de test détaillées (ClassementTest et OrderedLinkedListTest) en utilisant le framework de test unittest, pour vérifier votre implémentation de la classe Classement.

L'archive contient déjà une implémentation primitive de la classe Classement à base d'un dictionnaire. Néanmoins, cette implémentation est encore incomplète (elle ne gère pas correctement la position des coureurs dans le classement). Vous devez la remplacer par votre implémentation. Elle permet toutefois au programme de fonctionner. Il suffit d'exécuter la méthode de class main() de la classe Main: le programme simulera à la console l'ajout d'un nouveau résultat aléatoire toute seconde.

Etapes

Lors de la mission, vous allez implémenter un classement de résultats de coureurs, chaque résultat représenté par un coureur (ayant un certain nom et âge) et le temps effectué par ce coureur. Ces résultats doivent être ordonnés dans la liste selon leur temps. Le meilleur résultat (le coureur avec le meilleur temps) se trouve en tête de la liste. Le résultat du coureur le plus lent se trouve en queue de la liste.
Vous allez utiliser une liste chaînée ordonnée (OrderedLinkedList ) pour implémenter un tel classement de coureurs. Réfléchissez aux différentes opérations qu'on peut effectuer sur un classement et comment on devrait les implémenter en utilisant une liste chaînée ordonnée.
Avant de commencez à implémenter cette classe Classement, représentez la structure de votre classement comme liste chaînée ordonnée graphiquement, et montrez ce qu'il se passe lorsque, successivement:
- Vous créez un classement vide;
- Vous ajoutez un résultat pour le coureur A en tête de classement (méthode add);
- Vous ajoutez un résultat pour le coureur B en fin de classement (méthode add);
- Vous ajoutez un résultat pour le coureur C en milieu de classement (méthode add);
- Vous recherchez les résultats des coureurs A, B et C (méthode get);
- Vous recherchez les positions des coureurs A, B et C (méthode getPosition);
- Vous retirez le résultat du coureur B (méthode remove);
- Vous retirez le résultat du coureur A (méthode remove);
- Vous tentez de retirer le résultat d'un coureur D (méthode remove).
Implémentez la classe OrderedLinkedList dont vous aurez besoin pour implémenter votre classe Classement.
Implémentez une classe de test OrderedLinkedListTest pour tester le bon fonctionnement de votre classe OrderedLinkedList.

Sur base de notre implémentation incomplète de la classe Classement au moyen d'une dictionnaire, écrivez un squelette de votre classe Classement au moyen d'une liste chaînée ordonnée, qui remplacera la notre. Respectez bien les pré- et post-conditions des différentes méthodes de la classe :

class Classement :

    def __init__(self):
        """
        @pre: -
        @post: un classement vide de taille 0 a été créé
        """

    def size(self):
        """
        Méthode accesseur.
        Retourne la taille de ce classement.
        @pre:  -
        @post: Le nombre de résultats actuellement stockés dans ce classement a été retourné.
        """

    def add(self,r):
        """
        Ajoute un résultat r dans ce classement.
        @pre:  r est une instance de la classe Resultat
        @post: Le résultat r a été inséré selon l'ordre du classement.
               En cas d'ex-aequo, r est inséré après les autres résultats de même ordre.
        """

    def get(self,c):
        """
        Retourne le résultat d'un coureur donné.
        @pre c est un Coureur
        @post retourne le premier (meilleur) Resultat r du coureur c dans le
              classement. Retourne None si le coureur ne figure pas (encore)
              dans le classement.
        """

    def get_position(self,c):
        """
        Retourne la meilleure position d'un coureur dans ce classement.
        @pre c est un Coureur
        @post retourne un entier représentant la position du coureur c dans ce classement,
              à partir de 1 pour la tête de ce classement. Si le coureur figure plusieurs fois
              dans le classement, la première (meilleure) position est retournée.
              Retourne -1 si le coureur ne figure pas dans le classement.
        """

    def remove(self,c):
        """
        Retire un résultat du classement.
        @pre  c est un Coureur
        @post retire le premier (meilleur) résultat pour le coureur c du classement.
              c est comparé au sens de __eq__. Retourne c si un résultat a été retiré,
              of False si c n'est pas trouvé dans la liste.
        """

    def __str__(self):
        """
        Méthode magique
        Retourne une représentation string de cet objet.
        @pre:  -
        @post: Retourne une représentation de ce classement sous forme d'un string,
               avec une ligne par résultat.
        """

Ecrivez une classe de test ClassementTest, la plus complète possible permettant de vérifier le bon fonctionnement de votre implémentation de la classe Classement. Utilisez pour cela les méthodes comme assertEqual ou d'autres méthodes définies dans unittest.
Pensez à découper votre classe de test en plusieurs méthodes. Cela facilitera la visualisation des résultats des tests. Vous trouverez sur la tâche INGInious un exemple de classe de test CoureurTest pour la classe Coureur.
Justifiez vos tests dans le fichier README.TXT.
Remplacer votre classe Classement par celle qui vous est fourni et exécutez la méthode main() de la classe Main. Observez que vos classements sont correctement mis à jour. Félicitations!
N'oubliez pas de soumettre votre implémentation des classes OrderedLinkedList et Classement, vos classes de test OrderedLinkedListTest et ClassementTest et votre fichier README.TXT à votre tuteur.

Remise de votre solution

Pour cette mission, vous devez soumettre au serveur de soumissions de programmes du cours, vos classes OrderedLinkedList et Classement dans des fichier orderedlinkedlist.py et classement.py, vos classes test OrderedLinkedListTest et ClassementTest dans des fichiers orderedlinkedlisttest.py et classementtest.py, ainsi que votre fichier README.txt.