Apprendre à programmer les listes chaînées en C

Une liste chaînée 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.

Dans ce tutoriel, vous allez apprendre à programmer les listes chaînées en C.

Pour réagir au contenu de cet article, un espace de dialogue vous est proposé sur le forum .
1 commentaire Donner une note à l'article (3.5)

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Liste chaînée 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ée qui se situent la plupart du temps aux extrémités de la liste.

Dans la pratique ces points d'entrée seront des pointeurs soit sur le premier ou le dernier élément de la liste, voire sur les deux ou même mobile.

Les éléments de la liste sont chaînés entre eux à l'aide de pointeurs sur leur élément suivant ou précédent, voire 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 assimiler tout cela.

Notre choix va s'orienter sur une pile (dernier entré, premier sorti). Pourquoi ce choix ? 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 :

 
Sélectionnez
1.
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 :

 
Sélectionnez
1.
        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 :

Image non disponible

La première chose à laquelle 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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
void Push(pile **p, int Val)
{
        pile *element = malloc(sizeof(pile));
        if(!element) exit(EXIT_FAILURE);     /* Si l'allocation a échoué. */
        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 :

 
Sélectionnez
1.
     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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
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 :

 
Sélectionnez
1.
      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éments de la pile.

 
Sélectionnez
1.
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êts d'initialiser le pointeur de départ à NULL.
Exemple d'utilisation de la fonction Length :

 
Sélectionnez
1.
      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

 
Sélectionnez
1.
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 :

 
Sélectionnez
1.
       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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
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 parcourue à l'envers.
Exemple d'utilisation de la fonction View :

 
Sélectionnez
1.
        View(MaPile);

Vue de l'extérieur, 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. 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 :

 
Sélectionnez
1.
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_PILE_H
#define CGI_PILE_H

 /*  Structure représentant 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éments 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 :

 
Sélectionnez
1.
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.
#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é. */
        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 :

 
Sélectionnez
1.
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;
}

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

II. Liste chaînée triée

II-A. Introduction

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-B. Un exemple concret

Le code est identique au code de laPileListe chaînée simple de l'article précédent à 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).

 
Sélectionnez
1.
2.
3.
4.
5.
 typedef struct slist
        {
                int valeur;
                struct slist *suiv;
        } slist ;

Comme pour la pileListe chaînée simple le point d'entrée sera un pointeur sur l'élément de début de liste impérativement initialisé à NULL :

 
Sélectionnez
1.
        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 :

Image non disponible

Voyons ensuite 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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
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. À la sortie de la boucle, tmp pointe 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 :

 
Sélectionnez
1.
     Insert(&Mysl,9);

Le code des autres fonctions étant strictement identique au code de laPileListe chaînée simple, il ne sera donc pas commenté.

II-C. Codes sources de l'exemple

Sortlist.h :

 
Sélectionnez
1.
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ésentant 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éments 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 :

 
Sélectionnez
1.
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.
#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 :

 
Sélectionnez
1.
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;
}

III. Liste doublement chaînée

III-A. Introduction

Une liste doublement chaînée est une liste dont chaque élément peut accéder à l'aide de pointeurs aux éléments positionnés immédiatement avant et après lui dans la liste. Le chaînage se fait donc dans les deux sens, ce qui permet de parcourir la liste en avant comme en arrière, ce qui n'était pas possible avec la liste simple.

De plus s'il est aisé d'ajouter des éléments à chaque extrémité d'une liste simple, cela l'est beaucoup moins quand il s'agit de retirer l'élément en fin de liste (dans le sens du chaînage). La liste doublement chaînée nous en facilitera la tâche.

Comme pour la liste simple, les éléments de la liste sont chaînés entre eux à l'aide de pointeurs sur des éléments du même type qu'eux. Dans le cas de la liste chaînée double, chaque élément aura un pointeur sur l'élément précédent et un pointeur sur l'élément suivant.

III-B. Un exemple concret

Nous allons nous aider d'un exemple simple. Comme dans la liste simple, nous mémoriserons seulement un entier dans chaque élément.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
typedef struct elem
        {
                int value;
                struct elem *prev;
                struct elem *next;
        } elem ;

Notre liste aura deux points d'entrée un en tête de liste l'autre en fin de liste. Pour éviter de traîner deux pointeurs, nous les mettrons dans une structure. Ceci aura pour avantage de n'avoir qu'une seule variable à traiter par liste.

 
Sélectionnez
1.
2.
3.
4.
5.
  typedef struct
        {
          elem *first;
          elem *last;
        }dblist;

