Données Liste Implémentation

Identification

Infoforall

14 - Implémenter une Liste 3/3


Si on résume les épisodes précédents :

  • Le type abstrait LISTE consiste en une séquence d'éléments ordonnés et en un ensemble de fonctions nommées interface permettant d'y lire et insérer des éléments.
  • On peut implémenter cette LISTE comme un simple tuple (tête, queue) mais les coûts en lecture et insertion sont linéaires dans le pire des cas.
  • On peut implémenter cette LISTE sous forme d'un tableau et dans ce cas, la lecture a un coût constant mais l'insertion reste à coût linéaire.

Nous allons voir aujourd'hui comment parvenir à créer une implémentation permettant d'insérer des éléments de manière efficace (constant dans certains cas), mais la lecture sera linéaire...

Aujourd'hui, nous allons encore devoir insérer et supprmier la tête puis agir sur n'importe quel élément, si possible.

Image tirée du film Alice de Tim Burton
Image tirée du film Alice de Tim Burton

Prérequis : nous allons utiliser la programmation objet. Rien de bien méchant, mais c'est mieux d'avoir vu ces notions du coup.

1 - Liste chaînée

Qu'est-ce qu'un tableau ?

Nous avons vu que le tableau était une implémentation possible du type LISTE. Une implémentation qui permet la lecture des éléments à coût constant.

L'idée derrière le tableau est de placer les éléments les uns derrière les autres "en mémoire" de façon à trouver facilement leurs localisations par un simple calcul lié à leur numéro d'index. On parle de zones contiguës.

Principe du tableau

Remarque : l'implémentation réelle en machine va dépendre du langage de programmation.

Si on veut insérer un nouvel élément en index 2, il va donc falloir d'abord déplacer le contenu de l'index 2 vers l'index 3 puis insérer le nouveau contenu dans l'index 2.

1 - On "déplace" l'ancien élément

Principe du tableau

2 - On insère le nouvel élément

Principe du tableau

Insérer un élément prend donc du temps car si on veut placer un nouvel élément en position 0 par exemple, il va falloir déplacer le contenu du 2 en 3, le contenu du 1 en 2, le contenu du 0 en 1 puis on pourra enfin placer notre nouvel élément sur l'index 0... C'est long car c'est linéaire....

Principe du tableau : insertion linéaire

L'avantage du tableau par contre, c'est qu'on trouve très rapidement le contenu associé à un index. Là, c'est à coût constant.

Liste chaînée

Une liste chaînée est une liste composée de cellules ou de mailles, comme une chaîne en métal.

Chaque maillon (ou cellule) est associé à au moins deux informations :

  1. Le contenu de la cellule
  2. L'adresse ou l'identifiant de la prochaine cellule

Et c'est tout.

Du coup, la représentation de la liste donnerait cette fois quelque chose comme ceci :

Principe de la liste chaînée

Ici, j'ai placé les maillons (ou cellules) les uns derrière les autres, mais rien ne nous y oblige.

Et si je veux insérer un nouvel élément ? Il suffit de rediriger la lecture vers le nouvel élément et de créer un lien entre notre nouvel élément et le suivant dans la liste. Exemple ci-dessous : je fais pointer B vers le nouvel élément.

Principe de la liste chaînée

Du coup, il n'y a toujours que 2 étapes pour insérer un nouvel élément, quelque soit la longueur de la liste. Nous devrions donc obtenir sur nos implémentations futures, un coût d'insertion constant.

Une grosse liste :

Principe de la liste chaînée

Le changement de tête ne nécessite que deux opérations avec une liste chaînée (alors qu'avec un tableau, il fallait déplacer toutes les cases avant de placer l'index 0) :

Principe de la liste chaînée

Le désavantage lors de l'implémentation (si on implémente juste cette idée basique) va être la lecture : pour lire le contenu de la 5e cellule, il faut passer par la lecture des précédentes : on commence par aller à la tête qui va nous dire où aller ensuite, ect...

Comme pour les autres types, nous verrons qu'il existe plusieurs manières d'implémenter réellement cette idée abstraite.

2 - Cellule en tant que Classe

Voyons comment réaliser ce type de structure de données. Nous allons travailler ici avec le type le plus simple de liste chaînée, qu'on nomme liste simplement chaînée.

Avant d'implémenter la Liste dans une Classe, il faut commencer par implémenter... la Cellule.

01° Créer une classe Cellule qui peut recevoir deux paramètres lors de l'appel du constructeur : un paramètre valeur et un paramètre suivant. Les deux valeurs transmises devront être stockées dans deux attributs nommés v et s.

...CORRECTION...

1 2 3 4
class Cellule : def __init__(self, valeur, suivant) : self.v = valeur self.s = suivant

02° Tester le constructeur de votre Classe Cellule avec quelques créations.

Par exemple :

>>> c1 = Cellule(5, None) >>> c2 = Cellule(15, c1) >>> c3 = Cellule(25, c2) >>> c4 = Cellule(35, c3)

03° Représenter sur feuille la structure séquentielle linéaire créée par les instructions précédentes.

...CORRECTION...

Liste chaînée 35 -> 25 -> 15 -> 5

04° Vérifions les contenus en partant de la Cellule de tête qui est donc ici contenue dans la variable c4.

Nous allons à chaque fois utiliser l'attribut s qui contient ... l'adresse de la cellule suivante. On peut donc y trouver des attributs s et v également !

>>> # voir le contenu de la tête >>> c4.v 35 >>> # voir le contenu suivant >>> c4.s.v 25 >>> # voir le contenu suivant >>> c4.s.s.v 15 >>> # voir le contenu suivant >>> c4.s.s.s.v 5

Notre Cellule possède encore un léger problème : on pourrait lui transmettre n'importe quoi sur le paramètre suivant, pas nécessairement quelque chose de comptatible avec l'attribut s qui doit contenir un objet Cellule ou None. On pourrait donc imposer en programmation défensive que ce paramètre soit bien l'instance d'une Cellule ou None. Ce sont en effet les deux possibilités.

1 2 3 4 5 6 7 8 9 10 11 12 13
class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : '''Méthode constructeur ou initialisateur :: param valeur(Elt) :: un élément compatible avec la liste :: param suivant(Cellule|None) :: la référence de la cellule suivante ''' assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant

05° Mettre cette version en mémoire.

Utiliser alors les instructions suivantes :

