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):
        """Crée et initialise une liste vide"""
        self.donnees = []
    
    def est_vide(self):
        """Renvoie True si la liste est vide."""
        return self.donnees == []
    
    def est_vide2(self):
        """Renvoie True si la liste est vide."""
        return len(self.donnees) == 0
    
    def tete_liste(self):
        """
            Renvoie la valeur de l'élément en tête de la liste sans le supprimer.
            Si L est vide lève une exception.
        """
        if self.est_vide():
            raise IndexError("La liste est vide : il y a un débordement négatif !")
        else:
            return self.donnees[0]
        
    def queue(self):
        """
            Renvoie la liste privée de son premier élément.
            Lève une exception si la liste est vide.
        """
        if self.est_vide():
            raise IndexError("La liste est vide !")
        return self.donnees[1:]
    
    def insere_tete(self, elt):
        """Insère elt à la tête de la liste."""
        self.donnees.insert(0, elt)
        return None
    
    def __str__(self):
        return f"{self.donnees}"
    
    def __repr__(self):
        return f"Liste({self.donnees})"

1.2. Pile

class Pile:
    """
        Implémentation d'une pile à l'aide d'une liste Python et la POO.
    """
    
    def __init__(self):
        """Crée et initialise une pile comme une pile vide"""
        self.donnees = []
    
    def __len__(self):
        """Renvoie le nombre d'éléments de la pile."""
        return len(self.donnees)
    
    def est_vide(self):
        """Renvoie True si la pile est vide, False sinon."""
        if not self:
            return True
        return False
     
    def est_vide2(self):
        """Renvoie True si la pile est vide."""
        return self.donnees == []
    
    def est_vide3(self):
        """Renvoie True si la pile est vide."""
        return len(self.donnees) == 0
    
    def empile(self, elt):
        """Insère elt au sommet de la pile (à l'exrême droite dans la pile)."""
        self.donnees.append(elt)
        
    def top(self):
        """
            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 exception si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("La pile est vide !")
        return self.donnees[-1]
    
    def depile(self):
        """
            Renvoie et supprime l'élément au sommet de la pile (FIFO).
            Lève une exception si la pile est vide.
        """
        if self.est_vide():
            raise IndexError("La pile est vide !")
        return self.donnees.pop()
    
    def __str__(self):
        return f"{self.donnees}"
    
    def __repr__(self):
        return f"Pile({self.donnees})"

une_pile = Pile()

# On donne
graph = {
    "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 1 :

On considère l'objet graph, ci-dessus.
• Créer une instance de Pile que l'on référencera à l'aide de la variable une_pile.
• À l'aide d'une boucle for insérer dans une_pile les premiers éléments des clés de graph c'est-à-dire 1, 4, 7, 10, 14 et 17.
• Afficher le sommet de une_pile.
• Vérifier qu'elle n'est pas vide.
• Quel est l'élément au sommet de la pile ?

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.

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 2 :

On considère la pile ci-dessus, une_pile.
• Créer une instance de File que l'on référencera à l'aide de la variable ma_file.
• À l'aide d'une boucle, dépiler puis insérer dans ma_file les éléments de une_pile.
• Afficher le premier élément de ma_file.
• Vérifier que ma_file n'est pas vide.
• Quel élément se trouve à la sortie de cette file ?

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

2.1. Classe Noeud

Une structure de données linéaire est un ensemble d'éléments ordonnés et qui peuvent être reliés entre eux. Ainsi, chaque élément possède, en plus de la donnée, un pointeur (ou des pointeurs) vers l'élément (les éléments) qui le suit (qui lui sont adjacents) dans la liste.
L'accès aux éléments d'une liste se fait de manière séquentielle. chaque élément permet l'accès au suivant mais, cet accès ne peut se faire par l'indexation.
Aussi, on définit une structure de base, la classe Nœud (ou Cellule) ou Maillon, qui permet de représenter un élément de la liste. Cet élément est caractérisé par un objet contenant deux attributs :

• un attribut cle (valeur ou donnee) définissant la valeur contenue dans ce Noeud (nombre, texte, un autre objet de nature quelconque…) ;
• et un pointeur définissant l’adresse du successeur ou suivant (qui est le Noeud suivant dans l’ordre de la structure).

Implanter un nœud

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

Créer 3 nœuds séparés.

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

print(noeud1)

nsi

noeud1

Noeud('nsi', None)

noeud2

Noeud('maths', None)

noeud3

Noeud('philo', None)

Faites-vous plaisir 3 :

• Créer une méthode get_donnee qui renvoie la donnée contenue dans le nœud.
• Créer une méthode set_donnee qui met à jour la donnée d'un nœud avec une nouvelle donnée.
• Créer une méthode get_successeur qui renvoie le successeur du nœud auto-référencé.

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

noeud1.successeur = noeud2
noeud2.successeur = noeud3

noeud2

Noeud('maths', Noeud('philo', None))

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

nsi
maths
philo

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

10 -> 11 -> 12 -> 13 -> 

2.2. Liste chaînée

class Noeud:
    """Crée un maillon d'une liste chaînée."""
    def __init__(self, cle=None, successeur=None):
        """Crée et initialise un Noeud comme un nœud vide."""
        self.cle = cle
        self.successeur = successeur
    
    #Afficher le nœud
    def __str__(self):
        """Affiche la valeur (cle, donnée) contenue dans le nœud."""
        return f"{self.cle}"
    
    def __repr__(self):
        """Affiche l'objet nœud."""
        return f"Noeud({repr(self.cle)}, {repr(self.successeur)})"
        

