Structures de données linéaires - les listes

I. Structures de données linéaires⚓︎

De nombreux algorithmes "classiques" manipulent des structures de données plus complexes que de simples nombres (nous aurons l'occasion d'en voir plusieurs cette année).

Nous allons ici étudier quelques-unes de ces structures de données. Nous allons commencer par des types de structures relativement simples : les listes, les piles et les files.

Ces trois types de structures sont qualifiées de linéaires. Dans ce chapitre, nous allons etudier le type LISTE

liste

II. Les listes⚓︎

Le langage de programmation Lisp

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").

Les listes

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.

Implémentations

Il y a de nombreuses possibilités pour implémenter ce type abstrait, et vous n'avez pas besoin de connaître cette implémentation. Il vous 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.

Attention

🌵 L'informatique est jeune, en perpétuelle évolution. Les définitions ne sont pas toutes stabilisées. En particulier, on trouve différentes définitions du type abstrait LISTE. Nous étudierons ici le type abstrait LISTE souvent appelé récursif (issu du langage Lisp). Nous verrons dans les compléments une présentation des listes chaînées.

😊 Pas d'inquiétude, les types abstraits utilisés vous seront toujours définis précisément pour que vous puissiez les utiliser.

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.

La manière dont sont affichées les listes dépend de leur implémentation. Dans ce qui suit nous avons choisi un affichage qui ressemble à celui du type list de python :

Une liste vide s'écrit []

Exemple d'affichage d'une LISTE: [1, 2, 3]

III. Les primitives⚓︎

A vous d'utiliser les primitives

Chercher les spécifications de chaque primitive

Solution

Recopier dans la console, un par un :

Python Console Session

>>> help(Vide)
>>> help(Liste)
>>> help(est_vide)
>>> help(tete)
>>> help(queue)

A vous de jouer

Tester

Affichages

Vous observez que ces structures de types abstraits LISTE sont affichées avec des crochets, comme pour le type list de python. Ces crochets ne servent qu'à l'affichage, et aucune autre syntaxe utilisant ces crochets n'est possible avec ce type abstrait LISTE.

Exercice 1

Ecrire ci-dessous le code permettant de créer la liste liste_exemple qui serait affichée ainsi : ["a", "b", "c"].

Vous ne pouvez utiliser que les cinq primitives données ... et rien d'autre !

Solution

Python

# Creation de la liste ["a", "b", "c"]

liste_exemple = Vide()
liste_exemple = Liste("c", liste_exemple)
liste_exemple = Liste("b", liste_exemple)
liste_exemple = Liste("a", liste_exemple)
print(liste_exemple)

Exercice 2

Vous devez écrire le code pour :

créer une LISTE lst1 vide
afficher pour lst1 True ou False selon que lst1 est vide ou pas
créer une LISTE lst2 en ajoutant 2 en tête de lst1 et afficher lst2
puis afficher si lst2 est vide ou pas
ajouter 3 en tête de lst2 et afficher lst2
retirer 3 en tête de lst2 et afficher lst2

Astuce pour retirer 3 en tête de lst2 et afficher lst2

Ne peut-on pas s'aider de la fonction queue ?

Solution

Python

lst1 = Vide()
print(lst1)
print(est_vide(lst1))
lst2 = Liste(2, lst1)
print(lst2)
print(est_vide(lst2))
lst2 = Liste(3, lst2)
print(lst2)
lst2 = queue(lst2)
print(lst2)

Imbriquer

Tester

Exercice 3

Utiliser l'imbrication vue ci-dessus pour créer en une ligne la LISTE affichée ainsi : ["a", "b", "c"].

Solution

Python

lst = Liste( 'a' , Liste('b' , Liste( 'c', Vide() )))
print(lst)

IV. Autres fonctions⚓︎

On peut maintenant construire toutes les fonctions qui nous viennent à l'esprit.

Voici quatre exercices à réaliser ci-dessous, pour implémenter de nouvelles fonctions.

Pour chacun de ces exercices, vous ne pouvez utiliser que les fonctions "primitives" définies précédemment, ou une fonction que vous avez vous-même implémentée dans un des exercices ci-dessous.

Contrainte

Vous ne devez donc pas utiliser les instructions usuelles en python pour le type list, notamment len ou accéder un élément avec ma_liste[0] par exemple.

Exercice 1

Compléter la fonction suivante sans utiliser de fonction récursive.

Solution

Python

def longueur(liste):
    """
    Cette fonction renvoie la longueur de la liste de type LISTE
    Précondition : liste est du type abstrait liste
    Postcondition : Cette fonction renvoie un entier
    Exemple :
    >>> liste_1 = Vide()
    >>> liste_2 = Liste(1, liste_1)
    >>> liste_2 = Liste(2, liste_2)
    >>> longueur(liste_1)
    0
    >>> longueur(liste_2)
    2

    """
    cpt = 0
    while not est_vide(liste):
        liste = queue(liste)
        cpt = cpt + 1
    return cpt

Exercice 2

Compléter la fonction suivante en utilisant une fonction récursive.

Solution

