Skip to content

Listes chaînées basiques

Énoncé

Dans cet exercice, nous allons travailler sur le modèle de listes chaînées le plus simple possible : une liste chaînée sera tout simplement une référence vers la première cellule (ou None si la liste est vide). Vous aurez besoin de la classe Cellule de l'exercice précédent.

Important : on rappelle qu'on travaille sur des listes chaînées, c'est-à-dire des cellules liées les unes aux autres par des références. À ne pas confondre avec les list Python qu'on avait appelé précédemment tableaux dynamiques ou vecteurs, et qu'on manipulait avec des [], append, etc.

Complétez le programme ci-dessous, en implantant les fonctions suivantes :

  • une fonction est_vide(liste) qui renvoie True ssi la liste chaînée passée en paramètre est vide ;
  • une fonction insere_tete(liste, val) qui insère en tête de la liste chaînée une nouvelle cellule dont la valeur est val et qui renvoie la nouvelle liste (c.a.d une référence vers la nouvelle cellule insérée en tête) ;
  • une fonction insere_queue(liste, val) qui insère en queue de la liste chaînée une nouvelle cellule dont la valeur est val (on rappelle que dans cet exercice, on ne dispose pas d'une référence vers la queue de la liste chaînée), et qui renvoie la nouvelle liste (attention à bien réfléchir à ce que veut dire « nouvelle liste » dans le cas d'une liste vide et dans celui d'une liste non-vide) ;
  • une fonction affiche(liste) qui affiche à l'écran le contenu de la liste chaînée, par exemple sous le format 1 -> 7 -> 4 -> 3 -> FIN.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/usr/bin/env python3

"""
  Programme pour tester des listes chaînées basiques
"""

from random import randint

# TODO implantez les fonctions suivantes :
#   - est_vide
#   - insere_tete
#   - insere_queue
#   - affiche




def main():
    """
    Fonction principale
    """
    lsc = None  # creation d'une liste simplement chaînée vide
    print("Liste chaînée initiale vide : ", end="")
    affiche(lsc)
    print("est vide =", est_vide(lsc))
    for _ in range(10):
        ins_en_tete = randint(0, 1) == 1
        val = randint(0, 5)
        if ins_en_tete:
            print(f"Insertion en tête de {val}  : ", end="")
            lsc = insere_tete(lsc, val)
        else:
            print(f"Insertion en queue de {val} : ", end="")
            lsc = insere_queue(lsc, val)
        affiche(lsc)
    print("est vide =", est_vide(lsc))


main()

Correction

Cliquez ici pour révéler la correction.

listes_chainees_basiques.py :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#!/usr/bin/env python3

"""
  Programme pour tester des listes chaînées basiques
"""

from random import randint

# TODO implantez les fonctions suivantes :
#   - est_vide
#   - insere_tete
#   - insere_queue
#   - affiche


class Cellule:
    """
    Une cellule est composée d'une valeur et d'une référence vers la
      cellule suivante (ou None s'il n'y a pas de suivant)
    """

    # pylint: disable=too-few-public-methods

    def __init__(self, val, suiv):
        """
        Constructeur
        """
        self.val = val
        self.suiv = suiv

    def __str__(self):
        """
        Afficheur
        """
        return f"{self.val} -> "


def est_vide(lsc):
    """
    Teste si la liste chaînée est vide
    """
    return lsc is None


def insere_tete(lsc, val):
    """
    Insère une cellule de valeur val en tête de la liste chaînée.
    Renvoie la nouvelle cellule en tête de liste chaînée.
    """
    return Cellule(val, lsc)


def insere_queue(lsc, val):
    """
    Insère une cellule de valeur val en queue de la liste chaînée
    """
    cell = Cellule(val, None)
    if est_vide(lsc):
        return cell
    cour = lsc
    while cour.suiv is not None:
        cour = cour.suiv
    cour.suiv = cell
    return lsc

def affiche(lsc):
    """
    Affiche la liste chaînée
    """
    cour = lsc
    while cour is not None:
        print(cour, end="")
        cour = cour.suiv
    print("FIN")




def main():
    """
    Fonction principale
    """
    lsc = None  # creation d'une liste simplement chaînée vide
    print("Liste chaînée initiale vide : ", end="")
    affiche(lsc)
    print("est vide =", est_vide(lsc))
    for _ in range(10):
        ins_en_tete = randint(0, 1) == 1
        val = randint(0, 5)
        if ins_en_tete:
            print(f"Insertion en tête de {val}  : ", end="")
            lsc = insere_tete(lsc, val)
        else:
            print(f"Insertion en queue de {val} : ", end="")
            lsc = insere_queue(lsc, val)
        affiche(lsc)
    print("est vide =", est_vide(lsc))


main()