Listes chaînées

typedef struct cellule {
    int valeur;                 /* donnee stockee : un entier.       */
    struct cellule *suivant;    /* pointeur sur la cellule suivante. */
} Cellule;

typedef Cellule *Liste;

1. Cellule *allouerCellule(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 valeur et NULL au champ suivant. S'il n'y a plus de place disponible, la fonction renvoie la valeur NULL ;
2. int insererEnTete(Liste *lst, int val) qui insère la valeur val en tête de la liste *lst. La fonction renvoie 0 en cas de problème et 1 sinon ;
3. int lireListe(Liste *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 0 en cas de problème et 1 sinon ;
4. void afficherListe(Liste lst) qui affiche dans l'ordre du chaînage, les éléments de la liste lst ;
5. Cellule *rechercher(Liste 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 libererListe(Liste *lst) qui libère tout l'espace mémoire occupé par la liste *lst.

1. void afficherInvListe(Liste lst) qui affiche dans l'ordre inverse du chaînage, les éléments de la liste lst ;
2. int insererApres(Liste *lst, int val, int apres) qui insère l'entier val après l'entier apres dans la liste *lst ou en fin de liste si apres n'est pas présent ; la fonction renvoie 0 en cas de problème et 1 sinon ;
3. Cellule *minimum(Liste 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 concatenerListes(Liste *lst1, Liste *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. Liste extraireImpaires(Liste *lst) qui extrait de la liste *lst toutes les cellules contenant des valeurs impaires. Les cellules contenant des valeurs paires 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 liste {
     rankdir=LR;
     node [shape=record];
     edge [tailclip=false, arrowtail=dot, dir=both];
     x1 [width=0.5, label="{ <suivant> }"];
     x1:suivant:c -> x2:valeur;
     x2 [width=1.0, label="{ <valeur> 3 | <suivant> }"];
     x2:suivant:c -> x3:valeur;
     x3 [width=1.0, label="{ <valeur> 1 | <suivant> }"];
     x3:suivant:c -> x4:valeur;
     x4 [width=1.0, label="{ <valeur> 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, vous pouvez utiliser printf("x%p", cell) pour générer son nom.