Cliquer ici pour imprimer

Dernière modification : 05/04/2022 à 17:59

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 :

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 :

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 :

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