Exercice : Listes chaînées

1. Dans les TP 9 et 10 vous avez implémenté une fonction de suppression d’une valeur quelconque dans une liste chaînée, puis une version optimisée pour le maximum. Une autre variante de la supression est de supprimer non pas la première occurence d’une valeur, mais l’ensemble de ses occurences. Définissez une telle fonction.

   BEGIN SOLUTION

   Il est relativement aisé d’adapter la fonction précédente supprimer_valeur pour supprimer l’ensemble des valeur et non pas juste la première. Il faut toutefois faire attention aux différents cas limites, notamment au cas où plusieurs valeurs à supprimer sont en tête de liste.

   void supprimer_valeur(liste *l, int val) {
       while (l->tete != NULL && l->tete->val == val) {
           elem *tmp = l->tete;
           l->tete = l->tete->next;
           l->nbelem--;
           free(tmp);
       }
       if (l->nbelem == 0)
           return;
       elem *e = l->tete;
       while (e->next != NULL) {
           if (e->next->val == val) {
               elem *tmp = e->next;
               e->next = tmp->next;
               l->nbelem--;
               free(tmp);
           }
           e = e->next;
       }
   }
   

   END SOLUTION

2. Dans le TP précédent, nous avons vu comment fusionner deux listes triées. Définissez maintenant une fonction qui fusionne deux listes quelconques en intercalant les éléments de la deuxième liste entre les éléments de la première. C’est-à-dire que si la première liste contient les éléments \(l_1,l_2,\ldots,l_n\) et la deuxième les éléments \(m_1,m_2,\ldots,m_n\), après l’appel à la fonction, la première liste devra contenir les éléments \(l_1,m_1,l_2,m_2,\ldots,l_n,m_n\) et la deuxième liste devra être vide. Si les deux listes ne sont pas de même longueur, tous les éléments supplémentaires devront être placés à la fin de la liste.

   BEGIN SOLUTION

   void intercal(liste *l1 liste *l2) {
       if (l1->tete == NULL) {
           l1->tete = l2->tete;
           l2->tete = NULL;
           return;
       }
       if (l2->tete == NULL)
           return;
       elem *e1 = l1->tete, *e2 = l2->tete;
       while (e1 != NULL && e2 != NULL) {
           elem *e1_next = e1->next;
           elem *e2_next = e2->next;
           e2->next = e1_next;
           e1->next = e2;
           e1 = e1_next;
           e2 = e2_next;
       }
       if (e2 != NULL) {
           l2->tete = e2;
           concat(l1, l2);
       }
       l2->tete = NULL;
   }
   

   END SOLUTION