Bibliothèque pour une pile dynamique


Cliquez ici pour retirer la feuille de style si vous souhaitez imprimer ce document (ou en cas de problème d'affichage).

Comparer des DynStack

Ajouter les deux fonctions suivantes à la bibliothèques :
  • int cpy_ds(DynStack* src, DynStack* dst) : copie src dans dst, renvoie 1 en cas de succes, 0 en cas d'echec. Attention les tableaux sous jacents n'ont pas forcément la même taille.
  • int cmp_ds(DynStack* ds1, DynStack* ds2) : renvoie -1 si ds1 inférieur à ds2, 0 si égalité, 1 si ds1 supérieur à ds2. La comparaison se fera deux à deux de gauche à droite, exactement comme lorsque vous comparez deux mots dans un dictionnaire (ordre lexicographique).
  • En principe, votre fonction de comparaison fonctionne car vous travaillez avec des entiers, et donc la comparaison avec les opérateurs du C est possible. Comme on veut une bibliothèque la plus générique possible, vous allez écrire une fonction de comparaison de MyType et la passer par pointeur à votre fonction cmp_ds(). En effet, comme n'importe quel autre type de donnée en mémoire, une fonction peut être manipulée par son adresse et non directement par son nom. Inspirez vous de l'exemple basique ci dessous :
    1. #include <stdio.h>
    2.  
    3. void fonction1(int n)
    4. {
    5. printf("fonction 1, paramètre : %d\n",n);
    6. }
    7.  
    8.  
    9. /* exemple d'une fonction qui prend l'adresse d'une autre fonction en paramètre :
    10.  * ptrf est le nom du pointeur,
    11.  * le void est le type de retour de la fonction
    12.  * le int dans les parenthèses indique que l'on attend un pointeur vers une fonction qui prend un seul paramètre de type int*/
    13. void fonction2(int n, void (*ptrf)(int))
    14. {
    15. (*ptrf)(n); /*Appel de la fonction pointée par ptrf*/
    16. }
    17.  
    18. int main(void)
    19. {
    20. /* exemple de l'appel de la fonction qui prend en paramètre l'adresse d'une autre fonction */
    21. fonction2(13,fonction1);
    22. fonction2(13,&(fonction1)); /* les deux syntaxes sont correctes */
    23.  
    24. return 0;
    25.  
    26. }
    27.  
    28.  
    Le prototype de la fonction de comparaison de DynStack est donc : int cmp_ds(DynStack*,DynStack*,int(*cmpMyType)(MyType,MyType));
  • En fait, on ne veut pas manipuler des pointeurs de fonction. On va faire beaucoup plus simple. Ajoutez à votre projet les deux fichiers suivants :
    • my_type.h :
      1.  
      2. #ifndef _MY_TYPE_H
      3. #define _MY_TYPE_H
      4.  
      5. typedef int MyType;
      6.  
      7. void print_mt(MyType v);
      8.  
      9. int cmp_mt(MyType a, MyType b);
      10.  
      11. #endif
      12.  
    • my_type.c :
      1. #include "my_type.h"
      2.  
      3. #include <stdio.h>
      4.  
      5. void print_mt(MyType v)
      6. {
      7. printf("%d",v);
      8. }
      9.  
      10. int cmp_mt(MyType a, MyType b)
      11. {
      12. return a-b;
      13. }
      14.  
    Modifiez dyn_stack.h pour remplacer le typedef de MyType par une inclusion de my_type.h. Changer le prototype de cmp_ds() pour qu'il ne prenne plus de fonction en parametre, il appelera la fonction cmp_mt() définie dans le fichier ci dessus. Changer également votre fonction print_tab() pour qu'elle appelle print_mt() à la place de printf(). Notre bibliotheque devrait maintenant etre générique : pour changer les int en autre chose, il suffira de remplacer les fichiers my_type.h et my_type.c
    Note : vous pouvez laisser dans votre code la version de cmp_ds() avec pointeur de fonction en la renomant cmp_ds_wp().
  • Ecrivez une fonction test() si ce n'est pas déjà fait qui teste tout ca. Vous pouvez essayer de remplacer les fichiers my_type.h et my_type.c par des version où MyType est autre chose qu'un int pour vérifier que tout fonctionne (par exemple un Complex ? c'est un bon exercice).

Quelques fonctions supplémentaires

  • int get_size(DynStack*); renvoie le nombre d'éléments présents dans le DynStack dont l'adresse est passée en paramètre.
  • int find_value(DynStack*, MyType*); parcourt le DynStack dont l'adresse est passée en paramètre à la recherche du MyType dont l'adresse est passée en paramètre. Pour chaque élément la fonction cmp_mt() definie dans my_type.h est appellée et si elle renvoie 0 pour un élément à la position i, find_value() renvoie i. Si on arrive à la fin du parcourt et que cmp_mt a toujours renvoyé autre chose que 0, alors find_value() renvoie -1.