Listes chainées

Lire cette page

On se donne une structure de liste chaînée de données de type int définie ainsi : 
  1. typedef struct _cell {
  2.  int v;
  3.  struct _cell * next;
  4. }Cell;
  5. typedef Cell * List;
  6.  

Exercice 1

Écrire une fonction List empty_list () qui renvoie la valeur de pointeur que vous aurez choisie pour représenter la liste vide, puis la fonction Boolean is_empty (List l) qui teste si une liste est vide (vous devrez définire le type Boolean, avec une enum).

Exercice 2

Écrire deux fonctions d'affichage des éléments d'une liste. L'une itérative, l'autre récursive.

Exercice 3

Écrire une fonction List add_first(int data, List l) qui renvoie une liste ayant comme premier élément data et dont la suite est constituée par la liste l ainsi que la fonction List remove_first(List l) qui prend une liste non vide l, lui enlève sa tête et renvoie la suite de la liste. Assurez vous que toute la mémoire allouée par X appels à add_first soit libérée par X appels à remove_first.
Ecrire une fonction main() pour tester votre code.

Exercice 4

Changez les signatures de add_first et remove_first pour que le code suivant (à completer) fonctionne comme attendu : 
  1. List l = empty_list();
  2. int i;
  3. for(i=5;i>0;i--)
  4. 	add_first(i,/* a completer */);
  5. print_list(l); /* affiche 1 2 3 4 5*/
  6. for(i=0;i<5;i++)
  7. 	remove_first(/* a completer */);
  8. if(is_empty(l)) printf("la liste est vide\n");
  9.  

Exercice 5

Écrire une fonction void free_list(List * l) qui libère toute la mémoire occupée par une liste l. Pourquoi la liste est-elle passée par adresse ? en remplacant la boucle du code précédant par un appel à free_list, le comportement du programme ne doit pas changer.

Exercice 6

Écrire une fonction Cell* get(int v, List * l) qui enlève la première occurrence de v dans la liste l passée par adresse. La mémoire associée au maillon enlevé ne doit pas être libéré, en revanche un pointeur vers ce maillon est renvoyé. Ecire ensuite une fonction List add_cell(Cell* c, List * l); qui ajoute le maillon c passé par addresse à la fin de la liste l passée par adresse. Testez le code : 
  1. List l = empty_list();
  2. List l2 = empty_list();
  3. int i;
  4. for(i=5;i>0;i--)
  5. 	add_first(i,/* a completer */);
  6. print_list(l); /* affiche 1 2 3 4 5*/
  7. for(i=1;i<=5;i++)
  8. 	add_cell(get(1,&l),&l2);
  9. if(is_empty(l)) printf("la liste l est vide\n");
  10. print_list(l2);
  11.  

Application au mini projet

Nous souhaitons ajouter au mini projet la possibilité de revenir en arrière. Pour cela nous allons gérer une pile des Grilles. Chaque fois qu'une nouvelle Grille est calculée, elle vient s'ajouter sur la pile. Si l'on souhaite revenir en arrière, il suffit de "dépiler", c'est à dire d'enlever la grille qui se situe en haut de la pile. La Grille courant (a afficher) est celle en haut de la pile.

Pour programmer cette pile, nous allons utiliser une liste chainée. Le premier maillon représente le sommet de la pile. Empiler consiste donc à rajouter un maillon en tête, tandis que dépiler consiste à enlever la tête de liste.

Ajoutez à votre projet un bibliotheque pile.h dans laquelle vous définirez une liste chainée de Grille et ses fonctions de manipulation (création, ajout d'une Grille en tête, retire une Grille en tête, libération de la mémoire, et d'autres si vous le jugez utile).

Vous rajouterez également une constante MAX_PILE définissant la taille maximum de la liste. Lorsque cette taille est atteinte, si l'on ajoute un nouveau maillon en tête de liste, le dernier est supprimé.

Ajoutez à votre projet la possibilité de revenir en arrière grace à la touche b.