>>> a = Cellule('Marie-Antoinette', None) >>> b = Cellule('Louis XVI', a) >>> c = Cellule('Louis XV', 'Louis XVI') assert isinstance(suivant, Cellule) or suivant == None AssertionError

Expliquer ce qui provoque l'erreur : est-ce la documentation de la ligne 8 ? L'assertion de la ligne 11 ?

...CORRECTION...

La documentation n'a rien à voir dans cette histoire : il s'agit juste d'un texte qui permet d'informer l'utilisateur de votre Classe.

C'est bien l'utilisation du mot-clé assert qui permet de stopper le programme (en levant une exception) si l'expression située derrière n'est pas évaluée à True.

Attention : s n'est pas la queue mais un élément de la queue. Ce qu'on nomme queue est bien l'ensemble des valeurs derrière la tête, pas juste la première.

Bien. Nous sommes capables de créer des Cellules et les lier entre elles. Mais comment lire cette séquence de Cellules ?

Pour faire cela, nous allons créer une fonction renvoyerCelluleFinale récursive qui aura la charge d'afficher progressivement les valeurs des cellules et de renvoyer au final la référence de la dernière Cellule de la séquence, celle qui ne possède pas d'attribut s.

Principe de la lecture de la liste chaînée

Si on part ici de la tête qui contient le string "Lundi", on devrait lire la séquence des jours et renvoyer la référence de la dernière cellule, celle qui contient "Dimanche".

06° Travaillons maintenant sur la fonction renvoyerCelluleFinale.

Voici le prototype (pour information):

1
def renvoyerCelluleFinale(cellule:Cellule) -> Cellule :

C'est une méthode récursive. Le principe est le suivant :

  • Si l'attribut s de cette cellule est vide : renvoyer cellule (la Cellule en cours d'étude) En effet, s'il n'y a pas de suite, c'est bien que cellule est la dernière.
  • Sinon : renvoyer renvoyerCelluleFinale(cellule.s)

Questions

  1. Quelle est la condition d'arrêt ?
  2. Quel est le cas de base ?
  3. Comment parvient-on à avancer dans les Cellules ? Que fait l'appel récursif ?

...CORRECTION...

La condition d'arrêt correspond au fait que la Cellule en cours n'ai pas de successeur : son attribut s, comme suivant, contient None.

Le cas de base revient alors à fournir l'adresse de cette dernière Cellule.

On parvient à avancer car on appelle à nouveau renvoyerCelluleFinale mais en fournissant en argument la référence de la Cellule suivante.

07° Compléter la fonction renvoyerCelluleFinale.

Vous rajouterez un print en début de fonction pour afficher le contenu de la Cellule. Nous supprimerons cette fonctionnalité ensuite. Mais c'est pratique pour voir si la fonction fonctionne bien.

Voici le prototype :

1
def renvoyerCelluleFinale(cellule:Cellule) -> Cellule :

Pour vérifier si votre fonction fonctionne, rajoutez ce jeu de test à la fin de votre programme. J'utilise ici juste une suite d'instructions qui ne vont s'activer que lors de l'activation directe de notre programme plutôt que le module doctest.

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
# Déclaration des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant=None) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant # Déclaration des fonctions def renvoyerCelluleFinale(Cellule) : print(cellule.v) # Programme principal if __name__ == '__main__' : di = Cellule("Dimanche") sa = Cellule("Samedi", di) ve = Cellule("Vendredi", sa) je = Cellule("Jeudi", ve) me = Cellule("Mercredi", je) ma = Cellule("Mardi", me) lu = Cellule("Lundi", ma) assert renvoyerCelluleFinale(lu) == di

...CORRECTION...

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
# Déclaration des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant=None) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant # Déclaration des fonctions def renvoyerCelluleFinale(Cellule) : print(cellule.v) if cellule.s == None : return Cellule else : return renvoyerCelluleFinale(cellule.s) # Programme principal if __name__ == '__main__' : di = Cellule("Dimanche") sa = Cellule("Samedi", di) ve = Cellule("Vendredi", sa) je = Cellule("Jeudi", ve) me = Cellule("Mercredi", je) ma = Cellule("Mardi", me) lu = Cellule("Lundi", ma) assert renvoyerCelluleFinale(lu) == di

Nous savons donc maintenant obtenir la dernière Cellule d'une séquence de Cellules.

derniere = renvoyerCelluleFinale(lu) derniere <__main__.Cellule object at 0x7fca115ec780> derniere.v 'Dimanche' derniere.s

Notre print n'était là que pour montrer qu'on lit les Cellules de façon séquentielle. Pour l'instant, on ne peut atteindre la fin qu'en passant par toutes les Cellules, une par une.

Par contre, c'est un peu dommage : nous avons créé une fonction, alors que nous avons créé les cellules sous forme d'objet. Autant intégrer directement cette fonctionnalité dans une méthode non ?

Voici le code intégrant la méthode renvoyerCelluleFinale.

1 2 3 4 5 6 7 8 9 10 11 12 13
class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant=None) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale()

On peut voir que l'écriture d'un appel récursif sur la méthode est un peu différente puisqu'on place finalement l'objet sur lequel on va agir devant la méthode plutôt qu'à l'intérieur des parenthèses :

Un rappel si vous avez du mal à voir comment fonctionne les appels récursifs via la méthode : lorsqu'on lance la première ligne ci-dessous, c'est un peu comme si l'interpréteur Python réalisait la seconde.

return self.s.renvoyerCelluleFinale() return Cellule.renvoyerCelluleFinale(self.s)

Nous savons maintenant créer des Cellules valides. Néanmoins, nous sommes toujours obligés de savoir où commence la liste. Il est temps de créer une classe Liste qui aura comme seul attribut au départ l'adresse de la tête.

3 - Liste chaînée en tant que Classe

08° Compléter la classe Liste. Elle doit posséder un seul attribut qu'on nommera tete. Nommer également le paramètre de la méthode d'initialisation tete.

On veuillera avec une assertion à ce que tete soit bien une instance de Cellule ou None. Vous lui donnerez d'ailleurs une valeur par défaut None.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# Déclaration des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant=None) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe permettant de créer une liste chaînée'''

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete

Remarque 1 : Je ne placerai plus les documentation lors des questions intermédiaires. Elles sont par contre dans les versions finalisées. Cela rendra le code moins long, et comme vous êtes en plein dedans, la documentation peut parfois faire too much.

