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 :

liste_chainee.JPG

Dans ce TP, nous considérerons l'interface suivante pour les listes chaînées :

from interface import Interface, implements

class InterfaceListeChainee(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
        '''
        pass

    def est_vide(self) -> bool:
        '''
        Méthode permettant de tester si la liste est vide
        return : True si la liste est vide, False sinon
        '''
        pass
         
    def ajoute_en_tete(self, donnee):
        '''
        Méthode permettant d'ajouter un noeud en tête de liste
        param donnee : donnée du noeud à ajouter
        '''
        pass
    
    def suppr_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
        '''
        pass
    
    def longueur(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.

Exemple :

>>> l1 = ListeChaineeV1()
>>> l1.affiche()
-> None
>>> l2 = ListeChaineeV1(3)
>>> l2.affiche()
-> [3 | .] -> None 
>>> l3 = ListeChaineeV1(2, ListeChaineeV1(7, ListeChaineeV1(3)))
>>> l3.affiche()
-> [2 | .] -> [7 | .] -> [3 | .] -> None

Q3. Compléter le corps de la méthode d'instance est_vide qui renvoie True si la liste est vide et False sinon.

Exemple :

>>> l1 = ListeChaineeV1()
>>> l1.est_vide()
True
>>> l2 = ListeChaineeV1(3)
>>> l2.est_vide()
False

Q4. Compléter le corps de la méthode d'instance ajoute_en_tete qui :

  • Prend en paramètre une valeur donnee
  • Affecte à l'attribut tete :
    • Le couple ({donnee}, None) si tete contient None
    • Le couple ({donnee}, {ancienne valeur de tete}) sinon

Exemple :

>>> l = ListeChaineeV1()
>>> l.affiche()
-> None
>>> l.ajoute_en_tete(3)
>>> l.affiche()
-> [3 | .] -> None 
>>> l.ajoute_en_tete(7)
>>> l.affiche()
-> [7 | .] -> [3 | .] -> None

Q4. Compléter le corps de la méthode d'instance suppr_en_tete qui permet de :

  • Modifier l'attribut tete en lui affectant le couple du second noeud
  • Renvoyer la valeur de la donnée du noeud supprimé
    Si l'attribut tete contient None, la méthode renverra simplement None.

Exemple :

>>> l = ListeChaineeV1(7, ListeChaineeV1(3))
>>> print(l.suppr_en_tete())
7
>>> print(l.suppr_en_tete())
3
>>> print(l.suppr_en_tete())
None

Q5. Compléter le corps de la méthode d'instance longueur qui permet de renvoyer la longueur de la liste chaînée.

Exemple :

>>> l1 = ListeChaineeV1()
>>> l1.longueur()
0
>>> l2 = ListeChaineeV1(3)
>>> l2.longueur()
1
>>> l3 = ListeChaineeV1(2, ListeChaineeV1(7, ListeChaineeV1(3)))
>>> l3.longueur()
3

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 [ ]:
from interface import Interface, implements

class InterfaceListeChainee(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
        '''
        pass

    def est_vide(self) -> bool:
        '''
        Méthode permettant de tester si la liste est vide
        return : True si la liste est vide, False sinon
        '''
        pass

    def ajoute_en_tete(self, donnee):
        '''
        Méthode permettant d'ajouter un noeud en tête de liste
        param donnee : donnée du noeud à ajouter
        '''
        pass

    def suppr_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
        '''
        pass

    def longueur(self) -> int:
        '''
        Méthode qui renvoie la longueur de la liste chaînée
        return : nombre de données dans la liste
        '''
        pass
In [ ]:
class ListeChaineeV1(implements(InterfaceListeChainee)):
    def __init__(self, donnee=None, liste_chainee=None):
        if donnee is None:
            self.tete = None
        elif liste_chainee is None:
            self.tete = (donnee, None)
        else:
            self.tete = (donnee, liste_chainee.tete)
    
    def est_vide(self):
        return self.tete is None
         
    def ajoute_en_tete(self, donnee):
        if self.tete is None:
            self.tete = (donnee, None)
        else:
            self.tete = (donnee, self.tete)
    
    def suppr_en_tete(self):
        if self.tete is not None:
            donnee, couple = self.tete
            self.tete = couple
            return donnee
        return None
    
    def longueur(self):
        if self.tete is None:
            return 0
        res = 0
        couple = self.tete
        while couple is not None:
            res += 1
            couple = couple[1]
        return res
        
    def affiche(self):
        if self.tete is None:
            print('-> None')
        else:
            donnee, couple = self.tete
            while couple is not None:
                print(f'-> [{donnee} | .]', end=' ')
                donnee = couple[0]
                couple = couple[1]
            print(f'-> [{donnee} | .] -> None', end=' ')
            print()
    
    def get_donnee_tete(self):
        if self.tete is not None:
            return self.tete[0]
        return None
In [ ]:
l1 = ListeChaineeV1()
l1.affiche()
l2 = ListeChaineeV1(3)
l2.affiche()
l3 = ListeChaineeV1(2, ListeChaineeV1(7, ListeChaineeV1(3)))
l3.affiche()

l1 = ListeChaineeV1()
print(l1.est_vide())
l2 = ListeChaineeV1(3)
print(l2.est_vide())

l = ListeChaineeV1()
l.affiche()
l.ajoute_en_tete(3)
l.affiche()
l.ajoute_en_tete(7)
l.affiche()

l = ListeChaineeV1(7, ListeChaineeV1(3))
print(l.suppr_en_tete())
print(l.suppr_en_tete())
print(l.suppr_en_tete())

l1 = ListeChaineeV1()
print(l1.longueur())
l2 = ListeChaineeV1(3)
print(l2.longueur())
l3 = ListeChaineeV1(2, ListeChaineeV1(7, ListeChaineeV1(3)))
print(l3.longueur())

Partie B : Implémentation des Listes Chaînées à l'aide d'une classe Noeud


Dans cette seconde partie, nous allons implémenter une liste chaînée utilisant des instances d'une classe Noeud.

Q1. Créer une classe Noeud définie récursivement contenant les trois méthodes suivantes :

  • Le constructeur qui initialise deux attributs d'instance donnee et suivant :
    • L'attribut donnee, de type quelconque, sera initialisée à l'aide du paramètre donnee.
    • L'attribut suivant, de type Noeud, sera initialisé avec le paramètre de type Noeud qui aura pour valeur par défaut None.
  • La méthode d'instance represente qui renverra la chaîne -> [{valeur de la donnée} | .]
  • 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.

Exemple :

>>> n1 = Noeud(3)
>>> n2 = Noeud(7, n1)
>>> n3 = Noeud(2, n2)
>>> print(n1.represente())
-> [3 | .]
>>> print(n2.represente())
-> [7 | .]
>>> print(n3.represente())
-> [2 | .]
>>> print(n1, n2, n3, sep='\n')
-> [3 | None]
-> [7 | -> [3 | None]]
-> [2 | -> [7 | -> [3 | None]]]
In [ ]:
class Noeud:
    def __init__(self, donnee, noeud_suivant=None):
        self.donnee = donnee
        self.suivant = noeud_suivant
        
    def represente(self):
        return f'-> [{self.donnee} | .]'
        
    def __repr__(self):
        return f'-> [{self.donnee} | {self.suivant}]'
In [ ]:
n1 = Noeud(3)
n2 = Noeud(7, n1)
n3 = Noeud(2, n2)
print(n1.represente())
print(n2.represente())
print(n3.represente())
print(n1, n2, n3, sep='\n')

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.

Exemple :

>>> l1 = ListeChaineeV2()
>>> l1.affiche()
-> None
>>> l2 = ListeChaineeV2(3)
>>> l2.affiche()
-> [3 | .] -> None 
>>> l3 = ListeChaineeV2(2, ListeChaineeV1(7, ListeChaineeV1(3)))
>>> l3.affiche()
-> [2 | .] -> [7 | .] -> [3 | .] -> None

Q4. Compléter le corps des méthodes est_vide, ajoute_en_tete, suppr_en_tete et longueur.

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

Exemple d'utilisation :

l = ListeChaineeV2()
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
l.ajoute_en_tete(3)
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
l.ajoute_en_tete(7)
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
print(l.suppr_en_tete())
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
print(l.suppr_en_tete())
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
print(l.suppr_en_tete())
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')

Affichage produit :

-> None
est_vide ? True, longueur : 0
-> [3 | .] -> None
est_vide ? False, longueur : 1
-> [7 | .] -> [3 | .] -> None
est_vide ? False, longueur : 2
7
-> [3 | .] -> None
est_vide ? False, longueur : 1
3
-> None
est_vide ? True, longueur : 0
None
-> None
est_vide ? True, longueur : 0
In [ ]:
class ListeChaineeV2(implements(InterfaceListeChainee)):
    def __init__(self, donnee=None, liste_chainee=None):
        if donnee is None:
            self.tete = None
        elif liste_chainee is None:
            self.tete = Noeud(donnee, None)
        else:
            self.tete = Noeud(donnee, liste_chainee.tete)
    
    def est_vide(self):
        return self.tete is None
    
    def ajoute_en_tete(self, donnee):
        self.tete = Noeud(donnee, self.tete)
    
    def suppr_en_tete(self):
        if self.tete is not None:
            res = self.tete.donnee
            self.tete = self.tete.suivant
            return res
        return None
    
    def longueur(self):
        if self.tete is None:
            return 0
        noeud = self.tete
        res = 0
        while noeud is not None:
            res += 1
            noeud = noeud.suivant
        return res
    
    def affiche(self):
        if self.tete is None:
            print('-> None')
        else:
            noeud = self.tete
            while noeud is not None:
                print(noeud.represente(), end=' ')
                noeud = noeud.suivant
            print('-> None')

    def get_donnee_tete(self):
        if self.tete is not None:
            return self.tete.donnee
        return None
In [ ]:
l = ListeChaineeV2()
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
l.ajoute_en_tete(3)
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
l.ajoute_en_tete(7)
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
print(l.suppr_en_tete())
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
print(l.suppr_en_tete())
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')
print(l.suppr_en_tete())
l.affiche()
print(f'est_vide ? {l.est_vide()}, longueur : {l.longueur()}')

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 :

pile.JPG

Dans ce TP, nous considérerons l'interface suivante pour les piles :

from interface import Interface, implements

class InterfacePile(Interface):
    def __init__(self):
        '''Constructeur permettant la création d'une pile vide'''
        pass

    def is_empty(self) -> bool:
        '''
        Méthode permettant de tester si la pile est vide
        return : True si la pile est vide, False sinon
        '''
        pass

    def push(self, donnee):
        '''
        Méthode permettant d'empiler donnee sur la pile
        param donnee : donnée à empiler
        '''
        pass

    def pop(self):
        '''
        Méthode permettant de dépiler l'élément en haut de la pile
        return : donnée en haut de la pile
        '''
        pass

    def top(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
        '''
        pass

    def size(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 [ ]:
from interface import Interface, implements

class InterfacePile(Interface):
    def __init__(self):
        '''Constructeur permettant la création d'une pile vide'''
        pass

    def is_empty(self) -> bool:
        '''
        Méthode permettant de tester si la pile est vide
        return : True si la pile est vide, False sinon
        '''
        pass

    def push(self, donnee):
        '''
        Méthode permettant d'empiler donnee sur la pile
        param donnee : donnée à empiler
        '''
        pass

    def pop(self):
        '''
        Méthode permettant de dépiler l'élément en haut de la pile
        return : donnée en haut de la pile
        '''
        pass

    def top(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
        '''
        pass

    def size(self) -> int:
        '''
        Méthode renvoyant le nombre d'éléments de la pile
        return : nombre d'élément de la pile
        '''
        pass
In [ ]:
class Pile(implements(InterfacePile)):
    def __init__(self):
        self.linked_list = ListeChaineeV2()
        #self.linked_list = ListeChaineeV1()
    
    def is_empty(self):
        return self.linked_list.est_vide()
    
    def push(self, donnee):
        self.linked_list.ajoute_en_tete(donnee)
    
    def pop(self):
        return self.linked_list.suppr_en_tete()
    
    def top(self):
        return self.linked_list.get_donnee_tete()
    
    def size(self):
        return self.linked_list.longueur()
    
    def display(self):
        self.linked_list.affiche()
In [ ]:
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 :

file.JPG

Dans ce TP, nous considérerons l'interface suivante pour les files :

from interface import Interface, implements

class InterfaceFile(Interface):
    def __init__(self):
        '''Constructeur permettant la création d'une file vide'''
        pass

    def is_empty(self) -> bool:
        '''
        Méthode permettant de tester si la file est vide
        return : True si la file est vide, False sinon
        '''
        pass

    def enqueue(self, donnee):
        '''
        Méthode permettant d'ajouter donnee en fin de file
        param donnee : donnée à ajouter
        '''
        pass

    def dequeue(self):
        '''
        Méthode qui supprime et renvoie le premier élément de la file
        return : donnée en début de file
        '''
        pass

    def first(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
        '''
        pass

    def size(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 [ ]:
from interface import Interface, implements

class InterfaceFile(Interface):
    def __init__(self):
        '''Constructeur permettant la création d'une file vide'''
        pass

    def is_empty(self) -> bool:
        '''
        Méthode permettant de tester si la file est vide
        return : True si la file est vide, False sinon
        '''
        pass

    def enqueue(self, donnee):
        '''
        Méthode permettant d'ajouter donnee en fin de file
        param donnee : donnée à ajouter
        '''
        pass

    def dequeue(self):
        '''
        Méthode qui supprime et renvoie le premier élément de la file
        return : donnée en début de file
        '''
        pass

    def first(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
        '''
        pass

    def size(self) -> int:
        '''
        Méthode renvoyant le nombre d'éléments de la file
        return : nombre d'éléments de la file
        '''
        pass
In [ ]:
class File(implements(InterfaceFile)):
    def __init__(self):
        self.linked_list = ListeChaineeV2()
    
    def is_empty(self):
        return self.linked_list.est_vide()
    
    def enqueue(self, donnee):
        if self.linked_list.tete is None:
            self.linked_list.ajoute_en_tete(donnee)
        else:
            noeud = self.linked_list.tete
            while noeud.suivant is not None:
                noeud = noeud.suivant
            noeud.suivant = Noeud(donnee)
    
    def dequeue(self):
        return self.linked_list.suppr_en_tete()
    
    def first(self):
        if self.linked_list.tete is not None:
            return self.linked_list.tete.donnee
    
    def size(self):
        return self.linked_list.longueur()
    
    def display(self):
        self.linked_list.affiche()
In [ ]:
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.

td_linkedlist_stack_queue_exo3.JPG

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
In [ ]:
class FileV2(implements(InterfaceFile)):
    def __init__(self):
        self.p1 = Pile()
        self.p2 = Pile()
    
    def is_empty(self):
        return self.p1.is_empty()
    
    def enqueue(self, donnee):
        while self.p1.size() != 0:
            self.p2.push(self.p1.pop())
        self.p1.push(donnee)
        while self.p2.size() != 0:
            self.p1.push(self.p2.pop())
              
    def dequeue(self):
        if self.p1.size() == 0:
            return None
        return self.p1.pop()
    
    def first(self):
        if self.p1.size() == 0:
            return None
        return self.p1.top()
    
    def size(self):
        return self.p1.size()
    
    def display(self):
        self.p1.display()
In [ ]:
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 :

td_linkedlist_stack_queue_exo5.JPG

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 exemple
arbre = Node(7, Node(2), Node(3, Node(4), Node(6)))

Q2. Donner la représentation schématique des arbres suivants :

a1 = Node(4, Node(3, Node(1)), Node(9, None, 6))
a2 = Node(9, Node(1), Node(7, Node(2, Node(5, Node(4), Node(3)), None), Node(6, Node(8))))

Q3. Créer une méthode d'instance get_data renvoyant le contenu de l'attribut data.

Exemple :

>>> n1 = Node(9, Node(5))
>>> n1.get_data()
9
>>> n2 = Node(7, Node(2), Node(3, Node(4), Node(6)))
>>> n2.get_data()
7

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.

Exemple :

>>> n1 = Node(9, Node(5))
>>> n1
(9, (5, None, None), None)
>>> n2 = Node(7, Node(2), Node(3, Node(4), Node(6)))
>>> n2
(7, (2, None, None), (3, (4, None, None), (6, None, None)))
In [ ]:
class Node:
    def __init__(self, data, fils_gauche=None, fils_droit=None):
        self.data = data
        self.fils_gauche = fils_gauche
        self.fils_droit = fils_droit

    def get_data(self):
        return self.data

    def __repr__(self):
        return f'({self.data}, {self.fils_gauche}, {self.fils_droit})'
In [ ]:
n1 = Node(9, Node(5))
print(n1)
n2 = Node(7, Node(2), Node(3, Node(4), Node(6)))
print(n2)