Nous allons construire cette liste afin qu'on puisse y insérer des éléments en début ou en fin de liste et qu'on puisse les en retirer aussi bien par le début que par la fin de liste. Aidons-nous d'un schéma :

Image non disponible

Ici aussi il faudra initialiser les pointeurs d'entrée à NULL, comme ils sont deux et pour simplifier l'utilisation de la liste, nous allons nous aider d'une fonction que l'on nommera Init.

 
Sélectionnez
1.
2.
3.
4.
5.
void Init(dblist *l)
{
   l->first = NULL;
   l->last = NULL;
}

L'appel de la fonction Init est donc obligatoire avant toute utilisation de la liste. Elle ne doit pas être appelée sur une liste déjà initialisée et surtout pas si la liste n'est pas vide, sinon nos pointeurs de début et de fin de liste seraient perdus à jamais.

Pour l'insertion d'éléments, nous utiliserons deux fonctions PushBack et PushFront, la première ajoutera l'élément en fin de liste et la deuxième en début de liste. Elles recevront donc comme paramètres la valeur à mémoriser, mais aussi l'adresse d'une variable de type dblist préalablement défini.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
void PushBack(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(EXIT_FAILURE);
   nouv->value = val;
   nouv->prev = l->last;
   nouv->next = NULL;
   if(l->last) l->last->next = nouv;
   else l->first = nouv;
   l->last = nouv;        
}
/******************************************************************************/

void PushFront(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(EXIT_FAILURE);
   nouv->value = val;
   nouv->next = l->first;
   nouv->prev = NULL;      
   if(l->first) l->first->prev = nouv;
   else l->last = nouv;
   l->first = nouv;
}

Le principe est fort semblable à la liste simpleListe chaînée simple, donc sans commentaire. Attention toutefois dans le cas de l'insertion du premier élément de la liste les deux pointeurs de la structure dblist devront pointer sur cet élément.

Voici un exemple d'utilisation des fonctions PushBack et PushFront :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
dblist MaListe;

        /*La liste doit obligatoirement être initialisée avant utilisation*/
        Init(&MaListe);

        PushFront(&MaListe,10);
        PushBack(&MaListe,20);

Le retrait des valeurs se fera à l'aide des fonctions PopBack et PopFront. La première retirera l'élément de fin de liste et la deuxième celui de début de liste. Elles recevront évidemment comme paramètre l'adresse de la variable identifiant la liste et retourneront la valeur de l'élément retiré.

 
Sélectionnez
1.
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.
int PopBack(dblist *l)
{
   int val;
   elem *tmp = l->last;
   if(!tmp) return -1;
   val = tmp->value;
   l->last = tmp->prev;
   if(l->last) l->last->next = NULL;
   else l->first = NULL;
   free(tmp);
   return val;
}
/******************************************************************************/

int PopFront(dblist *l)
{
   int val;
   elem *tmp = l->first;
   if(!tmp) return -1;
   val = tmp->value;
   l->first = tmp->next;
   if(l->first)l->first->prev = NULL;
   else l->last = NULL;
   free(tmp);
   return val;
}

Ici aussi le principe est semblable à la liste simple, donc aussi sans commentaire. Attention toutefois dans cas du retrait du dernier élément de la liste les deux pointeurs de la structure dblist devront pointer sur NULL.

III-C. Codes sources de l'exemple :

dblist.h :

 
Sélectionnez
1.
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.
#ifndef CGI_DBLIST_H
#define CGI_DBLIST_H

 /*  Structure représentant un élément de la liste. */

        typedef struct elem
        {
                int value;
                struct elem *prev;
                struct elem *next;
        } elem ;

 /*  Structure d'accès à la liste. */

        typedef struct
        {
          elem *first;
          elem *last;
        }dblist;

#ifdef __cplusplus
extern "C" {
#endif

 /*  Initialisation de la liste. */

        void Init(dblist *l);

 /*  Ajout d'une valeur en fin de liste. */

        void PushBack(dblist *l, int val);

 /*  Ajout d'une valeur en début de liste. */

        void PushFront(dblist *l, int val);

 /*  Retrait d'une valeur en fin de liste. */

        int PopBack(dblist *l);

 /*  Retrait d'une valeur en début de liste. */

        int PopFront(dblist *l);

 /*  Affichage de toute la liste. */

        void View(dblist l);

 /*  Vidage de toute la liste. */

        void Clear(dblist *l);

#ifdef __cplusplus
}
#endif

