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
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 :
>>> help(Vide)
>>> help(Liste)
>>> help(est_vide)
>>> help(tete)
>>> help(queue)
A vous de jouer
Tester
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
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 !
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
# 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 quelst1
est vide ou pas - créer une LISTE
lst2
en ajoutant 2 en tête delst1
et afficherlst2
- puis afficher si
lst2
est vide ou pas - ajouter 3 en tête de
lst2
et afficherlst2
- retirer 3 en tête de
lst2
et afficherlst2
Astuce pour retirer 3 en tête de lst2
et afficher lst2
Ne peut-on pas s'aider de la fonction queue
?
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
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
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Exercice 3
Utiliser l'imbrication vue ci-dessus pour créer en une ligne la LISTE affichée ainsi : ["a", "b", "c"]
.
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
ma_liste = Liste('a', Liste('b', Liste('c', Vide())))
print(ma_liste)
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.
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
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.
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
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.
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
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
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
def appartient(x, liste):
"""
Cette fonction renvoie 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
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)
Solution
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 ... 😊
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)