Données Liste

Identification

Infoforall

11 - type abstrait de données Liste


L'an dernier, vous avez vu la différence entre un algorithme et son implémentation concrète en programme : un même algorithme peut être traduit dans différents langages (et donc différents programmes concrets) ou même en différentes versions de programmes pour un même langage.

Or, un algorithme manipule des données. Nous ne pouvons donc pas rattacher notre algorithme abstrait à des données concrètes en machine !

Vous allez donc comprendre aujourd'hui une nouvelle notion fondamentale en informatique.

Nous allons cette année faire la même chose pour les données : nous attarder sur les types abstraits de données qu'on retrouve dans la plupart des problèmes que l'informatique tente de résoudre. Et nous verrons qu'on peut les implémenter sous différentes structures de données concrètement en machine.

Ainsi,

  • un algorithme manipule des types abstraits de données (c'est la phase de conception théorique)
  • un programme manipule des structure de données concrètes (c'est la phase de réalisation pratique)

En réalité, ce n'est pas vraiment nouveau pour vous.

La plupart de nos algorithmes utilisaient des tableaux statiques (un type abstrait).

Et nous avons créé des programmes Python qui implémentent ces tableaux en le type list de Python (une structure de données concrète).

Bien entendu, le vocabulaire porte à confusion. Nous n'y pouvons rien... Mais vous allez voir qu'une fois qu'on a compris l'idée que se cache derrière type abstrait et structure concrète, tout sera beaucoup plus clair pour vous.

Documents de cours : open document ou pdf

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

1 - La Liste en tant que type abstrait de données

Nous allons voir ici qu'on peut travailler sur des données organisées de façon purement théorique, répondant à des contraintes théoriques, sans se soucier de la façon dont elles vont être concrétement programmées en interne par votre programme.

1er partie de la définition du type abstrait de données LISTE

Principe général d'organisation

Une liste est un type abstrait de données ayant les propriétés suivantes :

  • elle est composée d'une séquence finie et ordonnée d'éléments. On peut donc la voir comme un ensemble de couples (position, contenu). Quelque soit la nature de position, il doit permettre d'ordonner les éléments sans ambiguïtés.
  • on peut accéder librement à n'importe quel élément de la liste
  • on peut rajouter ou supprimer des éléments à n'importe quelle position
  • On désigne le premier élément de la liste sous le nom de tête (head en anglais). On ordonne les éléments à partir de cette tête.
  • Le reste des éléments de la liste porte le nom de queue (tail en anglais). Il s'agit donc de l'ensemble des éléments excepté la tête.

Exemple

Deux façons de voir graphiquement une liste contenant une tête valant 5 suivi d'une queue valant 8, 2 et 3.

  • 5823
  • 3285

01° Quel élément forme ici la tête ? Quelle est la séquence qui forme la queue ? Que contient au total la liste ?

1245-15

...CORRECTION...

La tête est ici identifiée par la couleur ET le sens des flèches.

La tête contient donc 12.

La queue est donc composée de la séquence (4, 5, -15).

La liste complète est donc (12, 4, 5, -15).

02° Quel élément forme ici la tête ? Quelle est la séquence qui forme la queue ? Que contient au total la liste ?

23124601

...CORRECTION...

La tête est ici identifiée par la couleur ET le sens des flèches.

La tête contient donc 1.

La queue est donc composée de (460, 12, 23).

La liste complète est donc (1, 460, 12, 23).

03° Sans l'information couleur. Quel élément forme ici la tête ? Quelle est la séquence qui forme la queue ? Que contient au total la liste ?

2112130

...CORRECTION...

La tête est ici identifiée par le sens des flèches : c'est le premier élément.

La tête contient donc 21.

La queue est donc composée de (12, 13, 0).

La liste complète est donc (21, 12, 13, 0).

04° Quel élément forme ici la tête ? Quelle est la séquence qui forme la queue ? Que contient au total la liste ?

20451018

...CORRECTION...

La tête est ici identifiée par le sens des flèches : c'est le premier élément.

La tête contient donc 18.

La queue est donc composée de (10, 45, 20).

La liste complète est donc (18, 10, 45, 20).

05° Seule la tête est indiquée. Quel élément forme ici la tête ? Quelle est la séquence qui forme la queue ? Que contient au total la liste ?

23 - 12 - 460 - 1

...CORRECTION...

La tête est ici identifiée par la couleur.

La tête contient donc 1.

La queue est donc composée des éléments situés linéairement derrière cette tête : (460, 12, 23).

La liste complète est donc (1, 460, 12, 23).

Deux Représentations abstraites du type LISTE

Comment représenter une telle liste ?

Représentation Tête - Queue

Une tête et une queue, voilà ce qui est vraiment fondamental dans une liste.

5823

Le 5 étant la tête de la liste qu'on nommera liste1, on notera sa queue liste2.

5liste2

On pourrait alors noter ceci : liste1 = (5, liste2).

Et que contient liste2 : une tête 8 et une queue liste3...

8liste3

liste2 = (8, liste3)

On obtient alors l'enchaînement suivant (si vous avez déjà fait la partie sur la récursivité, cela devrait vous rappeler l'empilement) :

  • liste1 = (5, liste2)
  • liste2 = (8, liste3)
  • liste3 = (2, liste4)
  • liste4 = (3, liste5)
  • liste5 = ()

Définition

On remarque donc qu'une liste peut être soit

  • l'ensemble d'une tête et d'une queue,
  • soit un ensemble vide.

On pourrait remonter dans l'autre sens dans nos déclarations et obtenir ceci (si vous avez fait la récursivité, on trouve un dépilement) :

  • liste4 = (3, ())
  • liste3 = (2, (3, ()))
  • liste2 = (8, (2, (3, ())))
  • liste1 = (5, (8, (2, (3, ()))))

Représentation en Séquence ordonnée

Ci-dessous, on remarque bien l'enchaînement des valeurs. On dispose donc de deux façons pour représenter symboliquement nos listes :

Avec des parenthèses : (5, (8, (2, (3)))) ou plus facilement par (5, 8, 2, 3)

Avec des crochets : [5, [8, [2, [3]]]] ou plus facilement par [5, 8, 2, 3]

Avec des accolades : {5, {8, {2, {3}}}} ou plus facilement par {5, 8, 2, 3}

Ou avec chevrons : <5, <8, <2, <3>>>> ou plus facilement par <5, 8, 2, 3>

Il faut juste choisir, le noter clairement et s'y tenir dans le cadre d'un même projet.

Ici, nous utiliserons des parenthèses par exemple.

Retenez donc bien qu'on peut représenter une même série de données de plusieurs façons tout en ne changeant rien aux données elles-mêmes.

06° Donner deux représentations de la liste suivante (en mode (tete, queue) et en mode sequence d'éléments ordonnés) :

124

...CORRECTION...

En représentation (tête, queue)

(12, liste2)

(12, (4, ()))

En séquence linéaire : (12, 4)

07° Donner deux représentations de la liste suivante (en mode (tete, queue) et en mode sequence d'éléments ordonnés) :

5210

...CORRECTION...

Première représentation

(5, liste2)

(5, (2, liste3))

(5, (2, (10, ())))

La deuxième représentation est donc (5, 2, 10).

2e partie de la définition du type abstrait de données LISTE : son interface

Un type abstrait de données est en réalité défini par deux choses :

  1. un principe général d'organisation des données stockées (c'est ce qu'on a vu ci-dessus)
  2. les fonctions d'interface permettant à l'algorithme d'interagir avec les données stockées (on va le voir ci-dessous)

Description de l'interface du type abstrait Liste

On doit donc donner la description des opérations fondamentales que les algorithmes vont pouvoir effectuer sur le type Liste.

L'une des spécificités du type liste est que sa définition est très très large. Il n'existe pas réellement de normalisation des fonctions d'interface. Le tout est que votre propre version puisse ếtre équivalente à ceci :  :

Principe de l'interface entre l'utilisateur et les données
  1. nouvelleListe() : on crée une nouvelle liste vide. On pourra l'identifier à (), None ou encore Nil... En anglais, cela pourrait donner newList.
  2. estVide(lst) : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide. En anglais, cela pourrait donner isNil ou isNull.
  3. inserer(elt, lst) : on ajoute l'élément elt dans la liste lst. Plusieurs versions sont possibles :
    • Où insérer ? En tête, à la fin, à la position k...
    • On modifie en place ? ou on renvoie une nouvelle liste ?

    Le tout est d'avoir au moins une version de cette méthode. En anglais, cela pourrait se nommer add.

  4. supprimer(lst et + ?) : on supprime un élément de la liste lst. Encore une fois, il faudra définir
    • Quel est l'élément supprimé (la tête, la fin de la queue, la position k...)
    • On modifie la liste en place ou en renvoie une nouvelle liste ?
    • On renvoie l'élément qu'on vient de supprimer ou pas ?

    En anglais, ça pourrait se nommer .

  5. lire(lst et + ?) : on lit le contenu d'un élément précis de la liste. Encore une fois, il faudra détailler la méthode utilisée : on envoie le numéro d'index ? on passe au suivant en fournissant l'identifiant d'un élément ? Il existe beaucoup de possibilités.

Tous les types de données qui collent à la définition et qui possèdent des fonctions similaires sont donc des listes.

Nous allons maintenant regarder quelques versions précises, compatibles avec le cas général.

Néanmoins, s'agissant de fonctions théoriques que nous allons devoir utiliser plus tard dans un vrai programme, il faut réfléchir à la manière dont nous allons concevoir notre interaction :

  1. Via de la programmation impérative : c'est la programmation que nous avons utilisée le plus souvent. C'est une suite d'instructions exécutées dans l'ordre qui permet au programme de modifier son état.
  2. Via de la programmation orientée objet : on crée des objets qui interagissent entre eux. On a donc besoin de modifier certaines structures par effet de bord. Voir vos activités et votre cours sur les objets.
  3. Via de la programmation fonctionnelle : tout est basé sur des 'fonctions pures', des fonctions assimilables aux fonctions mathématiques : elles ne travaillent qu'avec les données qu'on leur transmet en paramètres (elles ne lisent aucune variable globale), qui ne modifient aucune variable globale (même par effet de bord) et qui fournissent juste une réponse.
  4. ... et beaucoup d'autres non exigibles en NSI ...

2 - Définitions précises acceptables

Description des entrées-sorties des fonctions

  • Liste désigne une liste (le type abstrait)
  • Elt désigne le ou les types acceptables pour les contenus de notre liste :
  • Les types de données standards (booléens, entiers...) seront précisés en utilisant la dénomination Python par choix arbitraire.

Commençons par voir l'un des cas les plus basiques. Grace à lui, nous allons voir que nous pourrions bâtir les suivants.

Exemple 1 : Interface plutôt restrictive qui n'agit que sur la tête

Pour ce premier exemple, j'ai choisi de travailler avec le paradigme fonctionnel. Mais nous aurions pu définir des fonctions similaires en objet ou en impératif.

Voici une proposition des fonctions d'interface pour ce paradigme (d'autres possibilités existent, il n'y a pas de normalisation). Cette proposition mime les listes de LISP initialement.

Principe de l'interface LISP entre l'utilisateur et les données
  1. nouvelleListe() -> Liste : on crée une nouvelle liste vide (). En anglais, cela pourrait donner newList.
  2. listeA = nouvelleListe()
    Le contenu de listeA est alors ().

  3. estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide. En anglais, cela pourrait donner isEmpty ou isNull ou isNil.
  4. listeA = nouvelleListe()
    estVide(listeA) va donc renvoyer l'équivalent de True (il faut alors voir comment a été défini votre type abstrait Booléen pour savoir ce que vous devriez écrire : True, true, Vrai, vrai, 1, Haut, Cool...).

  5. 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.
  6. listeA = nouvelleListe()
    listeB = insererTete(5, listeA)
    listeB contient alors quelque chose comme (5, ()) qu'on pourrait noter simplement (5,).

    listeB = insererTete(15, listeB)
    listeB contient alors quelque chose comme (15, (5, ())), qu'on peut plutôt représenter par (15, 5).

  7. 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.
  8. On considère que listeB contient (25, (15, (5, ()))) ou (25, 15, 5)
    listeC = supprimerTete(listeB)
    listeC contient désormais (15, (5, ())) ou (15, 5).
    Par contre, listeB contient toujours (25, (15, (5, ()))) ou (25, 15, 5)

    Souvenez-vous qu'en fonctionnel, on n'utilise pas l'effet de bord. On obtient donc bien une nouvelle liste qui est la queue de la liste reçue en paramètre. Historiquement, dans LISP cette fonction se nomme cdr (comme contents of decrement register).

  9. lireTete(lst:Liste) -> Elt : on renvoie la tête de la liste lst. Attention, on ne modifie pas la liste ! Dans LISP, cette fonction se nomme car (pour contents of address register)
  10. On considère que listeB contient (25, (15, (5, ())))
    recup = lireTete(listeB)
    recup contient alors désormais 25. La liste n'a pas été modifiée.

08° Donner le contenu des variables au fur et à mesure de l'exécution de ce code. J'utilise une syntaxe type Python pour mimer notre pseudo-langage.

1 2 3 4 5 6
listeA = insererTete(4, nouvelleListe()) listeB = insererTete(6, listeA) listeC = insererTete(0, listeB) x = lireTete(listeC) listeD = supprimerTete(listeC) a = listeB == listeD

...CORRECTION...

Ligne 1 : listeA contient (4, ()) ou (4,)

Ligne 2 : listeB contient (6, (4, ())) ou (6, 4)

Ligne 3 : listeC contient (0, (6, (4, ()))) ou (0, 6, 4)

Ligne 4 : x contient 0

Ligne 5 : listeD contient (0, (6, (4, ()))) ou (0, 6, 4)

Pour la ligne 6, on ne peut pas savoir... Il faut savoir ce qui a été décidé. Les contenus sont similaires mais pas leurs identifiants-mémoires.

Si on part sur le langage que vous connaissez le plus (Python), un test d'égalité peut donner True ou False en fonction des cas.

Avec un type mutable, == teste les adresses. On aurait donc False.

Avec un type non mutable, == teste le contenu. On aurait donc True.

Mais... Nous ne sommes pas censés nous demander comment cela va se passer dans tel ou tel langage ! Souvenez-vous que le type abstrait sert à l'élaboration d'algorithme, pas à la réalisation concrète d'un programme dans un langage donné.

Comme vous le voyez, il manque en réalité encore des informations dans notre type abstrait : Si vous voulez tester l'égalité entre deux Listes, il faudra donc expliquer clairement ce que devrait renvoyer une fonction estEgal qu'on pourrait rendre équivalente à l'écriture ==.

Comme vous le voyez, nous n'avez fait que gratter le sommet de l'iceberg :o)

Bon, maintenant que vous avez compris le principe de la tête et de la queue, nous allons représenter de cette façon simplifiée la liste tant qu'elle ne comporte que des éléments de même type :

listeC contient (0, (6, (4, ())))

listeC représentée par (0, 6, 4)

Tiré de Wikipédia :

Cette utilisation des parenthèses pour générer des listes dans LISP donne lieu à des moqueries utilisant l'acronyme LISP : « Lots of Irritating and Silly Parentheses » (« Des tas de parenthèses irritantes et idiotes »), ou « Lots of Insipid and Stupid Parentheses » (« Des tas de parenthèses insipides et stupides »), ou « Langage Informatique Stupidement Parenthésé », ou « Langage Insipide Saturé de Parenthèses ».

09° Fournir l'ensemble des instructions qui vont permettre de passer de la liste listeA contenant initialement (0, 6, 4) à un contenu correspondant à (10, 6, 4)

Voici la première ligne en pseudo-Python pour vous éviter de la taper :

1
listeA = insererTete(0, insererTete(6, insererTete(4, ())))

...CORRECTION...

1 2 3
listeA = insererTete(0, insererTete(6, insererTete(4, ()))) listeA = supprimerTete(listeA) listeA = insererTete(10, listeA)

10° Fournir l'ensemble des instructions qui vont permettre de passer de la liste listeA contenant initialement (0, 6, 4) à un contenu correspondant à (10, 45, 4)

Voici le début en pseudo-Python si ça peut vous éviter de la taper :

1
listeA = insererTete(0, insererTete(6, insererTete(4, ())))

...CORRECTION...

1 2 3 4 5
listeA = insererTete(0, insererTete(6, insererTete(4, ()))) listeA = supprimerTete(listeA) listeA = supprimerTete(listeA) listeA = insererTete(45, listeA) listeA = insererTete(10, listeA)

Ou alors en moins long mais avec de l'imbrication :

1 2 3
listeA = insererTete(0, insererTete(6, insererTete(4, ()))) listeA = supprimerTete( supprimerTete(listeA) ) listeA = insererTete(10, insererTete(45, listeA))

Si vous avez déjà fait l'activité Récursivité, vous devriez voir qu'on va pouvoir utiliser la récursivité pour réaliser ces changements.

11° Du coup, en utilisant uniquement les fonctions d'interface ci-dessus, pourrons-nous créer les fonctions suivantes également ? Expliquer rapidement la technique sans rentrer dans les détails.

  1. insererPosition(x:Elt, lst:Liste, position:int) -> Liste : on renvoie une nouvelle liste où l'élément fourni n 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.
  2. listeA = (12, 15, 18, 4)
    listeB = inserer(5, listeA, 2)
    listeB contient alors (12, 15, 5, 18, 4).

  3. supprimerPosition(lst:Liste, position:int) -> Liste : on renvoie une nouvelle liste où l'élément en position position est supprimé, rendant la liste moins longue.
  4. listeA = (12, 15, 18, 4)
    listeB = supprimer(listeA, 1)
    listeB contient alors (12, 18, 4).

  5. supprimerElement(lst:Liste, x:Elt) -> Liste : on renvoie une nouvelle liste où la première occurence de l'élément x est supprimée (si on en trouve une), rendant la liste moins longue.
  6. listeA = (12, 15, 4, 18, 4)
    listeB = supprimer(listeA, 4)
    listeB contient alors (12, 15, 18, 4).

...CORRECTION...

Et oui. Il suffira dans les trois cas de démonter en partie notre liste (mémoriser les têtes, supprimer les têtes) puis de la remonter en rajouter les nouvelles valeurs voulues pour les têtes successives.

Comme vous pouvez le remarquer, avec quelques fonctions de base, on peut parvenir à réaliser des fonctions beaucoup plus complexes que les primitives. On ne peut donc pas limiter réellement une liste à la manipuler (suppression, rajout, lecture) de la tête. Si on peut faire cela sur la tête, on peut le faire sans problème sur n'importe quel autre élément, mais cela aura un coût...

C'est l'une des raisons de la difficulté à définir précisement ce type abstrait Liste : chacun aura son assemblage préféré de fonctions d'interface. Mais au final, elles auront toutes les mêmes possibilités théoriques.

Exemple 2 : Liste plus souple
Principe de l'interface d'une liste plus souple
  1. nouvelleListe() -> Liste : on crée une nouvelle liste vide (). En anglais, cela pourrait donner newList.
  2. listeA = nouvelleListe()
    Le contenu de listeA est alors ().

  3. estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide. En anglais, cela pourrait donner isEmpty ou isNull ou isNil.
  4. listeA = nouvelleListe()
    estVide(listeA) va donc renvoyer l'équivalent de True (il faut alors voir comment a été défini votre type abstrait Booléen pour savoir ce que vous devriez écrire : True, true, Vrai, vrai, 1, Haut, Cool...).

  5. insererPosition(x:Elt, lst:Liste, position:int) -> Liste : on renvoie une nouvelle liste où l'élément fourni n 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.
  6. listeA = (12, 15, 18, 4)
    listeB = inserer(5, listeA, 2)
    listeB contient alors (12, 15, 5, 18, 4).

  7. supprimerPosition(lst:Liste, position:int) -> Liste : on renvoie une nouvelle liste où l'élément en position position est supprimé, rendant la liste moins longue.
  8. listeA = (12, 15, 18, 4)
    listeB = supprimer(listeA, 1)
    listeB contient alors (12, 18, 4).

  9. lirePosition(lst:Liste, position:int) -> Liste : on renvoie l'élément stocké en position position.
  10. listeA = (12, 15, 18, 4)
    reponse = lirePosition(listeA, 1)
    reponse contient alors 15.

3 - Implémentation

Lorsqu'on veut réellement réaliser un programme, il faut passer de l'abstraction algorithmique (un algorithme agissant sur des types abstraits) à une réalisation pratique (programme agissant sur des structures de données).

Implémentation et encapsulation

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 en structure de données réelles en machine.

L'utilisateur n'a à connaître que les rôles et prototypes des fonctions d'interface. Deux avantages :

  • Si vous désirez modifier le code interne de la structure de données pour qu'elle soit plus performante, rien ne change de l'extérieur : les programmes de l'utilisateur seront toujours fonctionnels.
  • La structure de données a été concue et vérifiée pour être fonctionnelle. L'utilisateur n'a pas à modifier ce code au risque de le casser, parfois sans s'en rendre compte.
Interface et encapsulation

C'est le principe de l'encapsulation, que nous avons déjà rencontré également sur les objets. Ce principe peut bien entendu être utilisé sur des programmes non-objet.

Selon les langages, certains types abstraits sont déjà implémentés efficacement en pratique. Le langage de programmation possède alors déjà des classes ou des types natifs permettant de les utiliser.

Par exemple, en Python :

  • 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.

Comme vous le voyez, certains noms vont à la fois référence à un type abstrait et à une structure de données présente nativement dans un langage.

Nous allons voir la prochaine fois qu'il y a globalement trois façons de voir les listes :

  1. en utilisant un tuple de deux éléments : la tête et la queue
  2. en utilisant un tableau tel que vous le connaissez déjà
  3. en utilisant une liste chainée

4 - FAQ

Activité publiée le 21 09 2020
Dernière modification : 17 10 2020
Auteur : ows. h.