Liste comme structure abstraite

Pourquoi définir des structure abstraites ?

Qu'est-ce ?

Lorsque l'on fait des algorithmes ou du pseudo-code, on raisonne sur des structures comme TANT QUE ... RÉPÉTER. On définit comme cela fonctionne et comment l'utiliser. Mais on ne dit pas comment cela s'écrira dans un langage de programmation, on ne dit pas comment cela sera réalisé concrètement dans la machine.

Si on veut implémenter l'algorithme dans un certain langage, il suffira d'implémenter les structures utiles dans ce langage et l'algorithme sera compris.

Quel intérêt ?

Les langages sont variés, les technologies évoluent… On veut pouvoir raisonner sur un algorithme de façon abstraite sans avoir à se soucier de la façon dont cet algorithme sera effectivement réalisé – implémenté.

Pour cela on définit des structures en précisant les propriétés qu'elles doivent posséder sans se soucier de la façon dont elles seront implémentées dans tel ou tel langage.

Définition des listes

Liste

C'est un structure de données contenant un ensemble d'items et avec les caractéristiques suivantes :

Le nombre d'items est variable. On peut ajouter ou enlever des items.
Les items sont rangés dans un certain ordre. On peut donc associer chaque item avec un rang ou indice.
L'accès est séquentiel : Pour atteindre un item, il faut passer par les précédents.

Rappel : tableau

Un tableau est une structure proche d'une liste mais :

a un nombre fixe d'items, tous de même taille en mémoire,
a un accès direct : connaissant le rang de l'item, on peut l'atteindre directement sans passer par les précédents.

L'accès direct permet au tableau d'atteindre les items plus vite mais cela se fait au prix d'une taille fixe.

Le type list de Python, malgré son nom, n'implémente pas vraiment une liste. Il s'agit d'un tableau dynamique. C'est un tableau auquel on peut ajouter des items, ce qui conduit à une réorganisation de la mémoire, ce qui peut être long. Le type list permet donc de réaliser une liste. list va vite pour lire un item mais est plus lent s'il s'agit d'insérer ou supprimer un item autre que le dernier.

Comment représenter la liste ?

Prenons une liste L contenant dans l'ordre les éléments 4, 9, 17, 3. Il est utile de prévoir une façon d'indiquer clairement que L contient ces éléments.

On peut écrire L = [4, 9, 17, 3] comme pour le type list de Python. On pourrait écrire L = {4, 9, 17, 3} comme pour les tableaux dans certains langages.

Certains langages sont beaucoup plus formels et ne font pas de confusions comme Python qui appelle list un tableau… C'est le cas de oCaml. Je propose donc d'utiliser la notation des listes dans oCaml : L = 4:9:17:3

On convient de noter une liste, pour l'affichage à l'écran ou pour l'écrire sur papier, en adoptant la notation d'oCaml. Une liste contenant les éléments 4, 9, 17, 3 dans cet ordre, sera notée 4:9:17:3

J'insiste : Il ne s'agit pas du tout d'une notation Python ! Nous sommes en train de faire de l'informatique à un niveau abstrait, en pensée ou sur papier. Il s'agit juste d'une notation pour que l'on se comprenne, pas d'un code de programmation.

Interface

L'interface d'un objet définit comment on interagit avec lui. L'interface d'une liste va définir comment on crée une liste, comme on lui ajoute des items, comment on lit un item, etc.

Méthode	Description	remarque
CREER_LISTE_VIDE()	Renvoie une liste de contenu vide
LONGUEUR(L)	Renvoie le nombre d'items de la liste L
RECHERCHER(L,e)	Renvoie le rang du premier item de L égal à e	Que faire si e n'est pas dans la liste ?
LIRE(L,i)	Renvoie l'item de rang i dans la liste L précondition : `0 <= i < LONGUEUR(L)`
INSERER(L, e, i)	Insère dans L l'item e au rang i précondition: `0 <= i <= LONGUEUR(L)`	Modifie L ou renvoie une copie modifiée ?
MODIFIER(L, e, i)	Remplace, dans la liste L, l'item de rang i par e précondition: `0 <= i < LONGUEUR(L)`	idem
SUPPRIMER(L, i)	Supprime l'item de rang i dans la liste L précondition: `0 <= i < LONGUEUR(L)`	idem

Les remarques vous montrent qu'en dépit de la définition abstraite, il reste des choix à faire. Ces choix sont fait au moment de l'implémentation. Par exemple pour la recherche : Certains langages (Javascript) choisiront de renvoyer -1 si l'élément recherché est absent, d'autres (Python) choisiront de lever une erreur.

Exercices

Exercice 1

Donner la liste obtenue après exécution des lignes suivantes :

L = CREER_LISTE_VIDE()
INSERER(L, 'X', 0)
INSERER(L, 'B', 0)
INSERER(L, 'E', 1)
INSERER(L, 'Z', 0)
SUPPRIMER(L, 1)
MODIFIER(L, 'H', 2)

Exercice 2

Écrire en pseudo-code une fonction qui reçoit une liste L contenant des nombres et qui retourne la valeur de l'item maximum parmi ceux contenu.

Exercice 3

Écrire en pseudo-code une fonction qui reçoit une liste L contenant des entiers et qui retourne la somme de ces entiers.

Exercice 4

Écrire en pseudo-code une fonction qui reçoit une liste L et qui renvoie une liste M contenant les mêmes items que L mais en sens inverse.