I. Les listes chainées simple▲
I-A. 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++.
I-B. 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 :
2.
3.
4.
5.
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 : 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.
2.
3.
4.
5.
6.
7.
8.
9.
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 : 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.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
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 :
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.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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êt d'initialiser le pointeur de départ à NULL.
Exemple d'utilisation de la fonction Length :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
2.
3.
4.
5.
6.
7.
8.
9.
10.
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 :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.
2.
3.
4.
5.
6.
7.
8.
void View(pile *p)
{
while(p)
{
printf(« %d»,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 : 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.
I-C. Code 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
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
#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
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
#include <stdlib.h>
#include <stdio.h>
#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 :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
#include <stdlib.h> /* Pour la fonction system. */
#include <stdio.h>
#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;
}
II. Les listes chaînées triées▲
Nous allons voir une autre liste simple, ceci afin d'aborder un autre aspect des listes chaînées : une liste où les éléments sont triés à leur insertion. Cette liste montre un autre avantage des listes chaînées : seulement deux pointeurs sont affectés pour insérer l'élément, dans un tableau il aurait fallu déplacer plusieurs éléments.
II-A. Une exemple concret▲
Le code est identique au code de la Pile à l'exception de la fonction Push qui sera remplacée par une fonction nommée Insert, dont la fonction sera d'insérer l'élément dans la liste de façon à ce qu'il soit trié dès son insertion. Le tri se fait bien sûr en fonction du contenu de la liste, dans notre exemple ce sera l'attribut valeur de la structure.
Le pointeur sur l'élément précédent sera remplacé par un pointeur sur l'élément suivant, mais ceci revient strictement au même (il y a juste le nom qui change et la représentation visuelle que l'on peut s'en faire).
2.
3.
4.
5.
typedef struct slist
{
int valeur;
struct slist *suiv;
} slist ;
Comme pour la pile le point d'entrée sera un pointeur sur l'élément de début de liste impérativement initialisé à NULL : slist *Mysl = NULL;
Pour faciliter la compréhension de cet exemple, agrémentons-le d'un schéma donnant une représentation visuelle de la liste :
Voyons de suite la fonction Insert qui doit faire une insertion ordonnée des éléments. On lui passera donc comme paramètre la valeur à sauvegarder et l'adresse du pointeur identifiant la liste.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
void Insert(slist **sl, int Val)
{
slist *tmp = NULL;
slist *csl = *sl;
slist *elem = malloc(sizeof(slist));
if(!elem)
exit(EXIT_FAILURE);
elem->valeur = Val;
while(csl && csl->valeur < Val)
{
tmp = csl;
csl = csl->suiv;
}
elem->suiv = csl;
if(tmp) tmp->suiv = elem;
else *sl = elem;
}
La fonction Insert crée un nouvel élément, puis parcourt la liste à l'aide de la boucle while jusqu'à ce qu'elle trouve un élément ayant une valeur inférieure à la valeur de l'élément que l'on est en train d'insérer. A la sortie de la boucle tmp pointent sur l'élément qui va le précéder et csl sur celui qui va le suivre. Il n'y a donc plus qu'à affecter correctement les pointeurs. Si la boucle n'est pas exécutée tmp est donc NULL ce qui signifie que le nouvel élément doit être positionné en début de liste, en conséquence le pointeur identifiant la liste devra être modifié pour pointer sur ce nouvel élément.
Voici un exemple d'utilisation de la fonction Insert : Insert(&Mysl,9);
Le code des autres fonctions étant strictement identique au code de la Pile, il ne sera donc pas commenté.
II-B. Code source de l'exemple▲
Sortlist.h :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
#ifndef CGI_SORTLIST_H
#define CGI_SORTLIST_H
/* Structure représantant un élément de la liste. */
typedef struct slist
{
int valeur;
struct slist *suiv;
} slist ;
#ifdef __cplusplus
extern "C"
{
#endif
/* Insert insert une valeur dans la liste. */
void Insert(slist **, int);
/* Pop retire la dernière valeur de la liste. */
int Pop(slist **);
/* Clear vide la liste. */
void Clear(slist **);
/* Lenght retourne le nombre d'élément de la liste. */
int Length(slist *p);
/* Affiche la totalité de la liste en commençant par le sommet. */
void View(slist *);
#ifdef __cplusplus
}
#endif
#endif
Sortlist.c :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
#include<stdlib.h>
#include<stdio.h>
#include "SortList.h"
/********************************************************************/
void Insert(slist **sl, int Val)
{
slist *tmp = NULL;
slist *csl = *sl;
slist *elem = malloc(sizeof(slist));
if(!elem)
exit(EXIT_FAILURE);
elem->valeur = Val;
while(csl && csl->valeur < Val)
{
tmp = csl;
csl = csl->suiv;
}
elem->suiv = csl;
if(tmp) tmp->suiv = elem;
else *sl = elem;
}
/*********************************************************************/
int Pop(slist **sl)
{
int Val;
slist *tmp;
if(!*sl)
return -1;
tmp = (*sl)->suiv;
Val = (*sl)->valeur;
free(*sl);
*sl = tmp;
return Val;
}
/*********************************************************************/
void Clear(slist **sl)
{
slist *tmp;
while(*sl)
{
tmp = (*sl)->suiv;
free(*sl);
*sl = tmp;
}
}
/*******************************************************************/
int Length(slist *sl)
{
int n=0;
while(sl)
{
n++;
sl = sl->suiv;
}
return n;
}
/*********************************************************************/
void View(slist *sl)
{
while(sl)
{
printf("%d\n",sl->valeur);
sl = sl->suiv;
}
}
Voici un exemple d'utilisation de la liste que nous venons de construire.
main.c :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
#include <stdlib.h>
#include <stdio.h>
#include "SortList.h"
int main()
{
slist *Mysl = NULL;
Insert(&Mysl,12);
Insert(&Mysl,8);
Insert(&Mysl,3);
Insert(&Mysl,5);
Insert(&Mysl,9);
Insert(&Mysl,5);
Insert(&Mysl,2);
Insert(&Mysl,7);
printf("Nb d'elements : %d\n",Length(Mysl));
View(Mysl);
puts("Retrait de deux elements :");
printf("%d\n",Pop(&Mysl));
printf("%d\n",Pop(&Mysl));
printf("Nb d'elements : %d\n",Length(Mysl));
View(Mysl);
puts("Vidage de la liste puis ajout de 3 elements :");
Clear(&Mysl);
Insert(&Mysl,3);
Insert(&Mysl,9);
Insert(&Mysl,5);
printf("Nb d'elements : %d\n",Length(Mysl));
View(Mysl);
Clear(&Mysl);
#ifdef _WIN32
system("PAUSE"); /* Pour la console Windows. */
#endif
return 0;
}