Listes chainées¶

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

Rendu¶

N'oubliez pas de pousser votre travail sur gitlab !

Dans un répertoire nommé login_tp6 copiez vos .c, makefile et .h. Vous pouvez y ajouter un fichier texte README si vous avez des choses à expliquer à joindre à votre rendu. Depuis le répertoire parent, tapez la commande tar czf login_tp6.tgz login_tp6. Déposez sur blackboard le fichier obtenu.