:

structure de données abstraites linéaires II

Implémentation à l'aide de la POO

1. En utilisant une liste Python

1.1. Type abstrait liste

class Liste:
    """
        Implémentation d'une liste à l'aide d'une liste Python et de la POO.
    """
    
    def __init__(self) -> None:
        """Crée et initialise une liste vide"""
        self.donnees = []
    
    def est_vide(self) -> bool:
        """Renvoie True si la liste est vide. False, sinon."""
        return self.donnees == []
    
    def est_vide2(self):
        """Renvoie True si la liste est vide."""
        return len(self.donnees) == 0

    def premier(self) -> object:
        """
            Renvoie la valeur de l'élément de tête sans le supprimer.
            Lève une IndexError si l'instance est vide.
        """
        if self.est_vide():
            raise IndexError("Liste vide : impossible de lire la tête")
        else:
            return self.donnees[0]
        
    def queue(self) -> Liste:
        """
            Renvoie la liste privée de son premier élément.
            Lève une IndexError si la liste est vide.
        """
        ...
    
    def inserer_en_tete(self, elt) -> None:
        """Insère elt à la tête de la liste."""
        ...
    
    def __str__(self) -> str:
        return f"{self.donnees}"
    
    def __repr__(self) -> str:
        return f"Liste({self.donnees})"

Faites-vous plaisir 1 :

Compléter les méthodes queue et inserer_en_tete de la classe Listes

1.2. Pile

class Pile:
    """
        Implémentation d'une pile à l'aide d'une liste Python et de la POO.
    """
    
    def __init__(self) -> None:
        """Crée et initialise une pile comme une pile vide"""
        self.donnees = []
    
    def __len__(self) -> int:
        """Renvoie le nombre d'éléments de la pile."""
        return len(self.donnees)

    def est_vide(self) -> bool:
        """Renvoie True si la pile est vide."""
        return len(self.donnees) == 0 
    
    def empiler(self, elt) -> None:
        """Insère elt au sommet de la pile (à l'exrême droite dans la pile)."""
        self.donnees.append(elt)
        
    def sommet(self) -> object:
        """
            Renvoie (sans le supprimer) l'élément au sommet (c'est-à-dire l'élément à l'extême droite dans la pile).
            Lève une IndexError si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("Pile vide : impossible de lire le sommet !")
        return self.donnees[-1]
    
    def depiler(self):
        """
            Renvoie et supprime l'élément au sommet de la pile.
            Lève une IndexError si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("Pile vide : dépilement impossible !")
        return self.donnees.pop()
    
    def __str__(self):
        return f"{self.donnees}"
    
    def __repr__(self):
        return f"Pile({self.donnees})"

une_pile = Pile()

# On donne
graphe = {
    "a": [1, 2, 3],
    "e": [4, 5, 6],
    "i": [7, 8, 9],
    "o": [10, 11, 13],
    "u": [14, 15, 16],
    "y": [17, 18, 19]
}

Faites-vous plaisir 2 :

1. On considère l'objet graphe, ci-dessus
   1. Créer une instance de Pile nommée pile_de_graphe.
   2. À l'aide d'une boucle for empiler dans pile_de_graphe les valeurs suivantes (dans cet ordre) de graphe : 1, 4, 7, 10, 14 et 17.
   3. Dépiler une fois pile_de_graphe.
   4. Vérifier que la pile n'est pas vide.
   5. Donner l’élément au sommet de la pile (sans le dépiler).
2. Écrire une méthode d'instance, inverser_pile, qui inverse l’ordre des éléments de la pile (le bas devient le haut).

1.3. File

En vous basant sur l'implémentation de la classe Pile, écrire la classe File en transformant en méthodes les fonctions associées à la structure File vues dans la première implantation, notamment est_vide, enfiler, defiler.

class File:
    """
        Implémentation d'une file à l'aide d'une liste Python et de la POO.
    """
    
   


   
    def __str__(self):
        return f"{self.donnees}"
    
    def __repr__(self):
        return f"File({self.donnees})"

Faites-vous plaisir 3 :

