Table des matières

Mission 11 - Listes chainées

Phase de démarrage

Phase de réalisation

Questions complémentaires

Mission 11 : Les listes chaînées

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

1 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.

2 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.

3 Préparation, étude et apprentissage

Comment bien préparer la mission?

Assister au cours et regarder les capsules vidéos 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 :
- 7 - 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.

4 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.

4.1 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.

4.2 Questions ouvertes

4.2.1 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.

4.2.2 Utilisation d'une `LinkedList`

Question 1 : 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 2 : 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?

4.2.3 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()
[ ]

4.2.4 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.2.5 Initialiser une liste chaînée

4.2.6 Supprimer un élément

4.2.7 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.

Étapes de l'ajout d'un noeud dans une liste chainée :

Créer un nouveau nœud (new_node) composé de la valeur à ajouter dans la liste.
Parcourir la structure pour identifier le nœud précédant l’emplacement où insérer new_node.
Pour ne pas perdre la référence vers le nœud suivant, faire pointer new_node.next vers le nœud qui suit le nœud courant .
Insérer new_node (cas général, attention aux cas particuliers), en faisant pointer le nœud courant vers new_node.
Mettre à jour les attributs de la classe le cas échéant (taille, tête de liste, etc.).

Pour plus de détails sur les étapes, allez voir le catalogue : Ajout d'un noeud dans une liste chainée .

4.2.8 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.

4.2.9 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. Adaptez 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?

4.2.10 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".
```
 
 
 
 
 
 
 
 
```

4.2.11 Tests unitaires

Lors de la mission précédente, les tests unitaires avec unittest ont été introduits. 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 4.2.6), add_to_end(valeur) (question 4.2.7) ou insert(valeur) (question 4.2.10). 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

1 Description

Lors de cette dernière 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 selon leur temps dans une liste chaînée ordonnée. 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.

Pour compléter cette mission vous trouverez sur INGInious déjà 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. 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.

Vous aurez accès à 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. L'archive qu'on vous fournira contient également 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 classe main() de la classe Main dans le fichier main.py: le programme simulera à la console l'ajout d'un nouveau résultat aléatoire toute seconde.

2 Etapes

Avant de commencer lisez bien le code qui vous a été fourni afin que vous comprenez bien sa structure et son comportement.
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.

3 Diagramme de classes

Le diagramme de classes suivant résume les différentes classes et attributs qui feront partie de votre solution finale :

/syllabus/info1-exercises/assets/class_diagram_mission11.png

4 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.

Questions complémentaires

1 Méthode `str` de la classe LinkedList

Ajoutez également une méthode test correspondante à votre classe test pour vérifier le bon comportement de la méthode __str__.

2 Méthode `remove_from_end` de la classe LinkedList

Ajoutez également une méthode test correspondante à votre classe test pour vérifier le bon comportement de la méthode remove_from_end.

3 Méthode `contains` de la classe `LinkedList`

Ajoutez une méthode contains(e) dans la classe LinkedList qui retourne True si la valeur e se trouve dans la liste et False autrement.

Ajoutez également une méthode test correspondante à votre classe test pour vérifier le bon comportement de la méthode contains(e). N'oubliez pas de prendre en compte différents cas comme:

* la liste est vide;
* la liste contient un seul élément égal à l'élément cherché;
* la liste contient un seul élément différente de l'élément cherché;
* la liste contient différents fois un même élément;
* la liste contient différents fois l'élément cherché.

4 Lost Children

5 Classe LinkedList

6 Turing Machine

7 Liste doublement chaînée

Adaptez le code de la classe LinkedList pour créer une classe DoubleLinkedList représentant une liste doublement chaînée. Pour chaque noeud, en plus d'avoir un lien vers le noeud suivant, on ajoute un lien vers le noeud précédent. Ceci permet de parcourir la liste dans les deux sens: avancer en suivant la référence vers le noeud suivant, ou reculer en suivant la référence vers le noeud précédent. Votre classe DoubleLinkedList doit au moins fournir les méthodes suivantes:

add(e) pour ajouter un élément e en tête de la liste;
add_to_end(e) pour ajouter un élément e en fin de la liste;
remove_at_start() pour supprimer l'élément en tête de la liste;
contains(e) pour vérifier si l'élément e se trouve dans la liste;
size() retourne la taille de la liste;
isEmpty() vérifie si la liste est actuellement vide.

Ecrivez également une classe test unitaire TestDoubleLinkedList pour vérifier le bon comportement des différentes méthodes de la classe DoubleLinkedList. Cette classe test doit contenir des tests pour les différentes méthodes de la classe DoubleLinkedList.

8 Méthode `remove` de la classe DoubleLinkedList

Au code de la liste doublement chaînée de la question complémentaire précédente, ajoutez une méthode remove(e) pour supprimer la première occurrence de e de la liste doublement chainée.

Ajoutez également une méthode test correspondante à votre classe test pour vérifier le bon comportement de la méthode remove.