Exemple d'implémentation en Python du type LISTE
Le type abstrait de donnée LISTE
Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers langages de programmation à introduire cette notion de liste (Lisp signifie "list processing").
On trouve différentes définitions du type abstrait liste.
Dans ce cours, nous définirons une liste comme une structure de donnée permettant de regrouper des données. C'est une structure linéaire qu'on ne peut parcourir qu'en partant du début. Elle est définie par son interface, c'est à dire l'ensemble des fonctions (méthodes), appelées des primitives qui vont permettre de creer et gérer la liste.
Il y a de nombreuses possibilités pour implémenter ce type abstrait, et on a pas besoin de connaître cette implémentation pour l'utiliser. Il suffit de connaître les spécifications des fonctions primitives, pour pouvoir les utiliser et éventuellement écrire d'autres fonctions.
Attention : ce que nous appelons listes dans ce chapitre n'est pas la même chose que les listes que vous connaissez en python. Il s'agit ici de types abstraits qui n'existent pas nécessairement de façon native dans tous les langages, mais peuvent être implémentés.
Le type abstrait LISTE est différent du type list. Nous le noterons dans ce cours, pour bien le différencier, en majuscules : LISTE.
Pour résumé, une LISTE est composée de :
- sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste (en tête de liste)
- et sa queue (souvent noté cdr) qui correspond au reste de la liste.
Écriture d'une liste
La manière dont sont affichées les listes dépend de leur implémentation. Dans ce qui suit nous allons conserver un affichage qui permet de bien visualiser la tête et la queue de la liste. Nous allons voir 3 implémentations différentes du type liste, toutes valables et on pourrait en inventer bien d'autres. Mais nous resteront sur le concept initial de John McCarthy
Nous verrons d'abord un premier exemple, sans POO :
- Une liste vide contiendra | None | None | (ni queue ni tête)
- Une liste à une seul élément n'a pas de queue mais a une tête : | 2 | None |
- Une liste à plusieurs éléments : | 5 | 4 3 2 1 |
Notre type abstrait liste utilise donc des chaines de python pour la représentation, car il en faut bien une.
Un deuxième exemple : toujours sans POO, mais avec une notation différente, plus proche des list de python. Vous devrez construire l'interface pour ce cas.
Un troisième exemple : ave la POO
La POO est un outil très pratique pour modéliser des Listes. Nous pourront ainsi par exemple construire des liste ainsi :
une liste a 1 attribut contenu. Dans le cas d'une liste vide cet arrtibut contiendra []
Dans la littérature, on trouve des présentation très variées, souvent de ce type :
(5 , (4 , (3 , (2, (1,None)))))
mais aussi des présentation plus proche de celle de python :
[ 5 4 3 2 1] ou [5, 4, 3, 2, 1] ou avec des ( ).....
Tout est correct, puisque ce n'est qu'un choix de la façon de représenter un type abstrait. La représentation est plus ou moins lisible, mais les plus simples ne rendent pas toujours bien compte de la façon dont les données sont traitées en mémoire et comment on va y accéder.
Définition : Primitive
Un Type Abstrait de Données (TAD), parfois aussi nommé Structure de Données Abstraite (SDA) est implémenté grâce à un nombre restreint de primitives.
Une primitive est une fonction permettant de manipuler le TAD. Dans certain cas, ce peut être une classe (dans ce cas, c'est la constructeur qui joue le rôle d'une primitive lors de l'instanciation), ou une méthode, mais ça revient au même.
Quand on vous demande d'implémenter le type abstrait liste, la question est incomplète, car les définitions de ce TAD sont très variées. Nous allons dans tout ce cours utiliser un jeu de 5 primitives, ce qui correspond à la définition la plus couramment utilisée.
- Créer une liste vide
- savoir si une liste est vide (True ou False)
- ajouter un élément
- prendre la tête de la liste
- prendre la queue de la liste
Définition : Interface
L'ensemble des primitive de notre TAD est nommé interface du TAD
Avec cette interface, notre TAD est défini. Bien sur, nous pourront créer d'autres fonctions pour manipuler notre TAD, comme par exemple longueur qui donnera la longueur de la liste, on index qui cherche l'indice d'un élément etc et .... mais ces fonctions devront être implémentées en utilisant les primitives.
Tous les langages modernes, et Python ne fait pas exception, utilisent des listes, souvent différente de ce modèle abstrait, et donc tous ont une implémentation d'un jeu de primitives pour manipuler des conteneurs.
Ces fonctions primitives ne sont pas directement utilisées par le programmeur, qui dispose d'autre syntaxes qui font appel à ces primitives.
un premier exemple
Ci dessous nous avons implémenté les 5 primitives. Vous ne pouvez pas voir le code de l'impémentation, mais vous allez utiliser help( ) pour lire leurs documentations.
 | lisez attentivement les spécifications de chaque primitive, car elles vous permettront de comprendre leur fonctionnement. |
A vous maintenant !
Un second exemple
Dans le premier exemple nous utilisons une notation assez éloignée de celle à laquelle vous êtes habitués en python. Nous allons utiliser une interface très similaire à la première, mais avec une notation plus simple (mais qui ne permet pas aussi facilement de distinguer tête et queue de la liste).
Comme vous le voyez ici, notre TAD peut assez bien être utilisé pour implémente un type LISTE ressemblant au type list de python. Néanmoins, les liste de python peuvent aussi être utilisée d'autres façon, et ne sont pas limitées aux même usages que notre LISTE.
Vous vous rendez bien compte que, malgré la ressemblance, ce type LISTE n'est pas le même que le type list de python.