1. On considère pile_de_graphe, ci-dessus.
   1. Créer une file nommée file_de_graphe.
   2. Transférer tous les éléments de pile_de_graphe vers file_de_graphe en utilisant une boucle for.
   3. Afficher l'élément en tête de file_de_graphe sans le supprimer.
   4. Vérifier que file_de_graphe n'est pas vide.
   5. Dire quel élément se trouve à la sortie de cette file, sans le retirer.
   6. Enfilez votre prénom dans file_de_graphe.
2. Écrire une méthode d'instance taille_file qui renvoie le nombre d'éléments de la file. On n'utilisera ni len ni __len__ et ne détruira pas non plus la file.

2. Implémenter une structure linéaire à l'aide d'une liste chaînée

Une structure de données linéaire est un ensemble d'éléments ordonnés et qui peuvent être reliés entre eux.
Dans une liste chaînée, chaque élément (appelé nœud ou maillon) contient :

• une valeur (nombre, texte, objet, …) ;
• une référence vers le nœud suivant dans l’ordre (ou None s’il n’y en a pas).

L’accès aux éléments est séquentiel : on part de la tête de liste et l’on suit les références une à une.
Pas d’indexation directe comme pour une liste Python !

2.1. Classe Noeud

Un nœud regroupe donc deux attributs :

• valeur : la donnée stockée ;
• suivant : la référence vers le prochain nœud (ou None en fin de liste).

Implanter un nœud

class Noeud:
    """Modélise un maillon (une cellule) d'une structure linéaire."""
    def __init__(self, valeur, suivant = None):
        self.valeur = valeur
        self.suivant = suivant
        
#Afficher le noeud
    def __str__(self) -> str:
        """Affiche la valeur du nœud."""
        return f"{self.valeur}"
    
    def __repr__(self) -> str:
        """Affiche l'instance."""
        return f"Noeud({repr(self.valeur)}, {repr(self.suivant)})"

Créer 3 nœuds séparés : liste chaînée

# Lier des nœuds
noeud1 = Noeud("nsi")
noeud2 = Noeud("maths")
noeud3 = Noeud("philo")

print(noeud1)

noeud1

noeud2

noeud3

Faites-vous plaisir 4 :

• Créer une méthode get_valeur qui renvoie la valeur stockée dans le nœud.
• Créer une méthode set_valeur qui met à jour la valeur du nœud avec une nouvelle valeur.
• Créer une méthode get_suivant qui renvoie le nœud suivant, ou None s’il n’existe pas.

Lier les trois nœuds
Ces trois nœuds modélisent la liste chaînée suivante : "nsi", "maths", "philo".

noeud1.suivant = noeud2
noeud2.suivant = noeud3

noeud2

