Données Linéaires

Identification

Infoforall

21 - Types linéaires


Il ne s'agit pas d'une vraie activité. Juste d'un gros rappel sur les trois structures de données linéaires avec lesquelles nous avons travaillé :

  1. les listes,
  2. les piles et
  3. les files.

Le but est de réfléchir à la façon de réaliser une fiche-résumé avec un ensemble aussi conséquent de connaissances.

Pour réaliser une fiche, il faut avoir le cours (c'est fait), fait les exercices (vous avez fait les activités) et connaître les attendus de NSI (c'est en dessous) :

  • Structures de données, interface et implémentation.
    • Spécifier une structure de données par son interface.
    • Distinguer interface et implémentation.
    • Écrire plusieurs implémentations d’une même structure de données.
    • Remarque : l’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles).
  • Listes, piles, files : structures linéaires
    • Distinguer des structures par le jeu des méthodes qui les caractérisent.
    • Choisir une structure de données adaptée à la situation à modéliser.
    • Remarques : on distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files. On expliquera clairement que les listes (chaînées) n’existent pas de façon native en Python.

1 - VOCABULAIRE

Structure linéaire

Une structure de données est dite linéaire lorsque chaque donnée n'a qu'un successeur et un précédesseur au maximum : visualement, on peut donc représenter les données sous forme d'une chaîne ou d'une ligne.

Type abstrait (voire structure abstraite)

Un type abstrait de données, parfois nommée structure de données abstraite permet de formaliser ce qu'on pourrait réaliser sur des données en définissant deux choses :

  1. L'organisation générale des données qui se cache derrière ce terme
  2. Les fonctions d'interface autorisées et nécessaires pour gérer ces données (on parle également de primitives)

Puisqu'on reste dans l'abstraction, nous n'avons pas réellement besoin de gérer les coûts ou la complexité : il s'agit bien d'une vue de l'esprit.

Implémentation

Un algorithme travaille sur des types abstraits de données.

Lorsqu'on veut réaliser concrétement cet algorithme, on doit en réaliser l'implémentation :

  • L'algorithme devient alors un programme écrit dans un langage de programmation.
  • Le type abstrait devient une structure de données.

Il existe de multiples façons de réaliser cette implémentation, certaines mauvaises, d'autres bonnes sur certains points mais pas d'autres...

On peut donc réaliser une implémentation, réaliser son projet et se rendre compte plus tard que nous avons besoin de modifier notre implémentation. Il est donc nécessaire de respecter l'usage strict des fonctions d'interface pour manipuler les données plutôt que de les manipuler directement : en cas de mise à jour, il suffit de modifier les instructions internes des fonctions d'interface mais le reste du programme ne changera pas.

Muable ou mutable

Il s'agit des données qui sont modifiables directement en mémoire.

Lorsqu'on modifie une donnée muable, on n'a donc pas besoin de renvoyer sa référence puisqu'elle est directement modifiée.

Cela pose néanmoins des problèmes de cohérence et donc de sécurité.

Exemple avec un tableau [tete, queue].

2 - LISTE

2.1 - Définition du type abstrait LISTE

1er partie de la définition - Idée générale d'organisation

Séquence ordonnée d'un nombre fini d'éléments dans laquelle on peut

  • lire-modifier les données à n'importe quelle position
  • insérer-supprimer les données à n'importe quelle position
  • Analogie des dossiers suspendus

    5823

    Accéder à n'importe quel dossier de la liste est totalement normal et ces actions doivent donc être possibles.

  • Vocabulaire :
    • Tête : le premier élément de la liste (ici en rouge)
    • Queue : l'ensemble des données derrière la tête (ici en bleu)
  • Définition récursive : une liste est
    • soit une liste vide
    • soit un ensemble (tête, queue) dans lequel la queue est une liste.

2e partie de la définition - Interface

On doit pouvoir :

  • créer une nouvelle liste,
  • tester si une liste est vide,
  • insérer un élément (à une position à définir),
  • lire un élément (à une position à définir) d'une liste non vide,
  • supprimer un élément (à une position à définir) d'une liste non vide

Il existe donc de multiples variantes de ces fonctions d'interface.

Les prototypes varient en fonction de la nature muable ou pas de la pile.

