Données Liste Implémentation

Identification

Infoforall

14 - Implémenter une Liste 3/3


Nous avons vu qu'on implémente correctement l'idée d'une Liste Récursive immuable en utilisant en interne la notion de tuple (valeur de tête, successeur). On peut alors facilement insérer et supprimer en TETE de liste.

Nous avons vu que le type list de Python implémente bien l'idée d'une Liste Itérative et muable en utilisant en interne la notion de tableau dynamique. On peut alors facilement insérer et supprimer en FIN de liste.

Nous allons tenter de créer une implémentation de Liste Récursive basée sur une liste chainée muable permettant d'agir de manière efficace en TETE ET FIN. Ca, c'est l'avantage, le désavantage va venir de l'aspect sécurité globale. Muable veut dire effet de bord.

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 il faut avoir vu ces notions.

Documents de cours : open document ou pdf

1 - Liste chaînée sous forme d'objets : la base

Dans cette partie, nous allons construire une nouvelle implémentation de la liste (tête, queue), mais cette fois elle sera muable.

Nous allons voir qu'en terme de performances, on ne gagne pas grand chose par rapport à la version tuple.

Nous en conclurons que pour obtenir ce qu'on veut, il va falloir mettre plus d'informations que la simple référence de la tête...

RAPPEL : Implémentation sous forme de cellules-tuples immuables

1 - Contenu d'une Cellule

Dans la cette implémentation, les Cellules sont des tuples (valeur, successeur).

Le successeur est alors une référence menant :

  • soit à un tuple vide () s'il s'agit de la Cellule de Fin.
  • soit à un autre tuple (valeur, successeur)

2 - Contenu d'une Liste

La Liste est alors simplement une référence menant :

  1. soit à un tuple vide () pour indiquer qu'il s'agit d'une liste vide.
  2. soit à la Cellule en tête de liste.

3 - Exemple

Principe de la liste chaînée
1 2 3 4
cc = (5, ()) cb = (15, cc) ca = (25, cb) lst = ca

Modifier la liste en notant par exemple lst = () ne modifierait pas la cellule a puisque nous avons une structure immuable. On crée de nouvelles versions des listes et des cellules à chaque fois qu'on réalise une modification de la variable correspondantes.

4- Performances

Coût constant sur toutes les opérations sur la Tête.

Sécurité et stabilité via l'immuabilité.

Coût linéaire (en 𝞗(i) et donc 𝞞(n)) dès qu'on veut agir sur l'élément en position i car il faut supprimer et stocker les têtes, agir puis réinsérer les têtes mémorisées.

1.1 - Implémentation cellules-objets muables : les Cellules

Dans cette implémentation, les Cellules sont des instances de la classe Cellule possédant deux attributs : v pour la valeur, et s pour le successeur.

L'attribut s est alors une référence menant :

  • soit à None s'il s'agit de la Cellule de Fin.
  • soit à une autre instance de Cellule
1 2 3 4
class Cellule: def __init__(self, valeur:'Element', successeur:'None|Cellule'): self.v = valeur self.s = successeur

Exemples d'instanciation :

1 2
ca = Cellule(5, None) # Cellule finale ca contenant 5 cb = Cellule(15, ca) # Cellule cb contenant 15 menant à la cellule ca

Voici deux représentations mentales qu'on peut se faire des instructions précédentes :

Principe de la liste chaînée

Pour les primitives successeur() et contenu(), on peut :

  • soit utiliser la manipulation directe de la Cellule : c.v et c.s
  • soit passer par des méthodes de Cellule : contenu() et successeur().
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
class Cellule: def __init__(self, valeur:'Element', successeur:'Cellule|None'): self.v = valeur # Valeur ne peut pas être None si liste homogène self.s = successeur # successeur vaut None si Cellule de Fin def contenu(self:'Cellule') -> 'Element': '''Renvoie le contenu de la Cellule''' return self.v def successeur(self:'Cellule NON FIN') -> 'Cellule': '''Renvoie la Cellule suivante de self NON FIN''' return self.s def aSuccesseur(self:'Cellule') -> bool: '''Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule''' return not self.s is None # ou même return self.s is not None def estFin(self:'Cellule') -> bool: '''Prédicat qui renvoie True si la Cellule n'a pas de successeur''' return self.s is None # ou même return not self.aSuccesseur()

