Aller au contenu

Liste (Bac 🎯)⚓︎

Licence Creative Commons
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.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

🐍 Script Python
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

🐍 Script Python
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

🐍 Script Python
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 :

🐍 Script Python
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 :

🐍 Script Python
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 :

🐍 Script Python
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 :

🐍 Script Python
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\).