Cours NSI Terminale - Thème 1.
On rappelle que la structure d'une liste chaînée ressemble à ceci :
L'illustration montre une liste chaînée composée de 4 maillons. Chaque maillon est composé de 2 champs : une valeur et un pointeur vers le maillon suivant.
Pour implémenter une liste chaînée en python nous pourrions utiliser
La liste chaînée donnée en illustration pourrait donc être représentée ainsi :
maillons = [[3, 2], [8,None], [5, 1], [2,0]]
premier = 3
Vous constaterez que j'ai volontairement inscrit dans le tableau maillons
les éléments de la liste dans le désordre car il n'y a aucune raison que l'ordre des éléments corresponde à l'ordre dans le tableau maillons
si par exemple on insère en cours de route des éléments au milieu de la liste.
la variable premier
contient l'indice du premier élément de la liste, c'est donc le maillon [2,0]
correspondant à la valeur 2. L'élément suivant sera le maillon à l'indice 0 dans le tableau donc [3,2]
dont la valeur est 3. Ensuite on accède au maillon d'indice 2 donc [5,1]
de valeur 5 pour terminer par le maillon [8,None]
de valeur 8 marquant la fin de la liste. Au final la liste est donc bien $$2 - 3 - 5 - 8$$
Cette approche a le mérite de se baser sur des types python standard que vous conaissez bien mais nous avons besoin de deux variables pour décrire un seul objet
Cela alourdit énormément l'écriture des programmes que d'avoir un objet unique décrit par deux variables distinctes. Il y a moyen de faire beaucoup mieux grâce à la structure d'objets.
Dans ce TP, nous allons créer une classe ListeChainee permettant de créer et manipuler des objets de type liste chaînée.
class ListeChainee:
"""Implementation d'une liste chaînée"""
def __init__(self, maillons=[], premier=None):
"""Initialisation de la liste chainée"""
# tableau contenant les maillons de la liste
self.__maillons = maillons
# indice du premier élément.
self.__premier = premier # None lorsque la liste est vide
Comme vous le voyez, la classe ListeChainee regroupe en un seul objet les deux informations nécessaires à la gestion de notre liste chaînée à savoir
Nous utilisons ici des paramètres optionnels qui permettent le cas échéant d'initialiser notre liste chaînée avec du contenu.
Parfois nous ne voulons pas qu'il soit possible de modifier les valeurs des propriétés d'une classe autrement qu'en passant par les méthodes de la classe afin de préserver la cohérence des données.
Afin de protéger les propriétés d'un objet, on ajoute __ devant leur nom. Ainsi, elles ne seront accessibles que depuis les méthodes de la classe, pas au travers des instances de l'objet. On parle alors de propriétés privées (sous python, elles sont plutôt* cachées*).
Vous allez devoir implémenter les méthodes suivantes
premier()
longueur()
valeurs()
insere_debut(v)
v
v
au début de la listeinsere_fin(v)
v
v
à la fin de la listeAvant de vous laisser implémenter ces fonctionnalités, nous allons faire ensemble la première méthode et tester le comportement de notre classe.
class ListeChainee:
"""Implementation d'une liste chaînée"""
def __init__(self, maillons=[], premier=None):
"""Initialisation de la liste chainée"""
# tableau contenant les maillons de la liste
self.__maillons = maillons
# indice du premier élément.
self.__premier = premier # None lorsque la liste est vide
def premier(self):
"""renvoye la valeur du premier élément de la liste ou None si la liste est vide"""
return None if self.__premier is None else self.__maillons[self.__premier][0]
liste1 = ListeChainee()
# Aucun paramètre n'est passé, la liste1 est vide
print(liste1.premier())
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
Dans la cellule ci-desssus, j'ai fourni une liste de maillons et un premier élément à la création de la liste. Cela va permettre de l'initialiser avec du contenu. Nous allons pouvoir vérifier que le premier élément de la liste est bien 2 :
liste1.premier()
Essayons de récupérer l'indice du premier élément stocké das la propriété __premier : Vous constaterez une erreur. Cette propriété est cachée, on ne peut y accéder ni pour la consulter ni pour la modifier. C'est une sécurité nous garantissant l'intégrité des données.
liste1.__premier
L'ossature de la classe est déjà présente, il vous suffira de remplacer pass par la méthode que vous fabriquerez. Vous vous rappelez qu'une méthode se code comme une fonction, la seule différence est le paramètre self qui fait référence à l'objet qui contient la méthode. Ce paramètre est toujours le premier paramètre passé à la méthode.
class ListeChainee:
"""Implementation d'une liste chaînée"""
def __init__(self, maillons=[], premier=None):
"""Initialisation de la liste chainée"""
# tableau contenant les maillons de la liste
self.__maillons = maillons
# indice du premier élément.
self.__premier = premier # None lorsque la liste est vide
def premier(self):
"""renvoye la valeur du premier élément de la liste ou None si la liste est vide"""
return None if self.__premier is None else self.__maillons[self.__premier][0]
def longueur(self):
"""renvoie la longueur de la liste chainée (0 si elle est vide)."""
return 0 if self.__premier is None else len(self.__maillons)
def valeurs(self):
"""renvoye un tableau avec toutes les valeurs de la liste"""
pass
def insere_debut(self, v):
"""prend en paramètre la valeur à insérer v
insère la valeur v au début de la liste"""
pass
def insere_fin(self, v):
"""prend en paramètre la valeur à insérer v
insère la valeur v à la fin de la liste"""
pass
# YOUR CODE HERE
raise NotImplementedError()
# Test de la méthode valeur
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
assert liste1.valeurs() == [2, 3, 5, 8]
# Test de la méthode longueur
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
assert liste1.longueur() == 4
liste2 = ListeChainee()
assert liste2.longueur() == 0
# Test de la méthode insere_debut
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
liste1.insere_debut(-5)
assert liste1.valeurs() == [-5, 2, 3, 5, 8]
# Test de la méthode insere_fin
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
liste1.insere_fin(11)
assert liste1.valeurs() == [2, 3, 5, 8, 11]
Nous allons poursuivre l'ajout de méthodes à notre classe. Nous voudrions implémenter la méthode suivante :
insere_milieu(valeur, place)
valeur
et un emplacement place
dans la listevaleur
à l'emplaceemnt place
Cette méthode va nécessiter d'accéder aux propriétés privées __maillons et __premier. Puisque ce n'est pas possible directement, nous allons écrite des méthodes qui permettent de renvoyer ces valeurs sans toutefois permettre leur modification. Afin de sécuriser davantage les données, on renverra une copie du tableau maillon et non l'objet original. On est ainsi assuré qu'aucune modification ne sera réalisée sur ce dernier.
En programmation orientée objet, ces méthodes permettant d'accéder de manière sécurisée à des propriétés cachées s'appellent des accesseurs. Voici comment nous pouvons les implémenter :
class ListeChainee:
"""Implementation d'une liste chaînée"""
def __init__(self, maillons=[], premier=None):
"""Initialisation de la liste chainée"""
# tableau contenant les maillons de la liste
self.__maillons = maillons
# indice du premier élément.
self.__premier = premier # None lorsque la liste est vide
def lire_premier(self):
return self.__premier
def lire_maillons(self):
return [[m[0], m[1]] for m in self.__maillons]
def remplace_maillons(self, maillons):
self.__maillons = maillons
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
print(liste1.lire_premier())
print(liste1.lire_maillons())
Ainsi, nous accédons aux données interne de notre classe sans pour autant risquer de compromettre ces dernières par une écriture malheureuse. Dans l'exemple suivant, nous allons voir comment utiliser ces accesseurs pour implémenter l'algorithme d'insertion dans une lliste chaînée. Il vous restera ensuite à terminer notre classe avec la méthode concat()
class ListeChainee:
"""Implementation d'une liste chaînée"""
def __init__(self, maillons=[], premier=None):
"""Initialisation de la liste chainée"""
# tableau contenant les maillons de la liste
self.__maillons = maillons
# indice du premier élément.
self.__premier = premier # None lorsque la liste est vide
def lire_premier(self):
return self.__premier
def lire_maillons(self):
return [[m[0], m[1]] for m in self.__maillons]
def remplace_maillons(self, maillons):
self.__maillons = maillons
def premier(self):
"""renvoye la valeur du premier élément de la liste ou None si la liste est vide"""
return None if self.__premier is None else self.__maillons[self.__premier][0]
def longueur(self):
"""renvoie la longueur de la liste chainée (0 si elle est vide)."""
return 0 if self.__premier is None else len(self.__maillons)
def insere_milieu(self, valeur, pos):
"""prend en paramètre la valeur et la position
insère la valeur dans la liste à la position demandée
Si la position n'existe pas dans la liste, on insère à la fin"""
# On récupère les données internes
maillons = self.lire_maillons()
premier = self.lire_premier()
# On utilise les méthodes existantes pour les cas limites
if pos >= self.longueur():
self.insere_fin(valeur)
elif pos == 0:
self.insere_debut(valeur)
else:
# parcour de la liste à la recherche de la position
i = premier
for _ in range(pos-1):
if maillons[i][1] is not None:
i = maillons[i][1]
# On crée un nouveau maillon à la fin de la liste
maillons.append([valeur, maillons[i][1]])
# On change les liens de manière à insérer le maillon
maillons[i][1] = len(maillons)-1
self.remplace_maillons(maillons)
# Recopiez ici vos méthodes valeurs() et insere*()
# YOUR CODE HERE
raise NotImplementedError()
# Test de la méthode insere_milieu
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
liste1.insere_milieu(10,2)
assert liste1.valeurs() == [2, 3, 10, 5, 8]
Il ne vous reste plus à présent qu'à terminer notre classe ListeChainee en y ajoutant la méthode concat() :
concat(liste_c)
liste_c
liste_c
à la fin de la liste couranteclass ListeChainee:
"""Implementation d'une liste chaînée"""
def __init__(self, maillons=[], premier=None):
"""Initialisation de la liste chainée"""
# tableau contenant les maillons de la liste
self.__maillons = maillons
# indice du premier élément.
self.__premier = premier # None lorsque la liste est vide
def lire_premier(self):
return self.__premier
def lire_maillons(self):
return [[m[0], m[1]] for m in self.__maillons]
def remplace_maillons(self, maillons):
self.__maillons = maillons
def premier(self):
"""renvoye la valeur du premier élément de la liste ou None si la liste est vide"""
return None if self.__premier is None else self.__maillons[self.__premier][0]
def longueur(self):
"""renvoie la longueur de la liste chainée (0 si elle est vide)."""
return 0 if self.__premier is None else len(self.__maillons)
def insere_milieu(self, valeur, pos):
"""prend en paramètre la valeur et la position
insère la valeur dans la liste à la position demandée
Si la position n'existe pas dans la liste, on insère à la fin"""
# On récupère les données internes
maillons = self.lire_maillons()
premier = self.lire_premier()
# On utilise les méthodes existantes pour les cas limites
if pos >= self.longueur():
self.insere_fin(valeur)
elif pos == 0:
self.insere_debut(valeur)
else:
# parcour de la liste à la recherche de la position
i = premier
for _ in range(pos-1):
if maillons[i][1] is not None:
i = maillons[i][1]
# On crée un nouveau maillon à la fin de la liste
maillons.append([valeur, maillons[i][1]])
# On change les liens de manière à insérer le maillon
maillons[i][1] = len(maillons)-1
self.remplace_maillons(maillons)
# Recopiez ici vos méthodes valeurs() et insere*()
# YOUR CODE HERE
raise NotImplementedError()
# Test de la méthode concat
liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)
liste2 = ListeChainee([[6, 2], [8,None], [7, 1]], 0)
liste1.concat(liste2)
assert liste1.valeurs() == [2, 3, 5, 8, 6, 7, 8]