Algorithmique Et Structures de Données II Série 1 (Les Piles Et Les Files) [PDF]

Zitiervorschau

Algorithmique et structures de données II Série 1 (les piles et les files) Nous partons de la déclaration ci-après Type Cellule = Enregistrement Val : entier suiv : *Cellule Fin Enregistrement Pile=Enregistrement Sommet : *Cellule Fin Enregistrement File=Enregistrement Tête : *Cellule Queue : *Cellule Fin Enregistrement Nous supposons également que nous avons à notre disposition les fonctions et procédures suivantes :  La procédure Init_Pile : permettant d'initialiser une pile vide,  La procédure Empiler : permettant d'ajouter un élément en sommet d'une pile,  La fonction Depiler : permettant d'éliminer le sommet d'une pile en retournant sa valeur.  La procédure Init_File : permettant d'initialiser une file vide,  La procédure Enfiler : permettant d'ajouter un élément en queue d'une file,  La fonction Defiler : permettant d'éliminer la tête d'une file en retournant sa valeur.  La fonction Sommet : permettant de retourner le sommet de la pile/file sans le dépiler/défiler.  La fonction Est_vide : qui retourne l’état de la pile/file

Exercice 1 (a) Ecrire un algorithme qui permette d’afficher les éléments d’une liste linéaire chaînée dans l’ordre inverse en utilisant une pile. (b) Ecrire un algorithme qui permet d’implémenter le modèle des files en utilisant deux piles.

Exercice 2 On se donne une file d'entiers que l'on voudrait trier avec le plus grand élément en fin de file. Proposer une solution en utilisant 2 piles.

Exercice 3 Soit P1 et P2 deux piles. La pile P1 contient une suite de nombres entiers positifs. Ecrire un algorithme qui permet de déplacer les entiers de P1 dans P2 de façon à avoir dans P2 tous les nombres pairs au-dessus des nombres impairs (utiliser une troisième pile intermédiaire).

Ecole Nationale d’Ingénieurs de Sousse

2/2

Exercice 4 La notation infixée consiste à entourer les opérateurs par leurs opérandes, comme (a+b)∗c. La notation post-fixée consiste à placer les opérandes devant l’opérateur, comme ab+c*. Ecrire une fonction qui permet d’évaluer une expression post-fixée valide. On suppose que cette dernière se trouve dans un tableau dont les éléments sont de type : (Valeur, Type (opérateur ou opérande)). Exemple : la fonction renvoie 16 pour l’expression post-fixée 3 5 + 2 ∗.

Exercice 5 Une file d’attente avec priorité est une file où les éléments sont caractérisés par une priorité de service : un élément de priorité supérieure est servi même s’il n’est pas arrivé le premier. (a) Décrire les structures nécessaires à l’implémentation de ce modèle en utilisant les listes. (b) Ecrire les procédures Enfiler et Défiler de ce modèle. (c) Expliquer comment peut-on implémenter une pile à l’aide d’une file d’attente avec priorité. (d) Expliquer comment peut-on implémenter une file d’attente ordinaire à l’aide d’une file d’attente avec priorité.

Exercice 6 Un palindrome est une chaîne de caractères qui se lit de la même manière de gauche à droite et de droite à gauche. En utilisant des piles et des files, écrire un algorithme qui détermine si une chaîne de caractères est un palindrome. On suppose que la chaîne de caractères est passée en paramètre dans un tableau contenant n caractères et qui ne sera parcouru qu’une seule fois. L’algorithme doit donner en sortie vrai ou faux selon le cas.

Exercice 7 Soient p1 et p2 deux piles contenant chacune une suite d'entiers triée par ordre décroissant (c'est-à-dire que le sommet de chaque pile contient la valeur maximale de la suite associée). Ecrire la fonction fusion_triee_piles(p1 : pile, p2 : pile, p3 : pile) qui permet de remplir la pile p3, à partir des deux piles p1 et p2, de façon à avoir les éléments de p3 triés par ordre croissant. Le remplissage de p3 doit être effectué de façon à ne pas avoir un élément plus qu'une fois dans la pile. Cette fonction renvoie le nombre d'éléments empilés dans la pile p3. Exemple : L'ordre des éléments des différentes piles données dans cet exemple est celui du sommet de la pile vers la base. Si p1 contient les éléments suivants : 20 -> 15 -> 15 -> 12 et p2 contient les éléments suivants : 26 -> 23 -> 18 -> 9, alors p3 contiendra les éléments suivants : 9 -> 12 -> 15 -> 18 -> 20 -> 23 -> 26. Refaire le même exercice en considérant que la pile p3 doit être triée par ordre décroissant et non croissant.