TD2 : Listes chaînées

Exercices sur les listes chaînées
Indications
  • Utilisez les structures de données et les fonctions de base vues dans le cours sur les listes chaînées.
  • On supposera que les fonctions de base vue dans le cours sur les listes chaînées sont toutes disponibles (création de liste, insertion en tête, affichage, etc.).
  • Pour chaque exercice, vous aurez la possibilité d’utiliser les fonctions déjà implémentées dans les exercices précédents. On supposera que ces fonctions sont correctes.

1 Exercice 1 : Création et affichage

Dans cet exercice, on souhaite créer une liste chaînée à partir d’un tableau d’entiers puis l’afficher de manière récursive.

Par exemple, pour le tableau [1, 2, 3], on souhaite obtenir la liste chaînée 1 -> 2 -> 3 -> NULL.

  1. Création de la liste :

    1. En supposant que vous disposez d’une liste vide t_list l, parmi les opérations de bases vues en cours, lesquelles pouvez-vous utiliser pour construire la liste à partir du tableau ?

    2. Décrire ensuite les étapes nécessaires pour créer la liste chaînée à partir du tableau selon l’opération choisie en sachant que l’on doit conserver l’ordre des éléments du tableau.

    3. Écrivez alors une fonction create_list_from_array qui prend en paramètre un tableau d’entiers et sa taille, et qui crée une liste chaînée contenant les éléments du tableau dans le même ordre.

      t_list create_list_from_array(int arr[], int size);

  2. Affichage récursif:

    1. Rappelez brièvement comment fonctionne une fonction récursive.

    2. Afin d’afficher les éléments d’une liste chaînée de manière récursive, l’idée est de définir une fonction qui affiche la valeur de la cellule courante, puis appelle récursivement la même fonction sur la cellule suivante jusqu’à atteindre la fin de la liste (cellule NULL). Quel est le cas de base pour cette récursion ?

    3. Décrire alors la fonction print_list_rec de manière récursive, en complétant la description suivante : \[ \textsf{print\_list\_rec(cell)} = \begin{cases} \dots & \text{si } \dots \\ \dots & \text{sinon} \end{cases} \]

    4. Écrivez une fonction print_list_rec qui affiche les éléments d’une liste chaînée de manière récursive et dont le prototype est :

      void print_list_rec(t_cell * cell);

      L’affichage doit se faire dans le format suivant :

      Liste : 1 -> 2 -> 3 -> NULL

      Afin d’afficher une liste l, quelle est le paramètre à passer à print_list_rec ?

  3. Programme principal : Écrivez un programme principal qui :

    • Crée un tableau d’entiers int arr[] = {10, 20, 30, 40, 50};
    • Utilise create_list_from_array pour créer une liste chaînée à partir de ce tableau
    • Affiche la liste en utilisant print_list_rec
    • Libère la mémoire allouée pour la liste
    • Affiche à nouveau la liste pour vérifier qu’elle est vide.
Fonctions du cours utiles

Récupérez directement les fonctions du cours ici :

  • list-utils.h pour les entêtes des fonctions et les définitions des structures : ici.
  • list-utils.c pour les implémentations des fonctions de base : ici.

2 Exercice 2 : Recherche d’un élément

Pour rechercher un élément dans une liste, on doit parcourir les cellules jusqu’à trouver la valeur recherchée ou atteindre la fin de la liste.

  1. Quelle situation indique directement que l’élément n’est pas présent dans la liste sans avoir à parcourir toutes les cellules ?

  2. Pour une liste non vide, quelles seraient les conditions d’arrêt de la boucle de parcours ?

  3. Écrivez en langage C une fonction search qui prend en paramètres un pointeur sur une liste et une valeur à rechercher, et qui retourne un pointeur vers la cellule contenant la valeur, ou NULL si la valeur n’est pas trouvée.

    t_cell * search(t_list list, int value);

3 Exercice 3 : Calcul de la longueur

On souhaite calculer le nombre d’éléments présents dans une liste chaînée.

  1. Quelle est la longueur d’une liste vide ?

  2. Écrivez une fonction length_list qui calcule et retourne le nombre d’éléments dans une liste.

    int length_list(t_list list);

    Par exemple, pour la liste 10 -> 20 -> 30 -> NULL, la fonction doit retourner 3.