Remarque 2 : La correction de la question précédente utilise type plutôt que isinstance pour vérifier que l'objet reçu est bien une instance. C'est juste pour vous montrer qu'on peut tester cela de deux façons.

09° Pour créer une liste, il faut pour l'instant créer les cellules manuellement puis créer la liste. Voici un programme qui vous permettra de créer une petite liste sans avoir à tout taper à chaque fois.

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
# Déclarations des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete # Déclaration des fonctions # Programme principal if __name__ == "__main__" : a = Cellule('Marie-Antoinette', None) b = Cellule('Louis XVI', a) c = Cellule('Louis XV', b) lis1 = Liste(c)

Nous aurions pu simplement taper ceci dans le Shell de Python.

>>> a = Cellule('Marie-Antoinette', None) >>> b = Cellule('Louis XVI', a) >>> c = Cellule('Louis XV', b) >>> lis1 = Liste(c)

Questions

Une fois, la liste du programme en mémoire,

  1. Comment obtenir dans le Shell le contenu de la tête en utilisant l'objet lis1 ?
  2. Comment obtenir le contenu de l'élément suivant en utilisant l'objet lis1 ?
  3. Comment obtenir le contenu de l'élément encore derrière en utilisant l'objet lis1 ?

...CORRECTION...

>>> lis1.tete.v >>> lis1.tete <__main__.Cellule object at 0x7f03e9774a20> >>> lis1.tete.v 'Louis XV' >>> lis1.tete.s.v 'Louis XVI' >>> lis1.tete.s.s.v 'Marie-Antoinette'

Voyons maintenant comment réaliser l'interface. Nous allons chercher à réaliser l'interface permettant de gérer des listes de façon "souple", à savoir insérer et lire des éléments où on veut. Mais nous allons néanmoins réaliser les fonctions ne gérant que la tête au départ.

Comme nous sommes sur une implémentation objet, nous allons utiliser une version mutable de la liste. Le code obtenu sera plus facile à créer. Mais nous pourrions en réaliser une version non mutable si nécessaire.

Interface voulue : Liste "souple", version mutable
Principe de l'interface d'une liste plus souple
  1. nouvelleListe() -> Liste : on crée une nouvelle liste vide.
  2. listeA = nouvelleListe()
    Le contenu de listeA est alors une liste vide.

  3. estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.
  4. listeA = nouvelleListe()
    estVide(listeA) va donc renvoyer l'équivalent de True.

  5. insererPosition(x:Elt, lst:Liste, position:int) -> None : on modifie sur place la liste : l'élément fourni x est maintenant l'élément de la liste situé en position position. On prendra ici un système de position lié à un index commençant à 0.
  6. listeA peut être représentée par (12, 15, 18, 4)
    inserer(5, listeA, 2)
    listeA peut alors être représentée par (12, 15, 5, 18, 4).

  7. supprimerPosition(lst:Liste, position:int) -> None : on modifie sur place la liste : l'élément en position position est supprimé, rendant la liste moins longue.
  8. listeA peut être représentée par (12, 15, 18, 4)
    supprimer(listeA, 1)
    listeA peut alors être représentée par (12, 18, 4).

  9. lirePosition(lst:Liste, position:int) -> Elt : on renvoie l'élément stocké en position position.
  10. listeA peut être représentée par (12, 15, 18, 4)
    reponse = lirePosition(listeA, 1)
    reponse peut alors être représentée par 15.

10° Créer la fonction d'interface nouvelleListe. Votre fonction devra bien entendu travailler avec la classe Liste.. L'utilisateur pourra ainsi créer une nouvelle liste sans avoir à utiliser directement la fonction constructeur Liste.

nouvelleListe() -> Liste : on crée une nouvelle liste vide.

listeA = nouvelleListe()
Le contenu de listeA est alors une liste vide.

...CORRECTION...

Le code de la fonction :

1 2
def nouvelleListe() : return Liste()

Le code dans sa totalité :

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
# Déclarations des classes # Déclarations des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete # Déclaration des fonctions def nouvelleListe() : return Liste() # Programme principal

11° Créer la fonction d'interface estVide. Votre fonction devra bien entendu travailler avec la classe Liste. On ira lire directement son attribut tete, sans respect aucun pour l'encapsulation de l'objet.

La fonction peut contenir une seule ligne de code.

estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.

...CORRECTION...

1 2
def estVide(lst) : return lst.tete == None

12° Créer une fonction d'interface insererTete qui devra

  1. mémoriser dans une variable l'adresse de l'ancienne tête ,
  2. créer une instance de Cellule dont la valeur stockée est x et qui pointe en sortie vers l'ancienne tête
  3. modifier l'attribut tete de la Liste pour qu'il corresponde bien à notre nouvelle instance de Cellule.
  4. insererTete(x:Elt, lst:Liste) -> None : on modifie sur place la liste : l'élément fourni x est maintenant l'élément de tête.

    listeA peut être représentée par (12, 15, 18, 4)
    insererTete(5, listeA)
    listeA peut alors être représentée par (5, 12, 15, 18, 4).

    Un exemple d'utilisation qui devrait fonctionner sur votre fonction :

    >>> lst1 = nouvelleListe() >>> insererTete(5, lst1) >>> lst1.tete.v 5 >>> lst1.tete.s

    On voit donc ici qu'on ne dispose que d'une tête : l'élément suivant ne contient rien.

...CORRECTION...

Deux versions pour le prix d'une. Dans la première, on exécute l'une des étapes sur chaque ligne. La deuxième est plus courte, on fait tout progressivement aussi mais sur une seule ligne. En terme de clarté, c'est à vous de voir.

1 2 3 4 5 6 7
def insererTete(x, lst) : ancienne_tete = lst.tete # On récupère l'adresse de la Cellule nouvelle = Cellule(x, ancienne_tete) lst.tete = nouvelle def insererTete(x, lst) : lst.tete = Cellule(x, lst.tete)

Pour réaliser la vraie fonction insererPosition, il va falloir bien réflechir.

Imaginons qu'on veuille insérer une Cellule en position 2.

Il faudra :

  • Mémoriser l'adresse nommée predecesseur de l'élément en position 1 (celle de contenu B ici)
  • Mémoriser l'adresse nommée successeur de l'élément en position 2 actuellement (celle de contenu C ici).
  • Créer une nouvelle cellule nouvelle (celle de contenu Z ici) et la faire pointer vers successeur.
  • Faire pointer predecesseur sur notre nouvelle cellule.

