Implémenter une Liste Chainée
Si on résume les épisodes précédents :
- Le type abstrait LISTE consiste en une séquence d'éléments ordonnés et en un ensemble de fonctions nommées interface permettant d'y lire et insérer des éléments.
- On peut implémenter cette LISTE comme un simple tuple (tête, queue) mais les coûts en lecture et insertion sont linéaires dans le pire des cas.
- On peut implémenter cette LISTE sous forme d'un tableau et dans ce cas, la lecture a un coût constant mais l'insertion reste à coût linéaire.
Nous allons voir aujourd'hui comment parvenir à créer une implémentation permettant d'insérer des éléments de manière efficace (constant dans certains cas), mais la lecture sera linéaire...
Aujourd'hui, nous allons encore devoir insérer et supprmier la tête puis agir sur n'importe quel élément, si possible.
Prérequis : nous allons utiliser la programmation objet. Rien de bien méchant, mais c'est mieux d'avoir vu ces notions du coup.
1 - Liste chaînée
Qu'est-ce qu'un tableau ?
Nous avons vu que le tableau était une implémentation possible du type LISTE. Une implémentation qui permet la lecture des éléments à coût constant.
L'idée derrière le tableau est de placer les éléments les uns derrière les autres "en mémoire" de façon à trouver facilement leurs localisations par un simple calcul lié à leur numéro d'index. On parle de zones contiguës.
Remarque : l'implémentation réelle en machine va dépendre du langage de programmation.
Si on veut insérer un nouvel élément en index 2, il va donc falloir d'abord déplacer le contenu de l'index 2 vers l'index 3 puis insérer le nouveau contenu dans l'index 2.
1 - On "déplace" l'ancien élément
2 - On insère le nouvel élément
Insérer un élément prend donc du temps car si on veut placer un nouvel élément en position 0 par exemple, il va falloir déplacer le contenu du 2 en 3, le contenu du 1 en 2, le contenu du 0 en 1 puis on pourra enfin placer notre nouvel élément sur l'index 0... C'est long car c'est linéaire....
L'avantage du tableau par contre, c'est qu'on trouve très rapidement le contenu associé à un index. Là, c'est à coût constant.
Liste chaînée
Une liste chaînée est une liste composée de cellules ou de mailles, comme une chaîne en métal.
Chaque maillon (ou cellule) est associé à au moins deux informations :
- Le contenu de la cellule
- L'adresse ou l'identifiant de la prochaine cellule
Et c'est tout.
Du coup, la représentation de la liste donnerait cette fois quelque chose comme ceci :
Ici, j'ai placé les maillons (ou cellules) les uns derrière les autres, mais rien ne nous y oblige.
Et si je veux insérer un nouvel élément ? Il suffit de rediriger la lecture vers le nouvel élément et de créer un lien entre notre nouvel élément et le suivant dans la liste. Exemple ci-dessous : je fais pointer B vers le nouvel élément.
Du coup, il n'y a toujours que 2 étapes pour insérer un nouvel élément, quelque soit la longueur de la liste. Nous devrions donc obtenir sur nos implémentations futures, un coût d'insertion constant.
Une grosse liste :
Le changement de tête ne nécessite que deux opérations avec une liste chaînée (alors qu'avec un tableau, il fallait déplacer toutes les cases avant de placer l'index 0) :
Le désavantage lors de l'implémentation (si on implémente juste cette idée basique) va être la lecture : pour lire le contenu de la 5e cellule, il faut passer par la lecture des précédentes : on commence par aller à la tête qui va nous dire où aller ensuite, ect...
Comme pour les autres types, nous verrons qu'il existe plusieurs manières d'implémenter réellement cette idée abstraite.
2 - Cellule en tant que Classe
Voyons comment réaliser ce type de structure de données. Nous allons travailler ici avec le type le plus simple de liste chaînée, qu'on nomme liste simplement chaînée.
Avant d'implémenter la Liste dans une Classe, il faut commencer par implémenter... la Cellule.
01° Créer une classe Cellule qui peut recevoir deux paramètres lors de l'appel du constructeur : un paramètre valeur et un paramètre suivant. Les deux valeurs transmises devront être stockées dans deux attributs nommés v et s.
...CORRECTION...
1
2
3
4 | |
02° Tester le constructeur de votre Classe Cellule avec quelques créations.
Par exemple :
>>> c1 = Cellule(5, None)
>>> c2 = Cellule(15, c1)
>>> c3 = Cellule(25, c2)
>>> c4 = Cellule(35, c3)
03° Représenter sur feuille la structure séquentielle linéaire créée par les instructions précédentes.
...CORRECTION...
04° Vérifions les contenus en partant de la Cellule de tête qui est donc ici contenue dans la variable c4.
Nous allons à chaque fois utiliser l'attribut s qui contient ... l'adresse de la cellule suivante. On peut donc y trouver des attributs s et v également !
>>> # voir le contenu de la tête
>>> c4.v
35
>>> # voir le contenu suivant
>>> c4.s.v
25
>>> # voir le contenu suivant
>>> c4.s.s.v
15
>>> # voir le contenu suivant
>>> c4.s.s.s.v
5
Notre Cellule possède encore un léger problème : on pourrait lui transmettre n'importe quoi sur le paramètre suivant, pas nécessairement quelque chose de comptatible avec l'attribut s qui doit contenir un objet Cellule ou None. On pourrait donc imposer en programmation défensive que ce paramètre soit bien l'instance d'une Cellule ou None. Ce sont en effet les deux possibilités.
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
05° Mettre cette version en mémoire.
Utiliser alors les instructions suivantes :
>>> a = Cellule('Marie-Antoinette', None)
>>> b = Cellule('Louis XVI', a)
>>> c = Cellule('Louis XV', 'Louis XVI')
assert isinstance(suivant, Cellule) or suivant == None
AssertionError
Expliquer ce qui provoque l'erreur : est-ce la documentation de la ligne 8 ? L'assertion de la ligne 11 ?
...CORRECTION...
La documentation n'a rien à voir dans cette histoire : il s'agit juste d'un texte qui permet d'informer l'utilisateur de votre Classe.
C'est bien l'utilisation du mot-clé assert qui permet de stopper le programme (en levant une exception) si l'expression située derrière n'est pas évaluée à True.
Attention : s n'est pas la queue mais un élément de la queue. Ce qu'on nomme queue est bien l'ensemble des valeurs derrière la tête, pas juste la première.
Bien. Nous sommes capables de créer des Cellules et les lier entre elles. Mais comment lire cette séquence de Cellules ?
Pour faire cela, nous allons créer une fonction renvoyerCelluleFinale récursive qui aura la charge d'afficher progressivement les valeurs des cellules et de renvoyer au final la référence de la dernière Cellule de la séquence, celle qui ne possède pas d'attribut s.
Si on part ici de la tête qui contient le string "Lundi", on devrait lire la séquence des jours et renvoyer la référence de la dernière cellule, celle qui contient "Dimanche".
06° Travaillons maintenant sur la fonction renvoyerCelluleFinale.
Voici le prototype (pour information):
1 | |
C'est une méthode récursive. Le principe est le suivant :
- Si l'attribut s de cette cellule est vide : renvoyer
cellule(la Cellule en cours d'étude) En effet, s'il n'y a pas de suite, c'est bien que cellule est la dernière. - Sinon : renvoyer
renvoyerCelluleFinale(cellule.s)
Questions
- Quelle est la condition d'arrêt ?
- Quel est le cas de base ?
- Comment parvient-on à avancer dans les Cellules ? Que fait l'appel récursif ?
...CORRECTION...
La condition d'arrêt correspond au fait que la Cellule en cours n'ai pas de successeur : son attribut s, comme suivant, contient None.
Le cas de base revient alors à fournir l'adresse de cette dernière Cellule.
On parvient à avancer car on appelle à nouveau renvoyerCelluleFinale mais en fournissant en argument la référence de la Cellule suivante.
07° Compléter la fonction renvoyerCelluleFinale.
Vous rajouterez un print en début de fonction pour afficher le contenu de la Cellule. Nous supprimerons cette fonctionnalité ensuite. Mais c'est pratique pour voir si la fonction fonctionne bien.
Voici le prototype :
1 | |
Pour vérifier si votre fonction fonctionne, rajoutez ce jeu de test à la fin de votre programme. J'utilise ici juste une suite d'instructions qui ne vont s'activer que lors de l'activation directe de notre programme plutôt que le module doctest.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | |
Nous savons donc maintenant obtenir la dernière Cellule d'une séquence de Cellules.
derniere = renvoyerCelluleFinale(lu)
derniere
<__main__.Cellule object at 0x7fca115ec780>
derniere.v
'Dimanche'
derniere.s
Notre print n'était là que pour montrer qu'on lit les Cellules de façon séquentielle. Pour l'instant, on ne peut atteindre la fin qu'en passant par toutes les Cellules, une par une.
Par contre, c'est un peu dommage : nous avons créé une fonction, alors que nous avons créé les cellules sous forme d'objet. Autant intégrer directement cette fonctionnalité dans une méthode non ?
Voici le code intégrant la méthode renvoyerCelluleFinale.
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
On peut voir que l'écriture d'un appel récursif sur la méthode est un peu différente puisqu'on place finalement l'objet sur lequel on va agir devant la méthode plutôt qu'à l'intérieur des parenthèses :
Un rappel si vous avez du mal à voir comment fonctionne les appels récursifs via la méthode : lorsqu'on lance la première ligne ci-dessous, c'est un peu comme si l'interpréteur Python réalisait la seconde.
return self.s.renvoyerCelluleFinale()
return Cellule.renvoyerCelluleFinale(self.s)
3 - Liste chaînée en tant que Classe
08° Compléter la classe Liste. Elle doit posséder un seul attribut qu'on nommera tete. Nommer également le paramètre de la méthode d'initialisation tete.
On veuillera avec une assertion à ce que tete soit bien une instance de Cellule ou None. Vous lui donnerez d'ailleurs une valeur par défaut None.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | |
Remarque 1 : Je ne placerai plus les documentation lors des questions intermédiaires. Elles sont par contre dans les versions finalisées. Cela rendra le code moins long, et comme vous êtes en plein dedans, la documentation peut parfois faire too much.
Remarque 2 : La correction de la question précédente utilise type plutôt que isinstance pour vérifier que l'objet reçu est bien une instance. C'est juste pour vous montrer qu'on peut tester cela de deux façons.
09° Pour créer une liste, il faut pour l'instant créer les cellules manuellement puis créer la liste. Voici un programme qui vous permettra de créer une petite liste sans avoir à tout taper à chaque fois.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | |
Nous aurions pu simplement taper ceci dans le Shell de Python.
>>> a = Cellule('Marie-Antoinette', None)
>>> b = Cellule('Louis XVI', a)
>>> c = Cellule('Louis XV', b)
>>> lis1 = Liste(c)
Questions
Une fois, la liste du programme en mémoire,
- Comment obtenir dans le Shell le contenu de la tête en utilisant l'objet lis1 ?
- Comment obtenir le contenu de l'élément suivant en utilisant l'objet lis1 ?
- Comment obtenir le contenu de l'élément encore derrière en utilisant l'objet lis1 ?
...CORRECTION...
>>> lis1.tete.v
>>> lis1.tete
<__main__.Cellule object at 0x7f03e9774a20>
>>> lis1.tete.v
'Louis XV'
>>> lis1.tete.s.v
'Louis XVI'
>>> lis1.tete.s.s.v
'Marie-Antoinette'
Voyons maintenant comment réaliser l'interface. Nous allons chercher à réaliser l'interface permettant de gérer des listes de façon "souple", à savoir insérer et lire des éléments où on veut. Mais nous allons néanmoins réaliser les fonctions ne gérant que la tête au départ.
Comme nous sommes sur une implémentation objet, nous allons utiliser une version mutable de la liste. Le code obtenu sera plus facile à créer. Mais nous pourrions en réaliser une version non mutable si nécessaire.
Interface voulue : Liste "souple", version mutable
nouvelleListe() -> Liste: on crée une nouvelle liste vide.estVide(lst:Liste) -> bool: renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.insererPosition(x:Elt, lst:Liste, position:int) -> None: on modifie sur place la liste : l'élément fourni x est maintenant l'élément de la liste situé en position position. On prendra ici un système de position lié à un index commençant à 0.supprimerPosition(lst:Liste, position:int) -> None: on modifie sur place la liste : l'élément en position position est supprimé, rendant la liste moins longue.lirePosition(lst:Liste, position:int) -> Elt: on renvoie l'élément stocké en position position.
listeA = nouvelleListe()
Le contenu de listeA est alors une liste vide.
listeA = nouvelleListe()
estVide(listeA) va donc renvoyer l'équivalent de True.
listeA peut être représentée par (12, 15, 18, 4)
inserer(5, listeA, 2)
listeA peut alors être représentée par (12, 15, 5, 18, 4).
listeA peut être représentée par (12, 15, 18, 4)
supprimer(listeA, 1)
listeA peut alors être représentée par (12, 18, 4).
listeA peut être représentée par (12, 15, 18, 4)
reponse = lirePosition(listeA, 1)
reponse peut alors être représentée par 15.
10° Créer la fonction d'interface nouvelleListe. Votre fonction devra bien entendu travailler avec la classe Liste.. L'utilisateur pourra ainsi créer une nouvelle liste sans avoir à utiliser directement la fonction constructeur Liste.
nouvelleListe() -> Liste : on crée une nouvelle liste vide.
listeA = nouvelleListe()
Le contenu de listeA est alors une liste vide.
...CORRECTION...
Le code de la fonction :
1
2 | |
Le code dans sa totalité :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | |
11° Créer la fonction d'interface estVide. Votre fonction devra bien entendu travailler avec la classe Liste. On ira lire directement son attribut tete, sans respect aucun pour l'encapsulation de l'objet.
La fonction peut contenir une seule ligne de code.
estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.
...CORRECTION...
1
2 | |
12° Créer une fonction d'interface insererTete qui devra
- mémoriser dans une variable l'adresse de l'ancienne tête ,
- créer une instance de Cellule dont la valeur stockée est x et qui pointe en sortie vers l'ancienne tête
- modifier l'attribut tete de la Liste pour qu'il corresponde bien à notre nouvelle instance de Cellule.
insererTete(x:Elt, lst:Liste) -> None : on modifie sur place la liste : l'élément fourni x est maintenant l'élément de tête.
listeA peut être représentée par (12, 15, 18, 4)
insererTete(5, listeA)
listeA peut alors être représentée par (5, 12, 15, 18, 4).
Un exemple d'utilisation qui devrait fonctionner sur votre fonction :
>>> lst1 = nouvelleListe()
>>> insererTete(5, lst1)
>>> lst1.tete.v
5
>>> lst1.tete.s
On voit donc ici qu'on ne dispose que d'une tête : l'élément suivant ne contient rien.
...CORRECTION...
Deux versions pour le prix d'une. Dans la première, on exécute l'une des étapes sur chaque ligne. La deuxième est plus courte, on fait tout progressivement aussi mais sur une seule ligne. En terme de clarté, c'est à vous de voir.
1
2
3
4
5
6
7 | |
Pour réaliser la vraie fonction insererPosition, il va falloir bien réflechir.
Imaginons qu'on veuille insérer une Cellule en position 2.
Il faudra :
- Mémoriser l'adresse nommée predecesseur de l'élément en position 1 (celle de contenu B ici)
- Mémoriser l'adresse nommée successeur de l'élément en position 2 actuellement (celle de contenu C ici).
- Créer une nouvelle cellule nouvelle (celle de contenu Z ici) et la faire pointer vers successeur.
- Faire pointer predecesseur sur notre nouvelle cellule.
Avant d'inserer la nouvelle Cellule en position2, il faut mémoriser les identifiants des cellules contenant B (predecesseur, "index" 1) et C (successeur, "index" 2).
Après modification,
Quelques exemples :
- Si je veux insérer en position 1 : predecesseur est l'élément en position 0, soit ... la tête de la liste.
- Si je veux insérer en position 2 : predecesseur sera l'élément en position 1. Il faut donc faire un bond en avant depuis la tête.
- Si je veux insérer en position 3 : predecesseur sera l'élément en position 2. Il faut donc faire un bond en avant depuis la tête.
- Si je veux insérer en position
position: predecesseur sera la Cellule en positionposition - 1. Il faut donc faire un bond en avant depuis la tête.
Nous allons voir que le problème de la fonction d'interface telle qu'elle est définie ici ne vient pas de l'insertion mais de la recherche de la bonne Cellule !
13° Voici une fonction d'interface insererPosition.
insererPosition(x:Elt, lst:Liste, position:int) -> None : on modifie sur place la liste : l'élément fourni x est maintenant l'élément de la liste situé en position position. On prendra ici un système de position lié à un index commençant à 0.
listeA peut être représentée par (12, 15, 18, 4)
inserer(5, listeA, 2)
listeA peut alors être représentée par (12, 15, 5, 18, 4).
Lorsqu'on veut insérer ailleurs qu'à la tête, cette fonction va
- partir de la tête, effectuer
position -1saut vers la cellule suivante, et mémoriser l'identifiant de cette cellule dans predecesseur - mémoriser dans successeur la réference de la cellule actuellement à la suite de predecesseur.
- créer la nouvelle Cellule, et la faire pointer vers successeur
- modifier predecesseur pour qu'elle pointe vers nouvelle.
Question : analyser le code pour parvenir à identifier les lignes où sont effectuées précisement les actions 1 à 4 précédentes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | |
...CORRECTION...
- Lignes 46-47-48 : tenter de partir de la tête pour aboutir à la Cellule en position (position -1) et la mémoriser dans predecesseur
- Ligne 50 : on mémorise ensuite la réference de la cellule successeur en utilisant justement l'attribut s. On obtient donc None ou une vraie Cellule.
- Ligne 51 : Ensuite, on va créer la nouvelle Cellule et la faire pointer vers successeur et
- Ligne 52 : modifier la Cellule predecesseur pour qu'elle pointe vers nouvelle.
Plus court ?
Encore une fois, on peut réaliser un code plus court. Mais est-il plus compréhensible ? Ca dépend à quel point vous êtes à l'aise.
1
2
3
4
5
6
7
8
9
10
11 | |
14° L'insertion pure ne concerne que les lignes suivantes
50
51
52 | |
Ici le coût est bien constant. Par contre, que peut-on dire du coût de la recherche de la Cellule predecesseur dans le pire des cas ?
46
47
48 | |
Au total, que peut-on alors dire du coût de l'insertion ?
...CORRECTION...
Comme on doit lire les cellules une par une avant de pouvoir insérer, on retrouve sur la fonction en elle-même un coût linéaire dans le pire des cas !
C'est un peu décevant du coup...
En réalité, si l'utilisateur peut manipuler directement l'insertion en fournissant par exemple la référence de la Cellule predecesseur, on pourrait retrouver un coût constant.
C'est ce que vont certaines implémentations.
15° Compléter la fonction d'interface insererApres.
Prototype :
insererApres(x:Elt, lst:Liste, predecesseur:Cellule) -> Cellule : on modifie sur place la liste : l'élément x fourni est inséré dans une Celule qui est placée juste après la Cellule predecesseur. On renvoie la référence de la cellule qu'on vient de créer. Cela permettra de stocker la référence si elle est importante
Le paramètre predecesseur aura None comme valeur par défaut de façon à ne pas fournir de cellule si on sait que la liste est encore vide. Dans ce cas, la fonction est équivalente à insererTete.
Exemple
>>> lst1 = nouvelleListe()
>>> a = insererApres('Alice', lst1)
La liste abstraite correspondante serait maintenant ('Alice')
>>> b = insererApres('Bob', lst1, a)
La liste abstraite correspondante serait maintenant ('Alice', 'Bob')
>>> c = insererApres('Clark', lst1, a)
La liste abstraite correspondante serait maintenant ('Alice', 'Clark', 'Bob')
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | |
Comme vous pouvez le voir, une fois qu'on dispose des références, on retrouve une insertion à coût constant : il y a simplement 3 instructions lignes 8-9-10 dans la correction.
En réalité, la grande force des listes ne vient pas de l'insertion d'une Cellule individuelle (souvent on ne connait pas sa référence) mais de l'insertion d'une liste à la suite d'une autre liste. On parlera de concaténation de listes, comme avec les strings.
Imaginons qu'on dispose des deux listes. L'une de 20 000 éléments et l'autre de 20 000 éléments également. Si on désire insérer la deuxième liste après la première liste, cela risque d'être compliqué avec des tableaux :
D'abord, il faut réserver une nouvelle place mémoire de 40 000 places :
Ensuite, il faut déplacer un par un les 20 000 éléments du premier tableau.
Puis on déplace les 20 000 éléments du deuxième tableau.
16° Sur le cas ci-dessus, en quoi l'implémentation sous forme de liste chaînée va permettre de réalisrer plus rapidement la jonction de nos deux listes précédentes ?
...CORRECTION...
On part ici de deux listes chaînées ayant chacune leur propre tête.
Il suffit alors de connaître la dernière Cellule de la première liste (au pire, 20 000 lectures, c'est toujours mieux que 40 000 déplacements avec les tableaux !) et de la faire pointer vers la tête de la deuxième ligne.
Si on connait l'adresse de la Cellule de fin, on a même simplement UNE opération à faire : réorienter la Cellule de fin vers l'ancienne deuxième tête !
Aucun déplacement mémoire. Uniquement un changement de référence sur 1 Cellule...
On pourra donc écrire des choses comme cela : lst1 + lst2. Cela veut juste dire de faire pointer la Cellule de fin de la première liste vers la tête de la deuxième liste.
On peut faire l'inverse, lst2 + lst1 : on fait pointer la Cellule de fin de la liste 2 vers la tête de la liste 1.
Or, pour obtenir cet avantage majeur sur les tableaux, il nous faut la référence de la tête et de la dernière Cellule. Sinon, il faut lire la première liste séquentiellement jusqu'au bout... C'est long.
Il est donc temps de modifier notre classe Liste : nous allons lui rajouter un nouvel attribut fin qui va contenir la référence de la Cellule finale, celle qui ne mène nulle part et dont l'attribut s contient None.
Comme faire cela ? En utilisant la méthode renvoyerCelluleFinale de la classe Cellule. Que lui envoyer comme instance de Cellule ? La tête de la liste, c'est la seule dont on connaisse la référence.
Attention, s'agissant d'une méthode, on utilise la syntaxe avec le point.
1
2
3
4
5
6
7
8 | |
Cela veut bien dire : "va chercher l'espace mémoire de la tête et applique la méthode renvoyerCelluleFinale que tu vas y trouver".
Par contre, cela veut dire qu'il falloir mettre la jour cet attribut derniere lorsqu'on insère un élément qui ne possède pas de successeur : c'est lui désormais la nouvelle fin.
Voici le code que nous allons maintenant compléter. On remarque qu'il possède des instructions de mise à jour de cet attribut dans tous les cas où il est possible que la dernière cellule ai changé.
La fin de ce tp va consister à créer les fonctions d'interface manquantes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104 | |
17° Compléter la fonction insererFin qui consiste à insérer la nouvelle valeur dans une nouvelle cellule qui sera placée derrière la fin actuelle.
Prototype :
insererFin(x:Elt, lst:Liste) -> None : on modifie sur place la liste : l'élément x fourni est inséré dans une Celule qui est placée juste après la Cellule predecesseur. On ne renvoie rien. C'est inutile puisque la référence sera automatiquement stockée dans l'attribut derniere.
Vous pourrez vous inspirer de la fonction insererTete qui ne fait qu'un appel à insererPosition. Votre fonction pourrait ainsi n'être constituée que d'un appel à insererApres puisqu'on connaît bien la référence de la dernière cellule, stockée dans l'objet lui-même.
Question : quel est le coût de l'insertion en fin de liste ? Constant ? Linéaire ?
...CORRECTION...
1
2 | |
Le coût est donc constant car il s'agit du coût de la fonction insererApres.
Maintenant que notre implémentation commence à ressembler à quelque chose, nous voudrions peut-être obtenir le contenu de notre liste pour pouvoir le représenter.
Pour cela, nous allons utiliser les deux fonctions situées à la fin.
18° Modifier le programme principal en utilisant cette création de liste.
Question : en utilisant l'interface, l'utilisateur peut-il se douter que les données sont stockées sous forme d'une liste chaînée composée d'objets ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | |
>>> afficherListe(lst1)
"('Lundi', 'Mardi', 'Mercredi')"
...CORRECTION...
Et non. Toujours pas. L'utilisateur pourrait encore croire (comme avec l'implémentation tuple puis tableau) que nous avons stocké les données dans un string représentant un tuple...
19° Quatre sous-questions.
19.1 Quelle est la condition d'arrêt de la fonction récursive recupererValeur ?
19.2 Quel est son cas de base ?
19.3 Compléter ensuite sur feuille les réponses successives des appels récursifs à partir de l'appel de départ recupererValeur(lst1.tete) en travaillant à partir de cet empilement des appels :
Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + recupererValeur(lst1.tete.s)
Appel à recupererValeur(lst1.tete.s) renvoie ...
Appel ...
19.4 Finalement, effectuer le dépilement et fournir la réponse que va renvoyer l'appel à cette fonction en fournissant la tête de la liste en argument.
...CORRECTION...
La condition d'arrêt est le fait que l'attribut s de la Cellule contienne None : cela veut dire que cette Cellule est la dernière de la liste chaînée.
Le cas de base consiste alors à renvoyer la valeur de la Cellule sous forme d'un tableau d'une seule case.
Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + recupererValeur(lst1.tete.s)
Appel à recupererValeur(lst1.tete.s) renvoie ['Mardi'] + recupererValeur(lst1.tete.s.s)
Appel à recupererValeur(lst1.tete.s.s) renvoie ['Mercredi']
Effectuons le dépilement :
Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + recupererValeur(lst1.tete.s)
Appel à recupererValeur(lst1.tete.s) renvoie ['Mardi'] + ['Mercredi']
On renvoie donc la concaténation des deux tableaux.
Etape suivante :
Appel à recupererValeur(lst1.tete) renvoie ['Lundi'] + ['Mardi', 'Mercredi']
Nous allons donc renvoyer ['Lundi', 'Mardi', 'Mercredi']
20° Réaliser maintenant les trois fonctions d'interface de lecture des valeurs. On travaillera à partir des trois prototypes ci-dessous.
lireTete(lst:Liste) -> Elt: on renvoie l'élément stocké tête.lireFin(lst:Liste) -> Elt: on renvoie l'élément stocké à la fin de la liste.lirePosition(lst:Liste, position:int) -> Elt: on renvoie l'élément stocké en position position.
listeA peut être représentée par (12, 15, 18, 4)
reponse1 = lireTete(listeA)
reponse2 = lirePosition(listeA, 1)
reponse3 = lireFin(listeA)
reponse1 doit alors contenir 12, reponse2 doit alors contenir 15, reponse3 doit alors contenir 4.
Comment réaliser la lecture en fonction de la position ? En effectuant position sauts à partir de la tête. Nous pourrions le faire en récursif aussi au besion. Mais ici l'itération sera plus facile à insérer dans le code existant.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | |
21° Expliquer comment fonctionne cette version récursive de la fonction lirePosition.
1
2
3
4
5
6
7
8
9 | |
Pour cela, écrire sur feuille l'empilement des fonctions puis réaliser le dépilement. On travaillera sur l'appel suivant :
>>> lirePosition(lst1, 2)
On considère la liste suivante :
1
2
3
4 | |
...CORRECTION...
Appel à lirePosition(lst1, 2) renvoie lecture(2, lst1.tete)
Appel à lecture(2, lst1.tete) renvoie lecture(1, lst1.tete.s)
Appel à lecture(1, lst1.tete.s) renvoie lecture(0, lst1.tete.s.s)
Appel à lecture(0, lst1.tete.s.s) renvoie "Mercredi"
Le dépilement est donc très simple et rapide :
Appel à lirePosition(lst1, 2) renvoie lecture(2, lst1.tete)
Appel à lecture(2, lst1.tete) renvoie lecture(1, lst1.tete.s)
Appel à lecture(1, lst1.tete.s) renvoie "Mercredi"
Appel à lirePosition(lst1, 2) renvoie lecture(2, lst1.tete)
Appel à lecture(2, lst1.tete) renvoie "Mercredi"
Appel à lirePosition(lst1, 2) renvoie "Mercredi"
Passons à la concatenation de listes avec la réalisation de la fonction concatener qui doit modifier la dernière cellule de la liste gauche pour qu'elle pointe sur la tête de la liste droite.
22° Réaliser cette fonction dont voici le prototype :
concatener(gauche:Liste, droite:Liste) -> None : on doit réaliser l'opération suivante en modifiant la liste gauche.
Vous pourrez tester avec ce programme de test :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | |
Voici le contenu des listes avant la concaténation :
('Lundi', 'Mardi', 'Mercredi')
('Jeudi', 'Vendredi', 'Samedi', 'Dimanche')
Voici la liste de gauche après concaténation :
('Lundi', 'Mardi', 'Mercredi', 'Jeudi', 'Vendredi', 'Samedi', 'Dimanche')
La liste chaînée de droite n'a elle pas été modifiée :
('Jeudi', 'Vendredi', 'Samedi', 'Dimanche')
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12 | |
Activité publiée le 12 11 2020
Dernière modification : 12 11 2020
Auteur : Andjekel
Source : ows. h.