Listes chaînées: exercices avancés

Cet exercice contient des exercices plus avancés sur les listes chaînées. Il est conseillé de commencer par le premier exercice sur les listes chaînées avant celui-ci. À nouveau, une liste chaînée sera représentée par un pointeur sur la structure suivante

     typedef struct node {
       int value; /* valeur du nœud */
       struct node *next; /* pointeur vers l’élément suivant */
     } node;

La liste vide est représentée par un pointeur nul. Le but de l’exercice est de comprendre comment manipuler les pointeurs pour modifier des structures chaînées.

Dans toutes les sous-questions, vous devez réutiliser les nœuds des listes passées en argument et modifier leur structure. Il n’est jamais nécessaire d’allouer un nouveau nœud. (Remarque : vous ne devez jamais traiter le cas des listes contenant un cycle.)


Question 1: Inverser une liste

Écrivez le corps de la fonction void reverse(reverse **list), qui doit inverser la liste pointée par list et faire en sorte que list pointe sur le début de la liste inversée.

Question 2: Concaténation de listes

Écrivez le corps de la fonction node *append(node *a, node *b), qui doit renvoyer une liste contenant tous les éléments de la première liste suivis de tous ceux de la seconde.

Puisque cette fonction va modifier les nœuds des listes a et b, ces deux-ci ne peuvent plus être utilisées après l’appel de la fonction. Seule la liste renvoyée permet d’accéder aux données.

Question 3: Séparation d’une liste chaînée

Écrivez le corps de la fonction void split(node *list, node **first_half, node **second_half), qui va couper une liste en son milieu.

Après l’appel, first_half pointe vers le début d’une liste contenant la première moitié de la liste et de même pour second_half avec la seconde. Si la liste est de taille impaire, l’une de ces deux listes (peu importe laquelle) aura un élément de plus que l’autre.

Les nœuds de la liste originale ayant été redistribués entre les deux nouvelles listes, cette première ne pourra plus être utilisée après l’appel. (Une application concrète de cette fonction est l’implémentation d’un algorithme de tri appelé merge sort ou tri fusion.)

Information

Author(s) Kilian Verhetsel
Deadline No deadline
Submission limit No limitation

Sign in