Avant d'inserer la nouvelle Cellule en position2, il faut mémoriser les identifiants des cellules contenant B (predecesseur, "index" 1) et C (successeur, "index" 2).

Principe de la liste chaînée

Après modification,

Principe de la liste chaînée

Quelques exemples :

  • Si je veux insérer en position 1 : predecesseur est l'élément en position 0, soit ... la tête de la liste.
  • Si je veux insérer en position 2 : predecesseur sera l'élément en position 1. Il faut donc faire un bond en avant depuis la tête.
  • Si je veux insérer en position 3 : predecesseur sera l'élément en position 2. Il faut donc faire un bond en avant depuis la tête.
  • Si je veux insérer en position position : predecesseur sera la Cellule en position position - 1. Il faut donc faire un bond en avant depuis la tête.

Nous allons voir que le problème de la fonction d'interface telle qu'elle est définie ici ne vient pas de l'insertion mais de la recherche de la bonne Cellule !

13° Voici une fonction d'interface insererPosition.

insererPosition(x:Elt, lst:Liste, position:int) -> None : on modifie sur place la liste : l'élément fourni x est maintenant l'élément de la liste situé en position position. On prendra ici un système de position lié à un index commençant à 0.

listeA peut être représentée par (12, 15, 18, 4)
inserer(5, listeA, 2)
listeA peut alors être représentée par (12, 15, 5, 18, 4).

Lorsqu'on veut insérer ailleurs qu'à la tête, cette fonction va

  1. partir de la tête, effectuer position -1 saut vers la cellule suivante, et mémoriser l'identifiant de cette cellule dans predecesseur
  2. mémoriser dans successeur la réference de la cellule actuellement à la suite de predecesseur.
  3. créer la nouvelle Cellule, et la faire pointer vers successeur
  4. modifier predecesseur pour qu'elle pointe vers nouvelle.
Principe de la liste chaînée

Question : analyser le code pour parvenir à identifier les lignes où sont effectuées précisement les actions 1 à 4 précédentes.

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
# Déclarations des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete # Déclaration des fonctions def nouvelleListe() : return Liste() def estVide(lst) : return lst.tete == None def insererTete(x, lst) : ancienne_tete = lst.tete # On récupère l'adresse de la Cellule nouvelle = Cellule(x, ancienne_tete) lst.tete = nouvelle def insererPosition(x, lst, position) : if position == 0 : # On retrouve la fonction insererTete en réalité successeur = lst.tete nouvelle = Cellule(x, successeur) lst.tete = nouvelle elif position > 0 : predecesseur = lst.tete for etape in range(position-1) : # On avance encore de (position-1) coups pour trouver predecesseur predecesseur = predecesseur.s successeur = predecesseur.s # on mémorise la cellule qu'il faudra "déplacer" nouvelle = Cellule(x, successeur) predecesseur.s = nouvelle

...CORRECTION...

  1. Lignes 46-47-48 : tenter de partir de la tête pour aboutir à la Cellule en position (position -1) et la mémoriser dans predecesseur
  2. Ligne 50 : on mémorise ensuite la réference de la cellule successeur en utilisant justement l'attribut s. On obtient donc None ou une vraie Cellule.
  3. Ligne 51 : Ensuite, on va créer la nouvelle Cellule et la faire pointer vers successeur et
  4. Ligne 52 : modifier la Cellule predecesseur pour qu'elle pointe vers nouvelle.
Plus court ?

Encore une fois, on peut réaliser un code plus court. Mais est-il plus compréhensible ? Ca dépend à quel point vous êtes à l'aise.

1 2 3 4 5 6 7 8 9 10 11
def insererPosition(x, lst, position) : if position == 0 : # On retrouve la fonction insererTete en réalité lst.tete = Cellule(x, lst.tete) elif position > 0 : predecesseur = lst.tete for etape in range(position-1) : # On avance encore de (position-1) coups pour trouver predecesseur predecesseur = predecesseur.s predecesseur.s = Cellule(x, predecesseur.s)

14° L'insertion pure ne concerne que les lignes suivantes

50 51 52
successeur = predecesseur.s # on mémorise la cellule qu'il faudra "déplacer" nouvelle = Cellule(x, successeur) predecesseur.s = nouvelle

Ici le coût est bien constant. Par contre, que peut-on dire du coût de la recherche de la Cellule predecesseur dans le pire des cas ?

46 47 48
predecesseur = lst.tete for etape in range(position-1) : # On avance encore de (position-1) coups pour trouver predecesseur predecesseur = predecesseur.s

Au total, que peut-on alors dire du coût de l'insertion ?

...CORRECTION...

Comme on doit lire les cellules une par une avant de pouvoir insérer, on retrouve sur la fonction en elle-même un coût linéaire dans le pire des cas !

C'est un peu décevant du coup...

En réalité, si l'utilisateur peut manipuler directement l'insertion en fournissant par exemple la référence de la Cellule predecesseur, on pourrait retrouver un coût constant.

C'est ce que vont certaines implémentations.

15° Compléter la fonction d'interface insererApres.

Prototype :

insererApres(x:Elt, lst:Liste, predecesseur:Cellule) -> Cellule : on modifie sur place la liste : l'élément x fourni est inséré dans une Celule qui est placée juste après la Cellule predecesseur. On renvoie la référence de la cellule qu'on vient de créer. Cela permettra de stocker la référence si elle est importante

Le paramètre predecesseur aura None comme valeur par défaut de façon à ne pas fournir de cellule si on sait que la liste est encore vide. Dans ce cas, la fonction est équivalente à insererTete.

Exemple

>>> lst1 = nouvelleListe() >>> a = insererApres('Alice', lst1)

La liste abstraite correspondante serait maintenant ('Alice')

>>> b = insererApres('Bob', lst1, a)

La liste abstraite correspondante serait maintenant ('Alice', 'Bob')

>>> c = insererApres('Clark', lst1, a)

La liste abstraite correspondante serait maintenant ('Alice', 'Clark', 'Bob')

