Exercice 1 :
Un palindrome est une chaine de caractères qui se lit de la même manière de gauche à
droite et de droite à gauche. En utilisant une pile écrire un programme qui permet de vérifier
si une chaine de caractère est palindrome.
Exemple : AZIZA est palindrome.
Mohammed n’est palindrome.
Exercice 2 :
Définir une structure pile à l’aide d’un tableau d’entiers de N éléments au maximum et un
sommet. On considérera que N est une constante donnée.
1. Ecrire les fonctions suivantes :
- pile * InitialiserPile() ; qui crée et initialise une pile vide,
- int pileVide(pile p ) ; qui retourne 1 si la pile est vide et 0 sinon,
- int depiler(pile *p) ; qui retourne le dernier élément après l’avoir retiré de la pile,
- void empiler(pile *p , int elt) ; qui empile l’élément elt,
- int SommetPile(pile p) ; qui retourne le sommet de la pile.
On se donne trois piles P1, P2 et P3. La pile P1 contient une suite de nombres entiers
positifs.
2. Ecrire une fonction pour déplacer(pile p1, pile*p2) les entiers de P1 dans P2 de façon à
avoir dans P2 tous les nombres pairs au-dessus des nombres impairs.
3. Ecrire une fonction pour copier(pile p1, pile*p2) dans P2 les nombres pairs contenus
dans P1. Le contenu de P1 après exécution de l’algorithme doit être identique à celui avant
exécution. Les nombres pairs doivent être dans P2 dans l’ordre ou ils apparaissent dans P1.
Exercice 3 :
On se donne une file d’entiers que l’on voudrait trier avec le plus grand élément en fin de
file. On n’est autorisé à utiliser que la fonction fileVide(File*F), emfiler (File*F, int elm),
defiler (File*F) et les opérations suivantes:
- defilerEnfiler(File*F, File*F1) : Défile le premier élément de la première file et l’ajoute à la
deuxième file.
- comparer (File*F, File*F1): Retourne 1 si le premier élément de la première file est plus
grand ou égal au premier élément de la deuxième file et 0 sinon.
1. Définir les fonction fileVide , emfiler, defiler , defilerEnfiler et comparer.
2. Donner un algorithme de tri (File*F1, File*F2) qui utilise seulement ces opérations et 3
files. La file F1 contiendra les entiers à trier, file F2 contiendra les entiers triés après
exécution et la file F3 pourra servir de file auxiliaire.
Exercice 4: pile et élément avec priorité
On suppose que tout élément est muni d’une priorité strictement positive représentée par
un entier qui doit être précisé au moment de l’ajout de l’élément dans la pile. La fonction
retirer doit chercher l’élément le plus prioritaire. On s’intéresse à une implémentation
efficace des opérations (ajouter et retirer). Chaque élément de la pile sera défini par la
structure de donnée suivante :
typedef struct elt {
int priorite ; // priorite représente la priorité de l’élément de type entier
char donnee ; // donnée porte une valeur de type char
} element
1- Donner les structures de données pour manipuler la pile.
2- Donner une implémentation des fonctions ajouter et retirer dans les deux cas suivants :
A- la fonction ajouter range les éléments dans un ordre quelconque. Ce qui implique que la
fonction retirer doit parcourir la pile pour extraire les éléments jusqu’à elle arrive à
l’élément prioritaire puis elle doit rendre les éléments retirés dans le même ordre avant
l’extraction.
B- la fonction ajouter maintient les éléments par ordre de priorité croissante.
3- Ecrire la fonction main pour tester les différentes fonctions.
