TP : Listes Chaînées, Piles et Files, Arbres Binaires¶
Exercice 1 : Deux Implémentations des Listes Chaînées¶
La structure d'une liste chaînée comportant 3 noeuds peut être représentée ainsi :
Dans ce TP, nous considérerons l'interface suivante pour les listes chaînées :
frominterfaceimportInterface,implementsclassInterfaceListeChainee(Interface):def__init__(self,donnee=None,liste_chainee=None):''' Constructeur permettant de créer une nouvelle liste. Cette liste peut être : - La liste vide - La liste ayant pour tête le noeud contenant donnee et pour queue liste_chainee param donnee : Donnée à ajouter en tête de liste param liste_chainee : Liste représentant la queue de nouvelle liste '''passdefest_vide(self)->bool:''' Méthode permettant de tester si la liste est vide return : True si la liste est vide, False sinon '''passdefajoute_en_tete(self,donnee):''' Méthode permettant d'ajouter un noeud en tête de liste param donnee : donnée du noeud à ajouter '''passdefsuppr_en_tete(self):''' Méthode permettant de supprimer le noeud en tête de liste et qui renvoie la donnée correspondante return : donnée du noeud en tête '''passdeflongueur(self)->int:''' Méthode qui renvoie la longueur de la liste chaînée return : nombre de données dans la liste '''pass
Partie A : Implémentation des Listes Chaînées avec des Tuples¶
Dans cette partie, nous allons implémenter une liste chaînée à l'aide des objets de type tuple :
La chaîne vide sera représentée par None
Une chaîne ne possédant qu'un seul noeud sera représentée par un couple.
Exemple : (3, None)
Une chaîne ne possédant plusieurs noeuds sera représentée par des couples imbriqués.
Exemple : (2, (7, (3, None)))
Q1. Définir une classe ListeChaineeV1 implémentant l'interface InterfaceListeChainee.
Le constructeur aura deux arguments :
Le paramètre donnee : type voulu, avec pour valeur par défaut None
Le paramètre liste_chainee : type ListeChaineeV1, avec pour valeur par défaut None
Il devra initialiser l'attribut d'instance tete qui représente le premier noeud de la liste.
Trois cas de figures possibles :
La liste est vide : l'attribut tete est initialisé à None
La liste comporte un seul noeud : l'attribut tete est initialisé avec le couple ({donnee}, None)
La liste comporte plus d'un noeud : l'attribut tete est initialisé avec le couple ({donnee}, {tete du second noeud})
Exemple :
# Création d'une liste chaînée vide : -> None>>>l1=ListeChaineeV1()# Création de la liste chaînée : -> [3 | .] -> None>>>l2=ListeChaineeV1(3)# Création de la liste chaînée : -> [2 | .] -> [7 | .] -> [3 | .] -> None>>>l3=ListeChaineeV1(2,ListeChaineeV1(7,ListeChaineeV1(3)))
Q2. Compléter la classe ListeChaineeV1 avec une méthode d'instance affiche qui permet d'obtenir les affichages donnés en exemple.
Q6. Créer une méthode get_donnee_tete qui renvoie la valeur de la donnée en tête de liste si la liste est non vide et None sinon.
In [ ]:
frominterfaceimportInterface,implementsclassInterfaceListeChainee(Interface):def__init__(self,donnee=None,liste_chainee=None):''' Constructeur permettant de créer une nouvelle liste. Cette liste peut être : - La liste vide - La liste ayant pour tête le noeud contenant donnee et pour queue liste_chainee param donnee : Donnée à ajouter en tête de liste param liste_chainee : Liste représentant la queue de nouvelle liste '''passdefest_vide(self)->bool:''' Méthode permettant de tester si la liste est vide return : True si la liste est vide, False sinon '''passdefajoute_en_tete(self,donnee):''' Méthode permettant d'ajouter un noeud en tête de liste param donnee : donnée du noeud à ajouter '''passdefsuppr_en_tete(self):''' Méthode permettant de supprimer le noeud en tête de liste et qui renvoie la donnée correspondante return : donnée du noeud en tête '''passdeflongueur(self)->int:''' Méthode qui renvoie la longueur de la liste chaînée return : nombre de données dans la liste '''pass
Q2. Définir une classe ListeChaineeV2 implémentant l'interface InterfaceListeChainee.
Le constructeur aura deux arguments :
Le paramètre donnee : type voulu, avec pour valeur par défaut None
Le paramètre liste_chainee : type ListeChaineeV2, avec pour valeur par défaut None
Il devra initialiser l'attribut d'instance tete qui représente le premier noeud de la liste.
Trois cas de figures possibles :
La liste est vide : l'attribut tete est initialisé à None
La liste comporte un seul noeud : l'attribut tete est initialisé avec le noeud -> [{donnee}, None]
La liste comporte plus d'un noeud : l'attribut tete est initialisé avec le noeud :
-> [{donnee}, {maillon de tete de la liste chaînée passée en paramètre}]
Q3. Compléter la classe ListeChaineeV2 avec une méthode d'instance affiche qui permet d'obtenir les affichages donnés en exemple.
On pourra utiliser la méthode represente des instances de type Noeud.
Exercice 2 : Implémentation des Piles et de Files utilisant les Listes Chaînées¶
Partie A : Implémentation d'une Pile avec des Listes Chaînées¶
Schéma de fonctionnement d'une pile :
Dans ce TP, nous considérerons l'interface suivante pour les piles :
frominterfaceimportInterface,implementsclassInterfacePile(Interface):def__init__(self):'''Constructeur permettant la création d'une pile vide'''passdefis_empty(self)->bool:''' Méthode permettant de tester si la pile est vide return : True si la pile est vide, False sinon '''passdefpush(self,donnee):''' Méthode permettant d'empiler donnee sur la pile param donnee : donnée à empiler '''passdefpop(self):''' Méthode permettant de dépiler l'élément en haut de la pile return : donnée en haut de la pile '''passdeftop(self):''' Méthode permettant d'accéder à l'élément en haut de la pile mais sans le supprimer return : donnée en haut de la pile '''passdefsize(self)->int:''' Méthode renvoyant le nombre d'éléments de la pile return : nombre d'élément de la pile '''pass
Q1. Définir une classe Pile implémentant l'interface InterfacePile.
Le constructeur devra initialiser l'attribut d'instance linked_list, de type ListeChaineeV2, à la liste vide.
Q2. Compléter le corps des méthodes d'instances is_empty, push, pop, top et size.
On pourra utiliser certaines méthodes d'instances définies pour la classe ListeChaineeV2 sur l'attribut linked_list...
Q3. Créer une méthode display permettant de d'obtenir les affichages donnés en exemple.
On utilisera la méthode affichage de la classe ListeChaineeV2.
Q4. Définir une classe PileV2 implémentant l'interface InterfacePile.
Le constructeur devra initialiser l'attribut d'instance linked_list à la liste vide de type ListeChaineeV1.
Est-il nécessaire de modifier le corps des autres méthodes d'instance ?
Exemple d'utilisation :
p=Pile()p.display()print('est vide ?',p.is_empty())print('sommet :',p.top())print('taille :',p.size())p.push(5)p.push(6)p.push(7)p.push(10)p.display()print('est vide ?',p.is_empty())print('sommet :',p.top())print('taille :',p.size())print('on dépile :',p.pop())print('on dépile :',p.pop())p.display()print('est vide ?',p.is_empty())print('sommet :',p.top())print('taille :',p.size())
Affichage produit :
-> None
est vide ? True
sommet : None
taille : 0
-> [10 | .] -> [7 | .] -> [6 | .] -> [5 | .] -> None
est vide ? False
sommet : 10
taille : 4
on dépile : 10
on dépile : 7
-> [6 | .] -> [5 | .] -> None
est vide ? False
sommet : 6
taille : 2
In [ ]:
frominterfaceimportInterface,implementsclassInterfacePile(Interface):def__init__(self):'''Constructeur permettant la création d'une pile vide'''passdefis_empty(self)->bool:''' Méthode permettant de tester si la pile est vide return : True si la pile est vide, False sinon '''passdefpush(self,donnee):''' Méthode permettant d'empiler donnee sur la pile param donnee : donnée à empiler '''passdefpop(self):''' Méthode permettant de dépiler l'élément en haut de la pile return : donnée en haut de la pile '''passdeftop(self):''' Méthode permettant d'accéder à l'élément en haut de la pile mais sans le supprimer return : donnée en haut de la pile '''passdefsize(self)->int:''' Méthode renvoyant le nombre d'éléments de la pile return : nombre d'élément de la pile '''pass
p=Pile()p.display()print('est vide ?',p.is_empty())print('sommet :',p.top())print('taille :',p.size())p.push(5)p.push(6)p.push(7)p.push(10)p.display()print('est vide ?',p.is_empty())print('sommet :',p.top())print('taille :',p.size())print('on dépile :',p.pop())print('on dépile :',p.pop())p.display()print('est vide ?',p.is_empty())print('sommet :',p.top())print('taille :',p.size())
Partie B : Implémentation d'une File avec des Listes Chaînées¶
Schéma de fonctionnement d'une file :
Dans ce TP, nous considérerons l'interface suivante pour les files :
frominterfaceimportInterface,implementsclassInterfaceFile(Interface):def__init__(self):'''Constructeur permettant la création d'une file vide'''passdefis_empty(self)->bool:''' Méthode permettant de tester si la file est vide return : True si la file est vide, False sinon '''passdefenqueue(self,donnee):''' Méthode permettant d'ajouter donnee en fin de file param donnee : donnée à ajouter '''passdefdequeue(self):''' Méthode qui supprime et renvoie le premier élément de la file return : donnée en début de file '''passdeffirst(self):''' Méthode permettant d'accéder l'élément en début de file mais sans le supprimer return : donnée en début de file '''passdefsize(self)->int:''' Méthode renvoyant le nombre d'éléments de la file return : nombre d'éléments de la file '''pass
Q1. Définir une classe File implémentant l'interface InterfaceFile.
Le constructeur devra initialiser l'attribut d'instance linked_list, de type ListeChaineeV2, à la liste vide.
Q2. Compléter le corps des méthodes d'instances is_empty, enqueue, dequeue, first et size.
On prendra la convention suivante : Le premier élément de la file correspondra au premier élément de la liste chaînée.
On pourra utiliser certaines méthodes d'instances définies pour la classe ListeChaineeV2 sur l'attribut linked_list...
Q3. Créer une méthode display permettant de d'obtenir les affichages donnés en exemple.
On utilisera la méthode affichage de la classe ListeChaineeV2.
Exemple d'utilisation :
f=File()f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())f.enqueue(5)f.enqueue(6)f.enqueue(7)f.enqueue(10)f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())print('on dépile :',f.dequeue())print('on dépile :',f.dequeue())f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())
Affichage produit :
-> None
est vide ? True
first : None
taille : 0
-> [5 | .] -> [6 | .] -> [7 | .] -> [10 | .] -> None
est vide ? False
first : 5
taille : 4
on dépile : 5
on dépile : 6
-> [7 | .] -> [10 | .] -> None
est vide ? False
first : 7
taille : 2
In [ ]:
frominterfaceimportInterface,implementsclassInterfaceFile(Interface):def__init__(self):'''Constructeur permettant la création d'une file vide'''passdefis_empty(self)->bool:''' Méthode permettant de tester si la file est vide return : True si la file est vide, False sinon '''passdefenqueue(self,donnee):''' Méthode permettant d'ajouter donnee en fin de file param donnee : donnée à ajouter '''passdefdequeue(self):''' Méthode qui supprime et renvoie le premier élément de la file return : donnée en début de file '''passdeffirst(self):''' Méthode permettant d'accéder l'élément en début de file mais sans le supprimer return : donnée en début de file '''passdefsize(self)->int:''' Méthode renvoyant le nombre d'éléments de la file return : nombre d'éléments de la file '''pass
f=File()f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())f.enqueue(5)f.enqueue(6)f.enqueue(7)f.enqueue(10)f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())print('on dépile :',f.dequeue())print('on dépile :',f.dequeue())f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())
Exercice 3 : Implémentation d'une File utilisant deux Piles¶
Dans cet exercice, nous allons voir comment implémenter une file à l'aide de deux piles.
On considère deux piles numérotées 1 et 2.
Voici l'algorithme pour la méthode enqueue(self, donnee) utilisant deux piles :
Tant que la pile n°1 n'est pas vide :
Utiliser la méthode `pop` sur la pile n°1 pour récupérer le sommet
Utiliser la méthode `push` sur la pile n°2 pour ajouter ce sommet à cette pile
FinTantQue
Utiliser la méthode `push` sur la pile n°1 pour ajouter la nouvelle donnée
Tant que la pile n°2 n'est pas vide :
Utiliser la méthode `pop` sur la pile n°2 pour récupérer le sommet
Utiliser la méthode `push` sur la pile n°1 pour ajouter ce sommet à cette pile
FinTantQue
Pour "dépiler", il suffira d'utiliser la méthode pop sur la pile n°1
Exemple : On "enfile" successivement les items 1, 2 et 3 dans cet ordre.
Q1. Définir une classe FileV2 implémentant l'interface InterfaceFile.
Le constructeur devra initialiser deux attributs d'instance p1 et p2 avec des piles vides.
Q2. Compléter le corps des méthodes d'instances is_empty, enqueue, dequeue, first, size et display.
On utilisera les méthodes appropriées de la classe Pile sur les attributs p1 et p2...
Exemple d'utilisation :
f=File2()f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())f.enqueue(5)f.enqueue(6)f.enqueue(7)f.enqueue(10)f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())print('on dépile :',f.dequeue())print('on dépile :',f.dequeue())f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())
Affichage produit :
-> None
est vide ? True
first : None
taille : 0
-> [5 | .] -> [6 | .] -> [7 | .] -> [10 | .] -> None
est vide ? False
first : 5
taille : 4
on dépile : 5
on dépile : 6
-> [7 | .] -> [10 | .] -> None
est vide ? False
first : 7
taille : 2
f=FileV2()f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())f.enqueue(5)f.enqueue(6)f.enqueue(7)f.enqueue(10)f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())print('on dépile :',f.dequeue())print('on dépile :',f.dequeue())f.display()print('est vide ?',f.is_empty())print('first :',f.first())print('taille :',f.size())
Exercice 4 : Implémentation d'une Pile utilisant deux Files¶
Q1. En vous inspirant de l'exercice précédent, implémenter une pile à l'aide de deux files.
On créera pour cela une nouvelle classe PileV2 implémentant l'interface Pile.
Q2. Tester le bon fonctionnement des différentes méthodes de la classe PileV2.
Exercice 5 : Implémentation d'un Noeud d'un Arbre Binaire¶
Un exemple d'arbre binaire :
Le nombre 7 est la donnée du noeud racine. Ce noeud possède :
Un fils gauche, ayant pour donnée le nombre 2
Un fils droit, ayant pour donnée le nombre 3
Le noeud ayant pour donnée 3 possède lui-même deux noeuds fils.
Les noeuds ayant pour données les nombres 2, 4 et 6 n'ont pas de fils. On parle alors de feuilles.
Q1. Définir une classe Node représentant le noeud d'un arbre binaire.
Le constructeur aura trois arguments :
Le paramètre data : type voulu
Le paramètre fils_gauche : type Node, avec pour valeur par défaut None
Le paramètre fils_droit : type Node, avec pour valeur par défaut None
Exemple :
# Création de l'arbre donné en exemplearbre=Node(7,Node(2),Node(3,Node(4),Node(6)))
Q2. Donner la représentation schématique des arbres suivants :
Q4. Définir la méthode spéciale __repr__ qui renverra de manière récursive la chaîne de caractères représentant le premier noeud ainsi que ses successeurs.