Dans cette partie nous utiliserons donc ce jeu de primitives :
listeVide (): renvoie une LISTE vide
estListeVide (l) : renvoie True si l est une LISTE vide, False sinon
cons(x,l) : renvoie une nouvelle LISTE égale à l plus l'élément x ajouté en tête
listeQueue(l) : renvoie la queue de l
listeTete(l) : renvoie la tête de la LISTE
et nous ajouterons une première fonction dérivée des primitives de base :
longueur(l) : renvoie la longueur de la LISTE l
Le type des objet ainsi créés est nommé LISTE
Exercice à choix multiple : Complexité de la fonction cons :le nombre d'instructions requis pour cette fonction est :Correct !
Exercice à choix multiple : Complexité de la fonction longueur :le nombre d'instructions requis pour cette fonction est :Correct !
Bon, il est possible que notre représentation avec les tuples imbriqués ne vous plaise pas beaucoup... non ? En fait ceci n'est qu'une affaire de notation, et n'a pas grande importance. Dans l'exemple ci-dessous, nous allons modifier le constructeur pour changer la représentation de nos LISTE mais nous ne changeons pas les autres primitives (sauf listeQueue de façon marginale), et pas plus la fonction dérivée longueur, et tout fonctionne de façon identique :
Notez bien que, malgré l'implémentation un peu différente, les appels aux primitives sont strictement identiques (le programme principal est strictement identique, la fonction longueur également).
La représentation est bien la même, nous avons seulement affecté la notation.
Dans la suite, nous utiliserons cette version, qui donne un affichage plus lisible, mais pour autant, ne perdez pas de vue que nos LISTE sont toujours une tête et une queue.