1 2 3 4 5 6 7 8 9 10 11 12 13
def insererApres(x, lst, predecesseur=None) : '''On insére la nouvelle juste juste derrière la Cellule predecesseur, on renvoie la nouvelle Cellule''' if predecesseur == None : # on insère une nouvelle tête devant la tête actuelle successeur = lst.tete nouvelle = Cellule(x, successeur) lst.tete = nouvelle else : # Cette fois, on peut insérer pass lst1 = nouvelleListe() a = insererApres('Alice', lst1) b = insererApres('Bob', lst1, a) c = insererApres('Clark', lst1, a)

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def insererApres(x, lst, predecesseur=None) : '''On insére la nouvelle juste juste derrière la Cellule predecesseur, on renvoie la nouvelle Cellule''' if predecesseur == None : # On retrouve la fonction insererTete en réalité successeur = lst.tete nouvelle = Cellule(x, successeur) lst.tete = nouvelle else : # Cette fois, on peut insérer successeur = predecesseur.s nouvelle = Cellule(x, successeur) predecesseur.s = nouvelle return nouvelle lst1 = nouvelleListe() a = insererApres('Alice', lst1) b = insererApres('Bob', lst1, a) c = insererApres('Clark', lst1, a)

Comme vous pouvez le voir, une fois qu'on dispose des références, on retrouve une insertion à coût constant : il y a simplement 3 instructions lignes 8-9-10 dans la correction.

En réalité, la grande force des listes ne vient pas de l'insertion d'une Cellule individuelle (souvent on ne connait pas sa référence) mais de l'insertion d'une liste à la suite d'une autre liste. On parlera de concaténation de listes, comme avec les strings.

Imaginons qu'on dispose des deux listes. L'une de 20 000 éléments et l'autre de 20 000 éléments également. Si on désire insérer la deuxième liste après la première liste, cela risque d'être compliqué avec des tableaux :

D'abord, il faut réserver une nouvelle place mémoire de 40 000 places :

Création d'un nouveau tableau

Ensuite, il faut déplacer un par un les 20 000 éléments du premier tableau.

Déplacement des éléments de A

Puis on déplace les 20 000 éléments du deuxième tableau.

Déplacement des éléments de B

16° Sur le cas ci-dessus, en quoi l'implémentation sous forme de liste chaînée va permettre de réalisrer plus rapidement la jonction de nos deux listes précédentes ?

...CORRECTION...

On part ici de deux listes chaînées ayant chacune leur propre tête.

Il suffit alors de connaître la dernière Cellule de la première liste (au pire, 20 000 lectures, c'est toujours mieux que 40 000 déplacements avec les tableaux !) et de la faire pointer vers la tête de la deuxième ligne.

Changement de référence

Si on connait l'adresse de la Cellule de fin, on a même simplement UNE opération à faire : réorienter la Cellule de fin vers l'ancienne deuxième tête !

Aucun déplacement mémoire. Uniquement un changement de référence sur 1 Cellule...

On pourra donc écrire des choses comme cela : lst1 + lst2. Cela veut juste dire de faire pointer la Cellule de fin de la première liste vers la tête de la deuxième liste.

On peut faire l'inverse, lst2 + lst1 : on fait pointer la Cellule de fin de la liste 2 vers la tête de la liste 1.

Changement de référence

Or, pour obtenir cet avantage majeur sur les tableaux, il nous faut la référence de la tête et de la dernière Cellule. Sinon, il faut lire la première liste séquentiellement jusqu'au bout... C'est long.

Il est donc temps de modifier notre classe Liste : nous allons lui rajouter un nouvel attribut fin qui va contenir la référence de la Cellule finale, celle qui ne mène nulle part et dont l'attribut s contient None.

Comme faire cela ? En utilisant la méthode renvoyerCelluleFinale de la classe Cellule. Que lui envoyer comme instance de Cellule ? La tête de la liste, c'est la seule dont on connaisse la référence.

Attention, s'agissant d'une méthode, on utilise la syntaxe avec le point.

1 2 3 4 5 6 7 8
class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete self.derniere = None if self.tete != None : self.derniere = self.tete.renvoyerCelluleFinale()

Cela veut bien dire : "va chercher l'espace mémoire de la tête et applique la méthode renvoyerCelluleFinale que tu vas y trouver".

Par contre, cela veut dire qu'il falloir mettre la jour cet attribut derniere lorsqu'on insère un élément qui ne possède pas de successeur : c'est lui désormais la nouvelle fin.

Voici le code que nous allons maintenant compléter. On remarque qu'il possède des instructions de mise à jour de cet attribut dans tous les cas où il est possible que la dernière cellule ai changé.

La fin de ce tp va consister à créer les fonctions d'interface manquantes.

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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
# Déclarations des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete self.derniere = None if tete != None : self.derniere = self.tete.renvoyerCelluleFinale() # Déclaration des fonctions def nouvelleListe() : return Liste() def estVide(lst) : return lst.tete == None def insererTete(x, lst) : insererPosition(x, lst, 0) def insererPosition(x, lst, position) : if position == 0 : # On retrouve la fonction insererTete en réalité successeur = lst.tete nouvelle = Cellule(x, successeur) lst.tete = nouvelle elif position > 0 : predecesseur = lst.tete for etape in range(position-1) : # On avance encore de (position-1) coups pour trouver predecesseur predecesseur = predecesseur.s successeur = predecesseur.s # on mémorise la cellule qu'il faudra "déplacer" nouvelle = Cellule(x, successeur) predecesseur.s = nouvelle if nouvelle.s == None : lst.derniere = nouvelle def insererApres(x, lst, predecesseur=None) : '''On insére la nouvelle juste juste derrière la Cellule predecesseur, on renvoie la nouvelle Cellule''' if predecesseur == None : # On retrouve la fonction insererTete en réalité insererPosition(x, position, 0) else : # Cette fois, on peut insérer successeur = predecesseur.s nouvelle = Cellule(x, successeur) predecesseur.s = nouvelle if nouvelle.s == None : lst.derniere = nouvelle return nouvelle def insererFin(x, lst) : pass def lireTete(lst) : pass def lireFin(lst) : pass def lirePosition(lst, position) : pass def supprimerTete(lst) : pass def supprimerFin(lst): pass def supprimerPosition(lst, position) : pass def concatener(gauche, droite) : pass def afficherListe(lst) : tableau = recupererValeur(lst.tete) return str(tuple(tableau)) def recupererValeur(cellule) : if cellule.s == None : return [cellule.v] else : return [cellule.v] + recupererValeur(cellule.s) # Programme principal if __name__ == "__main__" : lst1 = nouvelleListe() insererTete('Lundi', lst1)

17° Compléter la fonction insererFin qui consiste à insérer la nouvelle valeur dans une nouvelle cellule qui sera placée derrière la fin actuelle.

Prototype :

insererFin(x:Elt, lst:Liste) -> None : on modifie sur place la liste : l'élément x fourni est inséré dans une Celule qui est placée juste après la Cellule predecesseur. On ne renvoie rien. C'est inutile puisque la référence sera automatiquement stockée dans l'attribut derniere.

Vous pourrez vous inspirer de la fonction insererTete qui ne fait qu'un appel à insererPosition. Votre fonction pourrait ainsi n'être constituée que d'un appel à insererApres puisqu'on connaît bien la référence de la dernière cellule, stockée dans l'objet lui-même.

Question : quel est le coût de l'insertion en fin de liste ? Constant ? Linéaire ?

...CORRECTION...

1 2
def insererFin(x, lst) : insererApres(x, lst, lst.derniere)

Le coût est donc constant car il s'agit du coût de la fonction insererApres.

Maintenant que notre implémentation commence à ressembler à quelque chose, nous voudrions peut-être obtenir le contenu de notre liste pour pouvoir le représenter.

Pour cela, nous allons utiliser les deux fonctions situées à la fin.

18° Modifier le programme principal en utilisant cette création de liste.

Question : en utilisant l'interface, l'utilisateur peut-il se douter que les données sont stockées sous forme d'une liste chaînée composée d'objets ?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def afficherListe(lst) : tableau = recupererValeur(lst.tete) return str(tuple(tableau)) def recupererValeur(cellule) : if cellule.s == None : return [cellule.v] else : return [cellule.v] + recupererValeur(cellule.s) # Programme principal if __name__ == "__main__" : lst1 = nouvelleListe() insererTete('Lundi', lst1) insererFin('Mardi', lst1) insererFin('Mercredi', lst1)
>>> afficherListe(lst1) "('Lundi', 'Mardi', 'Mercredi')"

...CORRECTION...

Et non. Toujours pas. L'utilisateur pourrait encore croire (comme avec l'implémentation tuple puis tableau) que nous avons stocké les données dans un string représentant un tuple...