Note

Question bonus : Comment pourriez-vous modifier la structure t_list pour que le calcul de la longueur ne nécessite pas de parcourir la liste ? Quels seraient les avantages et inconvénients de cette approche ?

4 Exercice 4 : Insertion à une position donnée

On souhaite insérer un élément à une position spécifique dans la liste (par exemple, en position 2).

  1. Cas particuliers : Identifiez les cas particuliers à traiter :

    • Que se passe-t-il si on veut insérer à la position 0 ?
    • Que se passe-t-il si la position demandée est invalide (plus grande que la taille de la liste) ?

  2. Algorithme : Décrivez l’algorithme d’insertion à une position donnée. Quels pointeurs devez-vous manipuler ?

  3. Visualisation : Sur papier, dessinez les étapes pour insérer la valeur 25 à la position 2 dans la liste 10 -> 20 -> 30 -> 40 -> NULL.

  4. Implémentation : Écrivez la fonction insert_at_position :

    void insert_at_position(t_list *list, int value, int position);

    La fonction doit afficher un message d’erreur si la position est invalide.

  5. Test : Testez votre fonction avec :

    • Insertion en position 0 (début)
    • Insertion en position valide au milieu
    • Insertion à la fin
    • Tentative d’insertion à une position invalide
Tip

Astuce : Pour insérer à la position n, il faut se placer à la position n-1, puis modifier les pointeurs appropriés. Pensez à réutiliser les fonctions existantes quand c’est possible !

5 Exercice 5 : Inversion d’une liste

Inverser une liste signifie renverser l’ordre des cellules. Par exemple, 10 -> 20 -> 30 -> NULL devient 30 -> 20 -> 10 -> NULL.

Visualisation : Voici comment la liste change :

---
config:
    look: 'handDrawn'
---
graph LR
   subgraph list
    head[head]
   end
   head --> A["[10 | @]"] --> B["[20 | @]"] --> C["[30 | NULL]"]

    style head fill:#FFE6E6

Après :

---
config:
    look: 'handDrawn'
---
graph LR
   subgraph list
      head[head]
   end
   head --> C["[30 | @]"] --> B["[20 | @]"] --> A["[10 | NULL]"]
    
    style head fill:#FFE6E6

  1. Comprendre le problème : Pour chaque cellule, que doit-on modifier ? Dans quelle direction doit pointer chaque next ?

  2. Pointeurs nécessaires : L’algorithme itératif nécessite trois pointeurs : prev, cur, et next. Expliquez le rôle de chacun.

  3. Étapes de l’algorithme : Décrivez en pseudo-code les étapes pour inverser une liste. Pour chaque cellule visitée, quelles sont les opérations à effectuer ?

  4. Implémentation : Écrivez la fonction reverse_list qui inverse l’ordre des éléments d’une liste :

    void reverse_list(t_list *list);

  5. Test sur papier : Tracez l’exécution de votre algorithme sur la liste [10, 20, 30] :

    • Dessinez l’état des trois pointeurs à chaque itération
    • Montrez comment les pointeurs next sont modifiés

  6. Implémentation en C : Testez votre fonction avec différentes listes (vide, un élément, plusieurs éléments).

Important

Attention ! Il est crucial de sauvegarder cur->next avant de modifier le pointeur next de la cellule courante, sinon vous perdrez l’accès au reste de la liste.

6 Exercice 6 : Fusion de deux listes triées

Soit deux listes chaînées triées par ordre croissant. On souhaite les fusionner en une seule liste triée. Cette fonction ne doit pas créer de nouvelles cellules, mais réutiliser celles des listes d’origine.

Exemple :

  • Liste 1 : 1 -> 3 -> 5 -> 7 -> NULL
  • Liste 2 : 2 -> 4 -> 6 -> 8 -> NULL
  • Liste fusionnée : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL

Stratégie : l’idée est de parcourir les deux listes simultanément, en comparant les éléments courants et en ajoutant le plus petit à la liste résultante.

  1. Que doit-on faire quand l’une des deux listes est vide ? Quelle est alors la condition de l’arrêt de la boucle qui parcourt simultanément les deux listes ?

  2. Écrivez la fonction merge_sorted_lists :

    t_list merge_sorted_lists(t_list * list1, t_list * list2);