Dans ce cours, nous utiliserons plutôt la méthode directe notamment car

  • ainsi, nous ne sommes pas contraint de respecter la précondition habituelle sur la primitive successeur() (à savoir qu'elle renvoie bien toujours une Cellule) et
  • que cette méthode ne contiendrait de toutes manières qu'une seule instruction.
Priorité des opérateurs
  1. Parenthèses (la plus haute priorité)
  2. Opérateurs arithmétiques

  3. Exposant, puissance
  4. Multiplication, division
  5. Addition, soustraction
  6. Opérateurs de comparaison

  7. Opérateur in
  8. Opérateurs is et is not
  9. Opérateurs d'ordre > <...
  10. Opérateur égalité et différence == !=
  11. Opérateurs logiques

  12. Opérateur not
  13. Opérateur and
  14. Opérateur or

Conséquences :

not self.s is None équivalent à not (self.s is None)

self.s is not None équivalent à self.s is not None

1.2 - Implémentation cellules-objets muables : la Liste

La Liste est une instance d'une classe Liste possédant un attribut tete faisant référence :

  1. soit à None pour indiquer qu'il s'agit d'une liste vide.
  2. soit à la Cellule en tête de liste.
6 7 8 9 10 11
class Liste: def __init__(self): self.tete = None def estListeVide(self:'Liste') -> bool: return self.tete is None

Exemples d'instanciation :

1 2 3
lst1 = Liste() # Liste vide lst1.tete = cc # lst est la liste 25 puis 15 puis 5 lst2 = Liste() # Liste vide

La liste n'est rien d'autre qu'une référence vers la première Cellule, la Cellule de Tête.

Principe de la liste chaînée
1.3 - Implémentation cellules-objets muables : un exemple

Nous utiliserons deux classes.

  1. La classe Cellule pour gérer l'enchaînement des Cellules et leurs valeurs stockées.
  2. La classe Liste pour savoir de quelle tête partir et former ainsi notre Liste Chaînée.
10 11 12 13 14
ca = Cellule(5, None) cb = Cellule(15, ca) cc = Cellule(25, cb) lst1 = Liste() lst1.tete = cc
Principe de la liste chaînée

On peut alors facilement accéder aux éléments stockés :

>>> lst.tete.v 25 >>> lst.tete.s.v 15 >>> lst.tete.s.s.v 5
1.4 - Méthode accesTete() et acces()

Intérêt ?

Avant de pouvoir agir sur une Cellule en position i, il faut d'abord pouvoir la localiser !

Les deux méthodes

1 2 3 4 5 6 7 8 9
class Liste: # ... def accesTete(self:'Liste NON VIDE') -> Cellule: '''Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE''' return self.tete def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule: '''Renvoie l'adresse de la cellule i dans la liste NON VIDE''' c = self.accesTete() # récupère la cellule de tête for _ in range(i): # Faire i fois c = c.s # passe au successeur return c

Puisqu'il faut renvoyer une instance de Cellule, il est nécessaire de pouvoir trouver une Cellule. Il y a donc deux PRECONDITIONS :

  1. La liste ne peut pas être vide car, dans ce cas, elle ne possède pas de Cellule.
  2. L'indice fourni doit correspondre à un indice possible dans notre liste, un indice où se trouve une Cellule.

Le coût de la méthode accesTete() est évidemment constant puisqu'on n'y fait que des lectures d'attributs.

cst
def accesTete(self:'Liste NON VIDE') -> Cellule: '''Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE''' return self.tete

Le coût de la méthode acces() est évidemment linéaire puisqu'on boucle i fois sur une action à coût constant. On a donc 𝞗(i) ou encore 𝞞(n).

cst lin cst cst
def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule: '''Renvoie l'adresse de la cellule i dans la liste NON VIDE''' c = self.accesTete() # récupère la cellule de tête for _ in range(i): # Faire i fois c = c.s # passe au successeur return c
1.5 - Méthode longueur()

1.5.1 - Intérêt ?

Fournir la taille de la liste pour connaître les valeurs possibles d'indice.

1.5.2 - Coût et principe

On peut le décrire soit en récursif, soit en itératif.

Dans les deux cas, il faudra parcourir la liste chaînée Cellule par Cellule en partant de la tête. Le coût est donc linéaire (en 𝞗(n)).

SI la liste est vide, on renvoie 0.

SINON, on localise la tête et on compte.

1.5.3 - Version itérative

  • On crée un compteur qui vaut 1 puisqu'on part de la tête qui existe.
  • Tant qu'un successeur existe, on augmente le compteur et on passe au successeur.
1 2 3 4 5 6 7 8 9 10 11
class Liste: # ... def longueur(self:'Liste') -> int: '''Renvoie la longueur de la liste''' if self.estListeVide(): return 0 else: c = self.tete nb = 1 while c.s is not None: nb = nb + 1 c = c.s return nb

1.5.4 - Version récursive

Si une cellule active n'a pas de successeur, c'est le cas de base : elle répond 1.

Les autres cellules répondront 1 + la réponse de leur successeur.

1 2 3 4 5 6
class Cellule: # ... def nbCellules(self:'Cellule') -> int: '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if self.s is None: # si il n'y a pas de successeur return 1 # il y a au moins la fin else: return 1 + self.s.nbCellules() # on demande au successeur...

Pour l'intégrer dans la Liste, on peut donc écrire ceci :

7 8 9 10 11 12
class Liste: # ... def longueur(self:'Liste') -> int: '''Renvoie la longueur de la liste''' if self.estListeVide(): return 0 else: return self.tete.nbCellules()

2 - Liste chaînée sous forme d'objets : l'insertion

Pour insérer, il faut connaître le prédécesseur de la cellule qu'on veut rajouter.

2.1 - Insérer une cellule en position de TETE dans notre liste chaînée

2.1.1 - Principe et coût de cette insertion

Cellule à localiser : la Tête actuelle.

Etape 1 : on crée la nouvelle Cellule cd (coût constant)

cd = Cellule(20, None)

Etape 2 : on définit le successeur de la Cellule cd comme étant l'attribut tete de la Liste qui est soit la référence d'une Cellule, soit None (coût constant : on lit ou modifie des attributs)

Principe de la liste chaînée

Etape 3 : on modifie la liste en modifiant l'adresse stockée comme Tête (coût constant)

Principe de la liste chaînée

Voici les instructions correspondantes :

(cst) Etape 1 (cst) Etape 2 (cst) Etape 3
nouvelle = Cellule(valeur_voulue, None) nouvelle.s = lst.tete lst.tete = nouvelle

Coût : cette insertion est donc à coût constant.

2.1.2 - Implémentation dans une méthode

1 2 3 4 5
class Liste: # ... def insererTete(self:'Liste', elt:'Element') -> None: '''Rajoute une nouvelle cellule contenant elt en tête de liste''' nouvelle = Cellule(elt, None) # Etape 1 : création de la cellule nouvelle.s = self.tete # Etape 2 : on relie la nouvelle cellule à l'"ancienne" tête self.tete = nouvelle # Etape 3 : modification de la liste

2.1.3 - Cas particulier de la liste vide

On notera que cela fonctionne même sur une liste vide : la tête pointe alors simplement sur None initialement.

Principe de la liste chaînée
2.2 - Insérer une cellule en position i dans notre liste chaînée

2.2.1 - Principe et coût de cette insertion en position i

Cellule à localiser : la Cellule d'indice i-1 (si elle existe) pour faire de son successeur la nouvelle Cellule en position i.

SI on reçoit un indice i de 0, on lance simplement un appel à insererTete().

SINON, il suffit de quatre opérations :

  • Etape 1 : Localiser le prédécesseur en i-1 de la Cellule i. On utilisera acces().
  • Exemple avec un 50 qu'on voudrait insérer en position 2, en poussant la cellulle cc actuellement à cet endroit. On devra localiser le prédécesseur, la cellule d'indice 1.

    Principe de la liste chaînée
  • Etape 2 : Créer la nouvelle Cellule.
  • Principe de la liste chaînée
  • Etape 3 : Faire pointer la nouvelle Cellule vers le successeur du prédécesseur. Si on arrête là, cc a deux prédécesseurs mais la liste n'est pas modifiée : en partant de la tête, on a toujours 25-15-5.
  • Principe de la liste chaînée
  • Etape 4 : Faire pointer le prédécesseur vers la nouvelle Cellule.
  • Principe de la liste chaînée

Les instructions correspondantes :

(cst) Etape 1 (cst) Etape 2 (cst) Etape 3 (cst) Etape 4
pred = acces(lst, i-1) nouvelle = Cellule(valeur_voulue, None) nouvelle.s = pred.s pred.s = nouvelle

Les étapes 2-3-4 sont à coût constant. Par contre, acces() est à coût linéaire (en 𝞞(n) ou encore en 𝞗(i))

Coût : l'insertion en position i est donc à coût linéaire (en 𝞞(n) ou encore en 𝞗(i)).

Cette fonction hérite de la PRECONDITION de acces() puisqu'elle l'utilise : l'indice i doit être un indice VALIDE.

Un autre exemple avec une liste 25-12-20-10-18-5 plus grande où on veut insérer une cellule contenant 20 derrière celle du 18 :

Principe de la liste chaînée

Si on connaissait déjà l'adresse du prédécesseur, il n'y aurait que trois étapes et on aurait une action à coût constant.

2.2.2 - Implémentation dans une méthode

1 2 3 4 5 6 7 8 9
class Liste: # ... def inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None: '''Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste NON VIDE''' if i == 0: self.insererTete(elt) else: pred = self.acces(i-1) # Etape 1 : recherche de la cellule i-1 nouvelle = Cellule(elt, None) # Etape 2 : création de la cellule nouvelle.s = pred.s # Etape 3 : liaison nouvelle i vers ancienne i pred.s = nouvelle # Etape 4 : liaison i-1 vers nouvelle i

2.2.3 - Insérer une cellule derrière la Fin pour en faire la nouvelle Fin ?

Si on a une liste de n éléments, la Tête est la cellule 0 et la Fin est la cellule n-1. Insérer une cellule derrière la Fin actuelle revient donc à vouloir positionner la nouvelle cellule en position n.

Cela se comprend mieux avec un None placé à l'extérieur de la Fin :

Principe de la liste chaînée
2.3 - Insérer une cellule derrière la position de fin

On veut faire l'équivalent de append() : insérer notre nouvelle cellule en tant que nouvelle Fin sans avoir à fournir le numéro d'indice de la Fin.

2.3.1 - Principe et coût

Cellule à localiser : la Fin actuelle pour faire de son successeur la nouvelle Cellule.

SI la liste est vide, on lance simplement un appel à insererTete().

SINON, il suffit de trois opérations, et seule l'étape 1 change par rapport à "inserer en i" :

  1. Etape 1 : localiser la Fin actuelle
    • On part de la Tête.
    • On avance TANT QUE la cellule actuelle a bien un successeur.
  2. Etape 2 : on crée la nouvelle Cellule
  3. Etape 3 : on impose que le successeur de notre cellule soit le successeur de son prédécesseur. Inutile puisqu'on sait que le successeur est None.
  4. Etape 3 : on relie l'ancienne Fin à la nouvelle

Encore une fois, le coût de cette étape 1 est linéaire puisqu'on va devoir parcourir toutes les cellules de la Tête jusqu'à la Fin.

2.3.2 - Implémentation dans une méthode

1 2 3 4 5 6 7 8 9 10
class Liste: # ... def insererFin(self:'Liste', elt:'Element') -> None: '''Rajoute une nouvelle cellule de Fin contenant elt dans la liste''' if self.estListeVide(): self.insererTete(elt) else: pred = self.tete # Etape 1 : recherche de la cellule de Fin while pred.s is not None: # TANT QUE pred n'est pas la fin actuelle pred = pred.s # on passe à la cellule suivante nouvelle = Cellule(elt, None) # Etape 2 : création de la cellule pred.s = nouvelle # Etape 3 : on relie l'ancienne Fin à la nouvelle

2.3.3 - Peut-on faire mieux ?

Oui, il faudrait stocker la référence de la Fin dans la Liste. Comme cela, localiser la Fin pourra se faire à coût constant.

Par contre, cela va complexifier le code de la classe puisqu'il faudra vérifier s'il faut mettre à jour l'attribut fin à chaque fois qu'on voudra insérer ou supprimer une cellule.

Principe de la liste chaînée

C'est ce que nous allons faire pendant le TP.

3 - Liste chaînée sous forme d'objets : la suppression

3.1 - Supprimer la cellule en position de TETE dans notre liste chaînée

3.1.1 - Principe et coût de cette suppression

Cellule à localiser : la Tête, pour trouver son successeur et en faire la nouvelle Tête.

Puisque la méthode n'aura rien à renvoyer, nous allons pouvoir en profiter pour lui faire renvoyer la valeur qu'elle vient de supprimer.

Etape 1 : on mémorise la valeur actuellement en tête de liste (coût constant). Elle vaut 20 sur l'exemple.

Etape 2 : on modifie l'attribut tete de la liste pour qu'il pointe vers le successeur de la tête actuelle (coût constant)

Principe de la liste chaînée

Etape 3 : on renvoie la valeur mémorisée (coût constant)

(coût constant) Etape 1 (coût constant) Etape 2 (coût constant) Etape 3
ancienne_valeur = lst.tete.v lst.tete = lst.tete.s return ancienne_valeur

Coût : cette suppression est donc à coût constant.

On retrouve une PRECONDITION évidente lorsqu'on regarde les étapes 1 et 2 : la liste doit être NON VIDE : si lst.tete pointe sur None, cela déclencherait une erreur en cherchant None.s !

3.1.2 - Implémentation dans une méthode

1 2 3 4 5 6 7 8 9 10 11 12
class Liste: def __init__(self): self.tete = None # .... def supprimerTete(self:'Liste NON VIDE') -> 'Elt': '''Supprime la cellule de tête et renvoie l'élément qui y était stocké''' ancienne_valeur = self.tete.v # Etape 1 : on mémorise la valeur en tête self.tete = self.tete.s # Etape 2 : la tête devient le successeur de la tête return ancienne_valeur # Etape 3 : on renvoie la valeur stockée
3.2 - Supprimer la cellule en position i dans notre liste chaînée

3.2.1 - Principe et coût de cette suppression

Cellule à localiser : la Cellule d'indice i-1 (si elle existe) pour supprimer la Cellule actuellement en position i.

SI on reçoit un indice i de 0, on lance simplement un appel à supprimerTete().

SINON, il suffit de quatre opérations :

  • Etape 1 : Trouver la Cellule en position i-1, le prédécesseur.
  • Exemple avec la cellule en position 2 qu'on voudrait supprimer.

    Principe de la liste chaînée
  • Etape 2 : on mémorise la valeur actuellement en position i (15 sur l'exemple), en partant de son prédécesseur connu (coût constant)
  • Etape 3 : on fait pointer le prédécesseur vers le successeur de son successeur. La cellule cc a maintenant deux prédécesseurs mais la cellule cb n'est plus référencée dans la liste : en partant de la tête, on a 20-25-5. C'est donc fini.
  • Principe de la liste chaînée
  • Etape 4 : on renvoie la valeur mémorisée (coût constant)

Les instructions correspondantes :

(coût linéaire) Etape 1 (coût constant) Etape 2 (coût constant) Etape 3 (coût constant) Etape 4
pred = lst.acces(i-1) ancienne_valeur = pred.s.v pred.s = pred.s.s return ancienne_valeur

Coût : la suppression en position i est donc à coût linéaire (en 𝞞(n) ou encore en 𝞗(i)).

Cette fonction hérite de la PRECONDITION de acces() puisqu'elle l'utilise : l'indice i doit être un indice VALIDE.

PRECONDITION liée à la première : la liste ne doit pas être vide pour qu'un indice valide existe.

3.2.2 - Implémentation dans une méthode

1 2 3 4 5 6 7 8 9 10 11 12 13
class Liste: # ... def supprimer(self:'Liste', i:'int VALIDE') -> 'Element': '''Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké''' if i == 0: # En réalité, on veut supprimer la Tête return self.supprimerTete() else: pred = self.acces(i-1) # Etape 1 : recherche de la cellule i-1 ancienne_valeur = pred.s.v # Etape 2 : on mémorise la valeur en position i actuellement pred.s = pred.s.s # Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeur return ancienne_valeur # Etape 4 : on renvoie la valeur mémorisée

3.2.3 - Supprimer la cellule en Fin ?

Il suffit de demander à supprimer l'indice n-1.

3.3 - Supprimer la cellule en fin de liste chaînée

3.3.1 Principe et coût

Cellule à localiser : le prédécesseur de la Fin, pas la Fin elle-même !

Les étapes :

  • Etape 1 : Il faut trouver le prédécesseur de la Fin, une Cellule dont le successeur du successeur est None. Puisqu'on va devoir partir de la Tête et descendre les Cellules une à une presque jusqu'à la Fin, le coût sera linéaire.
  • Etape 2 : On mémorise la valeur de Fin (coût constant)
  • Etape 3 : On impose que le successeur du prédécesseur soit maintenant None, ou le successeur de la Fin précédente, ca revient à la même chose (coût constant).
  • Etape 4 : On renvoie l'ancienne valeur de la Fin (coût constant).

On voit donc facilement que le coût de cette opération de suppression est linéaire à cause de l'étape 1.

Ci-dessous, un exemple qui montre que supprimer en fin revient à la même chose que supprimer une Cellule interne. La seule différence vient du fait que le successeur de la Fin est None.

Principe de la liste chaînée

Au final, on obtient donc ceci :

Principe de la liste chaînée

3.3.2 - Implémentation dans une méthode

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
class Liste: # ... def supprimerFin(self:'Liste NON VIDE') -> 'Element': '''Supprime la cellule de Fin d'une liste NON VIDE et renvoie l'élément qui y était stocké''' if self.tete.s is None: return self.supprimerTete() else: # Etape 1 : on cherche le prédécesseur de la Fin pred = lst.tete # on part de la tête while pred.s.s is not None: # tant que c n'est pas le prédécesseur de la Fin pred = pred.s # on passe à la cellule suivante ancienne_valeur = pred.s.v # Etape 2 : on mémorise la valeur en position i actuellement pred.s = None # Etape 3 : on fait pointer le prédécesseur sur None return ancienne_valeur # Etape 4 : on renvoie la valeur mémorisée

3.3.3 - On peut faire mieux si on connaît la Fin ?

Et non. Ici, nous avons besoin du prédécesseur de la Fin. Et connaître la fin ne nous aide en rien à le trouver. Nous allons donc devoir partir de la Tête et remonter une à une les cellules.

Principe de la liste chaînée

4 - TP : Cellule en tant que Classe

Voyons comment réaliser ce type de structure de données. Vous allez récupérer la liste ne référençant que la Tête et allez devoir réaliser l'implémentation intégrant la référence de la Fin également.

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

01° Placer en mémoire la classe Cellule qui peut recevoir deux paramètres lors de l'appel du constructeur : un paramètre valeur et un paramètre successeur.

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
class Cellule: '''Cellule (valeur, successeur)''' def __init__(self, valeur:'Element', successeur:'Cellule|None'): self.v = valeur # Valeur ne peut pas être None si liste homogène self.s = successeur # successeur vaut None si Cellule de Fin def contenu(self:'Cellule') -> 'Element': '''Renvoie le contenu de la Cellule''' return ... def successeur(self:'Cellule NON FIN') -> 'Cellule': '''Renvoie la Cellule suivante de self NON FIN''' return ... def estFin(self:'Cellule') -> bool: '''Prédicat qui renvoie True si la Cellule n'a pas de successeur''' return ... def nbCellules(self:'Cellule') -> int: '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if ... : # si il n'y a pas de successeur return ... # il y a au moins la fin else: return 1 + ... # on demande au successeur

Questions

  1. L'attribut v peut-il référencer None dans cette implémentation si la liste est homogène ?
  2. Que veut dire cette documentation 'Cellule|None' sur le type attendu du paramètre successeur ?
  3. Quel est le nom d'une cellule dans l'attribut s référencera None dans cette implémentation ?
  4. Dans le programme principal :

  5. Créer une cellule cve contenant "Vendredi" qui n'a pas de successeur.
  6. Créer une cellule cje contenant "Jeudi" qui mène à cve.
  7. Créer une cellule cma contenant "Mardi" qui mène à cje.

Comme vous pouvez le voir, il manque des jours.

...CORRECTION...

Question 1

L'attribut v est initialisé avec le paramètre valeur. En regardant la documentation, on voit que cette valeur doit être du type Element. A moins de vouloir stocker uniquement des valeurs None, ce n'est donc pas possible.

Le commentaire sur la ligne L5 est explicite également sur la question.

Question 2

'Cellule|None' veut dire que le paramètre successeur peut être soit une instance de Cellule, soit la valeur None.

Question 3

Une Cellule sans successeur possède un attribut s à None. Il s'agit d'une Cellule de Fin de Liste.

Question 4+

1 2 3
cve = Cellule("Vendredi", None) cje = Cellule("Jeudi", cve) cma = Cellule("Mardi", cje)

02° Représenter sur feuille la structure séquentielle linéaire créée par les instructions suivantes 

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

...CORRECTION...

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

03° Mettre les 4 cellules en mémoire et vérifier les contenus en partant de la Cellule de tête qui est donc 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 !

>>> c4.v 35 >>> c4.s.v 25 >>> c4.s.s.v 15 >>> c4.s.s.s.v 5

04° Compléter maintenant les méthodes contenu(), successeur() et estFin().

...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
class Cellule: '''Cellule (valeur, successeur)''' def __init__(self, valeur:'Element', successeur:'Cellule|None'): self.v = valeur # Valeur ne peut pas être None si liste homogène self.s = successeur # successeur vaut None si Cellule de Fin def contenu(self:'Cellule') -> 'Element': '''Renvoie le contenu de la Cellule''' return self.v def successeur(self:'Cellule NON FIN') -> 'Cellule': '''Renvoie la Cellule suivante de self NON FIN''' return self.s def estFin(self:'Cellule') -> bool: '''Prédicat qui renvoie True si la Cellule n'a pas de successeur''' return self.s is None def nbCellules(self:'Cellule') -> int: '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if ... : # si il n'y a pas de successeur return ... # il y a au moins la fin else: return 1 + ... # on demande au successeur

Bien. Nous sommes capables de créer des Cellules et les lier entre elles. Regardons maintenant comment les compter.

Pour faire cela, nous allons créer une fonction récursive nommée nbCellules() qui aura la charge de donner le nombre de cellules reliées entre elles à partir de la cellule qu'on signale comme étant la Tête de Liste.

05° Partir de la tête et suivre la liste pour être certain de comprendre comment cela se lit.

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

La tête désigne ici la cellule clu qui contient le string "Lundi" et qui mène à la cellule cma,...

06° Travaillons maintenant sur la méthode nbCellules() qu'on notera d'abord juste nbC().

Voici le prototype :

1
def nbC(self:'Cellule') -> int:

On voit qu'on attend nécessairement un paramètre qui est une instance de la classe Cellule.

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

  • Cas de base : la cellule n'a pas de successeur. Elle peut répondre 1 pour signaler qu'elle existe.
  • Cas récursif : elle répondra 1 + la réponse de l'appel qu'elle formule à son successeur.

Questions théoriques (la fonction n'est pas fournie pour l'instant)

  1. Réaliser l'empilement des fonctions lorsqu'on lance l'appel cve.nbC().
  2. cve.nbC() va renvoyer 1 + csa.nbC()

    ...

    ...

  3. Réaliser le dépilement pour obtenir la réponse finale théorique.

...CORRECTION...

Empilement

cve.nbC() va renvoyer 1 + csa.nbC()

....csa.nbC() va renvoyer 1 + cdi.nbC()

........cdi.nbC() RENVOIE 1

Dépilement

Ici, c'est simple, la réponse du cas de base va juste remonter jusqu'à l'appel initial.

cdi.nbC() RENVOIE 1 à csa.nbC()

csa.nbC() RENVOIE 1+1 donc 2 à ... cve.nbC()

cve.nbC() RENVOIE 1+2 donc 3 à ... l'entité informatique qui a fait appel à elle.

07° Compléter maintenant la méthode nbCellules() dans le programme.

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
class Cellule: '''Cellule (valeur, successeur)''' def __init__(self, valeur:'Element', successeur:'Cellule|None'): self.v = valeur # Valeur ne peut pas être None si liste homogène self.s = successeur # successeur vaut None si Cellule de Fin def contenu(self:'Cellule') -> 'Element': '''Renvoie le contenu de la Cellule''' return self.v def successeur(self:'Cellule NON FIN') -> 'Cellule': '''Renvoie la Cellule suivante de self NON FIN''' return self.s def estFin(self:'Cellule') -> bool: '''Prédicat qui renvoie True si la Cellule n'a pas de successeur''' return self.s is None def nbCellules(self:'Cellule') -> int: '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if ... : # si il n'y a pas de successeur return ... # il y a au moins la fin else: return 1 + ... # on demande au successeur # Instructions du programme principal if __name__ == '__main__': cdi = Cellule("Dimanche", None) csa = Cellule("Samedi", cdi) cve = Cellule("Vendredi", csa) cje = Cellule("Jeudi", cve) cme = Cellule("Mercredi", cje) cma = Cellule("Mardi", cme) clu = Cellule("Lundi", cma) assert clu.nbCellules() == 7

...CORRECTION...

1 2 3 4 5 6
def nbCellules(self:'Cellule') -> int: '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if self.s is None : # si il n'y a pas de successeur return 1 # il y a au moins la fin else: return 1 + self.s.nbCellules() # on demande au successeur

08° Donner le coût (et la complexité) de la méthode nbCellules() en considérant une séquence de n cellules dont on connait la tête. Justifier votre réponse.

  1. Le coût est constant et la complexité en 𝞞(1)
  2. Le coût est constant et la complexité en 𝞗(1)
  3. Le coût est logarithmique et la complexité en 𝞞(lg n)
  4. Le coût est logarithmique et la complexité en 𝞗(lg n)
  5. Le coût est linéaire et la complexité en 𝞞(n)
  6. Le coût est linéaire et la complexité en 𝞗(n)
  7. Le coût est quadratique et la complexité en 𝞞(n2)
  8. Le coût est quadratique et la complexité en 𝞗(n2)
  9. Le coût est exponentielle et la complexité en 𝞞(en)
  10. Le coût est exponentielle et la complexité en 𝞗(en)

...CORRECTION...

Le coût est linéaire puisqu'on doit partir de la tête et parcourir les cellules une à une.

On peut écrire 𝞗(n) puisque la complexité est réellement linéaire dans tous les cas. Quelque soit le contenu de la liste, il n'y a pas de cas où on pourrait s'arrêter avant d'avoir atteint la Fin. Seule la taille n de la liste importe.

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.

5 - TP : Liste chaînée en tant que Classe

09° Placer le programme en mémoire puis répondre aux questions sur la classe Liste.

Questions

  1. Que contient l'attribut tete de la liste lst après exécution de la ligne 57 ?
  2. Que contient l'attribut tete de la liste lst après exécution de la ligne 58 ?
  3. Expliquer la ligne 59 en mode pas à pas
1 2 3 4 5 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
class Cellule: '''Cellule (valeur, successeur)''' def __init__(self, valeur:'Element', successeur:'Cellule|None'): self.v = valeur # Valeur ne peut pas être None si liste homogène self.s = successeur # successeur vaut None si Cellule de Fin def nbCellules(self:'Cellule') -> int: '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if self.s is None : # si il n'y a pas de successeur return 1 # il y a au moins la fin else: return 1 + self.s.nbCellules() # on demande au successeur class Liste: '''Liste chaînée muable''' def __init__(self): self.tete = None def estListeVide(self:'Liste') -> bool: return self.tete is None def accesTete(self:'Liste NON VIDE') -> Cellule: '''Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE''' return self.tete def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule: '''Renvoie l'adresse de la cellule i dans la liste NON VIDE''' c = self.accesTete() # récupère la cellule de tête for _ in range(i): # Faire i fois c = c.s # passe au successeur return c def longueur(self:'Liste') -> int: '''Renvoie la longueur de la liste''' if self.estListeVide(): return 0 else: return self.tete.nbCellules() # Instructions du programme principal if __name__ == '__main__': cdi = Cellule("Dimanche", None) csa = Cellule("Samedi", cdi) cve = Cellule("Vendredi", csa) cje = Cellule("Jeudi", cve) cme = Cellule("Mercredi", cje) cma = Cellule("Mardi", cme) clu = Cellule("Lundi", cma) assert clu.nbCellules() == 7 lst = Liste() lst.tete = clu assert lst.acces(2).v == "Mercredi"

...CORRECTION...

10° Remplacer uniquement le programme principal pour celui-ci.

46 47 48 49 50 51 52
if __name__ == '__main__': a = Cellule('Marie-Antoinette', None) b = Cellule('Louis XVI', a) c = Cellule('Louis XV', b) ls_1 = Liste() ls_1.tete = c

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

  1. Comment obtenir la tête en utilisant l'objet li_1 ?
  2. Comment obtenir le contenu de la tête en utilisant l'objet li_1 ?
  3. Comment obtenir la valeur du successeur de la tête en utilisant l'objet ls_1 ?
  4. Comment obtenir le contenu du successeur du successeur de la tête en utilisant l'objet ls_1 ?

...CORRECTION...

Pour obtenir la tête de la liste (l'indice 0), puis son contenu :

>>> ls_1.tete <__main__.Cellule object at 0x7f03e9774a20>
>>> ls_1.tete.v 'Louis XV'

Pour obtenir le contenu du successeur de la tête (l'indice 1 en gros)

>>> ls_1.tete.s.v 'Louis XVI'

Pour obtenir le contenu du successeur du successeur de la tête (l'indice 2 en gros)

>>> ls_1.tete.s.s.v 'Marie-Antoinette'

Nous allons maintenant enrichir les fonctions disponibles pour commencer à retrouver nos fonctions d'interface.

Nous allons commencer par fournir au moins l'interface ci-dessous, pour justifier que nous avons bien une Liste.

11° Observer la liste des primitives et expliquer pourquoi nous avons bien une liste muable.

...CORRECTION...

On voit qu'insérer() ne renvoie rien.

On voit que supprimer() renvoie l'élément supprimé.

Cela indique clairement que les listes sont modifiées en place.

Vous allez trouver ci-dessous une implémentation intégrant déjà quelques méthodes correspondant à ce qu'on désire.

  1. primitive nouvelleListeVide() -> constructeur Liste() : ok
  2. primitive estListeVide() -> méthode de Liste.estListeVide(): ok
  3. primitive insererTete() -> méthode de Liste.insererTete(): à faire
  4. primitive supprimerTete() -> méthode de Liste.supprimerTete(): à faire
  5. primitive accesTete() -> méthode de Liste.accesTete(): ok
  6. primitive contenu() -> méthode de Cellule.contenu(): ok
  7. primitive successeur() -> méthode de Cellule.successeur(): ok
  8. premier() -> méthode de Liste.premier(): à faire

Attention, cette implémentation comporte deux attributs pour la liste : un attribut tete et un attribut fin.

12° Mettre en mémoire le programme suivant qui intègre notre module de liste chaînée muable Tete-Fin.

Compléter ensuite la méthode insererTete() SANS GERER l'attribut fin pour le moment. Faire comme si cet attribut n'était pas là.

MODULE :

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 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
'''Module du TP implémentant une liste chaînée TETE-FIN MUABLE sous forme d'un objet composé : + d'un objet Liste référençant la Tête et la Fin + d'instances de classe Cellules (valeur, successeur) ''' class Cellule: '''Cellule (valeur, successeur) Les Cellules disposent de deux attributs : + un attribut v : la valeur contenue dans cette cellule + un attribut s : le successeur de la cellule, None ou Cellule Méthodes -------- contenu(self:'Cellule') -> 'Element' # coût constant successeur(self:'Cellule NON FIN') -> 'Cellule' # coût constant aSuccesseur(self:'Cellule') -> bool # coût constant estFin(self:'Cellule') -> bool # coût constant nbCellules(self:'Cellule') -> int # Coût linéaire θ(n) ''' def __init__(self, valeur:'Element', successeur:'Cellule|None'): self.v = valeur # Valeur ne peut pas être None si liste homogène self.s = successeur # successeur vaut None si Cellule de Fin # Méthodes ayant un lien avec une primitive de liste chaînée def contenu(self:'Cellule') -> 'Element': '''Renvoie le contenu de la Cellule''' return self.v def successeur(self:'Cellule NON FIN') -> 'Cellule': # coût constant '''Renvoie la Cellule suivante de self NON FIN''' return self.s # Autres méthodes def aSuccesseur(self:'Cellule') -> bool: # coût constant '''Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule''' return self.s is not None # ou return not self.s is None def estFin(self:'Cellule') -> bool: # coût constant '''Prédicat qui renvoie True si la Cellule n'a pas de successeur''' return self.s is None # ou même return not self.aSuccesseur() def nbCellules(self:'Cellule') -> int: # Coût linéaire θ(n) '''Renvoie le nombre de cellules dans la chaîne à partir de cette cellule''' if self.s is None: # si il n'y a pas de successeur return 1 # il y a au moins la fin else: return 1 + self.s.nbCellules() # on demande au successeur... class Liste: '''Liste chaînée muable Les objets disposent de deux attributs : + un attribut tete : None si liste vide ou la référence de la Cellule de Tête + un attribut fin : None si liste vide ou la référence de la Cellule de Fin Méthodes primitives ------------------- estListeVide(self:'Liste') -> bool # coût constant insererTete(self:'Liste', elt:'Element') -> None # coût constant supprimerTete(self:'Liste NON VIDE') -> 'Elt' # coût constant accesTete(self:'Liste NON VIDE') -> Cellule # coût constant premier(self:'Liste NON VIDE') -> Element # coût constant Méthodes primitives (extension) ------------------------------- accesFin(self:'Liste NON VIDE') -> Cellule # coût constant insererFin(self:'Liste', elt:'Element') -> None # Coût ??? supprimerFin(self:'Liste NON VIDE') -> 'Element' # Coût ??? Autres méthodes (on peut les construire avec les primitives) --------------- acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule # Coût linéaire θ(i) O(n) inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None # Coût linéaire θ(i) O(n) supprimer(self:'Liste', i:'int VALIDE') -> 'Element' # Coût linéaire θ(i) O(n) longueur(self:'Liste') -> int # Coût linéaire θ(n) afficher(self:'Liste') -> None ''' def __init__(self): self.tete = None # Seule une liste vide par avoir cette valeur d'attribut self.fin = None # Seule une liste vide par avoir cettte valeur d'attribut # Méthodes-primitives de liste chaînée basique def estListeVide(self:'Liste') -> bool: # coût constant return self.tete is None def insererTete(self:'Liste', elt:'Element') -> None: # coût constant '''Rajoute une nouvelle cellule contenant elt en tête de liste''' ... # Etape 1 : création de la cellule ... # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête ... # Etape 3 : modification de la liste def supprimerTete(self:'Liste NON VIDE') -> 'Elt': # coût constant '''Supprime la cellule de tête et renvoie l'élément qui y était stocké''' ... # Etape 1 : on mémorise la valeur en tête ... # Etape 2 : la tête devient le successeur de la tête ... # Etape 3 : on renvoie la valeur stockée def accesTete(self:'Liste NON VIDE') -> Cellule: # coût constant '''Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE''' return self.tete def premier(self:'Liste NON VIDE') -> 'Element': # coût constant '''Renvoie la valeur de la cellule de Tête dans la liste NON VIDE''' return self.tete.v # Méthodes-primitives de l'extentsion liste chaînée Tête et Fin def accesFin(self:'Liste NON VIDE') -> Cellule: # coût constant '''Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE''' pass def insererFin(self:'Liste', elt:'Element') -> None: # Coût ??? '''Rajoute une nouvelle cellule de Fin contenant elt dans la liste''' pass def supprimerFin(self:'Liste NON VIDE') -> 'Element': # Coût ??? '''Supprime la cellule de fin d'une liste NON VIDE et renvoie l'élément qui y était stocké''' pass # Autres méthodes def acces(self:'Liste NON VIDE', i:'int VALIDE') -> Cellule: # Coût linéaire θ(i) O(n) '''Renvoie l'adresse de la cellule i dans la liste NON VIDE''' c = self.accesTete() # récupère la cellule de tête for _ in range(i): # Faire i fois c = c.s # passe au successeur return c def inserer(self:'Liste', elt:'Element', i:'int VALIDE') -> None: # Coût linéaire θ(i) O(n) '''Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste NON VIDE''' if i == 0: self.insererTete(elt) else: pred = self.acces(i-1) # Etape 1 : recherche de la cellule i-1 nouvelle = Cellule(elt, None) # Etape 2 : création de la cellule nouvelle.s = pred.s # Etape 3 : le successeur de la nouvelle est le successeur du prédécesseur pred.s = nouvelle # Etape 4 : le successeur du prédécesseur est la nouvelle cellule def supprimer(self:'Liste', i:'int VALIDE') -> 'Element': # Coût linéaire θ(i) O(n) '''Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké''' if i == 0: # En réalité, on veut supprimer la Tête return self.supprimerTete() else: pred = self.acces(i-1) # Etape 1 : recherche de la cellule i-1 ancienne_valeur = pred.s.v # Etape 2 : on mémorise la valeur en position i actuellement pred.s = pred.s.s # Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeur return ancienne_valeur # Etape 4 : on renvoie la valeur mémorisée def longueur(self:'Liste') -> int: # Coût linéaire θ(n) '''Renvoie la longueur de la liste''' if self.estListeVide(): return 0 else: return self.tete.nbCellules() def afficher(self:'Liste') -> None: # Coût linéaire actuellement = self.accesTete() while actuellement is not None: print(f"{actuellement.v} -> ", end='') actuellement = actuellement.s print('x') # Programme if __name__ == '__main__': def tester_insererTete(): print("Tests de insererTete())...", end="") lst = Liste() lst.insererTete(5) assert lst.tete == lst.fin lst.insererTete(10) assert lst.tete != lst.fin assert lst.tete.v == 10 assert lst.fin.v == 5 lst.insererTete(20) assert lst.tete != lst.fin assert lst.tete.v == 20 assert lst.fin.v == 5 print("ok") def tester_supprimerTete(): print("Tests de supprimerTete())...", end="") lst = Liste() lst.insererTete(5) lst.insererTete(10) lst.insererTete(20) lst.supprimerTete() assert lst.tete != lst.fin assert lst.tete.v == 10 assert lst.fin.v == 5 lst.supprimerTete() assert lst.tete == lst.fin assert lst.fin.v == 5 lst.supprimerTete() assert lst.tete == lst.fin assert lst.fin == None print("ok") def tester_insererFin(): print("Tests de insererFin())...", end="") lst = Liste() lst.insererFin(5) assert lst.tete == lst.fin lst.insererFin(10) assert lst.tete != lst.fin assert lst.tete.v == 5 assert lst.fin.v == 10 lst.insererFin(20) assert lst.tete != lst.fin assert lst.tete.v == 5 assert lst.fin.v == 20 lst.insererTete(200) assert lst.tete != lst.fin assert lst.tete.v == 200 assert lst.fin.v == 20 print("ok") def tester_supprimerFin(): print("Tests de supprimerFin())...", end="") lst = Liste() lst.insererTete(5) lst.insererTete(10) lst.insererTete(20) lst.insererTete(200) lst.supprimerFin() assert lst.tete != lst.fin assert lst.tete.v == 200 assert lst.fin.v == 10 lst.supprimerTete() assert lst.tete != lst.fin assert lst.tete.v == 20 assert lst.fin.v == 10 lst.supprimerFin() assert lst.tete == lst.fin assert lst.fin.v == 20 lst.supprimerFin() assert lst.tete == lst.fin assert lst.fin == None print("ok") #tester_insererTete() #tester_supprimerTete() #tester_insererFin() #tester_supprimerFin()

...CORRECTION...

1 2 3 4 5
def insererTete(self:'Liste', elt:'Element') -> None: # coût constant '''Rajoute une nouvelle cellule contenant elt en tête de liste''' nouvelle = Cellule(elt, None) # Etape 1 : création de la cellule nouvelle.s = self.tete # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête self.tete = nouvelle # Etape 3 : modification de la liste

13° Répondre aux questions suivantes :

  1. Une liste vide pointe-t-elle au même endroit sa Tête et sa Fin ?
  2. Une liste de un élément pointe-t-elle au même endroit sa Tête et sa Fin ?
  3. Une liste de deux éléments ou plus pointe-t-elle au même endroit sa Tête et sa Fin ?
  4. En déduire si on doit mettre à jour l'attribut fin si on utilise insererTete() sur une liste vide ?
  5. En déduire si on doit mettre à jour l'attribut fin si on utilise insererTete() sur une liste de un élément ?
  6. En déduire si on doit mettre à jour l'attribut fin si on utilise insererTete() sur une liste de deux éléments ou plus ?

...CORRECTION...

  1. Une liste vide pointe-t-elle au même endroit sa Tête et sa Fin ?
  2. Oui, les deux attributs pointent vers None.

  3. Une liste de un élément pointe-t-elle au même endroit sa Tête et sa Fin ?
  4. Oui, les deux attributs pointent vers la seule cellule présente.

  5. Une liste de deux éléments ou plus pointe-t-elle au même endroit sa Tête et sa Fin ?
  6. Non, chaque attribut pointe vers une cellule différente.

  7. En déduire si on doit mettre à jour l'attribut fin si on utilise insererTete() sur une liste vide ?
  8. Oui, fin devra pointer vers la nouvelle cellule.

  9. En déduire si on doit mettre à jour l'attribut fin si on utilise insererTete() sur une liste de un élément ?
  10. Non, fin devra toujours pointer vers l'ancienne cellule qui jouait le rôle de Tête avant. Inutile de la mettre à jour, elle a été poussée et joue toujours le rôle de Fin. C'est la Tête qui devra être modifiée.

  11. En déduire si on doit mettre à jour l'attribut fin si on utilise insererTete() sur une liste de deux éléments ou plus ?
  12. Non plus, la fin reste la fin.

14° Compléter alors maintenant la méthode insererTete() pour qu'elle gère correctement la mise à jour de l'attribut fin lorsqu'il le faut.

Attention : on veut une fonction à coût constant.

Vous avez des fonctions de test à décommenter pour tester votre réalisation. Si vous ne voyez pas où est votre erreur, vous pouvez modifier les fonctions de tests en rajoutant lst.afficher() avant et après avoir modifié la liste en lui rajoutant une tête. Vous pourrez un peu mieux voir ce qui se passe.

...CORRECTION...

Aucune boucle et que des opérations à coût constant. La fonction est donc à coût constant.

1 2 3 4 5 6 7
def insererTete(self:'Liste', elt:'Element') -> None: # coût constant '''Rajoute une nouvelle cellule contenant elt en tête de liste''' c = Cellule(elt, None) # Etape 1 : création de la cellule if self.estListeVide(): # Etape supplémentaire si la liste est vide initialement self.fin = c c.s = self.tete # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête self.tete = c.s # Etape 3 : modification de la liste

15° Compléter la méthode supprimerTete().

Commencer par gérer uniquement l'attribut tete et la modification de la liste. C'est clairement au programme.

Ensuite, il faudra vous demander dans quel(s) cas la mise à jour de fin va être nécessaire :

  • passage de 3 cellules à 2 cellules ?
  • Passage de 2 cellules à 1 cellule ?
  • Passage de 1 cellule à une liste vide ?

Vous avez des fonctions de test à décommenter pour tester votre réalisation.

Attention : on veut une fonction à coût constant.

...CORRECTION...

Puisqu'on supprime la tête, nous n'avons pas besoin de mettre à jour la fin sauf lorsque la liste devient vide, l'attribut fin ne doit plus pointer vers une cellule mais vers None.

...CORRECTION...

Aucune boucle et que des opérations à coût constant. La fonction est donc à coût constant.

1 2 3 4 5 6 7
def insererTete(self:'Liste', elt:'Element') -> None: # coût constant '''Rajoute une nouvelle cellule contenant elt en tête de liste''' c = Cellule(elt, None) # Etape 1 : création de la cellule if self.estListeVide(): # Etape supplémentaire : on met fin à jour, ou pas self.fin = c c.s = self.tete # Etape 2 : on relie la nouvelle cellule à l'"ancienne" Tête self.tete = c.s # Etape 3 : modification de la liste

16° Compléter la méthode accesFin() pour la forme (facile) puis la méthode insererFin() (moyen). Donner également les coûts de ces méthodes.

Si la liste est vide, on peut faire appel à insererTete() puisqu'insérer une fin dans une liste vide revient à insérer une tête.

Si la liste n'est pas vide, c'est à vous d'agir : il faudra que la nouvelle cellule soit le successeur de la fin précédente. Il faut donc mettre la main sur la fin précédente pour lui dire qu'elle a un successeur maintenant.

Attention, on veut une fonction à coût constant cette fois. Il faudra donc trouver la fin avec un coût constant... Comment faire ?

Une fois la gestion de la fin bien réaliser, il faudra vous demander dans quel(s) cas la mise à jour de tete va être nécessaire :

  • Passage de liste vide à une liste de 1 cellule ?
  • Passage de 1 cellules à 2 cellule ?
  • passage de 2 cellules à 3 cellules ?

Vous avez des fonctions de test à décommenter pour tester votre réalisation.

...CORRECTION...

Puisqu'on rajoute une fin, l'attribut fin devra toujours être modifié.

Si la liste est vide, on fait appel à insererTete(), et c'est elle qui va mettre les attributs.

Si la liste est contient déjà une Cellule, inutile de modifier l'attribut tete, il pointe au bon endroit. La cellule sera modifiée pour indiquer qu'elle a un successeur maintenant, mais la liste doit toujours pointer vers elle en tant que Tête.

Si la liste possède déjà 2 cellules ou plus, inutile de se demander s'il faut modifier la Tête, les deux attributs pointaient déjà vers deux cellules différentes.

En conclusion, nous n'aurons jamais à modifier la tête : dans le seul cas pù il aurait fallu le faire, on active une autre fonction.

...CORRECTION...

Aucune boucle et que des opérations à coût constant. La fonction est donc à coût constant.

1 2 3 4 5 6 7 8 9 10 11 12
def accesFin(self:'Liste NON VIDE') -> Cellule: # coût constant '''Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE''' return self.fin def insererFin(self:'Liste', elt:'Element') -> None: # Coût ??? '''Rajoute une nouvelle cellule de Fin contenant elt dans la liste''' if self.estListeVide(): # Si la liste est vide, on fait appel self.insererTete(elt) else: nouvelle = Cellule(elt, None) # Etape 1 : on crée la nouvelle Cellule self.fin.s = nouvelle # Etape 2 : on relie l'ancienne Fin à la nouvelle self.fin = nouvelle # Etape 3 : mise à jour de la liste

17° Quelle cellule faut-il localiser pour supprimer la Fin ? En déduire le coût de cet opération de suppression. Dans quel cas va-t-on juste faire appel à supprimerTete() ?

Compléter la méthode supprimerFin() (difficle). Donner également le coût de la méthode.

Vous avez des fonctions de test à décommenter pour tester votre réalisation.

...CORRECTION...

Il faut localiser le prédécesseur de la Fin.

Ca, on ne l'a pas en mémoire, il va falloir chercher. On peut en déduire immédiatement que le coût de l'opération va être linéaire.

Si la liste ne contient qu'une seule cellule, on pourra faire appel à supprimerTete() puisque Tête et Fin pointe vers la même cellule.

Pas la peine de gérer la liste déjà vide. La PRECONDITION explique clairement qu'on ne gère pas ce cas.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
def supprimerFin(self:'Liste NON VIDE') -> 'Element': # Coût Linéaire θ(n) '''Supprime la cellule de fin d'une liste NON VIDE et renvoie l'élément qui y était stocké''' if self.tete == self.fin: # si la liste ne possède qu'une seule cellule return self.supprimerTete() # on demande à l'autre fonction de faire le travail else : # Etape 1 : on cherche le prédécesseur de la Fin pred = self.tete # on part de la tête while pred.s.s is not None: # tant que c n'est pas le prédécesseur de la Fin pred = pred.s # on passe à la cellule suivante ancienne_valeur = pred.s.v # Etape 2 : on mémorise la valeur de Fin actuelle pred.s = None # Etape 3 : on fait pointer le prédécesseur sur None self.fin = pred # Etape 4 : on met la liste à jour return ancienne_valeur # Etape 5 : on renvoie la valeur mémorisée

Petit bilan des différentes listes vues jusqu'à présent.

Pour les insertions/suppressions

Insertion/suppression sur Tête n°i Fin
Liste contiguë Tableau statique LIN θ(n) LIN θ(n) LIN θ(n)
Liste contiguë list Python LIN θ(n) LIN θ(n-i) CST
Liste chaînée tuple (valeur de Tête, Queue) CST LIN θ(i) LIN θ(n)
Liste chaînée Objet Tête CST LIN θ(i) LIN θ(n)
Liste chaînée Objet Tête-Fin CST LIN θ(i) CST / LIN θ(n)

Pour les lectures/changement de valeur d'une place

Lecture/changement de valeur sur Tête n°i Fin
Liste contiguë Tableau statique CST CST CST
Liste contiguë list Python CST CST CST
Liste chaînée tuple (valeur de Tête, Queue) CST LIN θ(i) LIN θ(n)
Liste chaînée Objet Tête CST LIN θ(i) LIN θ(n)
Liste chaînée Objet Tête-Fin CST LIN θ(i) CST

6 - Effet de bord : concaténation et sécurité

En réalité, la plus grande force des listes chaînées ne vient pas juste de l'insertion d'une donnée individuelle mais de l'insertion d'une liste à la suite d'une autre liste. On parlera de concaténation de listes, comme avec les strings.

Lorsqu'on parle de concaténation, on parle de la création d'une nouvelle liste, pas de la modification d'une liste déjà existante :

concatener(Liste, Liste) -> Liste

Liste + Liste -> Liste

RAPPEL : concaténation de tableaux statiques

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 concaténer les deux listes, c'est long avec des tableaux :

Etape 1 : création d'un nouveau tableau

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

Création d'un nouveau tableau
Etape 2 : recopie des éléments de gauche

Il faut déplacer un par un les 20 000 éléments du premier tableau.

Déplacement des éléments de A
Etape 3 : recopie des éléments de droite

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

Déplacement des éléments de B

Concaténation de listes chaînées

Sur le papier, la concaténation de listes chaînées dont on connait les références de la cellule de Tête et de la cellule de Fin a l'air bien bien simple à mettre en oeuvre :

Changement de référence

18° Mettre cette méthode concatener_problematique() en mémoire. Voici son prototype :

concatener_problematique(self:'Liste', droite:'Liste') -> 'Liste'

Questions

  1. Expliquer ce qu'elle réalise ligne par ligne.
  2. Quel est le coût de cette opération ?
  3. Voyez-vous d'où vient le problème de cette façon d'agir ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
def concatener_problematique(self:'Liste', droite:'Liste') -> 'Liste': '''Renvoie une liste qui est la concaténation des listes self et liste_droite''' nouvelle = Liste() # ? if not self.estListeVide() and not droite.estListeVide(): # ? nouvelle.tete = self.tete # ? self.fin.s = droite.tete # ? nouvelle.fin = droite.fin # ? elif self.estListeVide() and not droite.estListeVide(): # ? nouvelle.tete = droite.tete # ? nouvelle.fin = droite.fin # ? elif droite.estListeVide() and not self.estListeVide(): # ? nouvelle.tete = droite.tete # ? nouvelle.fin = droite.fin # ? return nouvelle # ?

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
def concatener_problematique(self:'Liste', droite:'Liste') -> 'Liste': '''Renvoie une liste qui est la concaténation des listes self et liste_droite''' nouvelle = Liste() # on crée une instance de Liste if not self.estListeVide() and not droite.estListeVide(): # si aucune des deux listes n'est vide nouvelle.tete = self.tete # nouvelle a la même Tête que gauche self.fin.s = droite.tete # on fait pointer la fin de gauche sur la tête de droite nouvelle.fin = droite.fin # nouvelle a la même Fin que droite elif self.estListeVide() and not droite.estListeVide(): # si seule la liste de gauche est vide nouvelle.tete = droite.tete # nouvelle a la même Tête que droite nouvelle.fin = droite.fin # nouvelle a la même Fin que droite elif droite.estListeVide() and not self.estListeVide(): # si seule la liste de droite est vide nouvelle.tete = droite.tete # nouvelle a la même Tête que gauche nouvelle.fin = droite.fin # nouvelle a la même Tête que gauche return nouvelle # on renvoie la référence de notre nouvelle liste

Toutes les opérations internes sont à coût constant. La fonction parvient donc à agir à coût CONSTANT.

Le problème vient de la nature muable des cellules : nous n'avons pas copié le contenu, nous déclarons juste où se trouve le début (et la fin).

19° Rajouter ces instructions dans le programme principal.

Exécuter mentalement ce qui s'y passe et représenter l'état des listes au fur et à mesure.

Lancer ensuite le programme pour vérifier votre résultat...

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
gauche = Liste() gauche.insererFin(5) gauche.insererFin(15) gauche.insererFin(25) droite = Liste() droite.insererFin(40) droite.insererFin(50) droite.insererFin(60) print("\nAvant concaténation :") print("---------------------") print("Gauche : ", end='') gauche.afficher() print("Droite : ", end='') droite.afficher() t = gauche.concatener_problematique(droite) print("\nAprès concaténation :") print("---------------------") print("Gauche : ", end='') gauche.afficher() print("Droite : ", end='') droite.afficher() print("t = g+d : ", end='') t.afficher() droite.supprimerFin() droite.insererFin(1000) print("\nAprès modification de droite :") print("------------------------------") print("Gauche : ", end='') gauche.afficher() print("Droite : ", end='') droite.afficher() print("t = g+d : ", end='') t.afficher()

20° Comment se nomme ce type de modification, où un contenu muable associé à une variable est modifié à cause d'une action sur une autre variable ?

7 - FAQ

On m'a dit de faire attention aux copies de listes. C'est vrai ?

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 : 30 10 2022
Auteur : ows. h.