TP 3

    Pile de données

    Une pile ("stack" en anglais) est une structure de type LIFO : "Last In First Out". On considère qu'une pile est constituée de 2 éléments :

    • - Une structure de données values qui stockera les valeurs de la pile.
    • - Un entier stack_index qui donne l'index dans le tableau du dernier élément entré dans la pile.

    On se propose de créer en C les outils nécessaires pour gérer une pile de valeurs réels. La structure de données sera une liste doublement chaînées contenant des valeurs réel. La principale différence avec une liste simplement chaînées est la suivante : les maillons de la liste contiennent à la fois un pointeur vers le suivant et vers le précédent élément. La liste contient un pointeur vers le premier et le dernier élément de la liste.

    On commence par créer les outils nécessaire sur les listes doublement chaînées.

    Listes doublement chaînées

  1. Définir les structures cell_struct et list_struct permettant de représenter une liste doublement chaînées comme décrite ci-dessus. Définissez les alias de type cell et list à partir de ces structures.
  2. Programmez la fonction void init_list(list **l) permettant d'allouer l'espace mémoire pour une liste et de l'initialiser.
  3. La fonction void add_head_list(list* l, float val) permet d'ajouter un élément en tête de la liste (c'est à dire en première position). Implémentez la.
  4. De même, la fonction void add_tail_list(list* l, float val) permet d'ajouter un élément en queue de la liste (c'est à dire à la fin). Implémentez la également.
  5. Donnez le code de la fonction float pop_index(list *l, int index) qui renvoie la valeur du i^ème élément de la liste et le supprime de la liste.
  6. Programmez la fonction void delete_list(list *l) permettant de supprimer complètement une liste.
  7. Implémentez un main pour tester toutes vos fonctions précédentes.

    8. Bases sur les piles

  8. Définir la structure stack_struct permettant de représenter une pile comme décrite ci-dessus à partir des listes doublement chaînées. Définissez l'alias de type stack à partir de cette structure.
  9. Programmez la fonction void init_stack(stack **s) permettant d'allouer l'espace mémoire pour une pile et de l'initialiser.
  10. Donnez le code de la fonction bool is_empty(stack s) permettant de savoir si une pile est vide ou non.
  11. La fonction void add_stack(stack* s, float val) permet d'ajouter un élément à la pile. Implémentez la.
  12. Donnez le code de la fonction float pop_stack(stack *s) qui renvoie la valeur du premier élément à dépiler.
  13. Programmez la fonction void delete_stack(stack *s) permettant de supprimer complètement une pile.
  14. Implémentez un main pour tester toutes vos fonctions précédentes.


    15. Pour les plus rapides

    Imaginez que nous n'utilisions pas les listes doublement chaînées pour réaliser les piles, mais un simple tableau de nombres :

    #define MAX 20
    typedef struct {
        int stack_index;
        float values[MAX];
    } stack;

    Dans un nouveau fichier C, reprenez ces déclarations et recodez les fonctions demandées dans la partie précédente en faisant en sorte que le stack_index parcours le tableau de façon circulaire (arrivé au bout, on reprend au début). On codera une absence de valeur dans le tableau par -1.