19° Quatre sous-questions.

19.1 Quelle est la condition d'arrêt de la fonction récursive recupererValeur ?

19.2 Quel est son cas de base ?

19.3 Compléter ensuite sur feuille les réponses successives des appels récursifs à partir de l'appel de départ recupererValeur(lst1.tete) en travaillant à partir de cet empilement des appels :

Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + recupererValeur(lst1.tete.s) Appel à recupererValeur(lst1.tete.s) renvoie ... Appel ...

19.4 Finalement, effectuer le dépilement et fournir la réponse que va renvoyer l'appel à cette fonction en fournissant la tête de la liste en argument.

...CORRECTION...

La condition d'arrêt est le fait que l'attribut s de la Cellule contienne None : cela veut dire que cette Cellule est la dernière de la liste chaînée.

Le cas de base consiste alors à renvoyer la valeur de la Cellule sous forme d'un tableau d'une seule case.

Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + recupererValeur(lst1.tete.s) Appel à recupererValeur(lst1.tete.s) renvoie ['Mardi'] + recupererValeur(lst1.tete.s.s) Appel à recupererValeur(lst1.tete.s.s) renvoie ['Mercredi']

Effectuons le dépilement :

Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + recupererValeur(lst1.tete.s) Appel à recupererValeur(lst1.tete.s) renvoie ['Mardi'] + ['Mercredi']

On renvoie donc la concaténation des deux tableaux.

Etape suivante :

Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + ['Mardi', 'Mercredi']

Nous allons donc renvoyer ['Lundi', 'Mardi', 'Mercredi']

20° Réaliser maintenant les trois fonctions d'interface de lecture des valeurs. On travaillera à partir des trois prototypes ci-dessous.

  1. lireTete(lst:Liste) -> Elt : on renvoie l'élément stocké tête.
  2. lireFin(lst:Liste) -> Elt : on renvoie l'élément stocké à la fin de la liste.
  3. lirePosition(lst:Liste, position:int) -> Elt : on renvoie l'élément stocké en position position.
  4. listeA peut être représentée par (12, 15, 18, 4)
    reponse1 = lireTete(listeA)
    reponse2 = lirePosition(listeA, 1)
    reponse3 = lireFin(listeA)
    reponse1 doit alors contenir 12, reponse2 doit alors contenir 15, reponse3 doit alors contenir 4.

Comment réaliser la lecture en fonction de la position ? En effectuant position sauts à partir de la tête. Nous pourrions le faire en récursif aussi au besion. Mais ici l'itération sera plus facile à insérer dans le code existant.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14
def lireTete(lst) : if not estVide(lst) : return lst.tete.v def lireFin(lst) : if not estVide(lst) : return lst.derniere.v def lirePosition(lst, position) : if not estVide(lst) : cellule = lst.tete for x in range(position) : cellule = cellule.s return cellule.v

21° Expliquer comment fonctionne cette version récursive de la fonction lirePosition.

1 2 3 4 5 6 7 8 9
def lirePosition(lst, position) : if not estVide(lst) : return lecture(position, lst.tete) def lecture(position, cellule) : if position == 0 : return cellule.v else : return lecture(position-1, cellule.s)

Pour cela, écrire sur feuille l'empilement des fonctions puis réaliser le dépilement. On travaillera sur l'appel suivant :

>>> lirePosition(lst1, 2)

On considère la liste suivante :

1 2 3 4
lst1 = nouvelleListe() insererTete('Lundi', lst1) insererFin('Mardi', lst1) insererFin('Mercredi', lst1)

...CORRECTION...

Appel à lirePosition(lst1, 2) renvoie lecture(2, lst1.tete) Appel à lecture(2, lst1.tete) renvoie lecture(1, lst1.tete.s) Appel à lecture(1, lst1.tete.s) renvoie lecture(0, lst1.tete.s.s) Appel à lecture(0, lst1.tete.s.s) renvoie "Mercredi"

Le dépilement est donc très simple et rapide :

Appel à lirePosition(lst1, 2) renvoie lecture(2, lst1.tete) Appel à lecture(2, lst1.tete) renvoie lecture(1, lst1.tete.s) Appel à lecture(1, lst1.tete.s) renvoie "Mercredi"
Appel à lirePosition(lst1, 2) renvoie lecture(2, lst1.tete) Appel à lecture(2, lst1.tete) renvoie "Mercredi"
Appel à lirePosition(lst1, 2) renvoie "Mercredi"

Passons à la concatenation de listes avec la réalisation de la fonction concatener qui doit modifier la dernière cellule de la liste gauche pour qu'elle pointe sur la tête de la liste droite.

