Enoncé exercice 1
Ecrire un programme C qui permet de créer et de lire une liste chaînée d’entiers et affiche ensuite ses éléments.
La structure utilisée pour les cellule de la liste doit être constituée d’:
- un entier;
- un pointeur sur la structure de la liste.
Illustration:
Correction exercice 1
Dans cet exercice on va essayer de se familiariser avec la notion des listes chaînées. Une liste chaînée est composée d’un ensemble d’éléments qu’on appelle ici des cellules. La première chose à faire lorsqu’on traite un exercice sur les listes chaînées, est de définir le type de cette cellule. Bien évidement ce type ne sera pas un des types prédéfinis du langage C, mais on aura à le créer selon le besoin de l’exercice en utilisant les structures.
On veut donc, pour cet exercice, construire une liste chaînée qui contient des entiers, un seul par cellule. Et qui doit en plus avoir un pointeur dans chaque une de ces cellules pour créer la liaison entre elles afin de pouvoir se déplacer tout au long de la liste chaînée. Et comme ce pointeur doit contenir l’adresse d’une cellule, et si on appelle la structure utilisée cellule, le type de ce pointeur sera alors struct cellule *.
Après la définition du type de la cellule (lignes 3-6), on demande à l’utilisateur d’entrer le nombre d’éléments avec lesquels il souhaite travailler, et qui sera lu dans la variable n.
Pour une liste chaînée, il faut toujours garder dans l’esprit qu’un pointeur vers la première cellule de la liste doit être gardé quelque part, en général dans un pointeur de type struct cellule * qu’on appelle ici tete.
Pour pouvoir abriter les n élément qui seront entrés, on aura besoin de créer une liste chaînée composée de n cellules. Et ceci bien sûr sera fait manuellement. Donc pour ainsi faire, on va utiliser une boucle for à n itérations (lignes 14-21).
La création d’une cellule sera réalisée d’une façon dynamique, comme ça on pourra créer autant de cellules que l’utilisateur en aura besoin. On va se servir donc de la fonction malloc qui va prendre comme paramètre 1*sizeof(struct cellule) ou tout simplement sizeof(struct cellule) puisqu’on veut créer un seul élément de type struct cellule. Et on converti la valeur renvoyée par malloc vers le type du pointeur p par le biais de (struct cellule *) (ligne 16).
La cellule créée est maintenant pointée par p. Pour lire son composant entier on peut y accéder en utilisant (*p).a (ligne 17).
Pour assurer la liaison entre les différentes cellules, on doit toujours avoir sous la main l’avant dernière cellule créée. Concrètement un pointeur q sur elle sera conservé. Cette cellule doit contenir un pointeur sur la dernière cellule créée p. Pour réaliser cette liaison, on doit mettre l’adresse p dans la partie suiv (réservée au pointeur dans la structure cellule) de la cellule pointée par q (ligne 19). Elle faudra garder à jour le pointeur q en lui affectant l’adresse de la cellule dernièrement créée, en guise de préparation pour le nouvelle itération (ligne 20).
La première cellule créée, vu sa position dans la tête de la liste, bénéficiera d’un traitement différent. On doit seulement garder son adresse dans le pointeur tete (ligne 18).
Après la sortie de la boucle for, on doit mettre le pointeur suiv de la dernière cellule à NULL pour signaler ainsi la fin de la liste (ligne 22).
Pour afficher le contenu de la liste il faudra la parcourir. Généralement ceci est fait à l’aide d’une boucle while. Et on commence par son premier élément qui est pointé par tete et avec lequel on va initialiser le pointeur q qui va servir à parcourir la liste (ligne 24).
Après qu’on a entré dans la boucle, on va afficher à chaque fois le contenu de la cellule pointée par q. Puisque q pointe vers une cellule, donc cette cellule est la variable *q qui est de type struct cellule. On peut accéder donc à son élément entier par (*q).a (ligne 27).
Pour passer dans l’itération qui suit vers la cellule contiguë, on affecte à q le pointeur vers cette cellule et qui est (*q).suiv (ligne 28). Ce processus va se répéter jusqu’à ce qu’on arrive à la dernière cellule qui est marquée par le pointeur NULL dans sa partie suiv.
Solution exercice 1
#include<stdio.h>
#include<stdlib.h>
struct cellule{
int a;
struct cellule * suiv;
};
int main()
{
struct cellule *p,*q,*tete=NULL;
int i,n;
printf("Donnez le nombre d'elements de la liste:\n");
scanf("%d",&n);
printf("Donnez les elements de la liste:\n");
for(i=0;i<n;i++)
{
p=(struct cellule *)malloc(sizeof(struct cellule));
scanf("%d",&((*p).a));
if(i==0) tete=p;
else (*q).suiv=p;
q=p;
}
(*q).suiv=NULL;
printf("Les elements de la liste:\n");
q=tete;
while(q!=NULL)
{
printf("%d ",(*q).a);
q=(*q).suiv;
}
printf("\n");
system("pause");
return 0;
}