class ListeChainee:
    """Crée une liste chaînée."""
    def __init__(self):
        """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 est vide
        
    def est_vide(self):
        """
            Renvoie True si la liste chaînée est vide, False sinon.
        """
        return self.head is None
        
    def tete_liste(self):
        """Renvoie la tête de la liste chaînée.
           Lève une exception si la liste est vide.
        """
        if not self.est_vide():
            return self.head.cle
        raise ValueError("La liste est vide !")
    
    def queue(self):
        """Renvoie la liste privée de son premier élément.
           Lève une exception si la liste est vide.
        """
        sous_liste = None
        if not self.est_vide():
            sous_liste = ListeChainee()
            sous_liste.head = self.head.successeur
            return sous_liste
        raise ValueError("La liste est vide !")
            
    def __repr__(self):
        """Affiche l'objet Liste chaînée."""
        return f"ListeChainee({repr(self.head)})"
    
    def affiche_lst_chainee(self):
        """Affiche les données (clés, valeurs) de la liste chaînée."""
        noeud_courant = self.head
        while noeud_courant is not None:
            print(noeud_courant.cle, end=" --> ")
            noeud_courant = noeud_courant.successeur
            
    def insere_en_tete(self, nouvelle_cle):
        """Ajoute un élément à la tête de la liste chaînée."""      
            
    
    
    def __len__(self):
        """Renvoie le nombre total d'éléments de la liste chaînée."""

        
        
        

La tête de la liste chaînée head est l'identifiant de la liste entière. Si on doit passer la liste chaînée en paramètre, il suffit de passer seulement la référence à sa tête.

Faites-vous plaisir 3 :

On donne les noeuds ci-après :

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

• Créer, à partir des nœuds donnés ci-dessus, la liste chaînée, lst_chainee 1 -> 2 -> 3 -> 4 -> dont la tête est le nœud contenant la donnée 1.
• 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 insere_en_tete et len.

2.2. Pile

