Cliquer ici pour imprimer

Dernière modification : 05/06/2022 à 19:10

TODO : manque des bouts

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 :

typedef struct _cell {
 int v;
 struct _cell * next;
}Cell;
typedef Cell * List;

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 : 
List l = empty_list();
int i;
for(i=5;i>0;i--)
    add_first(i,/* a completer */);
print_list(l); /* affiche 1 2 3 4 5*/
for(i=0;i<5;i++)
    remove_first(/* a completer */);
if(is_empty(l)) printf("la liste est vide\n");

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 : 
List l = empty_list();
List l2 = empty_list();
int i;
for(i=5;i>0;i--)
    add_first(i,/* a completer */);
print_list(l); /* affiche 1 2 3 4 5*/
for(i=1;i<=5;i++)
    add_cell(get(1,&l),&l2);
if(is_empty(l)) printf("la liste l est vide\n");
print_list(l2);

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