Programmation impérative : TP 4

• TOUTES les fonctions demandées doivent être commentées (brièvement) ; en particulier on indiquera clairement les prérequis (pile non vide, etc.)
• TOUTES les fonctions demandées doivent être testées dans main.

Piles

Dans cette première partie, on va implémenter les piles à l'aide de tableaux statiques, dont la taille est fixe et constante. On considérera que les éléments mis dans les piles sont de type int.

1. Proposez une procédure d'affichage ainsi que les fonctions sur les piles mentionnées en cours :
   • Affichage d'une pile : sommet à gauche et base à droite, largeur constante ;
   • Initialisation qui a pour effet de rendre une pile vide ;
   • Test de vacuité qui retourne 1 si une pile est vide et 0 sinon ;
   • Empilement qui a pour effet de placer une valeur au sommet de pile ;
   • Dépilement qui a pour effet de retirer l'élement au sommet de la pile et le retourne.
Vous devez utiliser ces fonctions et uniquement celles-ci dans la suite pour toute manipulation des piles.
2. Proposez une procédure qui duplique l'élément à son sommet (on trouve donc ensuite cet élément au sommet et à l'étage juste en dessous ; la pile a gagné un élément).
3. On souhaite écrire une fonction qui calcule la factorielle d'un int à l'aide d'une pile.
   1. Proposez une procédure qui empile son sommet puis celui-ci moins 1 .
      Par exemple si une pile contient k éléments et que son sommet est n, au sortir de la fonction la pile aura k+1 éléments, son sommet sera n-1 et l'étage en dessous du sommet contiendra n.
   2. Proposez une fonction qui retourne le produit de tous les éléments d'une pile (éléments de type int) passée en paramètre.
   3. Proposez une fonction qui retourne la factorielle d'un int à l'aide (entre autre) des deux fonctions précédentes. Vous afficherez la pile à chaque étape.
4. On souhaite écrire une fonction qui calcule la factorielle d'un int à l'aide d'une pile mais de manière un peu différente.
   1. Proposez une procédure qui a pour effet d'empiler le produit des deux premiers éléments accessibles d'une pile (éléments de type int) puis l'ancien sommet moins 1.
      Par exemple si une pile contient k éléments, que son sommet est n et l'étage en dessous du sommet m, au sortir de la fonction la pile aura k éléments, son sommet sera n-1 et l'étage en dessous du sommet contiendra n*m.
   2. Proposez une fonction qui retourne la factorielle d'un int à l'aide (entre autre) de la fonction précédente. Vous afficherez la pile à chaque étape.
5. Quelle différence constatez-vous entre ces deux méthodes ?

Allocations

Vous avez besoin dans la suite de la bibliothèque stdlib.h.

N'hésitez pas à utiliser scanf dans main pour faciliter l'entrée de vos tableaux et valeurs. Un bon exercice consiste à demander à l'utilisateur une taille de tableau puis autant de valeurs à entrer dans les cases qu'il est nécessaire. Ce n'est toutefois pas nécessaire pour la suite dans un premier temps.

1. Proposez une fonction qui sur la donnée de deux double, et seulement deux, retourne un pointeur nouvellement alloué sur un double de la valeur maximale des deux paramètres.
2. Proposez une fonction qui sur la donnée de deux tableaux ta, tb de même taille size (donc trois paramètres) retourne un tableau de même taille nouvellement alloué qui contient leurs différences point-à-point.
3. On souhaite obtenir un tableau trié contenant les mêmes valeurs qu'un tableau t passé en paramètre sans modifier ce dernier. Proposez une fonction qui retourne un pointeur sur un tel tableau trié.

Piles avec redimensionnement dynamique

On va modifier l'implémentation des piles de la première partie pour utiliser des tableaux dynamiques dont on fera varier la taille en fonction du remplissage. On prendra 1 comme taille initiale.

1. Modifiez le type des piles. En particulier il faudra ajouter un champ contenant la taille courante du tableau.
2. Ajouter une procédure qui prend en argument une pile et une nouvelle taille, et qui redimensionne (par effet) la pile pour que son tableau soit de la nouvelle taille. On n'oubliera de libérer la mémoire du tableau précédemment alloué.
3. Modifier la fonction d'empilement pour doubler la taille du tableau en cas de dépassement de capacité.
4. Modifier la fonction de dépilement pour diminuer par deux la taille du tableau quand il est moins rempli qu'un tiers.
5. Vérifier que les fonctions calculant la factorielle fonctionnent toujours.