Filières : 1-ISI
A.U : 2020/2021
Enseignant : Dr. Omar NAIFAR
TD 2
Algorithmique et structure des données
(Les piles)
Exercice 1
Dans cet exercice, on écrira les fonctions et procédures nécessaires pour implémenter une pile.
Pour cela, considérer le programme incomplet suivant :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Element
{
int contenue;
struct Element *suivant;
}Element;
Element *CreateElement(int val)
{
... ... à faire ... ...
}
void afficher(Element *pile)
{
... ... à faire ... ...
}
int est_vide(Element *pile)
{
... ... à faire ... ...
}
void push(int n,Element **pile)
{
... ... à faire ... ...
}
void pop(Element **pile)
{
... ... à faire ... ...
}
int peek(Element *pile)
{
... ... à faire ... ...
}
1
int main()
{
Element *pile=NULL;
push(7,&pile);
push(5,&pile);
push(3,&pile);
push(1,&pile);
afficher(pile);
pop(&pile);
printf("Vide: %d",est_vide(pile));
afficher(pile);
printf("le sommet de la pile est : %d",peek(pile));
return 0;
}
1. Ecrire les fonctions et procédures qui sont « à faire ». Remarque : Ne changez pas les en-
têtes/définitions des fonctions/paramètres !
2. Déterminer la complexité asymptotique de chaque fonction/procédure que vous avez
écrits.
3. Qu’est-ce qui est affiché à l’écran lors du premier appel de afficher()?
4. Qu’est-ce qui est affiché à l’écran lors du premier appel de printf()?
5. Qu’est-ce qui est affiché à l’écran lors du deuxième appel de afficher()?
6. Qu’est-ce qui est affiché à l’écran lors du deuxième appel de printf()?
7. Ecrire une procédure fonction vider() qui vide la pile entièrement.
Exercice 2
Une chaine de caractères peut contenir des parenthèses ( ), des crochets [ ], et des accolades{}.
Ces éléments peuvent être imbriqués les uns dans les autres (exemple : {a(bc[d])[{ef}(g)]} )
Écrire une fonction qui parcourt une chaine de caractères et détermine si cette chaine est
correctement parenthésé, c’est-à-dire si toutes les parenthèses, crochets, etc. sont bien refermés
par un caractère du même type, et si les parenthèses, crochets et accolades sont correctement
imbriqués. Exemple d’une chaine de caractères incorrect : ({)}..
