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

[Admin]

2 - Une liste chaînée triée.
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.
Un exemple concret :

Le code est identique au code de la Pile 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).

Code:

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 :

Code:

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.

Code:

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 :

Code:

Insert(&Mysl,9);

Le code des autres fonctions étant strictement identique au code de la Pile, il ne sera donc pas commenté.
Codes sources de l'exemple :

Sortlist.h :

Code:

#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 :

Code:

#include
#include

#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 :

Code:

#include
#include

#include "SortList.h"

int main()
{
        slist *Mysl = NULL;

        Insert(&Mysl,12);
        Insert(&Mysl,[img]http://2img.net/i/fa/i/smiles/icon_cool.gif[/img];
        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;
}