Exercice : Mise en place

Exercice : Mise en place#

Dans ce TP, nous cherchons à implémenter un ensemble de structures de données et de fonctions permettant d’utiliser des listes simplement chaînées d’entiers. Chaque noeud de la liste doit donc contenir une valeur entière ainsi qu’un pointeur vers le nœud suivant.

Commençons par les éléments de base nécessaires à la création d’une liste et à son affichage afin de simplifier les tests des fonctions suivantes. N’oubliez pas de bien tester toutes vos fonctions au fur et à mesure que vous les écrivez et n’oubliez pas de réfléchir et tester les cas limites.

Commencer par définir les deux structures nécessaires à la gestion d’une liste chaînée : une structure pour les noeuds et une autre pour la liste elle même. On suppose que la structure de liste garde une trace du nombre d’éléments afin de ne pas avoir à parcourir la chaîne si celui-ci est nécessaire.

BEGIN SOLUTION
```
struct elem {
    elem *next;
    int   val;
};
struct liste {
    elem *tete;
    int   nbelem;
};
```
END SOLUTION

Écrivez maintenant une fonction permettant de créer une liste vide. Attention de bien initialiser tout ce qui doit l’être.

liste *nouvelle_liste();

BEGIN SOLUTION

liste *nouvelle_liste() {
    liste *l = (liste *)malloc(sizeof(liste));
    l->tete = NULL;
    l->nbelem = 0;
    return l;
}

END SOLUTION

Et enfin, une dernière fonction basique va nous être utile : une fonction permettant d’afficher le contenu d’une liste :
```
void afficher_liste(liste *l);
```
Nous ne disposons pas encore de fonctions pour ajouter des éléments dans une liste, les tests possibles à ce point sont donc limités. Après avoir réalisé la fonction suivante, pensez à revenir tester en profondeur cette fonction d’affichage. En pratique vous allez probablement devoir tester et corriger les deux fonctions en même temps.

BEGIN SOLUTION

Ici et dans la plupart des autres question, différentes boucles sont possibles suivant vos préférences mais faites bien attention de parcourir l’intégralitée des éléments.
```
void afficher_liste(liste *l) {
    elem *e = l->tete;
    while (e != NULL) {
        std::cout << e->val << " ";
        e = e->next;
    }
    std::cout << std::endl;
}
```
END SOLUTION