C3.3 : Varier les implémentations

Rappel de vocabulaires

Une structure de données est un ensemble cohérent qui permet de stocker et manipuler des informations à l'aide d'algorithmes.

Une structure de données se caractérise par :

  • - son interface : c'est l'ensemble de ce à quoi l'utilisateur de la structure de données peut accéder ;
  • - son implémentation : c'est le code utilisé pour programmer la structure de données (l'implémentation n'a pas besoin d'être connue de l'utilisateur de la structure de données).

Implémentations des piles et des files à l'aide de fonctions

A] Implémentation des piles

On considère le code ci-dessous :

def fonction1():
    return []

def fonction2(p):
    return p ==[]

def fonction3(p):
    if p != []:
        return p.pop()
    else:
        return None

def fonction4(p,e):
    p.append(e)

1) Justifier que ces quatre fonctions constituent bien une implémentation pour la manipulation de structures de données de type pile. Donner un nom adapté à chaque fonction.

2) Écrire le code qui permet d'exécuter successivement les actions suivantes :

Afficher la correction

1) Les quatre fonctions proposées correspondent aux quatre méthodes de base de l'interface d'une structure de données de type pile :

  • - f1 est le constructeur ;
  • - f2 est la méthode est_vide ;
  • - f3 est la méthode defile ;
  • - f4 est la méthode enfile.

2) 

def fonction1():
    return []

def fonction2(p):
    return p == []

def fonction3(p):
    if p != []:
        return p.pop()
    else:
        return None

def fonction4(p,e):
    p.append(e)

p1 = fonction1()
p2 = fonction1()
fonction4(p1, 4)
fonction4(p1, 8)
fonction4(p2, fonction3(p1))
fonction4(p2, fonction3(p1))
print(fonction2(p1)) # True
print(fonction2(p2)) # False

B] Implémentation des files

Q) Sur le même modèle, écrire une implémentation des structures de données de type file.

Afficher la correction 
def cree_file_vide():
    return []

def est_vide(f):
    return f == []

def defile(f):
    if f != []:
        return f.pop(0)
    else:
        return None

def enfile(f, e):
    f.append(e)

# Programme principal
f1 = cree_file_vide()
f2 = cree_file_vide()
enfile(f1, 4)
enfile(f1, 8)
enfile(f2, defile(f1))
enfile(f2, defile(f1))
print(est_vide(f1)) # True
print(est_vide(f2)) # False
print(defile(f2) == 4) # True

Implémentations des files à l'aide d'une classe et de piles

On considère le code suivant qui propose : 

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_pile_vide(self):
        return self.__valeurs == []

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_pile_vide()):
            return self.__valeurs.pop()
        else:
            return None

class File:
    def __init__(self):
        """Constructeur"""
        self.__donnees = Pile()

    def est_file_vide(self):
        """Méthode qui permet de tester si la file est vide ou non"""
        pass

    def enfile(self, elt):
        """Méthode qui permet d'ajouter elt à la file"""
        pass

    def defile(self):
        """Méthode qui permet d'enlever et de renvoyer le premier élément de la file"""
        pass

1) Compléter les méthodes de la classe File.

2) Proposer quelques lignes de code qui permettent de tester les différentes méthodes de la classe File.

Afficher la correction 
class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_pile_vide(self):
        return self.__valeurs == []

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_pile_vide()):
            return self.__valeurs.pop()
        else:
            return None

class File:
    def __init__(self):
        """Constructeur"""
        self.__donnees = Pile()

    def est_file_vide(self):
        """Méthode qui permet de tester si la file est vide ou non"""
        return self.__donnees.est_pile_vide()

    def enfile(self, elt):
        """Méthode qui permet d'ajouter elt à la file"""
        self.__donnees.empile(elt)

    def defile(self):
        """Méthode qui permet d'enlever et de renvoyer le premier élément de la file"""
        if not(self.est_file_vide()):
            p2 = Pile()
            while not(self.__donnees.est_pile_vide()):
                p2.empile(self.__donnees.depile())
            elt = p2.depile()
            while not(p2.est_pile_vide()):
                self.__donnees.empile(p2.depile())
            return elt
        else:
            return None

# Programme principal (pour tester la classe File)
f1 = File()
f1.enfile(4)
f1.enfile(5)
f1.enfile(6)
print(f1.defile() == 4)
f2 = File()
f2.enfile(f1.defile())
f2.enfile(f1.defile())
print(f2.defile() == 5)
print(f2.defile() == 6)
print(f1.est_file_vide() == True)
print(f2.est_file_vide() == True)