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).

Dans le cadre de notre projet nous devons travailler avec un tableau dynamique, c'est à dire un tableau dont la taille s'adapte automatiquement lorsqu'il se remplit ou se vide. De plus on ne pourra ajouter des éléments qu'à la fin du tableau (c'est une pile).

Nous allons donc concevoir une bibliothèque (library en anglais) permettant de définir un type représentant un tel tableau et les fonctions de manipulations associées (ajout et suppression d'éléments, récupération de la taille etc).

Cette bibliotèque se composera de 4 fichiers :

  • dyn_stack.h dans lequel on trouvera la déclaration des types et des fonctions
  • dyn_stack.c dans lequel on trouvera le code des fonctions
  • test.c dans lequel on trouvera une fonction main et des fonctions de test pour la bibliothèque
  • makefile, fichier de règles permettant l'automatisation de la compilation avec l'utilitaire make

Makefile

  1. Rappellez la commande permettant de compiler un fichier .c.
  2. Rappellez la commande permettant de réaliser l'édition des liens entre un ou des fichiers .o et les biblothèques pour produire un executable.
  3. Quelles options de compilation vous demande t on d'ajouter systèmatiquement pour cette unité ?
  4. L'utilitaire make est un programme permettant (entre autre) de compiler uniquement les fichiers dont les sources ont changé, de facon automatique. Pour cela, il a besoin d'un fichier de configuration, makefile, qui décrit la dépendance des fichiers entre eux et donne les options de compilations et actions par défaut voulues. Lire cette page jusqu'à la partie 8 incluse et adaptez le makefile proposé à l'étape 8 à notre cas.
Nous compilerons désormais simplement en invoquant dans un terminal la commande make.

Declaration des types et allocation mémoire

  1. Déclarez un type, qui sera celui utilisé dans le tableau : typedef int MyType; (pour tester la bibliothèque, le type sera donc un int, mais il sera aisé de le changer en modifiant uniquement cette ligne).
  2. Définissez une constante INIT_CAPACITY donnant la taille initiale du tableau (par exemple 10)
  3. Écrivez la fonction MyType* construct_ds(); qui créée un tableau de taille INIT_CAPACITY et renvoie son adresse. Si l'allocation n'est pas possible, la fonction renvoie NULL.
  4. Écrivez la fonction void destruct_ds(MyType*); qui libère la mémoire occupée par le tableau
La fonction suivante (à mettre dans test.c) doit fonctionner :
  1. void test1()
  2. {
  3. MyType * tab = construct_ds();
  4. if(tab!=NULL)
  5. {
  6. tab[0] = 8;
  7. tab[INIT_CAPACITY-1] = 12;
  8. destruct_ds(tab);
  9. }
  10. else
  11. {
  12. fprintf(stderr, "Allocation impossible\n");
  13. }
  14. }
  15.  

Manipulation du tableau dans les limites initiales

  1. Ajouter une première version d'une fonction int add(MyType* tab, MyType v, int pos); qui ajoute l'élément v à la position pos. La fonction renvoie 1 si l'élément à été ajouté, 0 sinon. Dans quel(s) cas la fonction renvoie t elle 0 ?
  2. Ajouter une fonction print_tab(MyType*); qui affiche le tableau (pourquoi la fonction n'a t elle pas besoin qu'on lui donne la taille tu tableau en parapmètre ?)
  3. Ajouter une fonction fill_tab(MyType*); qui remplit le tableau avec les entiers naturels en commencant à 1.
  4. Ajouter une fonction test2() au fichier test.c pour tester les trois fonctions précédantes.

Le tableau devient une pile

  1. On veut maintenant modifier la fonction add pour qu'elle ne prenne plus en paramètre la position de l'ajout : nous voulons utiliser le tableau comme une pile, c'est à dire toujours ajouter à la fin ! Il faut donc sauvegarder quelque part une information : la taille courante du tableau (le nombre d'élément que l'on a déjà ajouté). Réfléchissez aux différents choix possibles pour stocker cette information.
  2. Pour l'instant, nous allons céder à la facilité, et utiliser une variable globale int cs; (current size). Une variable gloable est une variable que l'on déclare en dehors de toute fonction, elle est donc accessible depuis toutes les fonctions (pratique mais dangereux, on va le voir).
  3. Modifier la fonction print_tab() pour qu'elle n'affiche que la portion du tableau contenant des éléments qui ont été ajoutés
  4. Si ce n'est pas fait, modifier fill_tab() pour qu'elle appelle correctement add() avec son nouveau prototype.
La fonction suivante (à mettre dans test.c) doit fonctionner :
  1. void test3()
  2. {
  3. int err;
  4. MyType * tab = construct_ds();
  5. if(tab!=NULL)
  6. {
  7. add(tab,1);
  8. print_tab(tab); /* affiche : 1*/
  9. add(tab,2);
  10. print_tab(tab); /* affiche : 1 2*/
  11. fill_tab(tab);
  12. print_tab(tab); /* affiche : 1 2 3 4 5 6 7 8 9 10*/
  13. err=add(tab,11); /* ne doit pas faire de segfault */
  14. print_tab(tab); /* affiche : 1 2 3 4 5 6 7 8 9 10*/
  15. printf("%d\n",err); /* affiche 0 */
  16. destruct_ds(tab);
  17. }
  18. else
  19. {
  20. fprintf(stderr, "Allocation impossible\n");
  21. }
  22. }
  23.  

La fonction pop()

  1. Ajouter une fonction int pop(MyType* tab); qui enlève le dernier élément du tableau. Elle renvoie 1 si un élément a été enlevé, 0 sinon (dans quel(s) cas ?)
  2. On veut également pouvoir récupérer la valeur de l'élément que l'on vient d'enlever. Comme le retour de la fonction pop() est déjà utilisé pour autre chose, on utilisera une variable passée par adresse. Modifier la fonction dont le prototype devient int pop(MyType* tab, MyType* pv);
  3. Sur le même principe, on aura occasionnelement besoin d'une fonction permettant de récupérer une valeur quelquonque du tableau, par son indice. Ajouter la fonction int get_value(MyType* tab, MyType* pv,int i); qui copie la valeur située à l'indice i à l'adresse stockée dans pv et renvoie 0 en cas d'erreur (quand ?) ou 1 en cas de succes.
  4. Ajouter une fonction test4() dans votre fichier test.c pour tester ces deux nouvelles fonctionnalitées.

On fait grandir le tableau !

Nous voulons maintenant que le tableau "grandisse" tout seul si on lui ajouter plus d'élément que sa capacité initiale.
  1. Commencez par remplacer la constante INIT_CAPACITY par une variable globale cc (current capcity). Modifier le code partout ou cela est necessaire
  2. Nous allons maintenant modifier la fonction add() pour quelle modifie la taille du tableau lorsque c'est nécessaire, et lorsque c'est possible
    • Lire la page de manuel de la fonction realloc()
    • Peut on dire ce qu'affiche le code suivant ?
      int * t1 = (int*)malloc(sizeof(int)*3);
      int * t2 = (int*)realloc(t1,sizeof(int)*5);
      printf("%d\n",t1==t2);
      
    • Dans quels cas affiche t il 0, dans quels cas affiche t il 1 ?
  3. Quel doit par conséquent être le nouveau prototype de la fonction add() ?
  4. Modifier le code de add() pour que la capacité du tableau soit doublée lorsque le nombre d'élément atteint 2 tiers de la capacité courante
  5. Modifier le prototype et le code de pop() sur le même model pour que la capacité du tableau soit divisée par deux lorsque son nombre d'élément descend en dessous d'un tiers de sa capacité courante
  6. Attention à bien gérer les cas possibles d'erreur d'allocation mémoire !!
  7. Si ce n'est pas déjà fait, ajouter une fonction test5() qui teste ces deux nouvelles fonctionnalitées
  8. Attention, il faut modifier la fonction fill_tab() si on ne veut pas qu'elle fasse une boucle infinie (il faut qu'elle remplisse le tableau sans appeler add car on ne veut pas que la taille augmente) !

Sans les variables globales

Testez le code suivant :
  1. void test6()
  2. {
  3. int err;
  4. MyType * tab1 = construct_ds();
  5. MyType * tab2 = construct_ds();
  6. if(tab1!=NULL && tab2!=NULL)
  7. {
  8. add(tab1,1);
  9. add(tab2,2);
  10. print_tab(tab1);
  11. print_tab(tab2);
  12. destruct_ds(tab1);
  13. destruct_ds(tab2);
  14. }
  15. else
  16. {
  17. fprintf(stderr, "Allocation impossible\n");
  18. destruct_ds(tab1);
  19. destruct_ds(tab2);
  20. }
  21. }
  22.  
Pourquoi cela ne fonctionne t il pas ? Pour pouvoir utiliser plusieurs piles dynamiques dans le même programme, il est nécéssaire de supprimer l'usage des variables gloables cc et cs (capacité courante et nombre d'élément courant). Vous allez donc déclarer une structure struct _dyn_stack et le type associé DynStack contenant :
  • les deux entiers cc et cs
  • un pointeur vers le premier élément d'un tableau de MyType
Adaptez toutes vos fonctions qui prenaient en paramètre un MyType* pour qu'elles prennent en paramètre un DynStack* (pourquoi un pointeur ? pourrait on faire avec juste un DynStack ? Il est important que vous compreniez la différence). Le code suivant doit fonctionner :
  1. void test7()
  2. {
  3. int err;
  4. DynStack * ds1 = construct_ds();
  5. DynStack * ds2 = construct_ds();
  6. if(ds1!=NULL && ds2!=NULL)
  7. {
  8. add(ds1,1);
  9. add(ds2,2);
  10. print_ds(ds1);
  11. print_ds(ds2);
  12. destruct_ds(ds1);
  13. destruct_ds(ds2);
  14. }
  15. else
  16. {
  17. fprintf(stderr, "Allocation impossible\n");
  18. destruct_ds(ds1);
  19. destruct_ds(ds2);
  20. }
  21. }
  22.  
Complétez la fonction test7() pour tester extenssivement toute la bibliothèque.