Cliquer ici pour imprimer

Dernière modification : 25/05/2020 à 18:38

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 allons modifier le mini projet pour que le serpent ne stocke plus ses positions dans un tableau mais dans une liste chainée de positions.

  • modifiez le type Position pour que la structure contienne un pointeur next
  • modifiez le type Snake pour remplacer le tableau de position par un pointeur vers une Position que vous appelerez segments_list
  • ajoutez aussi un champs entier size
  • ecrivez une fonction new_snake qui renvoit un nouveau serpent alloué dynamiquement dans lequel le champs size est à 0 et le champs segments_list est à NULL
  • ecrivez une fonction add_segment qui prend en paramètre un pointeur de Snake et deux entiers x et y,
    • créée une Position à partir de x et y, allouée dynamiquement et dont le champs next est à NULL
    • ajoute cette Position en queue de la liste des segments
  • ecrivez une fonction free_snake qui libère toute la mémoire associée à un serpent
  • modifiez le reste de votre code en conséquence pour qu'il marche comme avant avec ces modifications sur le type Snake. N'oubliez pas d'utiliser new_snake et free_snake