Liste (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- la ressource Eduscol sur les types de données
- le cours de mon collègue Pierre Duclosson
🔖 Synthèse de ce qu'il faut retenir pour le bac
Type abstrait Liste⚓︎
Point de cours 3
Le type abstrait Liste permet de créer une séquence d'éléments ordonnés par leur position dans la liste.
- Un liste peut être vide.
- Si la liste est non vide, contrairement aux types abstraits tableau ou dictionnaire, un seul élément de la liste est accessible directement, c'est la tête de liste
- La queue de liste permet d'accéder aux éléments suivants. La queue de liste est une liste donc on accède au deuxième élément de la liste (s'il existe) en prenant la tête de la queue de liste. De même pour accéder au troisième élément on prend la tête de la queue de la queue de liste ...
L'accès aux éléments successifs de la liste n'est donc pas direct mais nécessite une répétition d'opérations identiques, appelée parcours de liste. On dit qu'une liste est une structure linéaire.
Une interface minimale du type abstrait Liste est la suivante :
| Opération | Signature | Description |
|---|---|---|
| creer_liste | creer_liste() | Renvoie une liste vide |
| liste_vide | liste_vide(lis) | Renvoie un booléen indiquant si la liste lis est vide |
| inserer | inserer(lis, elt) | Insère elt en tête de la liste lis, renvoie une nouvelle liste ou modifie la liste en place |
| tete | tete(lis) | Renvoie l'élément en tête de liste |
| queue | queue(lis) | Renvoie la liste privée de l'élément en tête liste |
Liste homogène
Dans tout le chapitre on se restreint à manipuler uniquement des listes dont tous les éléments sont de même type.
Exercice 3
💻 Saisir ses réponses sur Capytale
Complétez l'implémentation du type abstrait Liste avec un tableau dynamique Python pour stocker les éléments.
def creer_liste():
return []
def liste_vide(lis):
return len(lis) == 0
def inserer(lis, elt):
lis.append(elt)
def tete(lis):
return lis[len(lis) - 1]
def queue(lis):
return [lis[k] for k in range(0, len(lis) - 1)]
def test():
lis1 = creer_liste()
inserer(lis1, 10)
inserer(lis1, 9)
assert tete(lis) == 9
lis2 = queue(lis1)
assert tete(lis2) == 10
print("Tests réussis")
Parcours⚓︎
Méthode 2
Le parcours d'une liste est une répétition d'opérations tete pour lire l'élément accessible en tête de liste et queue pour passer à l'élément suivant.
Cette répétition peut s'effectuer de façon itérative avec une boucle ou récursive.
Exemple 2
On peut écrire une fonction déterminant la longueur d'une liste de façon itérative ou récursive. Retenez bien ce modèle, qu'on peut décliner pour tous les parcours de liste.
Parcours de liste itératif
def longueur(lis):
lon = 0
courant = lis # élément en tête
while not liste_vide(courant):
# si besoin traitement sur tete(courant)
lon = lon + 1
courant = queue(courant)
return lon
Parcours de liste récursif
def longueur_rec(lis):
if liste_vide(lis):
return 0
return 1 + longueur_rec(queue(lis))
Exercice 4
💻 Saisir ses réponses sur Capytale
Question 1
Écrivez une fonction qui prend en paramètre une liste de nombres et qui renvoie leur somme. Donnez une version itérative et une version récursive.
Version itérative :
def somme(lis):
s = 0
courant = lis # élément en tête
while not liste_vide(courant):
# si besoin traitement sur tete(courant)
s = s + tete(courant)
courant = queue(courant)
return s
Version récursive :
def somme_rec(lis):
if liste_vide(lis):
return 0
return tete(lis) + somme_rec(queue(lis))
Question 2
Écrivez une fonction index qui prend en paramètre une liste de nombres et un nombre et qui renvoie l'indice de la première occurrence du nombre dans la liste si il s'y trouve et None sinon. On numérotera les positions à partir de 0 pour la tête de liste.
Donnez une version itérative et une version récursive.
Version itérative :
def index(lis, v):
s = 0
courant = lis # élément en tête
pos = 0
while (not liste_vide(courant)) and (tete(courant) != v):
courant = queue(courant)
pos = pos + 1
if liste_vide(courant):
return None
return pos
Version récursive avec accumulateurs :
def index_rec(lis, v, pos):
if liste_vide(lis):
return None
if tete(lis) == v:
return pos
return index_rec(queue(lis), v, pos + 1)
Question 3
Peut-on faire une recherche dichotomique dans une liste dont les éléments sont triés dans l'ordre croissant avec la même efficacité que dans un tableau ?
Pas de façon efficace car on ne peut pas accéder directement à tous les éléments comme dans un tableau, seul l'élément en tête de liste est accessible directement. Pour accéder à l'élément en position \(k\) il faut parcourir la liste de l'élément de tête jusqu'à celui en position \(k\).