TD3 : Listes chaînées 2/2 – Structures de Données Avancé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.

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 (incluants celles pour les listes head-tail): ici.
list-utils.c pour les implémentations des fonctions de base (incluants celles pour les listes head-tail): ici.

1 Exercice 2 : Fonction mystère

On rappelle les structures de données représentant une liste chaînée standard telle que définie dans le cours. Il vous est également donné les prototypes de fonctions pop_head et push_tail:

typedef struct s_cell {
   int value;
   struct s_cell * next;
} t_cell;

typedef struct s_list {
   t_cell * head;
} t_list;

t_cell * pop_head(t_list * list);
void push_tail(t_list * list, t_cell * cell);

La descriptions de ces fonctions est la suivante :

pop_head : retire la tête de la liste list et retourne un pointeur vers la cellule retirée. Si la liste est vide, elle retourne NULL. Elle met à jour le pointeur next de la cellule retirée pour qu’il pointe vers NULL en s’assurant que la liste list est correctement mise à jour.
push_tail : ajoute la cellule pointée par cell à la fin de la liste list. Si la liste est vide, la cellule devient la tête de la liste.

On considère par la suite les deux listes chaînées l1 et l2 suivantes :

l1 [head: @256]
@1024
 |
 v
[2 | @512] -> [4 | @104] -> [8 | @208] -> [16 | @80] -> [32 | @64] -> [64 | NULL]
@256           @512         @104          @208          @80          @64

l2 [head: @128]
@32
 |
 v
[1, @202] -> [3, @88] -> [5, @16] -> [7, NULL]
@128         @202        @88         @16

Puis la fonction dont la définition est donnée ci-dessous :

t_list xxx_lists (t_list * l1, t_list * l2) {
    if (l1->head == NULL) return *l2;
    if (l2->head == NULL) return *l1;

    t_list res;
    res.head = NULL;
    
    while (l1->head != NULL || l2->head != NULL) {
        t_cell * p = pop_head(l1);
        t_cell * q = pop_head(l2);
        if (p == NULL) {
            push_tail(&res, q);
        } else if (q == NULL) {
            push_tail(&res, p);
        } else {
            push_tail(&res, p);
            push_tail(&res, q);
        }
    }
    return res;
}

Question 1 : Donnez la représentation visuelle de la liste retournée par l’appel xxx_lists(&l1, &l2).
Question 2 : Quel est le rôle de la fonction xxx_lists ? Expliquez en quelques phrases ce que fait cette fonction.

2 Exercice 2 : Quelque chose en place

On considère la fonction suivante :

t_list xxx_in_place (t_list l) {
   t_cell * precedent = NULL;
   t_cell * courant = l.head;
   t_cell * suivant = NULL;

   while (courant != NULL) {
       suivant = courant->next;
       courant->next = precedent;
       precedent = courant;
       courant = suivant;
   }

   l.head = precedent;
   return l;
}

On considère par la suite la liste chaînée l suivante :

l [head: @256]
@1024
 |
 v
[1 | @512] -> [1 | @104] -> [2 | @208] -> [3 | @320] -> [5 | NULL] 
 @256          @512          @104          @208          @320

Complétez le tableau ci-dessous afin de représenter l’état des pointeurs precedent, courant et suivant à chaque itération de la boucle while de la fonction xxx_in_place lorsque l’on appelle l = xxx_in_place(l).

Itération	`precedent`	`precedent->next`	`courant`	`courant->next`	`suivant`	`suivant->next`
Avant la boucle	`NULL`	-	`@256`	`@512`	-	-
Iter 1
Iter 2
Iter 3	…	…	…	…	…	…

3 Exercice 3 : Affichage d’une liste head-tail

On considère une liste chaînée head-tail de type t_ht_list dont les cellules stockent des entiers, telle que définie dans le cours.

Rappelez la condition qui permet de savoir si une liste head-tail est vide.
On considère par la suite une liste t_ht_list myhtlist initialement vide. En utilisant les exemples de visualisation du cours, donnez la représentation visuelle de la liste après chacune des opérations suivantes :
1. Ajout d’une cellule pointée par new_cell contenant la valeur -4 en tête de la liste.
2. Ajout d’une cellule pointée par new_cell contenant la valeur 123 en tête de la liste.
Quelle différence remarquez-vous entre les deux opérations précédentes ? Que ce passe-t’il au niveau du pointeur tail lors de l’ajout en tête dans une liste vide ?
On souhaite désormais ajouter une cellule en fin de liste avec une valeur 7. Donnez la représentation visuelle de la liste après cette opération.
En vous appuyant sur les fonctions déjà implémentées dans le cours, écrivez une fonction print_ht_list qui affiche les éléments d’une liste head-tail dans le format suivant :
```
Liste head-tail : -4 -> 123 -> 7 -> NULL
```
Le prototype de la fonction est le suivant :
```
void print_ht_list(t_ht_list * list);
```
Écrivez le programme principal qui crée une liste head-tail, y insère les éléments -4, 123 et 7 comme décrit précédemment, puis affiche la liste en utilisant la fonction print_ht_list.