3.3.2. TD sur les implémentations de listes

Ce TD a pour but de réaliser plusieurs (au moins 2) implémentations de listes

Exercise 3.1

Implémenter une liste chainée sous la forme de fonctions opérant sur un objet de type list. En particulier, on devra voir les primitives suivantes :

• nil(liste_chainee: list) -> bool qui renvoie True si la liste est vide ;

• car(liste_chainee: list) qui renvoie le premier élément ;

• cdr(liste_chainee: list) qui renvoie [] si la liste ne comporte qu’un élément et la liste privée du premier élément sinon.

• cons(liste_chainee: list, valeur) qui ajoute un élément en tête de liste.

Exercise 3.2

Implémenter une liste chainée sous la forme de méthodes opérant sur un objet de classe ListeChainee. En particulier, on devra voir les primitives suivantes :

• nil() -> bool qui renvoie True si la liste est vide ;

• car() qui renvoie le premier élément ;

• cdr() qui renvoie [] si la liste ne comporte qu’un élément et la liste privée du premier élément sinon.

• cons(valeur) qui ajoute un élément en tête de liste.

Le squelette de la classe sera le suivant :

class ListeChainee:
    def __init__(self):
        ...
    def nil(self):
        ...
    def car(self):
        ...
    def cdr(self):
        ...
    def cons(self, valeur):
        ....

On se donne désormais une classe Maillon définie de la façon suivante :

class Maillon:
    def __init__(self, valeur=None, suivant=None):
        self.valeur = valeur
        self.suivant = suivant
    def __repr__(self):
        return f"Maillon({self.valeur}, {self.suivant})"

Exercise 3.3

1. Définir 3 Maillons contenant les valeurs 1, 2 et 3. L’attribut suivant des ces Maillons sera None

2. En affectant l’attribut suivant, créer une chaîne de Maillon.

3. Atticher la chaîne ainsi définie.

Exercise 3.4

Reprendre l’exercice Exercise 3.1 et mettre en œuvre les fonctions nil, car, cdr et cons en utilisant la classe Maillon.

Exercise 3.5

Reprendre l’exercice Exercise 3.2 avec une classe ListeMaillon.