Les listes chaînées en C 1/3

par **Admin** Ven 5 Nov - 15:58

1 - La liste chaînée simple.
Introduction :

Qu'est-ce qu'une liste chaînée ?
C'est un système informatique qui permet la sauvegarde dynamique de données en mémoire tout comme des variables ou tableaux mais sans se préoccuper de leur nombre et en rendant leur allocation plus transparente.
On dit liste chaînée car les données sont chaînées les unes avec les autres. On accède aux données à l'aide d'un ou deux points d'entrées qui se situent la plus part du temps aux extrémités de la liste.
Dans la pratique ces points d'entrées seront des pointeurs soit sur le premier ou le dernier élément de la liste voir sur les deux ou même mobile.
Les éléments de la liste sont chaînés entre eux à l'aide de pointeurs sur leurs éléments suivants ou précédents voir sur les deux. Ces pointeurs doivent donc faire partie de l'élément. Ce qui nous orientera vers l'utilisation d'une structure du langage C (struct). Cette structure aura donc la particularité d'avoir au moins un pointeur sur des variables du même type qu'elle. Ce pointeur servira à relier les éléments de la liste entre eux. La structure contiendra bien sûr aussi les données que l'on veut mémoriser.
Si vous débutez et que vous avez quelques difficultés avec les pointeurs, je vous propose d'aller voir cet article : Les pointeurs du C et C++.

Une liste concrète :

Quoi de mieux qu'un exemple pour mieux assimiler tout cela :
Notre choix va s'orienter sur une pile (dernier entré, premier sorti). Pourquoi ce choix car c'est une liste chaînée simple. Pour rester simple et ne pas alourdir l'exemple elle mémorisera un seul entier (int), mais le fait d'utiliser une structure nous permettrait d'utiliser une architecture de données plus complexe. Elle aura un seul point d'entrée : un pointeur sur le sommet de la pile (dernier élément de la liste chaînée). Le but est donc que ce pointeur pointe toujours sur le sommet de la pile, donc si un élément est ajouté au sommet de la pile le pointeur devra pointer dessus, mais pour ne pas égarer l'élément précédent le nouvel élément devra pointer sur le précédent...
On peut donc définir notre structure de cette façon :

Code:: typedef struct pile { int valeur; struct pile *prec; } pile ;

Maintenant que notre structure est définie il faut créer la pile, nous avons dit que l'accès à la pile se ferait à l'aide d'un pointeur sur son sommet, et bien créons ce pointeur :

Code:: pile *MaPile = NULL;

Il est très important de l'initialiser à NULL, ceci nous indique en premier lieu que la pile est vide, mais il sera aussi utile pour parcourir la pile, ce que nous verrons plus loin dans cet article.
Pour en faciliter la compréhension, agrémentons cet exemple d'un schéma donnant une représentation visuelle du chaînage de la pile :