Python

def longueur_rec(liste):
    """
    Cette fonction renvoie la longueur de la liste de type LISTE
    Précondition : liste est du type abstrait liste
    Postcondition : Cette fonction renvoie un entier
    Exemple :
    >>> liste_1 = Vide()
    >>> liste_2 = Liste(1, liste_1)
    >>> liste_2 = Liste(2, liste_2)
    >>> longueur_rec(liste_1)
    0
    >>> longueur_rec(liste_2)
    2

    """
    if est_vide(liste):
        return 0
    else:
        return 1 + longueur_rec(queue(liste))

Exercice 3

Compléter la fonction suivante qui enlève la tête de la liste.

Solution

Python

def enleve_tete(liste):
    """
    Cette fonction enlève la tête de la liste
    Précondition : liste est du type abstrait liste
    Postcondition : Cette fonction renvoie un type abstrait liste
    Exemple :

    >>> liste_1 = Vide()
    >>> liste_1 = Liste(1, liste_1)
    >>> liste_1 = Liste(2, liste_1)
    >>> liste_1 = Liste(3, liste_1)
    >>> enleve_tete(liste_1)
    [2, 1]

    """
    return queue(liste)

Exercice 4

Compléter cette fonction qui doit permettre de savoir si un élément x est dans la liste.

Contrainte

On interdit ici d'utiliser len, for, while et in

Compléter ci-dessous

Solution

```python def appartient(x, liste): """ Cette fonction retourne True si x appartient à liste, et False sinon Précondition : x est de n'importe quel type, liste est du type abstrait LISTE Postcondition : Cette fonction renvoie un booléen Exemples :

liste_1 = Vide() liste_1 = Liste(1, liste_1) liste_1 = Liste(2, liste_1) liste_1 = Liste(3, liste_1) appartient(4, liste_1) False appartient(3, liste_1) True liste_vide = Vide() appartient(2, liste_vide) False

"""

if est_vide(liste): return False elif x == tete(liste): return True else: return appartient(x, queue(liste))

```

Exercice 5

Compléter

Contrainte

On interdit ici d'utiliser len, for, while et in

Compléter ci-dessous

Solution

Python

def lire_index(n,liste):
    """
    Cette fonction retourne l'élément de rang n de liste.
    On utilise les conventions habituelles : le plus a gauche est de rang 0,
    le suivant de rang 1 etc...
    Si n est plus grand que longueur(liste)-1, ou negatif, la fonction affiche le message : n hors limite et retourne None.
    Precondition : n est de type entier, liste est de type abstrait LISTE
    Postcondition : le type retourne est celui de l element de rang n.La fonction retourne None si n est hors limite ou si
    la liste est vide. Elle affiche alors un message explicatif.

    Exemples :

    >>> liste_1 = Vide()
    >>> liste_1 = Liste(1, liste_1)
    >>> liste_1 = Liste(2, liste_1)
    >>> liste_1 = Liste(3, liste_1)
    >>> lire_index(1, liste_1)
    2
    >>> lire_index(3, liste_1)
    n hors limite
    >>> lire_index(4, liste_1)
    n hors limite
    >>> lire_index(0, liste_1)
    3
    >>> lire_index(-1, liste_1)
    n hors limite
    >>> liste_2 = Vide()
    >>> lire_index(2, liste_2)
    liste vide

    """

    if est_vide(liste) :
        print("liste vide")
        return None
    elif n > longueur(liste) - 1 or n < 0:
        print("n hors limite")
        return None
    elif n == 0:
        return tete(liste)
    else :
        return lire_index(n - 1, queue(liste))

Exercice 6

👉 Il existe plein de manière différentes de nommer les primitives, cela n'a pas d'importance. L'important est ce que fait la primitive. Pour montrer l'action des différentes primitives, voici par exemple une série d'instructions à partir de primitives de LISTES (les instructions ci-dessous s'enchaînent):

L = vide() => on a créé une liste vide
estVide(L) => renvoie vrai
cons(x, lst ) : => ajoute x en tête et renvoi lst
ajoutEnTete(3, L) => La liste L contient maintenant l'élément 3
estVide(L) => renvoie faux
ajoutEnTete(5, L) => la tête de la liste L correspond à 5, la queue contient l'élément 3
ajoutEnTete(8, L) => la tête de la liste L correspond à 8, la queue contient les éléments 3 et 5
t = supprEnTete(L) => la variable t vaut 8, la tête de L correspond à 5 et la queue contient l'élément 3
L1 = vide()
L2 = cons(8, cons(5, cons(3, L1))) => La tête de L2 correspond à 8 et la queue contient les éléments 3 et 5

👉 Voici une série d'instructions (les instructions ci-dessous s'enchaînent), expliquez ce qui se passe à chacune des étapes :

L = vide()
ajoutEnTete(10, L)
ajoutEnTete(9, L)
ajoutEnTete(7, L)
L1 = vide()
L2 = cons(5, cons(4, cons(3, cons (2, cons(1, cons(0,L1))))))

Solution

⏳ Attendre un peu ... 😊