2.2 Implémentation couple (tete, queue), version immuable

    5
    8
    2
    3 → X
  • Principe avec Python
    • On utilise un p-uplet (de type tuple en Python) ayant deux indices :

      • L'indice 0 pour la référence de la tête
      • L'indice 1 pour la référence de la queue

      Quelques notions à avoir en tête :

      • La structure de données native tuple de Python est immuable. Lorsqu'on "supprime une tête" ou qu'on "rajoute" une tête, on crée donc en réalité une nouvelle liste.
      • Toutes les opérations de lecture ou modification d'une "case" d'un tuple sont à coût constant.
      • Liste vide : a = ().
      • Liste d'un élément : a = (5, ())
      • Liste de 2 éléments : a = (5, (10, ()) )
      • Lire une tête revient à récupérer a[0], l'indice 0 du tuple .
      • "Supprimer la tête" revient à récupérer a[1], l'indice 1 du tuple.
      • "Insérer une tête" revient à créer un nouveau tuple en utilisant le nouvel élément x et l'ancienne liste a qui devient la queue.
      • Modifier la tête se fait en deux temps :
        1. supprimer la tête puis
        2. ajouter la nouvelle tête.
  • Implémentation Python
  • On notera que cette implémentation comporte de nombreuses préconditions sur les fonctions d'interface : à l'utilisateur de réfléchir au préalable plutôt que d'effectuer une multitude de vérifications ralentissant l'exécution dans les fonctions.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
    '''Implémentation d'une LISTE IMMUABLE via des tuples (tete, queue)''' class Elt : '''Type de données autorisées''' class Liste : '''Un tuple (tete, queue) ou ()''' def nouvelleListe() -> Liste: '''Renvoie une liste vide''' return () def estListeVide(lst:Liste) -> bool: '''Renvoie True si la liste est vide''' return lst == () def insererTete(x:Elt, lst:Liste) -> Liste: '''Renvoie une nouvelle liste où x est la tête''' return (x, lst) def lireTete(lst:Liste) -> Elt: '''Renvoie la tête de la liste lst NON VIDE''' return lst[0] def supprimerTete(lst:Liste) -> Liste: '''Supprime la tête d'une liste lst NON VIDE''' return lst[1] def lire(lst:Liste, indice:int) -> Elt: '''Renvoie l'élément d'indice VALIDE, lst NON VIDE''' for x in range(indice): lst = supprimerTete(lst) return lireTete(lst) def inserer(x:Elt, lst:Liste, indice:int) -> Liste: '''Renvoie une liste où x est inséré au bon indice VALIDE''' les_tetes = [] for etape in range(indice): les_tetes.append(lireTete(lst)) lst = supprimerTete(lst) lst = insererTete(x, lst) for etape in range(len(les_tetes)-1,-1,-1): lst = insererTete(les_tetes[etape], lst) return lst def supprimer(lst:Liste, indice:int) -> Liste: '''Renvoie une liste où l'élément d'indice VALIDE est supprimé''' les_tetes = [] for etape in range(indice): les_tetes.append(lireTete(lst)) lst = supprimerTete(lst) lst = supprimerTete(lst) for etape in range(len(les_tetes)-1,-1,-1): lst = insererTete(les_tetes[etape], lst) return lst
  • Avantages
    • Colle au plus près du principe (tête, queue) des listes.
    • Facile à implémenter
    • Coût constant pour toutes les opérations basées sur la tête : les fonctions lireTete(), supprimerTete() et insererTete() contiennent
      • des lectures de contenu de tuples via un indice (à coût constant)
      • des modifications de contenu de tuples via un indice (à coût constant)
  • Désavantages
    • Coût linéaire en 𝞞(n) pour les opérations internes : les fonctions lire(), supprimer() et inserer() contiennent des boucles bornées nécessitant un nombre de boucle lié à l'indice i voulu. On peut donc écrire soit 𝞞(n), soit 𝞗(i).
    • Coût linéaire lors des concaténations car cela revient à rajouter toutes les têtes d'une des listes à l'autre liste.

2.3 Implémentation tableau statique, version immuable ici

On obtient alors une liste contiguë.