La première chose à quoi l'on pense est d'ajouter des éléments sur la pile. Nous allons dédier ceci à une fonction que l'on nommera "Push". Son but est donc de créer un nouvel élément qui sera donc du type de la structure précédemment définie, d'y mémoriser la valeur et le pointeur sur l'élément précédent (celui qui était au sommet de la pile avant l'ajout du nouvel élément). Le pointeur identifiant la pile (MaPile dans l'exemple) doit lui pointer sur l'élément que l'on vient d'ajouter, puisqu'il devient le sommet de la pile.

Code:: void Push(pile **p, int Val) { pile *element = malloc(sizeof(pile)); if(!element) exit(EXIT_FAILURE); /* Si l'allocation a échouée. */ element->valeur = Val; element->prec = *p; *p = element; /* Le pointeur pointe sur le dernier élément. */ }

La fonction reçoit comme paramètres la valeur que l'on veut mémoriser mais aussi un pointeur sur le pointeur identifiant la pile. Pourquoi un pointeur de pointeur ? Ceci afin de passer l'adresse du pointeur à la fonction pour que celle-ci puisse le modifier.
Dans la fonction nous créons en premier lieu le nouvel élément (*element) avec l'instruction malloc. Nous lui affectons sa valeur, mais aussi l'adresse de l'élément précédent qui est en fait le sommet actuel de la pile et enfin nous affectons le pointeur identifiant la pile par pointeur déréférencé avec l'adresse de l'élément que l'on vient de créer afin qu'il devienne le sommet de la pile.
Exemple d'utilisation de la fonction Push :

Code:: Push(&MaPile, 10);

Ajouter des éléments c'est bien ! Mais sans doute vous voudrez aussi en retirer. Nous allons créer pour cela une fonction que l'on nommera "Pop" dont le but n'est que l'opération inverse de la fonction Push.
La fonction doit donc nous retourner la valeur, libérer la mémoire allouée pour l'élément, affecter au pointeur l'adresse de l'élément précédent afin qu'il devienne le sommet de la pile.

Code:: int Pop(pile **p) { int Val; pile *tmp; if(!*p) return -1; /* Retourne -1 si la pile est vide. */ tmp = (*p)->prec; Val = (*p)->valeur; free(*p); *p = tmp; /* Le pointeur pointe sur le dernier élément. */ return Val; /* Retourne la valeur soutirée de la pile. */ }

Exemple d'utilisation de Pop, retirant et affichant un élément de la pile :

Code:: printf("%d\n",Pop(&MaPile));

Nous allons maintenant créer une fonction qui va parcourir la pile, nommée Length elle retournera le nombre d'élément de la pile.

Code:: int Length(pile *p) { int n=0; while(p) { n++; p = p->prec; } return n; }

Le pointeur identifiant la pile ne devant pas être modifié, elle recevra donc seulement le pointeur comme paramètre et non pas son adresse.
La boucle while parcourt la pile en utilisant le membre prec de la structure mémorisant l'adresse de l'élément précédent de la pile et s'arrête dès que le pointeur est égal à NULL c'est à dire au bas de la pile d'où l'intérêts d'initialiser le pointeur de départ à NULL.
Exemple d'utilisation de la fonction Length :

Code:: printf("Nb d'elements : %d\n",Length(MaPile));

Nous allons y ajouter une autre fonction afin de vider la pile et de libérer la mémoire : Clear

Code:: void Clear(pile **p) { pile *tmp; while(*p) { tmp = (*p)->prec; free(*p); *p = tmp; } }

On parcourt la pile comme dans la fonction Length, au retour le pointeur identifiant la pile sera NULL puisque égal au membre prec du premier élément et toute la mémoire libérée.
Exemple d'utilisation de la fonction Clear :

Code:: Clear(&MaPile);

Nous allons ajouter une dernière fonction View qui n'est pas spécialement utile pour une pile mais qui nous servira de test dans l'exemple de fin d'article.

Code:: void View(pile *p) { while(p) { printf("%d\n",p->valeur); p = p->prec; } }

C'est aussi une fonction qui parcourt la pile dans le but de visualiser tous ses éléments. Ses éléments seront affichés en ordre inverse de leur introduction, la pile étant parcouru à l'envers.
Exemple d'utilisation de la fonction View :

Code:: View(MaPile);

Vu de l'exterieur cette pile est donc identifiée par un unique pointeur que l'on passe comme paramètre aux fonctions gérant cette pile, ce qui en rend la manipulation assez simple.

Codes sources de l'exemple :

Pour plus de lisibilité et de possibilité de réutilisation de cette pile, nous séparerons le code de la pile de son utilisation.

Pile.h :

Code:: #ifndef CGI_PILE_H #define CGI_PILE_H /* Structure représantant un élément de la pile. */ typedef struct pile { int valeur; struct pile *prec; } pile ; #ifdef __cplusplus extern "C" { #endif /* Push empile une valeur sur la pile. */ void Push(pile **, int); /* Pop retire la dernière valeur empilée sur la pile. */ int Pop(pile **); /* Clear vide la pile. */ void Clear(pile **); /* Length retourne le nombre d'élément de la pile. */ int Length(pile *p); /* Affiche la totalité de la pile en commençant par le sommet. */ void View(pile *); #ifdef __cplusplus } #endif #endif

Pile.c :

Code:: #include #include #include "Pile.h" /*************************************************************************/ void Push(pile **p, int Val) { pile *element = malloc(sizeof(pile)); if(!element) exit(EXIT_FAILURE); /* Si l'allocation a échouée. */ element->valeur = Val; element->prec = *p; *p = element; /* Le pointeur pointe sur le dernier élément. */ } /*************************************************************************/ int Pop(pile **p) { int Val; pile *tmp; if(!*p) return -1; /* Retourne -1 si la pile est vide. */ tmp = (*p)->prec; Val = (*p)->valeur; free(*p); *p = tmp; /* Le pointeur pointe sur le dernier élément. */ return Val; /* Retourne la valeur soutirée de la pile. */ } /*************************************************************************/ void Clear(pile **p) { pile *tmp; while(*p) { tmp = (*p)->prec; free(*p); *p = tmp; } } /*************************************************************************/ int Length(pile *p) { int n=0; while(p) { n++; p = p->prec; } return n; } /*************************************************************************/ void View(pile *p) { while(p) { printf("%d\n",p->valeur); p = p->prec; } }

Voici un exemple d'utilisation de la pile que nous venons de construire.

main.c :

Code:: #include /* Pour la fonction system. */ #include #include "Pile.h" int main() { pile *MaPile = NULL; /* Impératif de l'initialiser à NULL */ Push(&MaPile, 10); Push(&MaPile, 25); Push(&MaPile, 33); Push(&MaPile, 12); /* Empile 4 valeurs. */ puts("Affichage de la pile :"); View(MaPile); /* Affiche la totalité de la pile. */ puts("------"); printf("Nb d'elements : %d\n",Length(MaPile)); puts("------"); puts("Deux valeurs soutirees de la pile :"); printf("%d\n",Pop(&MaPile)); /* Affiche deux valeurs */ printf("%d\n",Pop(&MaPile)); /* soutirées de la pile. */ puts("------"); puts("Affichage de la pile :"); View(MaPile); /* Affiche la totalité de la pile. */ puts("------"); Clear(&MaPile); /* Vide la pile. */ Push(&MaPile, 18); /* Empile une valeur. */ puts("Affichage de la pile apres vidage et ajout d'une valeur :"); View(MaPile); /* Affiche la totalité de la pile. */ puts("------\n"); Clear(&MaPile); /* Vider la pile avant de quitter. */ #ifdef __WIN32__ system("PAUSE"); /* Pour la console Windows. */ #endif return 0; }

Afin de continuer sur le thème des listes chaînées, je vous propose un autre document : une liste triée où les éléments sont insérés dans la liste de façon à être triés dés leur insertion.