Algo ProgObjet Python Correction du TD n° 9 1) Piles 1.1) trois versions sont possibles : Version 1, qui vide la pile en affichant ses éléments : méthode afficher() : tant que non estVide() sommet().afficher() dépiler() Version 2, qui laisse la pile intacte tout en utilisant les méthodes fournies uniquement : méthode afficher() : P <- Pile() tant que non estVide() elt <- sommet() elt.afficher() P.empiler(elt) dépiler() tant que non P.estVide() empiler(P.sommet()) P.dépiler() Version 3, qui laisse la pile intacte, mais là, il faudra supposer que l'on dispose de détails sur la réalisation de la pile, qui ne sont pas donnés. Si, par exemple, la pile est réalisée par une liste chaînée, dont le premier élément est référencé par l'attribut "premier", on peut écrire : méthode afficher() : noeud <- premier tant que noeud != nil noeud.donnée().afficher() noeud <- noeud.suivant() 1.2) méthode dépilerKelts(k) : tant que k > 0 et non estVide() dépiler() k <- k - 1 1.3) méthode dépilerJusquà(elt) : tant que non estVide() et sommet() != elt dépiler() 2) Files 2.1) méthode afficher() F <- File() tant que non estVide() elt <- premier() elt.afficher() F.enfiler(elt) défiler() tant que non F.estVide() enfiler(F.premier()) F.défiler() Si, par contre, on disposait de ce qu'on appelle "constructeur de copie", on pourrait donner la définition suivante : méthode afficher() F <- File(self) # créer une copie exacte de cette file tant que non F.estVide() F.premier().afficher() F.défiler() 2.2) méthode défilerJusquà(elt) tant que non estVide() et premier() != elt défiler() 3) Piles et Files 3.1) méthode appartient(elt) : P <- Pile() tant que non estVide() et sommet() != elt P.empiler(sommet()) dépiler() résultat <- non estVide() tant que non P.estVide() empiler(P.sommet()) P.dépiler() renvoyer résultat Si l'on disposait d'un constructeur de copie, on pourrait écrire : méthode appartient(elt) : P <- Pile(self) tant que non P.estVide() et P.sommet() != elt P.dépiler() renvoyer (P.sommet() = elt) 3.2) méthode File::inverser() : P <- Pile() tant que non estVide() P.empiler(premier()) défiler() tant que non P.estVide() enfiler(P.sommet()) P.dépiler() 3.3) On utilisera deux piles auxiliaires, P1 et P2 : méthode Pile::inverser() : P1 <- Pile() tant que non estVide() P1.empiler(sommet()) dépiler() P2 <- Pile() tant que non P1.estVide() P2.empiler(P1.sommet()) P1.dépiler() tant que non P2.estVide() empiler(P2.sommet()) P2.dépiler() 4) File de priorité 4.1) La file après avoir inséré les éléments ayant clés 3, 8, 4, 5, 2, 7 : 8, 7, 5, 4, 3, 2 La file après avoir extrait deux fois l'élément ayant la plus grande clé (8 et 7) : 5, 4, 3, 2 La file après avoir inséré les éléments dont les clés sont 5 et 1 5, 5, 4, 3, 2, 1 La file après avoir extrait deux fois l'élément ayant la plus grande clé (5 et 5) : 4, 3, 2, 1 4.2) Complexité des opérations si les éléments sont conservés sous la forme d'un tableau trié : insertion d'un élément : O(n) extraction de l'élément ayant la plus grande clé : O(1) tester si vide: O(1) Le tableau sera trié par ordre de clé croissante, ainsi l'élément ayant la plus grande clé occupera la dernière position et son extraction se fera en temps constant. Pour l'insertion d'un élément, on l'ajoutera après le dernier élément, puis, tant que sa clé est inférieure de celle de l'élément précédent, on l'échangera avec l'élément précédant. Pour l'opération "augmenter la clé d'un élément", on augmentera sa clé et on procédéra par des échanges successifs avec l'élément suivant tant que sa clé est supérieure de celle de l'élément suivant, en effectuant, dans le pire des cas, O(n) échanges. 4.3) Une structure de données qui permettrait de gérer ces opérations de manière efficace est un tas décroissant : l'élément ayant la plus grande clé occupera la racine ; son extraction se fera en O(log n) (il faut promouvoir le fils ayant la plus grande clé récursivement en descendant vers les feuilles), ainsi que l'insertion d'un nouveau élément et l'augmentation de la clé d'un élément.