22° Réaliser cette fonction dont voici le prototype :

concatener(gauche:Liste, droite:Liste) -> None : on doit réaliser l'opération suivante en modifiant la liste gauche.

Changement de référence

Vous pourrez tester avec ce programme de test :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# Programme principal if __name__ == "__main__" : lst1 = nouvelleListe() insererTete('Lundi', lst1) insererFin('Mardi', lst1) insererFin('Mercredi', lst1) lst2 = nouvelleListe() insererTete('Jeudi', lst2) insererFin('Vendredi', lst2) insererFin('Samedi', lst2) insererFin('Dimanche', lst2) print(afficherListe(lst1)) print(afficherListe(lst2)) concatener(lst1, lst2) print(afficherListe(lst1)) print(afficherListe(lst2))

Voici le contenu des listes avant la concaténation :

('Lundi', 'Mardi', 'Mercredi') ('Jeudi', 'Vendredi', 'Samedi', 'Dimanche')

Voici la liste de gauche après concaténation :

('Lundi', 'Mardi', 'Mercredi', 'Jeudi', 'Vendredi', 'Samedi', 'Dimanche')

La liste chaînée de droite n'a elle pas été modifiée :

('Jeudi', 'Vendredi', 'Samedi', 'Dimanche')

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12
def concatener(gauche, droite) : if not estVide(gauche) : fin_gauche = gauche.derniere if not estVide(droite) : fin_gauche.s = droite.tete # On fait pointer la dernière de G sur la première de D gauche.derniere = droite.derniere else : if not estVide(droite) : gauche.tete = droite.tete gauche.derniere = droite.derniere

4 - Partie optionnelle : Méthodes spéciales

Pour les plus rapides. Pas de connaissances obligatoires en NSI ici. Je vais faire un topo en classe une fois que tout le monde aura fini l'activité. Si vous êtes motivé, allez y. C'es très intéressant de savoir manipuler ainsi les objets. Cela vous permettra de comprendre pas mal de choses.

Et comment faire la concaténation directement avec un plus ? Pour cela, il faut utiliser une méthode spéciale des objets, qui se nomme __add__. Avec cette méthode, nous allons pouvoir dire à l'interpréteur Python ce qu'il doit faire lorsqu'il rencontre une instruction du type lst1 + lst2. De base, ça n'a pas de sens pour lui : cela reviendrait à additionner deux identifiants-mémoire.