class Noeud:
    """Modélise un maillon d'une pile."""
    def __init__(self, cle=None, successeur=None):
        """Crée et initialise un Noeud comme un nœud vide."""
        self.cle = cle
        self.successeur = successeur
    
    #Afficher le nœud
    def __str__(self):
        """Affiche la valeur (cle, donnée) contenue dans le nœud."""
        return f"{self.cle}"
    
    def __repr__(self):
        """Affiche l'objet noeud."""
        return f"Noeud({repr(self.cle)}, {repr(self.successeur)})"

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

    def empile(self, nouvelle_cle):
        """Insère la donnée, nouvelle_cle, au sommet de la pile."""
        nouveau_noeud = Noeud(nouvelle_cle) # On crée un nouveau nœud avec la nouvelle donnée
        nouveau_noeud.successeur = self.head # Ce nouveau nœud a pour successeur l'ancien head
        self.head = nouveau_noeud # Ce nouveau noeud devient head
        print(f"{cle} a été inséré avec succès au sommet de la pile.")
        return None
    
    # Une autre écriture
    def empile(self, nouvelle_cle):
        """Insère la donnée, nouvelle_cle, au sommet de la pile."""
        self.head = Noeud(nouvelle_cle, self.head)
        return None

    def depile(self):
        """
            Renvoie et supprime l'élément au sommet de la pile (LIFO).
            Lève une exception si la pile est vide.
        """
        if self.est_vide():
            raise ValueError("La pile est vide !")
        cle_du_sommet = self.head.cle
        self.head = self.head.successeur
        return cle_du_sommet

    def top(self):
        """
            Renvoie (sans le supprimer) la clé du sommet.
            Lève une exception si la pile est vide.
        """
        if self.est_vide():
            raise ValueError("La pile est vide !")
        return self.head.cle

Faites-vous plaisir 4 :

On donne la pile suivante : pile_test = Pile(Noeud(40, Noeud(30, Noeud(20, Noeud(10, Noeud(0, None)))))).
1. Préciser le successeur 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.
4. Écrire une méthode supprime qui prend en entrée une pile, p, et une valeur, cle, et efface tous les éléments cle dans p.
   On suppose que la donnée cle est présente dans la pile.

2.3. File

class Noeud:
    """Modélise un maillon d'une file."""
    def __init__(self, cle=None, successeur=None):
        """Crée et initialise un Noeud comme un nœud vide."""
        self.cle = cle
        self.successeur = successeur
    
    #Afficher le noeud
    def __str__(self):
        """Affiche la valeur (cle, donnée) du nœud."""
        return f"{self.cle}"
    
    def __repr__(self):
        """Affiche le nœud."""
        return f"Noeud({repr(self.cle)}, {repr(self.successeur)})"
        
        
class File:
    def __init__(self):
        """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):
        """
            Renvoie True si la file est vide, False sinon.
        """
        return self.head is None

    def enfile(self, nouvelle_cle):
        """
            Insère la donnée, nouvelle_cle, à l'arrière (l'entrée) de la file (FIFO).
        """
        nouveau_noeud = Noeud(nouvelle_cle)
        if self.est_vide(): #ou self.head is None
            # Si la file est vide, le nouveau nœud est la tête de file
            self.head = nouveau_noeud
            self.queue = nouveau_noeud
        else:
            self.queue.successeur = nouveau_noeud #Le nouveau nœud devient le successeur de l'ancienne queue
            self.queue = nouveau_noeud #Le nouveau nouveau nœud devient la queue
        return None
              
    def defile(self):
        """
            Renvoie et supprime le premier élément (l'élément à la sorie) de la file.
            Lève une exception si la file est vide.
        """
        if self.est_vide():
            raise ValueError("La file est vide !")
        else:
            cle_de_sortie = self.head.cle
            self.head = self.head.successeur
            if self.est_vide():
                self.queue = None
            return cle_de_sortie
 
    def premier(self):
        if self.est_vide():
            raise ValueError("La file est vide !")
        else:
            return self.head.cle
        
    def taille_de_la_file(self):
        """Renvoie le nombre total d'éléments dans la file."""
        
    def __repr__(self):
    """Affiche la file."""
    return f"File({repr(self.head)})"
   

Faites-vous plaisir 5 :

• Compléter, dans la classe File, ci-dessus, la méthode taille_de_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 que l'on identifiera par la variable file_de_fruits.
  • À l'aide d'une boucle for et à partir de l'objet lst_de_fruits, insérer 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.