12 - Implémenter une Liste 1/3
Aujourd'hui, nous allons implémenter une Liste Récursive (Tête, Queue) sous forme d'une structure de donnée nommée Liste Chaînée.
Version du vocabulaire utilisé ici :
- Type abstrait de données : une idée abstraite mais précise de la façon de traiter les données. On trouve souvent l'acronyme TAD
- Type : l'implémentation en machine d'une donnée. Cela regroupe donc les types simples et les types construits.
- Type simple : l'implémentation en machine d'une donnée unique, comme un entier, un flottant...
- Type structuré, type construit : l'implémentation en machine d'une donnée se comportant comme un conteneur : elle contient d'autres données.
- Une structure de données est le nom qu'on donne à l'ensemble d'un type associé aux fonctions qu'on peut appliquer aux données stockées.
- TETE : la première Place d'une Liste.
- QUEUE : l'ensemble des autres Places d'une Liste.
- FIN : la dernière Place d'une Liste.
D'où le nom de la fonction native Python type().
Prerequis : l'activité sur les Listes.
Documents de cours : open document ou pdf
1 - Liste chainée sous forme de tuples
Implémentation correcte ?
Pour que l'implémentation soit qualifiée de "correcte", il faut que ces opérations primitives aient un coût faible.
1.1 - La structure Liste Chaînée : un ensemble de Cellules reliées entre elles
Une bonne manière d'implémenter une Liste Récursive est d'utiliser à l'interne une Liste Chaînée : les Places sont des Cellules sans numéro mais reliées entre elles.
Une Cellule contient au moins deux informations :
- L'Elément que la Cellule stocke
- La référence du successeur : la Cellule suivante dans la Liste Chainée
- La Tête est ici la Cellule contenant 25.
- La Queue est la Liste Chaînée qui commence par le Cellule contenant 15. La Queue est bien une Liste Chaînée, dont la Tête est la Cellule contenant 15.
- La Fin est la Cellule contenant 5.
1.2 La Liste Chaînée sous forme d'un tuple
De façon à obtenir facilement une structure immuable, nous décidons de partir sur la manipulation de tuples qui possèdent justement cette propriété dans Python.
Liste Vide
On fait le choix de représenter une Liste Vide par un tuple vide ().
>>> liste_vide = ()
Cellule (Elément de Tête, Queue)
On implémente chaque Cellule comme un tuple (Elément de tête, Successeur).
Cellule = (Element, Successeur)
Une Cellule c contient deux informations :
- c[0] : l'Elément stocké,
- c[1] : le Successeur qui peut être soit une Liste Vide, soit une Cellule
Exemple avec la Cellule a qui contient 5 et n'a pas de successeur.
>>> a = (5, liste_vide)
>>> a
(5, ())
Rajouter une Tête est donc facile. Exemple : rajoutons une Cellule b qui contient 15 et dont le successeur est la Cellule a.
>>> b = (15, a)
>>> b
(15, (5, ()))
Rajoutons une Cellule c qui contient 25 et dont le successeur est la Cellule b.
>>> c = (25, b)
>>> c
(25, (15, (5, ())))
Connaissant la localisation mémoire de la Cellule c, il est assez facile de trouver son contenu (25 pour c) et de trouver son successeur (b pour c) :
>>> c
(25, (15, (5, ())))
>>> c[0]
25
>>> c[1]
(15, (5, ()))
On voit assez facilement que supprimer une Tête ou récupérer une Queue est facile : il suffit de récupérer l'indice 1 de la Cellule de Tête.
>>> c
(25, (15, (5, ())))
>>> lst = c[1]
>>> lst
(15, (5, ()))
On voit que la queue qu'on récupère est donc simplement une référence vers la Cellule de tête d'avant, b.
Liste Chaînée ; une simple référence vers la Cellule de Tête ?
Presque car il y a une autre possibilité.
Dans notre implémentation Tête-Queue, une Liste est :
- soit une référence vers une Liste Vide, le tuple ().
- soit une référence vers la Cellule de Tête, un tuple (Element, Successeur)
On pourait donc écrire ceci :
>>> lst1 = c
Vous allons maintenant réaliser une implémentation de cette structure de données.
Une fois que les 7 opérations primitives auront été créées, nous compléteront l'interface de façon à offrir les fonctions manquantes pour permettre de qualifier cette structure de données de Liste.
Nous aurons alors un beau module qui nous permettra d'utiliser des Listes Chaînées et donc de pouvoir programmer facilement les algorithmes qui sont décrits en manipulant une Liste Récursive.
Le MODULE PRIMITIVES de la liste_chainee_tq de ce TP
Voici le module non finalisé implémentant une Liste Chaînée sous forme de tuples (vide ou couple (Elément de Tête, Queue)).
On notera que premier() n'est pas vraiment une primitive mais un raccourci bien pratique.
Pour l'instant, la plupart des fonctions ne contiennent que l'instruction pass.
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 | |
01° Enregistrer ce module en le nommant bien liste_chainee_tq.py, sans accent attention. Lancer le module directement.
>>> a = ()
>>> estListeVide(a)
???
>>> b = nouvelleListe()
>>> estListeVide(b)
???
Questions
- Que vont renvoyer ces instructions ?
- Quelle est la seule proposition qui utilise bien l'interface proposée plutôt que de manipuler directement l'implémentation de la liste (la documentation se trouve en début de module, voir les lignes 8 à 16) ?
- L'utilisateur d'un module est-il sensé savoir comment les données sont réellement implémentées ?
...CORRECTION...
Question 1
>>> a = ()
>>> estListeVide(a)
True
>>> b = nouvelleListe()
>>> estListeVide(b)
True
Question 2
Seule b respecte l'interface : avec a crée une liste sans passer par la fonction d'interface nouvelleListe(). Cette manipulation directe implique qu'on manipule directement les données.
Question 3
L'utilisateur n'est pas sensé manipuler les données internes du module : il doit utiliser uniquement les fonctions d'interface qu'on lui a fourni. De cette façon, ses programmes resteront fonctionnels même si les créateurs du module changent légèrement la gestion interne après une mise à jour.
02° Modifier la fonction d'interface insererTete() qui ne répond pas ce qu'il faut pour le moment.
Prototype
def insererTete(lst:'Liste', elt:'Element') -> 'Liste':
Exemple d'utilisation :
>>> a = nouvelleListe()
>>> a
()
>>> a = insererTete(a, 5)
>>> a
(5, ())
>>> a = insererTete(a, 2)
>>> a
(2, (5, ()))
AIDE : il suffit de renvoyer un nouveau tuple dont
- L'élément de tête est notre elt et
- Le successeur est l'ancien tuple lst qui pointe bien vers l'ancienne cellule de tête.
Vous pourrez tester votre résultat en activant la fonction de tests intégrée au module :
>>> tester_insererTete()
Historiquement, dans LISP cette fonction se nomme cons() (comme _cons_truct) lorsqu'elle insère bien le nouvelle élément en tant que nouvelle tête.
...CORRECTION...
1
2
3 | |
On remarquera que le fait de taper a dans la console permet de visualiser le contenu réel de notre liste. Il faudrait donc créer une fonction d'interface permettant de montrer le contenu de la liste à l'utilisateur sans qu'il sache qu'elle est stockée dans des tuples. Nous allons le faire à la question 5.
03° Modifier la fonction d'interface supprimerTete() qui ne renvoie pas la réponse attendue pour le moment.
Prototype
def supprimerTete(lst:'Liste Non Vide') -> 'Liste':
supprimerTete(lst:Liste) -> Liste
Renvoie une nouvelle liste où la tête est maintenant le deuxième élément (la tête de la queue précédente !).
Précondition : lst est une liste NON VIDE. Inutile donc gérer les cas où on vous envoie une liste vide, ou pire : un truc qui n'est pas une liste. Ce n'est pas votre problème en tant que concepteur de cette fonction.
Voici quelques exemples d'utilisation :
>>> a = nouvelleListe()
>>> a = insererTete(nouvelleListe(), 5)
>>> a
(5, ())
>>> b = supprimerTete(a)
>>> b
()
>>> a = (20, (15, (5, ())))
>>> a
(20, (15, (5, ())))
>>> b = supprimerTete(a)
>>> b
(15, (5, ()))
>>> a
(20, (15, (5, ())))
AIDE : on aurait pu nommer cette fonction recupererQueue() puisque c'est ce qu'elle fait.
Fonction de test
>>> tester_supprimerTete()
...CORRECTION...
1
2
3 | |
04° Passons aux fonctions manipulant les Cellules.
- Expliquer pourquoi, dans cette implémentation, la fonction accesTete() renvoie effectivement la Cellule de Tête avec l'instruction return lst.
- Modifier la fonction d'interface contenu() pour qu'elle renvoie bien l'élément contenu dans la Cellule c qu'on lui fournit.
- Modifier la fonction d'interface successeur() pour qu'elle renvoie bien le successeur Cellule de la Cellule c qu'on lui fournit. Attention à la précondtion : la Cellule envoyée DOIT avoir un vrai Successeur. Ce n'est pas à vous de gérer le cas où la Cellule qu'on vous transmet est la dernière et que son successeur est vide. C'est une précondition. C'est donc à l'utilisateur de vérifier.
39
40
41
42
43
44
45
46
47
48
49 | |
Fonctions de test
>>> tester_accesTete()
>>> tester_contenu()
>>> tester_successeur()
...CORRECTION...
Question 1
Dans cette implémentation, nous avions remarqué qu'une Liste Non Vide n'est finalement qu'une référence vers une Cellule.
La liste n'est donc qu'un alias pour désigner la Cellule de Tête.
Questions 2-3
39
40
41
42
43
44
45
46
47
48
49 | |
05-A° Il est assez pénible d'accéder à la valeur stockée dans la Cellule de Tête pour l'instant : il faut d'abord utiliser la fonction accesTete() puis utiliser contenu().
recup = contenu(accesTete(lst))
Réaliser la fonction premier() qui renvoie directement l'élément stocké en Tête d'une Liste NON VIDE. On vous demande ici de manipuler directement l'implémentation sans passer par les autres opérations primitives.
Prototype
def premier(lst:'Liste Non Vide') -> 'Element':
premier(lst:Liste) -> Element
Renvoie la tête de la liste lst.
PRECONDITION : La Liste ne doit pas être vide.
Exemple d'utilisation
>>> a = insererTete(nouvelleListe(), 5)
>>> a = insererTete(a, 15)
>>> premier(a)
15
>>> b = nouvelleListe()
>>> premier(b)
IndexError: tuple index out of range
...CORRECTION...
1
2
3 | |
05-B° Même question, mais cette fois, on vous demande de réaliser une version qui n'utilise que les autres opérations primitives déjà réalisées : vous devrez manipuler directement le tuple (élément, successeur).
...CORRECTION...
1
2
3 | |
05-C° On considère que l'implémentation Python des tuples permet de lire un tuple ou une case de tuple à coût constant.
- Quel est le coût de nouvelleListe() ?
- Quel est le coût de estListeVide() ?
- Quel est le coût de insererTete() ?
- Quel est le coût de supprimerTete() ?
- Quel est le coût de accesTete() ?
- Quel est le coût de contenu() ?
- Quel est le coût de successeur() ?
- Quel est le coût de premier() version 5A ?
- Quel est le coût de premier() version 5B ?
- Quelle est la version de premier() à privilégier ?
...CORRECTION...
- Quel est le coût de nouvelleListe() ?
- Quel est le coût de estListeVide() ?
- Quel est le coût de insererTete() ?
- Quel est le coût de supprimerTete() ?
- Quel est le coût de accesTete() ?
- Quel est le coût de contenu() ?
- Quel est le coût de successeur() ?
- Quel est le coût de premier() version 5A ?
- Quel est le coût de premier() version 5B ?
- Quelle est la version de premier() à privilégier ?
On renvoie juste un tuple. Le coût est donc constant.
On lit un tuple (coût constant), on lit le tuple vide (coût constant), on effectue une comparaison (coût constant).
On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 3 opérations basiques).
On lit la variable elt (coût constant), on lit la variable lst (coût constant), on génère un couple en fournissant les deux valeurs précédentes (coût constant).
On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 3 opérations basiques).
On lit la variable lst (coût constant), et on accède à son indice 0 (coût constant).
On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).
On lit juste la variable lst (coût constant).
On lit la variable lst (coût constant), et on accède à son indice 0 (coût constant).
On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).
On lit la variable lst (coût constant), et on accède à son indice 1 (coût constant).
On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).
On lit la variable lst (coût constant), et on accède à son indice 0 (coût constant).
On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).
On utilise l'opération primitive accesTete() (coût constant) puis à l'opération primitive contenu (coût constant).
On obtient donc un coût constant.
Puisque les deux fonctions ont le même coût, on préférera clairement la version qui manipule juste les opérations primitives puisqu'on ne manipule pas directement les données internes. On passe par des fonctions qui le font à notre place.
Il nous manque encore une chose qui pourrait être pratique mais qui ne fait pas partie de l'interface obligatoire : de quoi représenter la liste sans montrer son implémentation mémoire réelle. Il s'agit donc d'une fonction faisant partie de l'IHM (Interface Homme Machine).
Nous aimerions afficher '10 -> 15 -> 5' plutôt que de montrer le contenu réel (10, (15, (5, ()))) par exemple.
06° Placer cette fonction representerListe() parmi vos fonctions d'interface.
1
2
3
4
5
6
7
8 | |
Elle renvoie un string représentant le contenu interne de la Liste de façon totalement arbitraire : le contenu affiché n'a rien à voir avec le contenu réel (des tuples dans des tuples).
Utiliser les instructions suivantes :
>>> a = insererTete(insererTete(insererTete(nouvelleListe(), 5), 15), 20)
>>> representerListe(a)
'20 -> 15 -> 5'
Question : un utilisateur peut-il avoir une idée de l'implémentation interne de notre Liste en utilisant nos fonctions d'interface ?
...CORRECTION...
Non. C'est même le principe fondamental de l'interfaçage : quelque soit l'implémentation interne, l'utilisateur doit pouvoir utiliser les fonctions d'interface pour obtenir les mêmes effets. L'utilisateur ne doit donc pas avoir besoin de connaître l'implémentation interne pour manipuler ses données. Il doit juste utiliser les fonctions d'interface qu'on lui fournit, qui ont certainement étaient optimisées pour gérer ce type de données.
Attention : notre fonction d'affichage ne parviendra donc pas à gérer correctement les listes contenant des strings contenant des crochets [ et ] puisqu'elle les supprime de l'affichage.
Si vous voulez gérer des contenus de ce type, il faudra modifier la fonction.
Notre implémentation a deux avantages manifestes :
- Implémentation légère : pas de choses compliquées. Il faut se souvenir que l'ordre des qualités d'un programme est souvent : d'abord de marcher, ensuite d'être clair, et finalement d'être performant.
- Implémentation qui colle au plus près de la notion de Tête -> Queue.
2 - Création des autres opérations primitives
Nous allons maintenant voir que cette implémentation présente en réalite quelques désavantages.
Tentons de créer maintenant les autres opérations importantes du type Liste :
- On veut une fonction longueur()
- On veut une fonction inserer() pour insérer en tant que Cellule d'indice i
- On veut une fonction supprimer() pour supprimer la Cellule d'indice i
- On veut une fonction acces() pour accéder à la Cellule d'indice i
MODULE version 2
Voici le programme que vous allez utiliser sur cette deuxième partie : il contient les corrections de la partie 1 ainsi que les fonctions et fonctions de test de la partie 2.
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 | |
07° Utiliser ce nouveau module à la place de l'ancien. Trois questions :
- Expliquer pourquoi cette expression vérifie que la liste n'a pas de vrai successeur :
- Formuler en fançais la question qu'on pose à l'interpréteur en inversant la réponse precédente ?
- En se souvenant que NON (a OU b) est équivalent à (NON a) ET (NON b), comment aurait-on pu écrire la réponse de la fonction ?
- Expliquer ensuite pourquoi on ne peut pas juste utiliser la fonction successeur() et vérifier que la réponse n'est pas une Cellule vide. Pensez au "défaut" majeur de la fonction successeur().
estListeVide(lst) or estListeVide(supprimerTete(lst))
not( estListeVide(lst) or estListeVide(supprimerTete(lst)) )
...CORRECTION...
- Expliquer pourquoi cette expression vérifie que la liste n'a pas de successeur :
- Formuler en fançais la question qu'on pose à l'interpréteur en inversant la réponse precédente ?
- En se souvenant que NON (a OU b) est équivalent à (NON a) ET (NON b), comment aurait-on pu écrire la réponse de la fonction ?
- Expliquer ensuite pourquoi on ne peut pas juste utiliser la fonction successeur() et vérifier que la réponse n'est pas une Cellule vide. Pensez au "défaut" majeur de la fonction successeur().
estListeVide(lst) or estListeVide(supprimerTete(lst))
On demande si la liste est vide (et n'a donc évidemment pas de vrai successeur) ou si le successeur de la liste est vide (et la liste n'a donc pas de vrai successeur).
not( estListeVide(lst) or estListeVide(supprimerTete(lst)) )
L'inverse logique de "N'a pas de vrai successeur" est "A un successeur".
La question qu'on pose est donc "La Liste a-t-elle un successeur ?
not estListeVide(lst) and not estListeVide(supprimerTete(lst))
Pour éviter les confusions, on peut placer des parenthèses si on veut (mais ce n'est pas nécessaire ici car not)
(not estListeVide(lst)) and (not estListeVide(supprimerTete(lst)))
La documentation précise bien que la fonction renvoie TOUJOURS une Cellule. Or, pour que la fonction puisse renvoyer une Cellule, il faut que la Cellule est un vrai successeur. Il ne peut donc pas s'agir de la dernière Cellule d'une Liste Chaïnée.
08-A° Créer la fonction d'interface longueur() en utilisant les fonctions d'interface estListeVide() et supprimerTete(). Le principe est bien de compter une à une les cellules. Commencer soit par la version récursive, soit par la version itérative puis... faire la version qui vous plait moins.
Prototype
def longueur(lst:'Liste') -> int:
AIDE : puisque Successeur() a une précondition assez sérieuse, et que longueur est toujours à coût linéaire, le plus simple pour savoir si la Tête d'une Liste a un vrai successeur est de supprimer la Tête et de voir si on obtient une liste vide.
Vous pourrez utiliser la fonction tester_longueur() pour vérifier votre réponse OU comprendre ce qu'on attend de vous. Finalement, les fonctions de test, c'est pratique pour la phase d'écriture non ?
...CORRECTION...
1
2
3
4
5
6
7
8 | |
1
2
3
4
5
6
7 | |
08-B° Quel est le coût de votre fonction longueur() ? Sa complexité ?
09-A° Créer la fonction d'interface acces() en utilisant les fonctions d'interface existantes. Le principe est bien de se déplacer vers la bonne Cellule. Attention à la précondition : l'indice i qu'on vous envoie est valide et la liste n'est donc pas vide.
Prototype
def acces(lst:'Liste Non Vide', i:int) -> 'Cellule':
Vous pourrez utiliser la fonction tester_acces().
...CORRECTION...
Beaucoup de versions possibles : récursives ou itératives, avec successeur(), avec supprimerTete() ou avec supprimer()...
Quelques possibilités :
1
2
3
4
5
6 | |
1
2
3
4
5
6 | |
09-B° Quel est le coût de votre fonction acces() ? Sa complexité ?
10-A° Créer la fonction d'interface ieme(). Maintenant que la fonction acces() est réalisée, c'est facile.
Prototype
def ieme(lst:'Liste Non Vide', i:int) -> 'Element':
Vous pourrez utiliser la fonction tester_ieme().
...CORRECTION...
Beaucoup de versions possibles. Le plus simple est d'utiliser la primitive acces() qu'on vient de créer.
1
2
3 | |
10-B° Quel est le coût de votre fonction ieme() ? Sa complexité ?
RAPPEL : variable de boucle nommée _ ?
On utilise ce nom de variable de boucle lorsqu'on veut simplement dire qu'on veut faire l'action k fois : for _ in range(10) veut donc dire qu'on va faire le bloc 10 fois.
11° Observer la fonction inserer() ci-dessous.
inserer(lst:Liste, elt:Element, i:int) -> Liste
Renvoie une nouvelle liste où l'élément fourni lst est maintenant l'élément de la liste situé à l'indice i voulu.
PRECONDITION : l'indice doit être un indice VALIDE pour la liste fournie. Transmettre un indice égale à la longueur de la liste, cela veut dire de placer l'élément en fin de liste. Si la liste est vide, le seul indice valide est donc l'indice 0.
listeA = (12, 15, 18, 7)
listeB = inserer(listeA, 5, 2)
listeB contiendra les éléments dans cet ordre : (12, 15, 5, 18, 7).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | |
Exemple d'utilisation :
>>> a = insererTete(insererTete(insererTete(nouvelleListe(), 5), 15), 20)
>>> representerListe(a)
'20 -> 15 -> 5'
>>> a = inserer(a, 12, 1)
>>> representerListe(a)
'20 -> 12 -> 15 -> 5'
>>> a = inserer(a, 20, 2)
>>> representerListe(a)
'20 -> 12 -> 20 -> 15 -> 5'
Questions :
- Expliquer comment fonctionne cette fonction.
- Que vaut le coût de l'insertion d'un nouvel élément dans le pire des cas pour notre implémentation (c'est à dire lorsque l'élément à rajouter est à placer en fin de liste) :
- Le coût est constant : 𝞗(1)
- Le coût est logarithmique : 𝞗(lg n)
- Le coût est linéaire : 𝞗(n)
- Le coût est quadratique : 𝞗(n2)
- Le coût est exponentielle : 𝞗(en)
- Que vaut le coût de l'insertion d'un nouvel élément dans le meilleur des cas pour notre implémentation (c'est à dire lorsque l'élément à rajouter est à placer en tête de liste) :
- Le coût est constant : 𝞗(1)
- Le coût est logarithmique : 𝞗(lg n)
- Le coût est linéaire : 𝞗(n)
- Le coût est quadratique : 𝞗(n2)
- Le coût est exponentielle : 𝞗(en)
...CORRECTION...
Pire des cas
Si notre liste possède n éléments, on voudra le placer à l'index n-1.
On remarque qu'on a n-1 opérations de suppression de têtes puis n-1 opérations d'insertion de têtes.
On a donc 2 * (n-1) opérations linéaires à effectuer.
On a donc 2 n - 2 opérations.
Si on néglige le -2 pour les grandes valeurs de n, on obtient 2 n opérations.
On omet le facteur multiplicateur puisqu'on ne cherche que l'évolution pour cette même structure pour deux valeurs de n différentes : on voit donc que l'insertion possède un coût en n : il s'agit d'une évolution linéaire.
Meilleur des cas
Il suffit de créer un nouveau tuple en allant lire l'adresse de l'ancien tuple, en créant un nouveau tuple (tete, queue) et en renvoyant le résultat : 3 actions élémentaires quelque soit le nombre de données réel dans la liste. Le coût est donc constant quelque soit la longueur n des données.
12-A° Réaliser la fonction supprimer() qui se rapproche de la fonction inserer(). La différence vient de l'action une fois sur place. On supprime la Cellule plutôt que de créer une nouvelle liaison.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | |
12-B° Quel est le coût de votre fonction supprimer() ? Sa complexité ?
Coût de l'implémentation en tuple (tête, queue)
Vous venez de créer l'ensemble des opérations primitives permettant de nommer notre structure de données une Liste. Notre implémentation est basée sur la Liste Chaînée qui est la meilleure façon de réaliser une Liste Récursive.
On notera que toutes les actions sur la Tête sont à coût constant (complexité 𝞗(1)).
On peut dire que dans un cas quelconque :
- La lecture est à coût linéaire (complexité en 𝞞(n) car c'est linéaire ou moins)
- L'insertion et la suppression est à coût linéaire (complexité en 𝞞(n) car c'est linéaire ou moins)
3 - Concaténation et autres créations
Regardons l'un des autres avantages des Listes Chaînées : la concaténation de deux listes.
13-A° Créer la fonction d'interface concatener(). Elle doit parvenir à réaliser une nouvelle Liste à partir de la liste de gauche et de la liste de droite
- La Tête de la nouvelle liste est la Tête de la liste de gauche
- La Fin de la liste de gauche doit mener à la Tête de la liste de droite
- La Fin de la nouvelle liste est la Fin de la liste de droite
Prototype
def concatener(gauche:'Liste', droite:'Liste') -> 'Liste':
Attention, les listes de base peuvent très bien être vides.
13-B° Si on désigne par n1 la longueur de la liste de gauche et par n2 la longueur de la liste de droite, quel est le coût puis la complexité de cette opération de concaténation ?
- Coût linéaire par rapport à (n1+n2) et complexité 𝞗(n1 + n2)
- Coût linéaire par rapport à (n1+n2) et complexité 𝞞(n1 + n2)
- Coût linéaire par rapport à n1 et complexité 𝞗(n1)
- Coût linéaire par rapport à n1 et complexité 𝞞(n1)
- Coût linéaire par rapport à n2 et complexité 𝞗(n2)
- Coût linéaire par rapport à n2 et complexité 𝞞(n2)
Voilà, vous en avez fini pour la conception du module. Vous trouverez dans la partie FAQ de nouvelles fonctionnalités pratiques mais dont le coût est malheureusement linéaire. Quelqu'un ne comprennant pas le type Liste Chainée pourrait croire à tord qu'utiliser ces fonctions est très rapide puisqu'on les appelle en n'utilisant qu'une instruction. Vous avez maintenant compris qu'il faut plus de compréhension d'une structure de données pour répondre à la question de l'efficacité d'une instruction.
Description du MODULE final LISTE CHAINEE IMMUABLE TETE-QUEUE
Voici les fonctions d'interface disponibles, classées selon trois catégories :
- Caractéristiques et fondamentales du type Liste Chaînées,
- Primitives manquantes être le type Liste généraliste,
- Fonctions supplémentaires pratiques.
'''INTERFACE du type Liste Chaînée IMMUABLE basée sur des tuples : () ou (tete, queue)
Description des types non natifs
--------------------------------
Element : le type des éléments disponibles dans votre Liste si elle est homogène.
Cellule : la référence d'un conteneur (Element, Cellule suivante).
Liste : la référence de la Cellule de la Tête ou d'une Liste Vide.
Opérations primitives de la Liste Chainée
-----------------------------------------
+ nouvelleListe() -> Liste CST
+ estListeVide(lst:'Liste') -> bool CST
+ insererTete(lst:'Liste', elt:'Element') -> 'Liste' CST
+ supprimerTete(lst:'Liste Non Vide') -> 'Liste' CST
+ premier(lst:'Liste Non Vide') -> 'Element' CST
+ accesTete(lst:'Liste Non Vide') -> 'Cellule' CST
+ contenu(c:'Cellule') -> 'Element' CST
+ successeur(c:'Cellule Non Finale') -> 'Cellule' CST
Autres opérations nécessaires du type Liste
-------------------------------------------
+ longueur(lst:'Liste') -> int LIN θ(n)
+ acces(lst:'Liste Non Vide', i:int) -> 'Cellule' LIN θ(i) O(n)
+ inserer(lst:'Liste', elt:'Element', i:int) -> 'Liste' LIN θ(i) O(n)
+ supprimer(lst:'Liste Non Vide', i:int) -> 'Liste' LIN θ(i) O(n)
Fonctions d'interface supplémentaires
-------------------------------------
+ representerListe(lst:"Liste') -> str
+ aSuccesseur(lst:'Liste') -> bool CST
+ ieme(lst:'Liste Non Vide', i:int) -> 'Element' LIN θ(i) O(n)
+ concatener(gauche:'Liste', droite:'Liste') -> 'Liste' LIN θ(n_gauche)
+ rechercher(lst1:'Liste', elt:'Element') -> int LIN θ(i) O(n)
+ liste(x) -> 'Liste' LIN θ(n_x)
+ copie(lst:'Liste') -> 'Liste' LIN θ(n)
+ dernier(lst:'Liste Non Vide') -> 'Element' LIN θ(n)
+ accesFin(lst:'Liste Non Vide') -> 'Cellule' LIN θ(n)
'''
14° En regardant simplement la documentation des fonctions disponibles, quelle est la partie de la notre Liste Chaînée Tête-Queue basique sur laquelle il est le plus difficile d'intervenir ?
15° Aller chercher le module finalisé dans la partie FAQ. Nous allons réaliser un court programme en utilisant notre module de listes chaînées.
- Etudier la fonction liste() qui permet de générer une liste à partir d'une autre donnée, quelconque : quel est son coût ?
- Placer le module (qu'on nommera liste_chainee_tq.py) au même endroit que le programme suivant. Lancer pour constater le bon fonctionnement.
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205 | |
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
16° Etudier la fonction copie() et expliquer son fonctionnement et déterminer son coût par rapport aux nombres d'éléments n de la liste de base.
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
CONCLUSION ::Primitives du type et fonctions d'interface
En conclusion, les primitives sont un ensemble de fonctions bien choisies qui sont les seules à manipuler directement la structure interne de notre structure de données.
Toutes les autres fonctions manipulent juste les primitives et n'ont pas de contact direct avec les données internes.
4 - FAQ
On peut avoir le module déjà réalisé ?
Vous pouvez maintenant directement télécharger ce module :
Activité publiée le 14 10 2020
Dernière modification : 03 10 2022
Auteur : ows. h.