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 définissez 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

Définissez maintenant une fonction permettant de construire une liste vide. Veillez à 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

Définissez enfin une dernière fonction basique pour afficher le contenu d’une liste :
```
void afficher_liste(liste *l);
```
Afin de faire un premier test élémentaire de vos fonctions, écrivez un main qui utilise les deux fonctions pour créer une liste vide et afficher cette liste vide (si tout se passe bien, le programme n’affiche rien et s’exécute sans erreur).

Nous ne disposons pas encore de fonctions pour ajouter des éléments dans une liste. Les tests possibles à ce stade sont donc limités. Après avoir défini la fonction d’ajout dans la suite du TP, pensez à revenir tester en profondeur la 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 questions, différentes boucles sont possibles, suivant vos préférences. Dans tous les cas, il faut veiller à parcourir l’intégralité 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