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

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.

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

Transféré par

Droits d'auteur :

Formats disponibles

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

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

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

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique et structures de données II

Série 1 (les piles et les files)

Nous partons de la déclaration ci-après

Vous aimerez peut-être aussi