Skip to content

Listes simplement chaînées

Énoncé

On cherche à implémenter des listes simplement chaînées similaires à celles vues en TD. Pour cela, on va utiliser un type Cellule et un type ListeSimplementChainee.

Une liste composée des entiers 4, 2, 5 et 3 ressemble à : liste simplement chaînée

Analyser le schéma ci-dessus pour bien comprendre quels doivent êtres les attributs de chacune des deux classes. Compléter ensuite le fichier liste_simplement_chainnees.py disponible ici et affiché ci-dessous. Des appels au traceur sont faits dans la fonction de teste du code fourni. Il faudra donc avoir un module traceur opérationnel (aller voir les exercices associés mentionnés ci-dessous si besoin). On pourra bien entendu rajouter tous les appels au traceur nécessaires afin de déboguer plus facilement notre code.

 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
#!/usr/bin/env python3

"""Listes simplements chainees + quelques operations"""

import traceur

class Cellule:
    """Une cellule d'une liste."""
    # TODO
    ...

class ListeSimplementChainee:
    """Une liste simplement chainee."""
    # TODO
    ...

def ajoute_en_tete(liste_chainee, valeur):
    """Ajoute une cellule en tete"""
    # TODO
    ...

def ajoute_en_queue(liste_chainee, valeur):
    """Ajoute une cellule en queue."""
    # TODO
    ...

def recupere_cellules(liste_chainee):
    """Renvoie un vecteur contenant toutes les cellules de la liste_chainee"""
    # TODO
    ...

def recherche(liste_chainee, valeur):
    """Recherche uen valeur dans la liste_chainee donnée.

    Renvoie la premiere cellule contenant la valeur donnée ou
    None si la valeur n'est pas trouvée dans la liste_chainee.
    """
    # TODO
    ...

# TODO
...

def supprime(liste_chainee, valeur):
    """Enleve la premiere cellule contenant la valeur donnée."""
    # TODO
    ...

def test_listes():
    """On teste les operations de base, dans differentes configurations."""
    liste_chainee = ListeSimplementChainee()
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_0")
    ajoute_en_tete(liste_chainee, 3)
    ajoute_en_tete(liste_chainee, 5)
    ajoute_en_tete(liste_chainee, 2)
    ajoute_en_tete(liste_chainee, 4)
    print("liste_chainee : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_1")
    print("recherche : ", recherche(liste_chainee, 3).valeur)
    supprime(liste_chainee, 5)
    print("apres suppression de 5 : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_2")
    supprime(liste_chainee, 4)
    print("apres suppression de 4 : ", liste_chainee)
    traceur.display_instance(liste_chainee,
                             visualize=False,
                             image_name="liste_chainee_3")

if __name__ == "__main__":
    test_listes()

Difficulté

star star star

Exercices associés