L'exemple d'implémentation est une version liste immuable, mais nous pourrions créer une liste muable très facilement également.

    Principe du tableau
    A B C
  • Principe avec Python
    • Python ne possède pas de vrais tableaux statiques : on utilise donc un tableau dynamique (de type list en Python) en se limitant aux opérations possibles sur un tableau statique :

      • L'indice 0 sert à stocker la référence de la tête
      • L'indice 1 sert à stocker la référence du successeur de la tête
      • L'indice 2 sert à stocker la référence du successeur du successeur de la tête
      • ...

      Quelques notions à avoir en tête :

      • Le type list de Python est muable. Pour obtenir une liste immuable, nous allons devoir créer des copies à chaque opération...
      • Toutes les opérations de lecture ou modification d'une "case" d'un tableau sont à coût constant.
      • Liste vide :
        a = []
        .
      • Liste d'un élément :
        a = [5].
      • Liste de 2 éléments :
        a = [5, 10].
      • Lire une tête revient à récupérer tete = a[0], l'indice 0 du tableau statique correspondant.
      • Lire la dernière cellule revient à récupérer fin = a[len(a)-1] ou plus Pythonnesque fin = a[-1).
      • Lire n'importe quelle cellule revient à faire ceci a[i].
      • Modifier n'importe quelle cellule : a[i] = 25
      • Supprimer la tête ou n'importe quel autre élément : avec notre version immuable de la liste, c'est compliqué puisqu'il faut
        1. créer une copie du tableau ayant une case en moins
        2. y placer un à un les anciens éléments en les décalant d'un indice vers la gauche
        3. Principe de la suppression dans une liste sur une implémentation tableau
      • Insérer un élément à n'importe quelle position : idem, il faut
        • Créer une copie du tableau ayant une case en plus
        • Y placer les anciens éléments en les décalant d'une indice vers la droite
        • Principe de l'insertion dans une liste sur une implémentation tableau
  • Implémentation Python
    • 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
      '''Implémentation d'une LISTE IMMUABLE via un tableau statique class Elt : '''Type de données autorisées''' class Liste : '''Un tableau statique de n cases''' def nouvelleListe() -> Liste: '''Renvoie une liste vide''' return [] def estListeVide(lst:Liste) -> bool: '''Renvoie True si la liste est vide''' return lst == [] def lire(lst:Liste, indice:int) -> Elt: '''Renvoie la valeur stockée à l'indice VALIDE de lst NON VIDE''' return lst[indice] def inserer(x:Elt, lst:Liste, indice:int) -> Liste: '''Renvoie une Liste en insérant x à l'indice VALIDE''' temporaire = [0 for x in range(len(lst)+1)] # On crée une liste plus longue de 1 for i in range(indice): temporaire[i] = lst[i] # copie à l'identique temporaire[indice] = x # On place l'élément for i in range(indice, len(lst)): temporaire[i+1] = lst[i] # Décalage vers la droite return temporaire # On renvoie la nouvelle liste def supprimer(lst:Liste, indice:int) -> Liste: '''Renvoie une liste NON VIDE en supprimant l'élément à l'indice VALIDE''' temporaire = [0 for x in range(len(lst)-1)] # On crée une liste plus courte de 1 for i in range(indice): temporaire[i] = lst[i] # copie à l'identique for i in range(indice, len(temporaire)): temporaire[i] = lst[i+1] # Décalage vers la gauche return temporaire # On renvoie la nouvelle liste
  • Avantages
    • Coût constant en 𝞗(1) pour la lecture de n'importe quel élément.
    • Recherche d'éléments possible à coût logarithmique dans le cas d'une liste triée (recherche dichotomique)
  • Désavantages
    • Coût linéaire en 𝞗(n) pour insérer ou supprimer ou modifier n'importe quel élément : à cause de la copie à faire, on est obligé de bouger les données case par case.
    • Coût linéaire en 𝞗(n1+n2) pour concaténer deux listes (idem : création d'un nouveau tableau plus grand...)

2.4 Implémentation tableau dynamique (en version muable ici)

  • Principe avec Python
    • On utilise directement un tableau dynamique (de type list en Python).

      Quelques notions à avoir en tête :

      • Lire et modifier des cellules : aucune différence avec le cas précédent, mais ceci avec une opacité assez grande car savez-vous comment Python gère les tableaux dynamiques ?
      • Supprimer la tête de la liste (et récupérer sa valeur) :
        valeur = a.pop(0)
        Pratique mais avec un coût opaque. On peut considérer que c'est constant, sauf cas particulier.
      • Supprimer la fin de la liste (et récupérer sa valeur) :
        valeur = a.pop() Même remarque qu'au dessus.
      • Supprimer n'importe quelle cellule (et récupérer sa valeur) :
        valeur = a.pop(i) Même remarque qu'au dessus, et ça peut être souvent linéaire.
      • Insérer un élément en fin de liste :
        a.append(donnees_a_ajouter) : simple mais à quel coût ?
      • Insérer un élément à n'importe quelle position :
        a.insert(i, donnees_a_inserer) : simple mais à quel coût ?
  • Implémentation Python
    • 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
      class Elt : '''Type de données autorisées''' class Liste : '''Un tableau d'éléments''' def nouvelleListe() -> Liste: '''Renvoie une liste vide''' return [] def estListeVide(lst:Liste) -> bool: '''Renvoie True si la liste est vide''' return lst == [] def lire(lst:Liste, indice:int): '''Renvoie la valeur stockée à l'indice VALIDE voulu de lst NON VIDE''' return lst[indice] def inserer(x:Elt, lst:Liste, indice:int) -> None: '''Modifie en place la liste en insérant l'élément à l'indice fourni''' lst.insert(indice, x) def supprimer(lst:Liste, indice:int) -> Elt: '''Renvoie l'élément supprimé à l'indice VALIDE dans lst NON VIDE''' return lst.pop(indice)
  • Avantages
    • Ca à l'air plus simple qu'en construisant un tableau statique.
    • Assez optimisé en réalité.
    • Recherche d'éléments possible à coût logarithmique dans le cas d'une liste triée (recherche dichotomique)
  • Désavantages
    • Difficile de prévoir le coût : il va dépendre de beaucoup de choses et pour les connaître, il faut connaitre le code interne de Python.

2.5 Implémentation en liste simplement chaînée (tête - fin)

  • Principe avec Python
    • On utilise deux objets pour batir notre liste list en Python).

      Les objets Cellule ont besoin de deux attributs au moins :

      • un attribut valeur et
      • un attribut successeur qui pointe vers la cellule suivante, éventuellement None.

      Les objets Liste ont ici trois attributs :

      • un attribut tete,
      • un attribut fin
      • un attribut longueur qui contient le nombre de cellules dans la liste

      Quelques notions à avoir en tête :

      • Lire et modifier des cellules : coût constant pour les cellules référencées par tete ou fin ou leurs successeurs directs par exemple.
      • Supprimer la tête de la liste : coût constant car il suffit de faire pointer l'attribut tete sur le successeur de la tête.
      • Supprimer la cellule de fin : coût linéaire (en 𝞗(n)) car il faut récupérer la référence du prédecesseur pour la mémoriser dans fin. Et pour faire cela, nous avons besoin de partir de la tête jusqu'à la trouver et donc parcourir toute la liste, ou presque.
      • Insérer une tête ou insérer un élément après la tête ou la fin : coût constant car il suffit de créer une Cellule, de faire de la tête son successeur et faire pointer tete sur la nouvelle cellule.
      • Animation de l'insertion d'une tête
        CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
        Animation de l'insertion après une autre cellule
        CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
  • Implémentation (manque la lecture qui est une question de l'activité)
    • 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
      # Déclaration des classes servant uniquement pour la documentation class Elt : '''Type de données autorisées dans les cellules''' class CelluleOuNone: '''Instance de Cellule ou None''' # Déclaration des classes class Cellule: '''Classe permettant de créer des cellules non vides''' def __init__(self, valeur:Elt, successeur:CelluleOuNone=None): self.v = valeur self.s = successeur def obtenir_fin_de_chaine(self) -> 'Cellule': if self.s == None: return self else: return self.s.obtenir_fin_de_chaine() def obtenir_nombre_dans_chaine(self) -> int: if self.s == None: return 1 else: return 1 + self.s.obtenir_nombre_dans_chaine() class Liste: '''Classe permettant de créer une liste chaînée''' def __init__(self, tete:CelluleOuNone=None): self.tete = tete self.longueur = 0 self.fin = None self.mettre_a_jour() def mettre_a_jour(self) -> None: if self.tete == None: # La liste est une liste vide self.longueur = 0 self.fin = None else: # La liste contient au moins une cellule self.longueur = self.tete.obtenir_nombre_dans_chaine() self.fin = self.tete.obtenir_fin_de_chaine() def est_liste_vide(self) -> bool: return self.tete == None # Déclaration des fonctions def nouvelleListe() -> Liste: return Liste() def estListeVide(lst:Liste) -> bool: return lst.est_liste_vide() def insererTete(x:Elt, lst:Liste) -> None: nouvelle_cellule = Cellule(x, lst.tete) lst.tete = nouvelle_cellule lst.longueur = lst.longueur + 1 if lst.longueur <= 2: lst.mettre_a_jour() def insererApres(x:Elt, lst:Liste, position:str) -> None: if estListeVide(lst): insererTete(x, lst) elif position == "tete": nouvelle_cellule = Cellule(x, lst.tete.s) lst.tete.s = nouvelle_cellule lst.longueur = lst.longueur + 1 if lst.longueur <= 2: lst.mettre_a_jour() elif position == "fin": nouvelle_cellule = Cellule(x, lst.fin.s) lst.fin.s = nouvelle_cellule lst.fin = nouvelle_cellule lst.longueur = lst.longueur + 1 def supprimer(lst:Liste, position:str) -> Elt: if position == "tete" or lst.longueur == 1 : donnees = lst.tete.v lst.tete = lst.tete.s lst.longueur = lst.longueur - 1 if lst.longueur <= 1: lst.mettre_a_jour() elif position == "fin": donnees = lst.fin.v # Voir le if : si on arrive ici, c'est que la taille est d'au moins 2 predecesseur = lst.tete while predecesseur.s != lst.fin: predecesseur = predecesseur.s predecesseur.s = None lst.fin = predecesseur lst.longueur = lst.longueur - 1 if lst.longueur <= 1: lst.mettre_a_jour() return donnees
  • Avantages
    • Insertion à coût constant en tête et en fin.
    • Suppression de la tête à coût constant.
    • Concaténation de deux listes à coût constant (et ça, c'est très bien)
    • Changement de référence
  • Désavantages
    • Place mémoire plus grande qu'un simple tableau statique (il faut stocker les nombreux attributs en plus des données).
    • Lecture d'un élément connu par son indice du position à coût linéaire (en 𝞞(n)) car on ne connait pas le prédécesseur des cellules
    • Suppression de la fin à coût linéaire (en 𝞗(n)) car on ne connait pas le prédécesseur des cellules
    • Si on désire retrouver des fonctions d'interface avec un choix lié à l'indice, on a un coût linéaire (en 𝞞(n)) puisqu'il faudra partir de la tête et compter les cellules au fur et à mesure de la progression...

3 - PILE

3.1 - Définition du type abstrait PILE

1er partie de la définition - Idée générale d'organisation

  • Séquence ordonnée dans laquelle on peut lire, insérer ou supprimer les données uniquement sur l'une des extrémités qu'on nomme le SOMMET.
  • Concept LIFO : dernier arrivé, premier parti.
  • LIFO

2e partie de la définition - Interface

  • On doit pouvoir
    • créer une nouvelle pile,
    • insérer un élément au sommet (empiler),
    • lire le sommet d'une pile non vide,
    • supprimer le sommet actuel d'une file non vide (dépiler) et
    • tester si la pile est vide.
  • Les prototypes varient en fonction de la nature muable ou pas de la pile.

Remarque

Le type abstrait n'est qu'une idée, sans coût qui correspond lui à une implémentation. Mais lorsqu'on parle de PILE, on sous-entend qu'on va vouloir travailler avec une structure de données à coût constant. Sans cela, on peut considérer qu'il s'agit d'une "mauvaise implémentation".

3.2 - Implémentation tuple (sommet, queue) : coût CONSTANT à l'empilement et au dépilement

On retrouve la structure créée pour la LISTE.

La différence vient du nom des fonctions d'interface et du fait qu'on ne peut agir que sur le sommet.

Version immuable ci-dessous :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
'''Implémentation de type abstrait PILE IMMUABLE en utilisant des tuples (sommet, reste de la pile)''' class Elt: '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile: '''Juste pour pouvoir noter Pile dans les prototypes''' def nouvellePile() -> Pile: '''Renvoie une liste vide''' return () def estPileVide(p:Pile) -> bool: '''Renvoie True si la pile est vide''' return p == () def empiler(elt:Elt, p:Pile) -> Pile: '''Renvoie une nouvelle pile où x est le sommet et p la suite de notre nouvelle pile.''' return (elt, p) def lireSommet(p:Pile) -> Elt: '''Renvoie le sommet d'une pile NON VIDE''' return p[0] def depiler(p:Pile) -> Pile: '''Renvoie une nouvelle pile où on a supprimé l'ancien sommet d'une pile NON VIDE''' return p[1]

3.3 - Implémentation tableau dynamique : coût "CONSTANT" à l'empilement et au dépilement.

L'utilisation du type natif list pose toujours problème vis à vis de l'estimation du coût.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
'''Implémentation de type abstrait PILE MUABLE en utilisant des tableaux dynamiques''' class Elt: '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile: '''Juste pour pouvoir noter Pile dans les prototypes''' def nouvellePile() -> Pile: '''Renvoie la référence d'une nouvelle pile'' return [] def estPileVide(p:Pile) -> bool: '''Renvoie True si la pile est vide''' return p == [] def empiler(elt:Elt, p:Pile) -> None: '''Empile l'élément elt dans la pile p''' p.append(elt) # rajoute un élément à la fin du tableau def depiler(p:Pile) -> Elt: '''Renvoie le sommet qu'on supprime dans une pile NON VIDE''' return p.pop() # supprime et renvoie le dernier élément du tableau def lireSommet(p:Pile) -> Elt: '''Renvoie le sommet d'une pile NON VIDE''' return p[len(p)-1] # ou return pile[-1]

3.4 - Implémentation liste chaînée : coût CONSTANT à l'empilement et au dépilement.

Il suffit de prendre l'implémentation de la liste mais de se limiter au cas de l'insertion en tête et de la suppression en tête : les deux coûts sont constants.

Deuxième différence : inutile de stocker la référence de la fin.

Empiler revient à insérer une tête.

Dépiler revient à supprimer la tête.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
'''Implémentation de type abstrait PILE MUABLE en utilisant des listes chaînées''' # Déclaration des classes servant uniquement pour la documentation class Elt : '''Type de données autorisées dans les cellules''' class CelluleOuNone: '''Instance de Cellule ou None''' # Déclaration des classes class Cellule: '''Classe permettant de créer des cellules non vides''' def __init__(self, valeur:Elt, successeur:CelluleOuNone=None): self.v = valeur self.s = successeur def obtenir_fin_de_chaine(self) -> 'Cellule': if self.s == None: return self else: return self.s.obtenir_fin_de_chaine() def obtenir_nombre_dans_chaine(self) -> int: if self.s == None: return 1 else: return 1 + self.s.obtenir_nombre_dans_chaine() class Pile: '''Classe permettant de créer une Pile sous forme d'une liste chaînée''' def __init__(self, sommet:CelluleOuNone=None): self.tete = sommet self.longueur = 0 if self.tete != None: self.longueur = 1 def est_pile_vide(self) -> bool: return self.longueur == 0 # Déclaration des fonctions def nouvellePile() -> Pile: '''Renvoie la référence d'une nouvelle pile''' return Pile() def estPileVide(p:Pile) -> bool: '''Renvoie True si la pile p est vide''' return p.est_pile_vide() def empiler(x:Elt, p:Pile) -> None: '''Empile x dans la pile p''' nouvelle_cellule = Cellule(x, p.tete) p.tete = nouvelle_cellule p.longueur = p.longueur + 1 def depiler(p:Pile) -> Elt: '''Renvoie l'ancien sommet de la pile NON VIDE p qu'on défile''' donnees = p.tete.v p.tete = p.tete.s p.longueur = p.longueur - 1 return donnees def lireSommet(p:Pile) -> Elt: '''Renvoie le sommet d'une pile NON VIDE''' return p.tete.v

3.5 - Implémentation dictionnaire : coût CONSTANT à l'empilement et au dépilement.

On utilise un dictionnaire qui contient deux clés :

  • Le nombre d'éléments dans la pile.
  • Le nombre d'éléments au maximum dans la pile.
  • Les données de la pile dans un tableau statique (à taille fixe donc)

Comme c'est votre mini-projet, la correction n'est pas ici.

On retiendra néanmoins que les coûts sont bien constants (nous verrons que l'activité Dictionnaire que la lecture/modification d'une clé est presque toujours constant).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
'''Implémentation de type abstrait PILE MUABLE en utilisant un dictionnaire et un tableau statique''' # Phase d'importation # Phase de déclaration des CONSTANTES et variables globales TAILLE = 10 # Phase de déclaration des classes et fonctions class Elt: '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile: '''Juste pour pouvoir noter Pile dans les prototypes''' def nouvellePile() -> Pile: '''Renvoie la référence d'une nouvelle Pile de TAILLE limitée''' p = {} p['nb'] = 0 # contient le nombre de données stockées p['max'] = TAILLE p['data'] = [None for x in range(TAILLE)] # Aucune donnée au début return p def estPileVide(p:Pile) -> bool: '''Renvoie True si la Pile est bien vide, False sinon''' return p['nb'] == 0 def estPilePleine(p:Pile) -> bool: '''Renvoie True si la Pile est pleine, False sinon''' pass def empiler(elt:Elt, p:Pile) -> None: '''Empile l'élément dans une pile NON PLEINE''' pass def depiler(p:Pile) -> Elt: '''Dépile et renvoie le sommet d'une pile NON VIDE''' pass def lireSommet(p:Pile) -> Elt: '''Renvoie la donnée stockée au sommet de la pile NON VIDE p''' pass def taille(p:Pile) -> int: pass

4 - FILE

4.1 - Définition du type abstrait FILE

1er partie de la définition - Idée générale d'organisation

  • il s'agit d'une séquence finie et ordonnée de données
  • on s'impose strictement de n'agir que sur les deux extrémités. On insère d'un côté et on supprime et lit de l'autre
    • insérer un élément du côté de l'entrée (l'ARRIERE de la file) se nomme l'enfilement
    • supprimer l'élément du côté de la sortie (l'AVANT de la file) se nomme le défilement
    FIFO