Afficher les trois clés (valeurs)
Le premier nœud (noeud1) sert de référence à l'ensemble des trois nœuds : un objet ne peut être afficher que s'il est ou devient la tête (s'il est la clé du premier nœud) de la liste.

head = noeud1
while head is not None: # head != None est fortement déconseillé !
    print(head)
    head = head.successeur

Une autre façon de lier des nœuds

noeud4 = Noeud(13)
noeud3 = Noeud(12, noeud4)
noeud2 = Noeud(11, noeud3)
noeud1 = Noeud(10, noeud2)

head = noeud1
while head is not None:
    print(head, end=" -> ")
    head = head.successeur

2.2. Liste chaînée

class Noeud:
    """Crée un maillon d'une liste chaînée."""
    def __init__(self, valeur, suivant=None) -> None:
        self.valeur = valeur
        self.suivant = suivant # None = pas de suivant
    
    #Afficher le nœud
    def __str__(self) -> str:
        """Affiche la valeur (la donnée) du nœud."""
        return f"{self.valeur}"
    
    def __repr__(self) -> str:
        """Affiche l'objet linstance du nœud."""
        return f"Noeud({repr(self.cle)}, {repr(self.successeur)})"
        

class ListeChainee:
    """Modélise une liste simplement chaînée (tête -> ... -> None)."""
    def __init__(self) -> None:
        """Crée et initialise une liste chaînée comme une liste chaînée vide."""
        self.head = None #le nœud de tête
        
    def est_vide(self) -> bool:
        """
            Renvoie True si la liste chaînée est vide, False sinon.
        """
        return self.head is None
        
    def head(self):
        """Renvoie la valeur de tête.
           Lève une IndexError si la liste chaînée est vide.
        """
        if self.est_vide():
            raise IndexError("Liste vide : impossible de lire la tête !")
        return self.head.valeur
         
    def queue(self) -> ListeChainee:
        """Renvoie la liste privée de son premier élément.
           Lève une IndexError si la liste chaînée est vide.
        """
        if self.est_vide():
            raise IndexError("Liste vide : impossible de lire la queue !")
            
        sous_liste = ListeChainee()
        sous_liste.head = self.head.suivant
        return sous_liste
                
    def __repr__(self) -> str:
        """Affiche l'objet Liste chaînée."""
        return f"ListeChainee({repr(self.head)})"
    
    def affiche_lst_chainee(self) -> str:
        """Affiche les valeurs de la liste chaînée."""
        noeud_courant = self.head
        while noeud_courant is not None:
            print(noeud_courant.valeur, end=" --> ")
            noeud_courant = noeud_courant.suivant
            
    def inserer_en_tete(self, nouvelle_cle):
        """insère un nouvel élément en tête."""      
              
    
    def __len__(self):
        """Renvoie le nombre total d'éléments de la liste chaînée."""
     

Dans une liste chaînée, la tête (head) est une référence vers le premier nœud. Passer la tête en paramètre suffit pour accéder à toute la liste.

Faites-vous plaisir 4 :

On donne les nœuds ci-après :

# Lier des noeuds
noeud1 = Noeud(1)
noeud2 = Noeud(2)
noeud3 = Noeud(3)
noeud4 = Noeud(1)
noeud5 = Noeud(2)
noeud6 = Noeud(4)

• Chaîner ces nœuds pour obtenir la liste 1 -> 2 -> 3 -> 4 -> None dont la tête est le nœud de valeur 1.
• Construire lst_chainee (instance de ListeChainee) en fixant sa tête.
• Vérifier que lst_chainee n'est pas vide.
• Compléter, dans la classe ListeChainee, plus haut, les méthodes de liste chaînée inserer_en_tete et __len__ (parcours séquentiel).

2.2. Pile

class Noeud:
    """Modélise un maillon (valeur + suivant) d'une pile."""
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant # None = pas de suivant
    
    #Afficher le nœud
    def __str__(self) -> str:
        """Affiche la valeur du le nœud."""
        return f"{self.valeur}" # ou str(self.valeur)
    
    def __repr__(self):
        """Affiche l'instance de noeud."""
        return f"Noeud({repr(self.valeur)}, {repr(self.suivant)})"
        

class Pile:
    """
        Modélise une pile dont les éléments sont des nœuds.
    """
    def __init__(self):
        """Crée et initialise une pile comme une pile vide."""
        self.sommet = None # Le sommet de la pile
        
    def __repr__(self):
        """Affiche l'instance de Pile."""
        return f"Pile({repr(self.sommet)})"
        
    def est_vide(self) -> bool:
        """Renvoie True si la pile est vide. False sinon."""
        return self.sommet is None

    def empiler(self, nouvelle_valeur) -> None:
        """Insère nouvelle_valeur au sommet de la pile."""
        nouveau_noeud = Noeud(nouvelle_valeur)
        nouveau_noeud.suivant = self.sommet
        self.sommet = nouveau_noeud
        print(f"{nouvelle_valeur} a été inséré avec succès au sommet de la pile.")
    
    # une autre écriture
    def empiler(self, nv_valeur) -> None:
        """Insère nouvelle_valeur au sommet de la pile."""
        self.sommet = Noeud(nv_valeur, self.sommet)

    def depiler(self):
        """
            Renvoie et supprime l'élément au sommet de la pile (LIFO).
            Lève une une erreur si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("La pile est vide : impossible de dépiler !")
        val_sommet = self.sommet.valeur
        self.sommet = self.sommet.suivant
        return val_sommet

    def sommet(self):
        """
            Renvoie (sans le supprimer) la valeur du sommet.
            Lève une erreur si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("La pile est vide : impossible de lire le sommet !")
        return self.sommet.valeur

Faites-vous plaisir 5 :

On donne :
pile_test = Pile()
pile_test.head = Noeud(Noeud(40, Noeud(30, Noeud(20, Noeud(10, Noeud(0, None))))))

1. Préciser le suivant de chacun des noeuds présents dans cette Pile.
2. Afficher la donnée encapsulée par le sommet de la pile.
3. Écrire une méthode recherche qui prend en entrée une pile, p, et une donnée, cle, et renvoie True si la donnée est présente dans p, False sinon.

pile_test = Pile()
pile_test.head = Noeud(Noeud(40, Noeud(30, Noeud(20, Noeud(10, Noeud(0, None))))))

pile_test.est_vide()

2.3. File

class Noeud:
    """Modélise un maillon (valeur + suivant) d'une file."""
    def __init__(self, valeur, suivant=None) -> None:
        self.valeur = valeur
        self.suivant = suivant # None = pas de suivant
    
    #Afficher le nœud
    def __str__(self) -> str:
        """Affiche la valeur du le nœud."""
        return f"{self.valeur}" # ou str(self.valeur)
    
    def __repr__(self) -> str:
        """Affiche l'instance de noeud."""
        return f"Noeud({repr(self.valeur)}, {repr(self.suivant)})"
        
        
class File:
    def __init__(self) -> None:
        """Crée et initialise une file vide."""
        self.head = None #Sortie de la file
        self.queue = None #Entrée de la file
        
    def est_vide(self) -> bool:
        """
            Renvoie True si la file est vide, False sinon.
        """
        return self.head is None

    def enfiler(self, nouvelle_valeur) -> None:
        """
            Insère nouvelle_valeur, à l'arrière (l'entrée) de la file (FIFO).
        """
        nouveau_noeud = Noeud(nouvelle_valeur)
        if self.est_vide(): #ou self.head is None
            # premier élément : tête et queue pointent sur le même nœud
            self.head = nouveau_noeud
            self.queue = nouveau_noeud
        else:
            self.queue.suivant = nouveau_noeud
            self.queue = nouveau_noeud
              
    def defiler(self):
        """
            Renvoie et supprime le premier élément (l'élément à la sortie) de la file.
            Lève une erreur si la file est vide.
        """
        if self.est_vide():
            raise IndexError("La file est vide : impossible de défiler !")       
        valeur_de_sortie = self.head.valeur
        self.head = self.head.suivant
        if self.est_vide(): # ou self.head is None
            self.queue = None
        return valeur_de_sortie
 
    def premier(self):
        """
            Renvoie (sans supprimer) le premier élément (l'élément à la sortie) de la file.
            Lève une erreur si la file est vide.
        """
        if self.est_vide():
            raise IndexError("La file est vide : impossible de lire la tête !")
        else:
            return self.head.valeur
        
    def taille_file(self) -> int:
        """Renvoie le nombre total d'éléments dans la file."""
        
    def __repr__(self) ->  str:
    """Affiche la file."""
    return f"File({repr(self.head)})"
   

Faites-vous plaisir 6 :

• Compléter, dans la classe File, ci-dessus, la méthode taille_file.
• On donne :
  lst_de_fruits = [
  {"numéro": 1, "nom": "banane", "famille": "musacées"},
  {"numéro": 2, "nom": "raisin", "famille": "vitacées"},
  {"numéro": 3, "nom": "fraise", "famille": "rosacées"},
  {"numéro": 4, "nom": "kiwi", "famille": "actinidiacées"}
  ]
  • Créer une instance de File nommée file_de_fruits.
  • À l'aide d'une boucle for et à partir de l'objet lst_de_fruits, enfiler les noms des différents fruits dans cette instance de File.
  • Avec cette instance de File, tester les différentes méthodes de la classe.