Si vous regardez bien, vous pourrez voir que le code de la méthode __add_ est le code de la fonction concatener transformé pour s'adapter à la logique d'aller chercher une méthode ou un attribut à l'intérieur d'un objet.

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
class Liste : '''Classe implémenter une Liste sous forme Liste chaînée ''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete if tete != None : self.derniere = self.tete.renvoyerCelluleFinale() def __add__(self, droite) : gauche = self if not gauche.estVide() : fin_gauche = gauche.derniere if not droite.estVide() : fin_gauche.s = droite.tete # On fait pointer la dernière de G sur la première de D gauche.derniere = droite.derniere else : if not droite.estVide() : gauche.tete = droite.tete gauche.derniere = droite.derniere def estVide(self) : return self.tete == None

23° Sachant que Python transforme l'instruction de la ligne 1 en l'instruction de la ligne 2, expliquer ce que vont contenir les paramètres self et droite lors de l'appel de la méthode __add__ sur ce exemple.

1
lst1 + lst2
2
lst1.__add__(lst2)

...CORRECTION...

Il faut juste se persuader que la ligne 1 va provoquer l'appel de la méthode SPECIALE automatiquement. C'est justement une méthode spéciale. On ne l'appelle pas. C'est le système qui s'en charge lorsqu'un événement survient. Ici, c'est l'utilisation d'un + sur une instance de Liste.

1 2 3 4 5
lst1 + lst2 lst1.__add__(lst2) def __add__(self, droite) :

Il suffit alors de se rappeller que la dernière instruction veut dire que c'est l'objet lst1 qui lance l'appel à la méthode pour comprendre que :

  1. self contient lst1
  2. droite contient lst2

En réalité, on peut voir la dernière ligne comme équivalente à ceci :

1 2 3 4 5 6 7
lst1 + lst2 Equivalent à lst1.__add__(lst2) Equivalent à Liste.__add__(lst1, lst2) On compare à def __add__(self, droite) :

24° Placer cette nouvelle déclaration de la Classe (celle au dessus de la question 23) en mémoire ainsi que le code de test suivant.

1 2 3 4 5 6 7 8 9 10 11 12 13
# Programme principal if __name__ == "__main__" : lst1 = nouvelleListe() insererTete('Lundi', lst1) insererFin('Mardi', lst1) insererFin('Mercredi', lst1) lst2 = nouvelleListe() insererTete('Jeudi', lst2) insererFin('Vendredi', lst2) insererFin('Samedi', lst2) insererFin('Dimanche', lst2)

Effectuer alors les instructions dans le Shell de Python pour voir le résultat.

>>> afficherListe(lst1) "('Lundi', 'Mardi', 'Mercredi')" >>> afficherListe(lst2) "('Jeudi', 'Vendredi', 'Samedi', 'Dimanche')" >>> lst1 + lst2 >>> afficherListe(lst1) "('Lundi', 'Mardi', 'Mercredi', 'Jeudi', 'Vendredi', 'Samedi', 'Dimanche')"

Comme vous le voyez, l'utilisation d'objets pour implémenter les structures de données permet de customiser les opérations. On peut faire la même chose avec les autres opérateurs que sont -, * ou même >, < ou le fameux ==.

On pourrait ainsi dire qu'une liste chaînée est plus "grande" qu'une autre si la somme de ses éléments donne une somme plus grande que celle de l'autre liste. Ou alors de dire que c'est celle qui a les plus de Cellules qui gagne...

Une dernière méthode spéciale pour la route ?

25° Rajouter cette méthode spéciale __str__ dans votre classe Liste.

Tenter ensuite de voir à quoi elle sert en utilisant les instructions proposées dans le Shell.

1 2 3 4 5 6 7 8
def __str__(self) : tableau = [] if not self.estVide() : cellule = self.tete while cellule != None : tableau.append(cellule.v) cellule = cellule.s return str(tuple(tableau))
>>> afficherListe(lst1) "('Lundi', 'Mardi', 'Mercredi')" >>> print(lst1) ('Lundi', 'Mardi', 'Mercredi')

...CORRECTION...

Cette méthode spéciale permet de redefinir ce que va afficher la fonction native print dans la console. Vous vous souvenez de la notion d'interface. C'est pareil pour le print : vous utilisez une fonction native qui n'est rien d'autres qu'une interface proposée par le concepteur de Python ou d'une classe de Python pour "visualiser" ce qu'on vous propose de visualiser.

25° Cette méthode a-t-elle ici été codé en utiilsant la récursivité ou en utilisant les instructions classiques impératives ?

...CORRECTION...

Contrairement à la fonction afficherListe, j'ai utilisé des instructions impératives avec une boucle while. On peut faire l'un ou l'autre.

26° Modifier cette fonction spéciale pour qu'elle affiche "ACCES INTERDIT" lorsqu'on demande d'afficher la liste avec un print.

>>> afficherListe(lst1) "('Lundi', 'Mardi', 'Mercredi')" >>> print(lst1) ACCES INTERDIT

...CORRECTION...

1 2
def __str__(self) : return "ACCES INTERDIT"

27° Mettre en mémoire le code suivant qui implémente une liste chaînée avec pointeur de lecture.

Application :

...CODE LISTE CHAINEE INTERFACE...

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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
# Déclarations des classes class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class Liste : '''Classe implémenter une Liste sous forme Liste chaînée simplement chaînée''' def __init__(self, tete=None) : assert type(tete) == Cellule or tete == None self.tete = tete self.derniere = None if tete != None : self.derniere = self.tete.renvoyerCelluleFinale() self.pointeur = tete def __add__(self, droite) : gauche = self if not gauche.estVide() : fin_gauche = gauche.derniere if not droite.estVide() : fin_gauche.s = droite.tete # On fait pointer la dernière de G sur la première de D gauche.derniere = droite.derniere else : if not droite.estVide() : gauche.tete = droite.tete gauche.derniere = droite.derniere def __str__(self) : tableau = [] if not self.estVide() : cellule = self.tete while cellule != None : tableau.append(cellule.v) cellule = cellule.s return str(tuple(tableau)) def estVide(self) : return self.tete == None # Déclaration des fonctions hors interface def lecture(position, cellule) : if position == 0 : return cellule.v else : return lecture(position-1, cellule.s) def recupererCellule(position, cellule) : if position == 0 : return cellule else : return recupererCellule(position-1, cellule.s) def recupererValeur(cellule) : if cellule.s == None : return [cellule.v] else : return [cellule.v] + recupererValeur(cellule.s) # Déclaration des fonctions def nouvelleListe() : return Liste() def estVide(lst) : return lst.tete == None def insererTete(x, lst) : insererPosition(x, lst, 0) def insererPosition(x, lst, position) : if position == 0 : # On retrouve la fonction insererTete en réalité succcesseur = lst.tete nouvelle = Cellule(x, succcesseur) lst.tete = nouvelle if lst.pointeur == None : lst.pointeur = lst.tete elif position > 0 : predecesseur = lst.tete for etape in range(position-1) : # On avance encore de (position-1) coups pour trouver predecesseur predecesseur = predecesseur.s succcesseur = predecesseur.s # on mémorise la cellule qu'il faudra "déplacer" nouvelle = Cellule(x, succcesseur) predecesseur.s = nouvelle if nouvelle.s == None : lst.derniere = nouvelle def insererApres(x, lst, predecesseur=None) : '''On insére la nouvelle juste juste derrière la Cellule predecesseur, on renvoie la nouvelle Cellule''' if predecesseur == None : # On retrouve la fonction insererTete en réalité insererPosition(x, position, 0) else : # Cette fois, on peut insérer succcesseur = predecesseur.s nouvelle = Cellule(x, succcesseur) predecesseur.s = nouvelle if nouvelle.s == None : lst.derniere = nouvelle return nouvelle def insererFin(x, lst) : insererApres(x, lst, lst.derniere) def lireTete(lst) : if not estVide(lst) : return lst.tete.v def lireFin(lst) : if not estVide(lst) : return lst.derniere.v def lirePosition(lst, position) : if not estVide(lst) : return lecture(position, lst.tete) def supprimerTete(lst) : if not estVide(lst) : if lst.pointeur == lst.tete : lst.pointeur = None lst.tete = lst.tete.s def supprimerFin(lst): if not estVide(lst) : if lst.pointeur == lst.derniere : lst.pointeur = lst.tete if lst.tete == lst.derniere : lst.tete = None lst.pointeur = None else : cellule = lst.tete while cellule.s != lst.derniere : cellule = cellule.s cellule.s = None lst.derniere = Cellule def supprimerPosition(lst, position) : if position == 0 : supprimerTete(lst) elif position > 0 : predecesseur = recupererCellule(position-1, lst.tete) if predecesseur.s.s != None : predecesseur.s = predecesseur.s.s lst.pointeur = predecesseur.s else : supprimerFin(lst) def concatener(gauche, droite) : if not estVide(gauche) : fin_gauche = gauche.derniere if not estVide(droite) : fin_gauche.s = droite.tete # On fait pointer la dernière de G sur la première de D gauche.derniere = droite.derniere else : if not estVide(droite) : gauche.tete = droite.tete gauche.derniere = droite.derniere def afficherListe(lst) : tableau = recupererValeur(lst.tete) return str(tuple(tableau)) def lire(lst) : if not estVide(lst) : return lst.pointeur.v def avancer(lst) : if not estVide(lst) and lst.pointeur.s != None : lst.pointeur = lst.pointeur.s def localiser(lst) : if not estVide(lst) : return lst.pointeur def initialiser(lst) : lst.pointeur = lst.tete # Programme principal if __name__ == "__main__" : lst1 = nouvelleListe() insererTete('Lundi', lst1) insererFin('Mardi', lst1) insererFin('Mercredi', lst1) insererFin('Jeudi', lst1) insererFin('Vendredi', lst1) insererFin('Samedi', lst1) insererFin('Dimanche', lst1)

En conclusion, le type abstrait LISTE peut s'implémenter de plusieurs façons différentes.

Les deux grandes implémentations sont sous forme d'une structure de données tableaux (accès lecture à coût constant) et sous forme de listes chaînées (insertion parfois à coût constant et facilité de "déplacement" de grands blocs de données).

En fonction de besoin de votre algorithme, on prendra donc l'un ou l'autre.

Activité publiée le 14 10 2020
Dernière modification : 23 10 2020
Auteur : ows. h.