Listes chaînées

typedef struct _cell {
    int value;                 /* donnee stockee : un entier.       */
    struct _cell *next;        /* pointeur sur la cellule suivante. */
} cell;

typedef cell *list;

1. cell *allocate_cell(int val) qui alloue l'espace mémoire nécessaire pour une nouvelle cellule et retourne l'adresse de cette nouvelle cellule après avoir affecté la valeur val au champ value et NULL au champ next. S'il n'y a plus de place disponible, la fonction renvoie la valeur NULL ;
2. int insert_first(List *lst, int val) qui insère la valeur val en tête de la liste *lst. La fonction renvoie 0 si tout s'est bien passé et -1 en cas d'échec (si elle rencontre un problème lors de l'allocation par exemple);
3. int read_list(list *lst) qui crée une liste chaînée d'entiers non nuls saisis au clavier en les insérant successivement en tête de liste à partir de la liste *lst. La fonction s'arrête d'ajouter des éléments à la liste lorsqu'un entier nul (0) est saisi; elle renvoie -1 en cas de problème et 0 sinon ;
4. void print_list(list lst) qui affiche dans l'ordre du chaînage, les éléments de la liste lst ;
5. cell *find(list lst, int val) qui renvoie l'adresse de la cellule contenant l'entier val. La fonction renvoie NULL si l'entier n'est pas présent dans la liste lst ;
6. void free_list(list *lst) qui libère tout l'espace mémoire occupé par la liste *lst.

1. void print_reverse_list(list lst) qui affiche dans l'ordre inverse du chaînage, les éléments de la liste lst ;
2. int insert_after(list *lst, int new_value, int given_value) qui insère l'entier new_value après l'entier given_value dans la liste *lst ou en fin de liste si given_value n'est pas présent. La fonction renvoie 0 si tout s'est bien passé et -1 en cas d'échec;
3. cell *minimum(list lst) qui renvoie l'adresse d'une cellule contenant la valeur minimale de la liste lst. La fonction renvoie NULL si la liste lst est vide ;
4. void concat_lists(list *lst1, list *lst2)} qui concatène deux listes. La fonction reçoit deux listes et transforme la première en la concaténation des deux listes. Cette fonction ne doit pas créer de nouvelles cellules : elle modifie directement les listes passées en paramètres ;
5. list extract_odds(list *lst) qui extrait de la liste *lst toutes les cellules contenant des valeurs impaires. Les cellules contenant des valeurs impaires ne seront pas supprimées physiquement mais elles formeront une autre liste que la fonction renvoie.
   Par exemple, appliquée à la liste *lst = (5, 7, 2, 1, 9, 8), la fonction doit construire et renvoyer la nouvelle liste (5, 7, 1, 9) et elle doit transformer *lst en (2, 8).

1. Copier le code suivant dans un fichier list.dot.

   digraph list {
     rankdir=LR;
     cell [shape=record];
     edge [tailclip=false, arrowtail=dot, dir=both];
     x1 [width=0.5, label="{ <next> }"];
     x1:next:c -> x2:value;
     x2 [width=1.0, label="{ <value> 3 | <next> }"];
     x2:next:c -> x3:value;
     x3 [width=1.0, label="{ <value> 1 | <next> }"];
     x3:next:c -> x4:value;
     x4 [width=1.0, label="{ <value> 4 | / }"];
   }
   	

2. Taper dans un terminal dot -Tps2 list.dot > list.ps pour construire le graphique et gv list.ps ou evince list.ps pour le visualiser.
   
   
   
   
   
3. À partir de cet exemple, écrire une fonction qui prend une liste et qui génère le code pour la visualiser avec le programme dot. Générer le code soit dans le terminal, soit directement dans un fichier.
   • La documentation du langage DOT.
   • Conseil : Dans l'exemple, x1, x2, ... représentent les quatre boîtes dans le diagramme. Vous pouvez changer ces noms. Cela simplifie des choses si vous donnez les noms en utilisant les adresses des cellules. Par exemple, pour une cellule cell *my_cell, vous pouvez utiliser printf("x%p", my_cell) pour générer son nom.