#endif

dblist.c :

 
Sélectionnez
1.
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.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
#include <stdio.h>
#include<stdlib.h>

#include "dblist.h"

void Init(dblist *l)
{
   l->first = NULL;
   l->last = NULL;
}
/******************************************************************************/

void PushBack(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(EXIT_FAILURE);
   nouv->value = val;
   nouv->prev = l->last;
   nouv->next = NULL;
   if(l->last) l->last->next = nouv;
   else l->first = nouv;
   l->last = nouv;        
}
/******************************************************************************/

void PushFront(dblist *l, int val)
{
   elem *nouv = malloc(sizeof(elem));
   if(!nouv) exit(EXIT_FAILURE);
   nouv->value = val;
   nouv->next = l->first;
   nouv->prev = NULL;      
   if(l->first) l->first->prev = nouv;
   else l->last = nouv;
   l->first = nouv;
}
/******************************************************************************/

int PopBack(dblist *l)
{
   int val;
   elem *tmp = l->last;
   if(!tmp) return -1;
   val = tmp->value;
   l->last = tmp->prev;
   if(l->last) l->last->next = NULL;
   else l->first = NULL;
   free(tmp);
   return val;
}
/******************************************************************************/

int PopFront(dblist *l)
{
   int val;
   elem *tmp = l->first;
   if(!tmp) return -1;
   val = tmp->value;
   l->first = tmp->next;
   if(l->first)l->first->prev = NULL;
   else l->last = NULL;
   free(tmp);
   return val;
}
/******************************************************************************/

void View(dblist l)
{
   elem *pelem = l.first;
   while(pelem)
   {
     printf("%d\n",pelem->value);
     pelem = pelem->next;
   }
}
/******************************************************************************/

void Clear(dblist *l)
{
   elem *tmp;
   elem *pelem = l->first;
   while(pelem)
   {
     tmp = pelem;
     pelem = pelem->next;
     free(tmp);
   }
   l->first = NULL;
   l->last = NULL;
}


Voici un exemple d'utilisation de la liste doublement chaînée que nous venons de construire :

main.c :

 
Sélectionnez
1.
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.
#include <stdlib.h>
#include <stdio.h>

#include "dblist.h"

int main()
{
        dblist MaListe;

        Init(&MaListe);

        PushFront(&MaListe,10);
        PushBack(&MaListe,20);
        PushBack(&MaListe,40);
        PushFront(&MaListe,50);

        View(MaListe);
        puts("--------------");

        printf("%d\n",PopFront(&MaListe));
        printf("%d\n",PopFront(&MaListe));
        printf("%d\n",PopBack(&MaListe));
        puts("--------------");

        PushBack(&MaListe,30);
        
        printf("%d\n",PopFront(&MaListe));
        printf("%d\n",PopFront(&MaListe));
        puts("--------------");

        Clear(&MaListe);

#ifdef _WIN32
        system("PAUSE");  /* Pour la console Windows. */
#endif
        return 0;
}


Voici le même exemple, mais avec une création dynamique de la variable d'entrée.

main.c :

 
Sélectionnez
1.
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.
#include <stdlib.h>
#include <stdio.h>

#include "dblist.h"

int main()
{
        dblist *pdbListe = malloc(sizeof(dblist));

        Init(pdbListe);

        PushFront(pdbListe,10);
        PushBack(pdbListe,20);
        PushBack(pdbListe,40);
        PushFront(pdbListe,50);

        View(*pdbListe);
        puts("--------------");

        printf("%d\n",PopFront(pdbListe));
        printf("%d\n",PopFront(pdbListe));
        printf("%d\n",PopBack(pdbListe));
        puts("--------------");

        PushBack(pdbListe,30);
        
        printf("%d\n",PopFront(pdbListe));
        printf("%d\n",PopFront(pdbListe));
        puts("--------------");

        Clear(pdbListe);

        free(pdbListe);

#ifdef _WIN32
        system("PAUSE");  /* Pour la console Windows. */
#endif
        return 0;
}

IV. Conclusion et remerciements

Nous tenons à remercier gege2061 et Anomaly pour leur relecture technique, Claude Leloup pour la relecture orthographique et Malick SECK pour la mise au gabarit.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2016 CGi. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.