2e partie de la définition - Interface

On doit pouvoir

  • créer une nouvelle file,
  • insérer à l'arrière (enfiler)
  • lire l'avant d'une file non vide,
  • supprimer l'avant (défiler) d'une file non vide et
  • tester si la file est vide.

4.2 - Mauvaises implémentations d'une FILE

Comme avec les piles, une file implique qu'on désire un enfilement et un défilement à coût constant puisque cela est possible.

Il est tout à fait possible de créer des files dont les coûts sont médiocres (mais c'est une idée un peu étrange...)

Deux exemples que nous avons vu :

  1. Utiliser un simple tableau statique ou dynamique : sur l'une des extrémités, on va nécessairement avoir une insertion à coût linéaire ou une suppression à coût linéaire. C'est donc globalement une mauvaise idée.
  2. Utiliser une liste chainée et considérer que l'AVANT est la dernière cellule : lorsqu'on va vouloir la supprimer, on va devoir trouver le prédécesseur de la fin et donc se retrouver avec un coût linéaire.

4.3 -Implémentation sous forme de deux piles

Principe de fonctionnement

La File est constituée d'un tableau dont les deux premiers indices contiennent :

  • Indice 0 contient la référence d'une pile d'entrée. Les données qui arrivent sont stockées dans cette pile d'entrée.
  • Indice 1 contient la référence d'une pile de sortie. Les données qu'on veut extraire sont stockées dans cette pile de sortie.
  • File avec deux piles

    Que faire lorsqu'on doit enfiler des données ? : on les empile dans la pile d'entrée : coût constant !

    Que faire lorsqu'on doit défiler des données ? : on les dépile de la pile de sortie. Deux cas se présentent :

    1. La pile de sortie n'est pas vide : on dépile la sortie et c'est à coût constant.
    2. La pile de sortie est vide : zut, on va devoir déverser un à un les éléments de la pile d'entrée dans la pile de sortie. Et c'est à coût linéaire.
    3. Déversement qui inverse l'ordre

Implémentation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
'''Implémentation de File en utilisant un tableau de deux Piles Les Piles sont implémentées sous forme de tuples (sommet, autre_pile)''' # Déclarations de Classes ne servant qu'à la documentation class Elt: '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile: '''Juste pour pouvoir noter Pile dans les prototypes''' class File: '''Juste pour pouvoir noter File dans les prototypes''' # Fonctions d'interface des PILES non fournies ici mais nécessaires # Fonction de l'implémentation FILE hors Interface def deverser(f:File) -> None: '''Déverse entièrement la pile d'entrée dans la pile de sortie''' while not estPileVide(f[0]): element = lireSommet(f[0]) f[0] = depiler(f[0]) f[1] = empiler(element, f[1]) # Fonctions d'interface de la FILE def nouvelleFile() -> File: '''Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]''' pileEntree = nouvellePile() # inputStack en anglais pileSortie = nouvellePile() # outputStack en anglais return [pileEntree, pileSortie] def estFileVide(f:File) -> bool: '''Renvoie True si la File est entièrement vide, False sinon''' return estPileVide(f[0]) and estPileVide(f[1]) def enfiler(elt:Elt, f:File) -> None: '''Enfile l'élement elt dans la file f''' f[0] = empiler(elt, f[0]) def defiler(f:File) -> Elt: '''Défile le sommet de la file NON VIDE f et le renvoie''' if estPileVide(f[1]): deverser(f) valeur = lireSommet(f[1]) f[1] = depiler(f[1]) return valeur def lireAvant(f:File) -> Elt: '''Renvoie le sommet de la file NON VIDE f sans la modifier''' if estPileVide(f[1]): deverser(f) return lireSommet(f[1])

Avantages

  1. Implémentation plutôt simple
  2. Coût constant à l'insertion
  3. Coût presque constant en moyenne à la suppression

Désavantage

  1. Coût linéaire à la suppression dans le pire des cas : lorsque la pile de sortie est vide.

4.4 -Implémentation sous forme d'une liste chaînée (coût constant à l'enfilement et au défilement)

