Nous avons vu qu'on implémente correctement l'idée d'une Liste Récursive sous forme d'une implémentation Liste Chaînée Immuable utilisant en interne un tuple (valeur de tête, successeur).
On peut alors :
accéder, insérer et supprimer en TETE de liste à coût CONSTANT.
accéder en position i à coût LINEAIRE en 𝞗(i).
insérer et supprimer en position i à coût LINEAIRE en 𝞗(i).
concatener à coût LINEAIRE en 𝞗(ng) (uniquement les éléments de gauche).
Nous avons vu qu'on implémente correctement l'idée d'une Liste Itérative Muable sous forme d'une implémentation Liste Contiguë utilisant en interne une list-Python qui est un tableau dynamique.
On peut alors :
accéder, insérer, supprimer en FIN de liste à coût CONSTANT.
accéder à toutes les cases à coût CONSTANT.
insérer et supprimer en position i à coût LINEAIRE en 𝞗(i).
concatener à coût LINEAIRE en 𝞗(ng+nd) (les éléments à gauche ET à droite).
Aujourd'hui, vous allez implémenter correctement l'idée d'une Liste Récursive sous forme d'une implémentation Liste Chaînée Muable utilisant en interne un objet.
On voudrait alors :
accéder à la TETE ou la FIN de liste à coût CONSTANT.
insérer, supprimer en TETE et en FIN de liste à coût CONSTANT.
insérer et supprimer en position i à coût LINEAIRE en 𝞗(n-i).
concatener à coût LINEAIRE en 𝞗(ng+nd) (les éléments à gauche ET à droite).
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.
Prérequis : nous allons utiliser la programmation objet. Rien de bien méchant, mais il faut avoir vu ces notions.
classCellule:def__init__(self,valeur:'Element',successeur:'Cellule|None'):self.v=valeur# Valeur ne peut pas être None si liste homogèneself.s=successeur# successeur vaut None si Cellule de Findefcontenu(self:'Cellule')->'Element':"""Renvoie le contenu de la Cellule"""returnself.vdefsuccesseur(self:'Cellule NON FIN')->'Cellule':"""Renvoie la Cellule suivante de self NON FIN"""returnself.sdefa_successeur(self:'Cellule')->bool:"""Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule"""returnnotself.sisNone# ou même return self.s is not Nonedefest_fin(self:'Cellule')->bool:"""Prédicat qui renvoie True si la Cellule n'a pas de successeur"""returnself.sisNone# ou même return not self.a_successeur()
Dans ce cours, nous utiliserons plutôt la méthode directe notamment pour obtenir moins de lignes. Pour un prototype, c'est ok. Pas pour une production réelle.
Priorité des opérateurs
Parenthèses (la plus haute priorité)
Opérateurs arithmétiques
Exposant, puissance
Multiplication, division
Addition, soustraction
Opérateurs de comparaison
Opérateur in
Opérateurs is et is not
Opérateurs d'ordre > <...
Opérateur égalité et différence == !=
Opérateurs logiques
Opérateur not
Opérateur and
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 de la Liste
La Liste est une instance d'une classe Liste possédant un attribut tete faisant référence :
soit à None pour indiquer qu'il s'agit d'une Liste VIDE.
soit à la Cellule en tête s'il s'agit d'une Liste NON VIDE.
lst1=Liste() # Liste videca=Cellule(5, None)
cb=Cellule(15, ca)
cc=Cellule(25, cb)
lst1.tete=cc# lst est la liste 25 puis 15 puis 5lst2=Liste() # Liste vide
La liste est encore une référence vers la première Cellule, la Cellule de Tête. Mais ce n'est plus un simple alias : la référence est stockée dans la zone mémoire de l'objet Liste, différente de la zone-mémoire de la cellule de tête.
1.3 - Exemple d'utilisation
Nous utiliserons deux classes.
La classe Cellule pour gérer l'enchaînement des Cellules et leurs valeurs stockées.
La classe Liste pour savoir de quelle tête partir et former ainsi notre Liste Chaînée.
Avant de pouvoir agir sur une Cellule en position i, il faut d'abord pouvoir la localiser !
B - Les deux méthodes (version itérative)
1
2
3
4
5
6
7
8
9
classListe:# ...defacces_tete(self:'Liste NON VIDE')->Cellule:"""Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""returnself.tetedefacces(self:'Liste NON VIDE',i:'int VALIDE')->Cellule:"""Renvoie l'adresse de la cellule i dans la liste NON VIDE"""c=self.acces_tete()# récupère la cellule de têtefor_inrange(i):# Faire i foisc=c.s# passe au successeurreturnc
Puisqu'il faut renvoyer une instance de Cellule, il est nécessaire de pouvoir trouver une Cellule. Il y a donc deux PRECONDITIONS :
La liste ne peut pas être vide car, dans ce cas, elle ne possède pas de Cellule.
L'indice fourni doit correspondre à un indice possible dans notre liste, un indice où se trouve une Cellule.
C - Coûts
Le coût de la méthode acces_tete() est évidemment constant puisqu'on n'y fait que des lectures d'attributs.
cst
defacces_tete(self:'Liste NON VIDE')->Cellule:"""Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""returnself.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
defacces(self:'Liste NON VIDE',i:'int VALIDE')->Cellule:"""Renvoie l'adresse de la cellule i dans la liste NON VIDE"""c=self.acces_tete()# récupère la cellule de têtefor_inrange(i):# Faire i foisc=c.s# passe au successeurreturnc
1.5- Méthode longueur()
A - Intérêt ?
Fournir la taille de la liste pour connaître les valeurs possibles d'indice.
B - 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.
C - Version itérative
On crée un compteur qui vaut 0.
Si la liste n'est pas vide :
Tant qu'un successeur existe, on augmente le compteur et on passe au successeur.
On renvoie le compteur.
1
2
3
4
5
6
7
8
9
10
classListe:# ...deflongueur(self:'Liste')->int:"""Renvoie la longueur de la liste"""nb=0ifnotself.est_liste_vide():c=self.tetenb=1whilec.sisnotNone:nb=nb+1c=c.sreturnnb
D - Version récursive
Il va falloir commencer par enrichir notre classe Cellule d'une méthode permettant de renvoyer le nombre de cellules qui composent une chaîne.
Avec la méthode récursive :
Cas de base : la cellule active est la FIN (elle n'a pas de successeur). Elle répond 1.
Cas récursif : une cellule répondra un jour 1 + la réponse de son successeur.
1
2
3
4
5
6
classCellule:# ...defnb_cellules(self:'Cellule')->int:"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""ifself.sisNone:# si il n'y a pas de successeurreturn1# il y a au moins la finelse:return1+self.s.nb_cellules()# on demande au successeur...
Notez bien que nb_cellules() étant une méthode de la classe Cellule, il faut que devant le point on trouve une instance de cette classe. C'est le cas en ligne 6 : si on arrive ici, c'est que la cellule a une vraie cellule en tant que successeur et donc self.s est une cellule.
Pour l'intégrer dans la Liste, on peut donc écrire ceci :
7
8
9
10
11
12
classListe:# ...deflongueur(self:'Liste')->int:"""Renvoie la longueur de la liste"""ifself.est_liste_vide():return0else:returnself.tete.nb_cellules()
Notez bien que nb_cellules() étant une méthode de la classe Cellule, il faut que devant le point on trouve une instance de cette classe. C'est le cas en ligne 12 : si on arrive ici, c'est que la liste n'est pas vide et qu'elle possède une cellule de tête.
2 - Liste chaînée sous forme d'objets : l'insertion
le prédécesseur éventuel de la cellule qu'on veut rajouter : qui est la cellule juste avant ?
le successeur éventuel de la cellule qu'on veut rajouter : qui est la cellule juste derrière ?
Or, dans une liste chaînée, si on connaît le prédécesseur, on peut obtenir facilement le successeur.
CONCLUSION : il suffit de localiser le prédécesseur de la nouvelle cellule qu'on va insérer.
2.1 - Insérer une cellule en position de TETE dans notre liste chaînée
A - Principe et coût de cette insertion
Pour insérer en tête, on a besoin de la tête actuelle.
Etape 1 : on crée la nouvelle Cellule cd (coût constant)
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)
Etape 3 : on modifie la liste en modifiant l'adresse stockée comme Tête (coût constant)
classListe:# ...definserer_tete(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 cellulenouvelle.s=self.tete# Etape 2 : on relie la nouvelle cellule à l'"ancienne" têteself.tete=nouvelle# Etape 3 : modification de la liste
2.2 - Insérer une cellule en position i dans notre liste chaînée
A - Principe de l'insertion en position i
Pour insérer une cellule en position i, il faut localiser la cellule i-1. On pourra l'utiliser pour localiser la suite de la liste.
Par exemple, pour insérer en position 2, il suffit de localiser la cellule cb en position 1 :
SI on reçoit un indice i de 0, on lance simplement un appel à inserer_tete().
SINON, il suffit de quatre opérations :
Etape 1 : Localiser le prédécesseur, la Cellule i-1. On utilisera éventuellement acces() si elle existe.
Exemple avec un 50 qu'on voudrait insérer en position 2, on devra localiser le prédécesseur : la cellule d'indice 1.
Etape 2 : Créer la nouvelle Cellule.
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.
Etape 4 : Faire pointer le prédécesseur vers la nouvelle Cellule.
Les étapes 2-3-4 sont à coût constant. Par contre, acces() est à coût linéaire (en 𝞞(n) ou 𝞗(i))
Coût : l'insertion en position i est donc à coût linéaire (en 𝞞(n) ou encore en 𝞗(i)).
Un autre exemple avec une liste 25-12-20-10-18-5 plus grande où on veut insérer une cellule contenant 20 en position 5 :
La localisation à partir de la tête du 18 en position 4 est une opération linéaire.
Notez que sii on connaissait déjà l'adresse de ce prédécesseur, il n'y aurait que des étapes à coût constant.
C - Implémentation dans une méthode
1
2
3
4
5
6
7
8
9
classListe:# ...definserer(self:'Liste',elt:'Element',i:'int VALIDE')->None:"""Rajoute une nouvelle cellule contenant elt en position i VALIDE de la liste NON VIDE"""ifi==0:self.inserer_tete(elt)else:pred=self.acces(i-1)# Etape 1 : recherche de la cellule i-1nouvelle=Cellule(elt,None)# Etape 2 : création de la cellulenouvelle.s=pred.s# Etape 3 : liaison nouvelle i vers ancienne ipred.s=nouvelle# Etape 4 : liaison i-1 vers nouvelle i
D - 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 en tant que nouvelle Fin actuelle revient donc à vouloir positionner la nouvelle cellule en position n et à chercher la cellule n-1 qui est la Fin actuelle.
2.3 - Insérer une cellule en FIN de liste
On veut faire l'équivalent de append() : insérer notre nouvelle cellule en tant que nouvelle FIN sans fournir le numéro d'indice de la Fin.
A - Principe
Il suffit de localiser la cellule de Fin actuelle.
SI la liste est vide, on lance simplement un appel à inserer_tete(), puisque la cellule qu'on veut placer en fin de liste fera aussi office de tête.
SINON, il suffit de trois opérations :
Etape 1 : localiser la Fin actuelle
On part de la Tête.
On avance TANT QUE la cellule actuelle a bien un successeur.
Etape 2 : on crée la nouvelle Cellule
Etape 3 : gestion du successeur. Inutile puisqu'on sait que le successeur est None.
Etape 3 : on relie l'ancienne Fin à la nouvelle
B - Coût
Encore une fois, c'est le coût de l'étape 1 qui pose problème : linéaire puisqu'on va devoir parcourir toutes les cellules de la Tête jusqu'à la Fin.
C - Implémentation dans une méthode
1
2
3
4
5
6
7
8
9
10
classListe:# ...definserer_fin(self:'Liste',elt:'Element')->None:"""Rajoute une nouvelle cellule de Fin contenant elt dans la liste"""ifself.est_liste_vide():self.inserer_tete(elt)else:pred=self.tete# Etape 1 : recherche de la cellule de Finwhilepred.sisnotNone:# TANT QUE pred n'est pas la fin actuellepred=pred.s# on passe à la cellule suivantenouvelle=Cellule(elt,None)# Etape 2 : création de la cellulepred.s=nouvelle# Etape 3 : on relie l'ancienne Fin à la nouvelle
D - 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.
C'est ce que nous allons faire pendant le TP.
3 - Liste chaînée sous forme d'objets : la suppression
le prédécesseur éventuel de la cellule qu'on veut supprimer : qui est la cellule juste avant ?
le successeur éventuel de la cellule qu'on veut supprimer : qui est la cellule juste derrière ?
De cette façon, on pourrait dire que le prédécesseur mène maintenant directement au successeur du successeur. Or, dans une liste chaînée, si on connaît le prédécesseur, on peut obtenir facilement le successeur.
CONCLUSION : il suffit de localiser le prédécesseur de la cellule qu'on va supprimer.
3.1 - Supprimer la cellule en position de TETE dans notre liste chaînée
A - Principe et coût de cette suppression
Il suffit de localiser la cellule de Tête actuelle.
Puisque la méthode n'aura rien à renvoyer, nous allons pouvoir en profiter pour lui faire renvoyer la valeur de la tête 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)
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
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 !
B - Implémentation dans une méthode
1
2
3
4
5
6
7
8
9
10
11
12
classListe:def__init__(self):self.tete=None# ....defsupprimer_tete(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êteself.tete=self.tete.s# Etape 2 : la tête devient le successeur de la têtereturnancienne_valeur# Etape 3 : on renvoie la valeur stockée
3.2 - Supprimer la cellule en position i dans notre liste chaînée
A - Principe et coût de cette suppression
Pour supprimer la cellule i, il suffit de localiser la Cellulei-1 et de chercher le successeur de son successeur. A partir de celle-ci, on pourra trouver le successeur de son successeur.
SI on reçoit un indice i de 0, on lance simplement un appel à supprimer_tete().
SINON, il suffit de quatre opérations :
Etape 1 : Trouver la Cellule en position i-1, le prédécesseur (coût linéaire)
Exemple avec la cellule en position 2 qu'on voudrait supprimer, il faut trouver la cellule 1.
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.
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
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.
B - Implémentation dans une méthode
1
2
3
4
5
6
7
8
9
10
11
12
13
classListe:# ...defsupprimer(self:'Liste',i:'int VALIDE')->'Element':"""Supprime la cellule en position i VALIDE et renvoie l'élément qui y était stocké"""ifi==0:# En réalité, on veut supprimer la Têtereturnself.supprimer_tete()else:pred=self.acces(i-1)# Etape 1 : recherche de la cellule i-1ancienne_valeur=pred.s.v# Etape 2 : on mémorise la valeur en position i actuellementpred.s=pred.s.s# Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeurreturnancienne_valeur# Etape 4 : on renvoie la valeur mémorisée
3.3 - Supprimer la cellule en fin de liste chaînée
A - Principe et coût
Il suffit de localiser le prédécesseur de la Fin.
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).
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.
Au final, on obtient donc ceci :
B - Implémentation dans une méthode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classListe:# ...defsupprimer_fin(self:'Liste NON VIDE')->'Element':"""Supprime la cellule de Fin d'une liste NON VIDE et renvoie l'élément qui y était stocké"""ifself.tete.sisNone:returnself.supprimer_tete()else:# Etape 1 : on cherche le prédécesseur de la Finpred=lst.tete# on part de la têtewhilepred.s.sisnotNone:# tant que c n'est pas le prédécesseur de la Finpred=pred.s# on passe à la cellule suivanteancienne_valeur=pred.s.v# Etape 2 : on mémorise la valeur en position i actuellementpred.s=None# Etape 3 : on fait pointer le prédécesseur sur Nonereturnancienne_valeur# Etape 4 : on renvoie la valeur mémorisée
D - 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.
E - On ne peut vraiment pas mieux ?
Si mais cela va rendre le code encode plus complexe que juste placer la référence de fin dans la liste.
Nous parlerons de deux solutions possibles en fin de TP pour voir comment parvenir à gérer à coût constant le suppression en fin de liste chaînée.
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.
classCellule:"""Cellule (valeur, successeur)"""def__init__(self,valeur:'Element',successeur:'Cellule|None'):self.v=valeur# Valeur ne peut pas être None si liste homogèneself.s=successeur# successeur vaut None si Cellule de Findefcontenu(self:'Cellule')->'Element':"""Renvoie le contenu de la Cellule"""return...defsuccesseur(self:'Cellule NON FIN')->'Cellule':"""Renvoie la Cellule suivante de self NON FIN"""return...defest_fin(self:'Cellule')->bool:"""Prédicat qui renvoie True si la Cellule n'a pas de successeur"""return...defnb_cellules(self:'Cellule')->int:"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""if...:# si il n'y a pas de successeurreturn...# il y a au moins la finelse:return1+...# on demande au successeur
Questions
L'attribut v peut-il référencer None dans cette implémentation si la liste est homogène ?
Que veut dire cette documentation 'Cellule|None' sur le type attendu du paramètre successeur ?
Quel est le nom d'une cellule dans l'attribut s référencera None dans cette implémentation ?
Dans le programme principal :
Créer une cellule cve contenant "Vendredi" qui n'a pas de successeur.
Créer une cellule cje contenant "Jeudi" qui mène à cve.
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.
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 !
classCellule:"""Cellule (valeur, successeur)"""def__init__(self,valeur:'Element',successeur:'Cellule|None'):self.v=valeur# Valeur ne peut pas être None si liste homogèneself.s=successeur# successeur vaut None si Cellule de Findefcontenu(self:'Cellule')->'Element':"""Renvoie le contenu de la Cellule"""returnself.vdefsuccesseur(self:'Cellule NON FIN')->'Cellule':"""Renvoie la Cellule suivante de self NON FIN"""returnself.sdefest_fin(self:'Cellule')->bool:"""Prédicat qui renvoie True si la Cellule n'a pas de successeur"""returnself.sisNonedefnb_cellules(self:'Cellule')->int:"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""if...:# si il n'y a pas de successeurreturn...# il y a au moins la finelse:return1+...# 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 nb_cellules() 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.
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 nb_cellules() qu'on notera d'abord juste nbC().
Voici le prototype :
1
defnbC(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)
Réaliser l'empilement des fonctions lorsqu'on lance l'appel cve.nbC().
cve.nbC() va renvoyer 1 + csa.nbC()
...
...
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éthodenb_cellules() dans le programme.
classCellule:"""Cellule (valeur, successeur)"""def__init__(self,valeur:'Element',successeur:'Cellule|None'):self.v=valeur# Valeur ne peut pas être None si liste homogèneself.s=successeur# successeur vaut None si Cellule de Findefcontenu(self:'Cellule')->'Element':"""Renvoie le contenu de la Cellule"""returnself.vdefsuccesseur(self:'Cellule NON FIN')->'Cellule':"""Renvoie la Cellule suivante de self NON FIN"""returnself.sdefest_fin(self:'Cellule')->bool:"""Prédicat qui renvoie True si la Cellule n'a pas de successeur"""returnself.sisNonedefnb_cellules(self:'Cellule')->int:"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""if...:# si il n'y a pas de successeurreturn...# il y a au moins la finelse:return1+...# on demande au successeur# Instructions du programme principalif__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)assertclu.nb_cellules()==7
...CORRECTION...
1
2
3
4
5
6
defnb_cellules(self:'Cellule')->int:"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""ifself.sisNone:# si il n'y a pas de successeurreturn1# il y a au moins la finelse:return1+self.s.nb_cellules()# on demande au successeur
08° Donner le coût (et la complexité) de la méthode nb_cellules() en considérant une séquence de n cellules dont on connait la tête. Justifier votre réponse.
Le coût est constant et la complexité en 𝞞(1)
Le coût est constant et la complexité en 𝞗(1)
Le coût est logarithmique et la complexité en 𝞞(lg n)
Le coût est logarithmique et la complexité en 𝞗(lg n)
Le coût est linéaire et la complexité en 𝞞(n)
Le coût est linéaire et la complexité en 𝞗(n)
Le coût est quadratique et la complexité en 𝞞(n2)
Le coût est quadratique et la complexité en 𝞗(n2)
Le coût est exponentielle et la complexité en 𝞞(en)
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.
classCellule:"""Cellule (valeur, successeur)"""def__init__(self,valeur:'Element',successeur:'Cellule|None'):self.v=valeur# Valeur ne peut pas être None si liste homogèneself.s=successeur# successeur vaut None si Cellule de Findefnb_cellules(self:'Cellule')->int:"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""ifself.sisNone:# si il n'y a pas de successeurreturn1# il y a au moins la finelse:return1+self.s.nb_cellules()# on demande au successeurclassListe:"""Liste chaînée muable"""def__init__(self):self.tete=Nonedefest_liste_vide(self:'Liste')->bool:returnself.teteisNonedefacces_tete(self:'Liste NON VIDE')->Cellule:"""Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""returnself.tetedefacces(self:'Liste NON VIDE',i:'int VALIDE')->Cellule:"""Renvoie l'adresse de la cellule i dans la liste NON VIDE"""c=self.acces_tete()# récupère la cellule de têtefor_inrange(i):# Faire i foisc=c.s# passe au successeurreturncdeflongueur(self:'Liste')->int:"""Renvoie la longueur de la liste"""ifself.est_liste_vide():return0else:returnself.tete.nb_cellules()# Instructions du programme principalif__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)assertclu.nb_cellules()==7lst = Liste()
lst.tete=cluassertlst.acces(2).v=="Mercredi"
...CORRECTION...
10° Remplacer uniquement le programme principal pour celui-ci.
"""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)"""classCellule:"""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 a_successeur(self:'Cellule') -> bool # coût constant est_fin(self:'Cellule') -> bool # coût constant nb_cellules(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èneself.s=successeur# successeur vaut None si Cellule de Fin# Méthodes ayant un lien avec une primitive de liste chaînéedefcontenu(self:'Cellule')->'Element':"""Renvoie le contenu de la Cellule"""returnself.vdefsuccesseur(self:'Cellule NON FIN')->'Cellule':# coût constant"""Renvoie la Cellule suivante de self NON FIN"""returnself.s# Autres méthodesdefa_successeur(self:'Cellule')->bool:# coût constant"""Prédicat qui renvoie True si le successeur de notre Cellule est bien une Cellule"""returnself.sisnotNone# ou return not self.s is Nonedefest_fin(self:'Cellule')->bool:# coût constant"""Prédicat qui renvoie True si la Cellule n'a pas de successeur"""returnself.sisNone# ou même return not self.a_successeur()defnb_cellules(self:'Cellule')->int:# Coût linéaire 𝞗(n)"""Renvoie le nombre de cellules dans la chaîne à partir de cette cellule"""ifself.sisNone:# si il n'y a pas de successeurreturn1# il y a au moins la finelse:return1+self.s.nb_cellules()# on demande au successeur...classListe:"""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 ------------------- est_liste_vide(self:'Liste') -> bool # coût constant inserer_tete(self:'Liste', elt:'Element') -> None # coût constant supprimer_tete(self:'Liste NON VIDE') -> 'Elt' # coût constant acces_tete(self:'Liste NON VIDE') -> Cellule # coût constant premier(self:'Liste NON VIDE') -> Element # coût constant Méthodes primitives (extension) ------------------------------- acces_fin(self:'Liste NON VIDE') -> Cellule # coût constant inserer_fin(self:'Liste', elt:'Element') -> None # Coût ??? supprimer_fin(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'attributself.fin=None# Seule une liste vide par avoir cettte valeur d'attribut# Méthodes-primitives de liste chaînée basiquedefest_liste_vide(self:'Liste')->bool:# coût constantreturnself.teteisNonedefinserer_tete(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 listedefsupprimer_tete(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éedefacces_tete(self:'Liste NON VIDE')->Cellule:# coût constant"""Renvoie l'adresse de la cellule de Tête dans la liste NON VIDE"""returnself.tetedefpremier(self:'Liste NON VIDE')->'Element':# coût constant"""Renvoie la valeur de la cellule de Tête dans la liste NON VIDE"""returnself.tete.v# Méthodes-primitives de l'extentsion liste chaînée Tête et Findefacces_fin(self:'Liste NON VIDE')->Cellule:# coût constant"""Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE"""passdefinserer_fin(self:'Liste',elt:'Element')->None:# Coût ???"""Rajoute une nouvelle cellule de Fin contenant elt dans la liste"""passdefsupprimer_fin(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éthodesdefacces(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.acces_tete()# récupère la cellule de têtefor_inrange(i):# Faire i foisc=c.s# passe au successeurreturncdefinserer(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"""ifi==0:self.inserer_tete(elt)else:pred=self.acces(i-1)# Etape 1 : recherche de la cellule i-1nouvelle=Cellule(elt,None)# Etape 2 : création de la cellulenouvelle.s=pred.s# Etape 3 : le successeur de la nouvelle est le successeur du prédécesseurpred.s=nouvelle# Etape 4 : le successeur du prédécesseur est la nouvelle celluledefsupprimer(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é"""ifi==0:# En réalité, on veut supprimer la Têtereturnself.supprimer_tete()else:pred=self.acces(i-1)# Etape 1 : recherche de la cellule i-1ancienne_valeur=pred.s.v# Etape 2 : on mémorise la valeur en position i actuellementpred.s=pred.s.s# Etape 3 : on fait pointer le prédécesseur sur le successeur de son successeurreturnancienne_valeur# Etape 4 : on renvoie la valeur mémoriséedeflongueur(self:'Liste')->int:# Coût linéaire 𝞗(n) """Renvoie la longueur de la liste"""ifself.est_liste_vide():return0else:returnself.tete.nb_cellules()defafficher(self:'Liste')->None:# Coût linéaireactuellement=self.acces_tete()whileactuellementisnotNone:print(f"{actuellement.v} -> ",end='')actuellement=actuellement.sprint('x')# Programmeif__name__=='__main__':deftester_inserer_tete():print("Tests de inserer_tete())...",end="")lst=Liste()lst.inserer_tete(5)assertlst.tete==lst.finlst.inserer_tete(10)assertlst.tete!=lst.finassertlst.tete.v==10assertlst.fin.v==5lst.inserer_tete(20)assertlst.tete!=lst.finassertlst.tete.v==20assertlst.fin.v==5print("ok")deftester_supprimer_tete():print("Tests de supprimer_tete())...",end="")lst=Liste()lst.inserer_tete(5)lst.inserer_tete(10)lst.inserer_tete(20)lst.supprimer_tete()assertlst.tete!=lst.finassertlst.tete.v==10assertlst.fin.v==5lst.supprimer_tete()assertlst.tete==lst.finassertlst.fin.v==5lst.supprimer_tete()assertlst.tete==lst.finassertlst.fin==Noneprint("ok")deftester_inserer_fin():print("Tests de inserer_fin())...",end="")lst=Liste()lst.inserer_fin(5)assertlst.tete==lst.finlst.inserer_fin(10)assertlst.tete!=lst.finassertlst.tete.v==5assertlst.fin.v==10lst.inserer_fin(20)assertlst.tete!=lst.finassertlst.tete.v==5assertlst.fin.v==20lst.inserer_tete(200)assertlst.tete!=lst.finassertlst.tete.v==200assertlst.fin.v==20print("ok")deftester_supprimer_fin():print("Tests de supprimer_fin())...",end="")lst=Liste()lst.inserer_tete(5)lst.inserer_tete(10)lst.inserer_tete(20)lst.inserer_tete(200)lst.supprimer_fin()assertlst.tete!=lst.finassertlst.tete.v==200assertlst.fin.v==10lst.supprimer_tete()assertlst.tete!=lst.finassertlst.tete.v==20assertlst.fin.v==10lst.supprimer_fin()assertlst.tete==lst.finassertlst.fin.v==20lst.supprimer_fin()assertlst.tete==lst.finassertlst.fin==Noneprint("ok")#tester_inserer_tete()#tester_supprimer_tete()#tester_inserer_fin()#tester_supprimer_fin()
...CORRECTION...
1
2
3
4
5
definserer_tete(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 cellulenouvelle.s=self.tete# Etape 2 : on relie la nouvelle cellule à l'"ancienne" Têteself.tete=nouvelle# Etape 3 : modification de la liste
13° Répondre aux questions suivantes :
Une liste vide pointe-t-elle au même endroit sa Tête et sa Fin ?
Une liste de un élément pointe-t-elle au même endroit sa Tête et sa Fin ?
Une liste de deux éléments ou plus pointe-t-elle au même endroit sa Tête et sa Fin ?
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste vide ?
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de un élément ?
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de deux éléments ou plus ?
...CORRECTION...
Une liste vide pointe-t-elle au même endroit sa Tête et sa Fin ?
Oui, les deux attributs pointent vers None.
Une liste de un élément pointe-t-elle au même endroit sa Tête et sa Fin ?
Oui, les deux attributs pointent vers la seule cellule présente.
Une liste de deux éléments ou plus pointe-t-elle au même endroit sa Tête et sa Fin ?
Non, chaque attribut pointe vers une cellule différente.
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste vide ?
Oui, fin devra pointer vers la nouvelle cellule.
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de un élément ?
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 de sa place de Tête mais joue toujours le rôle de Fin. C'est la Tête qui devra être modifiée.
En déduire si on doit mettre à jour l'attribut fin si on utilise inserer_tete() sur une liste de deux éléments ou plus ?
Non plus, la fin reste la fin.
14° Compléter alors maintenant la méthode inserer_tete() 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.
Sans attribut Fin :
1
2
3
4
5
definserer_tete(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 cellulec.s=self.tete# Etape 2 : on relie la nouvelle cellule à l'"ancienne" Têteself.tete=c# Etape 3 : modification de la liste
Avec l'attribut Fin :
1
2
3
4
5
6
7
definserer_tete(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 celluleifself.est_liste_vide():# Etape supplémentaire si la liste est vide initialementself.fin=cc.s=self.tete# Etape 2 : on relie la nouvelle cellule à l'"ancienne" Têteself.tete=c# Etape 3 : modification de la liste
15° Compléter la méthode supprimer_tete().
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 avons besoin de mettre à jour l'attribut fin lorsque la liste possédait un dernier élément et qu'on vient de le supprimer : supprimer la tête revient à supprimer la fin. L'attribut fin doit alors pointer vers None.
...CORRECTION...
.
1
2
3
4
5
6
7
defsupprimer_tete(self:'Liste NON VIDE')->'Elt':# coût constant"""Supprime la tête et renvoie son contenu"""memoire=self.tete.v# Etape 1 : on mémorise l'ancienne valeurself.tete=self.tete.s# Etape 2 : la tête devient le successeur de l'ancienne têteifself.est_liste_vide():# si la liste est maintenant VIDEself.fin=Nonereturnmemoire
16° Compléter la méthode acces_fin() pour la forme (facile) puis la méthode inserer_fin() (moyen). Donner également les coûts de ces méthodes.
Si la liste est vide, on peut faire appel à inserer_tete() 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 cellule à 2 cellules ?
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 à inserer_tete(), 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
defacces_fin(self:'Liste NON VIDE')->Cellule:# coût constant"""Renvoie l'adresse de la cellule de Fin dans la liste NON VIDE"""returnself.findefinserer_fin(self:'Liste',elt:'Element')->None:# Coût ???"""Rajoute une nouvelle cellule de Fin contenant elt dans la liste"""ifself.est_liste_vide():# Si la liste est vide, on fait appelself.inserer_tete(elt)else:nouvelle=Cellule(elt,None)# Etape 1 : on crée la nouvelle Celluleself.fin.s=nouvelle# Etape 2 : on relie l'ancienne Fin à la nouvelleself.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 cette opération de suppression. Dans quel cas va-t-on juste faire appel à supprimer_tete() ?
Compléter la méthode supprimer_fin() (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 à supprimer_tete() 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
defsupprimer_fin(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é"""ifself.tete==self.fin:# si la liste ne possède qu'une seule cellulereturnself.supprimer_tete()# on demande à l'autre fonction de faire le travailelse:# Etape 1 : on cherche le prédécesseur de la Finc=self.tete# on part de la têtewhilec.s.sisnotNone:# tant que c n'est pas le prédécesseur de la Finc=c.s# on passe à la cellule suivanteancienne_valeur=c.s.v# Etape 2 : on mémorise la valeur de Fin actuellec.s=None# Etape 3 : on fait pointer le prédécesseur sur Noneself.fin=c# Etape 4 : on met la liste à jourreturnancienne_valeur# Etape 5 : on renvoie la valeur mémorisée
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 :
Etape 2 : recopie des éléments de gauche
Il faut déplacer un par un les 20 000 éléments du premier tableau.
Etape 3 : recopie des éléments de droite
Puis on déplace les 20 000 éléments du deuxième tableau.
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 :
18° Mettre cette méthode concatener_problematique() en mémoire. Voici son prototype :
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
defconcatener_problematique(self:'Liste',droite:'Liste')->'Liste':"""Renvoie une liste qui est la concaténation des listes self et liste_droite"""nouvelle=Liste()# ?ifnotself.est_liste_vide()andnotdroite.est_liste_vide():# ?nouvelle.tete=self.tete# ?self.fin.s=droite.tete# ?nouvelle.fin=droite.fin# ?elifself.est_liste_vide()andnotdroite.est_liste_vide():# ?nouvelle.tete=droite.tete# ?nouvelle.fin=droite.fin# ?elifdroite.est_liste_vide()andnotself.est_liste_vide():# ?nouvelle.tete=droite.tete# ?nouvelle.fin=droite.fin# ?returnnouvelle# ?
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
defconcatener_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 Listeifnotself.est_liste_vide()andnotdroite.est_liste_vide():# si aucune des deux listes n'est vide nouvelle.tete=self.tete# nouvelle a la même Tête que gaucheself.fin.s=droite.tete# on fait pointer la fin de gauche sur la tête de droitenouvelle.fin=droite.fin# nouvelle a la même Fin que droiteelifself.est_liste_vide()andnotdroite.est_liste_vide():# si seule la liste de gauche est videnouvelle.tete=droite.tete# nouvelle a la même Tête que droitenouvelle.fin=droite.fin# nouvelle a la même Fin que droiteelifdroite.est_liste_vide()andnotself.est_liste_vide():# si seule la liste de droite est videnouvelle.tete=droite.tete# nouvelle a la même Tête que gauchenouvelle.fin=droite.fin# nouvelle a la même Tête que gauchereturnnouvelle# 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...
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 ?
Attention aux concaténations muables de Listes
La muabilité fait gagner de la place mémoire puisqu'on ne stocke pas de multiples versions de presque les mêmes données.
Mais on perd en sécurité car on peut modifier des choses sans s'en rendre compte, par effet de bord.
Premier problème :
Voici ce qui se passe si on concatène de cette manière très muable une liste lst1 contenant 1->-5->7 à la liste lst2 contenant 10->-20->30.
flowchart LR
A[lst1] --> B(1) --> C(5) --> D(7)
E[lst2] --> F(10) --> G(20) --> H(30)
D --> F
Z[lst3=lst1+lst2] --> B
Nous avons obtenu ce que nous voulions avec notre concaténation muable. lst3 référence maintenant 1->-5->7->10->20->30.
Le problème, c'est que c'est aussi le cas de lst1...
Deuxième problème :
Imaginons qu'on veuille alors concaténer lst2 à la liste lst3 contenant 100->-400->800
flowchart LR
A[lst1] --> B(1) --> C(5) --> D(7)
E[lst2] --> F(10) --> G(20) --> H(30)
I[lst3] --> J[100] --> K[400] --> M[800]
D --> F
H --> J
Z[lst3] --> B
Y[lst4=lst2+lst3] --> F
Moralité : on a modifié lst1 en agissant sur autre chose de cette liste... lst1 référence maintenant 1->-5->7->10->20->30->100->400->800.
Troisème problème :
Que se passerait-il si on voulait supprimer la tête de la liste 2 ?
En supprimant la tête contenant 10, on supprime également la liaison avec la cellule contenant 7.
flowchart LR
A[lst1] --> B(1) --> C(5) --> D(7)
E[lst2] --> G(20) --> H(30)
I[lst3] --> J[100] --> K[400] --> M[800]
H --> J
Z[lst3] --> B
Y[lst4] --> F(10)
Moralité : on a modifié lst1 en agissant sur autre chose de cette liste... lst1 référence maintenant 1->-5->7. Idem pour lst4...
Comme vous le voyez, il faut être très prudent avec ces listes hautement muables.
CONCLUSION : manipuler directement les cellules et les liaisons est posible et permet de réaliser des choses très rapidement mais cela demande de vraiment réflechir à ce qui est fait.
Complément Hors programme
On comprendra bien que :
Les opérateurs == et != permettent de comparer les contenus.
Les opérateurs is et is not permettent de comparer les adresses et donc de savoir s'il s'agit d'alias ou pas.
a is b revient donc à noter id(a) == id(b)
Dans les sujets de BAC, vous ne devriez donc voir apparaître que == et !=.