Implémenter une Liste avec des Tuples
En informatique, l'implémentation est le passage de l'abstraction théorique à la programmation concrète.
Vous avez déjà implémenté des algorithmes en programmes Python ou Javascript.
Vous allez maintenant implémenter un type abstrait LISTE en structure de données réelles en machine.
Python possède déjà un certain nombres de structures de données qui permettent l'implémentation des types abstraits.
- On gère le type abstrait booléen en utilisant le type natif bool.
- On gère le type abstrait integer en utilisant le type natif int.
- On gère le type abstrait nombre à virgule flottante en utilisant le type natif float.
- On gère le type abstrait tableau statique (array en anglais) en utilisant le type natif ... list.
- On gère le type abstrait tableau dynamique (vector en anglais) en utilisant le type natif list.
- On gère le type abstrait tableau associatif en utilisant le type natif dict.
- On gère le type abstrait p-uplet nommé en utilisant le type natif dict.
- On gère le type abstrait p-uplet en utilisant le type natif tuple.
Prerequis : l'activité sur les Listes.
1 - Tuple (Tête, Queue)
Nous allons réaliser une implémentation qui permet d'obtenir l'interface du type abstrait Liste suivante :
De façon à obtenir une structure non mutable, nous décidons de partir sur la manipulation de tuples.
Nous allons voir que chaque implémentation possède des avantages et des désavantages en fonction de la façon dont on désire utiliser la liste.
L'avantage ici va porter sur la facilité d'extraction de la tête ou de la queue.
Le type-python tuple (structure de données)
Les tuples sont déclarés en utilisant les parenthèses.
On peut les lire à l'aide des boucles for.
Les tuples sont non-mutables : on ne peut pas modifier leurs contenus après création.
Quelques commandes Shells pour vous permettre de réactiver vos connaissances sur les tuples :
Tuple vide
>>> a = ()
>>> type(a)
<class 'tuple'>
>>> a
()
Tuple ne contenant qu'un seul élement (n'oubliez pas la virgule !). Le premier cas ne crée pas un tuple mais juste un integer, les parenthèses n'ayant que le rôle de ... parenthèses.
>>> a = (5)
>>> type(a)
<class 'int'>
>>> a
5
>>> a = (5,)
>>> type(a)
<class 'tuple'>
>>> a
(5,)
Tuple de deux éléments : la tête est un integer, la queue est un tuple aussi.
>>> a = (5, (8,()))
>>> type(a)
<class 'tuple'>
>>> a[0]
5
>>> a[1]
(8, ())
Voici le début d'une proposition d'implémentation de liste sous forme de tuple qui encoderont la tête et la queue sous cette forme : (tete, queue).
Voici d'abord les descriptions des fonctions d'interface avec ce qu'elles doivent faire, quelque soit l'implémentation réelle :
nouvelleListe() -> Liste : on crée une nouvelle liste vide ().
listeA = nouvelleListe()
Le contenu de listeA est alors ().
estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.
listeA = nouvelleListe()
estVide(listeA)
Et voici l'implémentation proposée pour notre liste :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | |
On notera qu'il est plus "propre" pour des élèves en informatique de faire ceci pour la réponse de la fonction estVide 'sans la documentation ici)' :
18
19 | |
01° Que vont renvoyer ces instructions ?
>>> a = ()
>>> estVide(a)
???
>>> b = None
>>> estVide(b)
???
>>> c = "C"
>>> estVide(c)
???
>>> d = nouvelleListe()
>>> estVide(d)
???
Question subsidiaire : quelle est la seule proposition qui respecte l'interface imposée par le créateur de cette implémentation ?
02° Créer maintenant la fonction d'interface suivante :
insererTete(x:Elt, lst:Liste) -> Liste : on renvoie une nouvelle liste où la tête est maintenant l'élément x et la queue la liste précédente lst.
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.
AIDE : il suffit de renvoyer un nouveau tuple dont la tête est notre x et la queue l'ancien tuple !
Voici un exemple d'utilisation :
>>> a = nouvelleListe()
>>> a = insererTete(5, a)
>>> a
(5, ())
>>> a = insererTete(2, a)
>>> a
(2, (5, ()))
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 | |
On remarquera que le fait de taper a pour visualiser le contenu ne fait pas partie de l'interface : un utilisateur ne devrait donc pas utiliser ce moyen de visualiser le contenu.
03° Réaliser la fonction d'interface permettant de lire la tête :
lireTete(lst:Liste) -> Elt : on renvoie la tête de la liste lst.
Précondition : lst est une liste (ici () ou (tete,queue)), queue étant une liste.
Attention, on ne modifie pas la liste ! Dans LISP, cette fonction se nomme car (pour contents of address register)
Attention : pensez à vérifier que la liste n'est pas vide avant de chercher à lire l'index 0 (la tête).
Exemple d'utilisation
>>> a = insererTete(5, nouvelleListe() )
>>> a = insererTete(15, a)
>>> lireTete(a)
15
>>> b = nouvelleListe()
>>> lireTete(b)
>>>
04° Dernière fonction d'interface, supprimer la tête :
supprimerTete(lst:Liste) -> Liste : on renvoie une nouvelle liste où la tête est maintenant le deuxième élément (la tête de la queue précédente !). Techniquement, cela revient bien à supprimer l'ancienne tête si on enregistre cette nouvelle version dans une variable. Notez bien qu'on aurait pu nommer cette fonction recupererQueue puisque c'est ce qu'elle fait.
Précondition : lst est une liste (ici () ou (tete,queue)), queue étant une liste.
Imaginons la liste suivante :
5 → 8 → 2 → 3
Votre fonction doit renvoyer ceci :
8 → 2 → 3
AIDE : la tête est l'index 0 de la liste et la queue est son index 1.
AIDE 2 : pensez à gérer
- le cas particulier de la liste vide () : pas de nouvelle tête puisque pas de queue. Il faudra renvoyer une liste vide.
- le cas général où la queue dans votre liste est une liste non vide.
Voici un exemple d'utilisation pour chacun des cas précédents :
>>> a = nouvelleListe()
>>> b = supprimerTete(a)
>>> b
()
>>> a = insererTete(5, nouvelleListe())
>>> b = supprimerTete(a)
>>> b
()
>>> a
(20, (15, (5, ())))
>>> b = supprimerTete(a)
>>> b
(15, (5, ()))
>>> c = supprimerTete(b)
>>> c
(5, ())
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.
Nous aimerions afficher (20, 15, 5) plutôt que (20, (15, (5, ()))).
05° Regarder cette fonction afficherListe.
1
2
3
4
5
6
7
8
9
10
11
12 | |
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(20, (15, (5, nouvelleListe())))
>>> afficherListe(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 ?
Tentons maintenant de créer la deuxième interface (la plus souple) à partir de celle-ci : nous voudrions par exemple parvenir à lire n'importe quelle valeur de notre liste, pas seulement la tête.
L'avantage de notre implémentation par rapport au type abstrait : on colle au plus près à la structure (tête, queue).
Voyons maintenant les désavantages.
Pour rappel, voici les fonctions d'interface que nous avons créé jusqu'à présent.
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 | |
06° Créer la fonction d'interface lireElement en utilisant les fonctions d'interface que nous avons déjà créé : il faudra utiliser supprimerTete jusqu'à arriver à la bonne.
- Combien de fois doit-on utiliser supprimerTete pour atteindre l'élément d'index position ?
- Que doit-on faire une fois qu'on a récupéré la bonne liste ?
lireElement(lst:Liste, position:int) -> Elt : on renvoie l'élément stocké en position position.
listeA = (12, 15, 18, 4)
reponse = lireElement(listeA, 1)
reponse contient alors 15.
Précondition : lst est une liste et position un index valide.
Exemple d'utilisation :
>>> a = insererTete(20, (15, (5, nouvelleListe())))
>>> lireElement(a, 1)
15
>>> lireElement(a, 0)
20
>>> lireElement(a, 2)
5
07° Le pire des cas pour la lecture est ici le fait de vouloir lire la dernière valeur de la liste.
Question : Que vaut le coût de la lecture d'éléments pour notre implémentation :
- A : Elle est logarithmique
- B : Elle est linéaire
- C : Elle est quadratique
- D : Elle est exponentielle
Coût de l'implémentation en tuple (tête, queue)
On notera donc que dans le pire des cas :
- La lecture est à coût linéaire (Θ(n))
- L'insertion et la suppression est à coût linéaire (Θ(n))
Cela peut paraître correct. Mais nous allons voir qu'on peut implémenter nos listes de deux façons différentes qui vont apporter un coût constant soit à la lecture, soit à l'insertion.
- L'implémentation en tableau pour la lecture à coût constant
- L'implémentation en liste chaînée pour l'insertion/suppression à coût constant
2 - FAQ
Rien pour l'instant
Activité publiée le 20 09 2022
Dernière modification : 21 09 2020
Modification : Andjekel
Source : ows. h.