Principe de fonctionnement

  • On enfile à la fin de la liste chaînée pour avoir un cout constant à l'enfilement.
  • On défile la tête de la liste chaînée pour avoir un cout constant au défilement.
  • Attention de ne pas faire l'inverse sous peine d'une performance linéaire pour défiler : dans une liste simplement chaînée, on ne connaît pas le prédecesseur d'une cellule et il faut donc le chercher en partant de la tête.

Implémentation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
'''Implémentation de File en utilisant une liste chaînée''' # Déclaration des classes servant uniquement pour la documentation class Elt : '''Type de données autorisées dans les cellules''' class CelluleOuNone: '''Instance de Cellule ou None''' # Déclaration des classes class Cellule: '''Classe permettant de créer des cellules non vides''' def __init__(self, valeur:Elt, successeur:CelluleOuNone=None): self.v = valeur self.s = successeur def obtenir_fin_de_chaine(self) -> 'Cellule': if self.s == None: return self else: return self.s.obtenir_fin_de_chaine() def obtenir_nombre_dans_chaine(self) -> int: if self.s == None: return 1 else: return 1 + self.s.obtenir_nombre_dans_chaine() class File: '''Classe permettant de créer une liste chaînée implémentant une File''' def __init__(self, nouveau:CelluleOuNone=None): self.tete = nouveau self.longueur = 0 self.fin = None self.mettre_a_jour() def mettre_a_jour(self) -> None: if self.tete == None: # La liste est une liste vide self.longueur = 0 self.fin = None else: # La liste contient au moins une cellule self.longueur = self.tete.obtenir_nombre_dans_chaine() self.fin = self.tete.obtenir_fin_de_chaine() def est_file_vide(self) -> bool: return self.tete == None # Déclaration des fonctions def nouvelleFile() -> File: '''Renvoie la référence d'une File''' return File() def estFileVide(f:File) -> bool: '''Renvoie True si la file est vide''' return f.est_file_vide() def enfiler(x:Elt, f:File) -> None: '''Enfile l'élément x à l'arrière de la File''' if estFileVide(f): nouvelle_cellule = Cellule(x) f.tete = nouvelle_cellule f.fin = nouvelle_cellule f.longueur = 1 else: nouvelle_cellule = Cellule(x) f.fin.s = nouvelle_cellule f.fin = nouvelle_cellule f.longueur = f.longueur + 1 def defiler(f:File) -> Elt: '''Défile et renvoie l'élément à l'avant de la file f NON VIDE''' donnees = f.tete.v f.tete = f.tete.s f.longueur = f.longueur - 1 if f.longueur <= 1: f.mettre_a_jour() return donnees def lireAvant(f:File) -> Elt: '''Renvoie le sommet de la file NON VIDE f sans la modifier''' return f.tete.v

