Structure liste

Cours/Système et réseau/C pour le système/Exercices/Structure liste

Une structure de liste en python est une version améliorée d'un tableau. On vous demande d'implémenter cette structure en C dans deux fichiers liste.c et liste.h dont vous testerez les fonctions dans un fichier main.c.

En C on utilisera les structures pour gérer des type composés comme les listes qui nécessitent à la fois un tableau, sa taille et le nombre actuel d'éléments présents.

Implémentation

Vous utiliserez la compilation séparée vue dans la partie sur la gestion du code source :

Créez le type liste associé à la structure struct liste dans un fichier liste.h :

typedef struct liste {
        int *t;
        size_t taille;
        size_t nombre;
} liste;

Cette structure permet de stocker une structure de liste contenant des entiers (via le pointeur t). La création d'une structure par une fonction doit nécessairement rendre un pointeur car il faut créer l'élément dans le tas.

Dans un fichier liste.c, créez les fonctions :

de création d'une liste vide (par défaut la taille sera de 1 et ne contiendra aucun élément) : liste liste_creation()
d'ajout d'un élément à la fin de la liste : void liste_ajoute(liste*, int)
d'évaluation d'un élément de la liste : int liste_valeur(liste*, size_t)
de remplacement d'un élément : void liste_remplace(liste*, size_t, int)
de suppression de l'élément en fin de liste : void liste_supprime_dernier(liste*)

Vous pourrez utiliser la fonction realloc pour le dimensionnement du tableau lorsqu'il faut ajouter un élément à une liste pleine ou que l'on supprime un élément d'une liste dont le nombre d'éléments restant est deux fois plus petit que sa taille.

Quelques questions pour voir si vous avez compris (faites des tests et comprenez avant de regarder la réponse) :

Pourquoi une fonction avec la signature suivante ne fonctionnerait pas ?

void liste_ajoute(liste, int)

corrigé

Le paramètre est copié dans la pile. Comme liste ajoute doit modifier l'attribut nombre de liste, il ne modifierait que la copie et pas l'original.

Il est important de passer des pointeurs sur la liste lorsqu'on la modifie, sinon le contenu est copié et placé dans la pile et on ne modifie que la copie et pas la liste originelle.

Cependant :

Pourquoi une fonction avec la signature suivante fonctionnerait parfaitement ?

void liste_remplace(liste, size_t, int)

corrigé

Cette fonction remplace une valeur à un endroit pointé par la structure. Ce qui est dupliqué c'est l'adresse, mais c'est la même adresse : on ne modifie pas la structure on modifie un endroit pointé par elle.

Testons nos fonctions :

Dans le programme principal main.c :

ajoutez les 100 entiers positifs
affichez le contenu de la liste
affichez la taille et le nombre d'élément de la liste
supprimez un à un tous les éléments de la liste
affichez la taille et le nombre d'élément de la liste

Amélioration

On remarque que presque toutes les fonctions manipulant les listes la modifie. Seule la création rend un objet de type liste. L'usage veut que l'on ne manipule les structures en C que via des pointeurs. On utilise alors plutôt ce type de structure :

typedef struct _liste {
        int *t;
        size_t taille;
        size_t nombre;
} _liste;
typedef _liste* liste;

Ce qui fait que l'on a à notre disposition deux types :

_liste qui est la composition de la structure, utile pour le malloc de la création,
liste qui est un pointeur sur la structure. C'est elle qui est utilisée par l'utilisateur.

Reprenez le code des fichiers pour rendre compte de cette nouvelle structure.

L'utilisation de la structure est maintenant transparente pour l'utilisateur. Il nous rete qu'une chose à faire : supprimer la liste.

Ajoutez la fonction void supprimer_liste(liste) qui supprime la liste aux possibilités de liste.

Cerise sur le gateau : liste générique

Pour l'instant notre liste est constituée uniquement d'entier.

Comment procéderiez vous pour créer une liste pouvant contenir tout ce qu'on veut ?

solution

On utilise une double indirection et on crée des tableaux de type void** t qui permettent de stocker des pointeurs sur des objets.

Il faudra cependant faire un cast pour chaque élément pour qu'il soit du bon type, ce qui est loin d'être pratique.