4.5 - Autres formes d'implémentation

Il existe encore de nombreuses façons d'implémenter cela de façon correcte. Par exemple, sous forme d'un dictionnaire qui contient

  • Une clé menant à un tableau statique de taille limitée qui contiendra les données à stocker.
  • Une clé contenant l'indice de l'avant
  • Une clé contenant l'indice de l'arrière

Voici un exemple de fonctionnement pour comprendre le principe :

Voici un exemple d'utilisation (avec toujours l'observation du contenu de structure uniquement pour que comprendre comment ça fonctionne)

>>> file = nouvelleFile() >>> file {'avant': None, 'arriere': None, 'taille': 0, 'max': 5, 'data': [None, None, None, None, None]} >>> enfiler(10, file) >>> file {'avant': 0, 'arriere': 0, 'taille': 1, 'max': 5, 'data': [10, None, None, None, None]} >>> enfiler(20, file) >>> enfiler(30, file) >>> enfiler(100, file) >>> file {'avant': 0, 'arriere': 3, 'taille': 4, 'max': 5, 'data': [10, 20, 30, 100, None]} >>> defiler(file) 10 >>> file {'avant': 1, 'arriere': 3, 'taille': 3, 'max': 5, 'data': [None, 20, 30, 100, None]}

Implémentation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
class Elt: '''Juste pour pouvoir noter Elt dans les prototypes''' class File: '''Juste pour pouvoir noter File dans les prototypes''' '''Implémentation de type abstrait Pile en utilisant un dictionnaire et un tableau statique''' def nouvelleFile(taille_max:int=5) -> File: donnees = [None for x in range(taille_max)] return {'avant':None, 'arriere':None, 'taille':0, 'max':taille_max, 'data':donnees} def fileVide(f:File) -> bool: assert type(f) == dict # On vérifie au moins que f est un dictionnaire return f['taille'] == 0 def filePleine(f:File) -> bool: assert type(f) == dict # On vérifie au moins que f est un dictionnaire return f['taille'] >= f['max'] # Normalement, ça ne peut être que égal, pas supérieur def enfiler(elt:Elt, f:File) -> None: if not filePleine(f): # On gére les valeurs d'index de l'arrière if fileVide(f): f['avant'] = 0 # On gère aussi l'avant car c'est la première valeur placée f['arriere'] = 0 # On définit l'index où inserer la première donnée f['taille'] = 1 else: f['arriere'] = f['arriere'] + 1 # On incrémente l'index de l'arrière f['arriere'] = f['arriere'] % f['max'] # On revient à l'index 0 si on a dépassé l'index max des données f['taille'] = f['taille'] + 1 # On augmente la taille # On place la valeur dans les données index_arriere = f['arriere'] # On récupère la valeur d'index où placer l'arrière f['data'][index_arriere] = elt # On place la valeur dans les données def defiler(f:File) -> Elt: if not fileVide(f): index_avant = f['avant'] # On cherche l'index de l'avant reponse = f['data'][index_avant] # On lit et stocke l'avant f['data'][index_avant] = None # Optionnel : on supprime vraiment le contenu de la case f['avant'] = f['avant'] + 1 # On incrémente l'index de l'avant f['avant'] = f['avant'] % f['max'] # On revient à l'index 0 si on a dépassé l'index max des données f['taille'] = f['taille'] - 1 # On diminue la taille if fileVide(f): f['avant'] = None f['arriere'] = None return reponse # On renvoie l'ancienne valeur à l'avant def lireAvant(f:File) -> Elt: if not fileVide(f): index_avant = f['avant'] # On cherche l'index de l'avant return f['data'][index_avant] # On lit et renvoie l'avant

Activité publiée le 25 10 2020
Dernière modification : 07 11 2021
Auteur : ows. h.