Developpez.com - C
X

Choisissez d'abord la catégorieensuite la rubrique :



Les listes chaînées en C.

Par CGi

Le 5 avril 2005


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).

        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.

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é.

Codes sources de l'exemple :

Sortlist.h :

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

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

#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;
}





Bonne lecture,
CGi.

Avec la contribution d'Anomaly pour la relecture.





LISTES CHAÎNÉES
  Liste simple.   Liste triée.   Liste double.


C/C++
  Les pointeurs du C/C++.   Les listes chaînées.             Liste simple.             Liste triée.             Liste double.   Les arbres.   Les tas.   Le C orienté objets ?

  1 - La fenêtre principale.   2 - Contrôles et messages.   3 - Les commandes.   4 - Dialogue std.   5 - Contexte de périph.   6 - Dessiner.   7 - Les ressources.   8 - Dialogue perso.   9 - Dialogue comm.   10 - Les accélérateurs.

Assembleur
  Assembleur sous Visual C++.

C++ BUILDER
  Trucs et astuces.   Composant.   TRichEdit.   TDrawGrid.   Application MDI.   TThread.   wxWidgets.   Style Win XP.

  Première application.   Construire un menu.   Dessiner.   Sisers, Timers...   Dialogues standards.   Dialogues perso.

DotNet
  Composant C# Builder.   Contrôle WinForm.   Application MDI.

Java
  Applet java.





Copyright 2002-2016 CGi - Tous droits réservés CGi. Toutes reproduction, utilisation ou diffusion de ce document par quelque moyen que ce soit autre que pour un usage personnel doit faire l'objet d'une autorisation écrite de la part de l'auteur, propriétaire des droits intellectuels.
Les codes sources de ce document sont fournis en l'état. L'utilisateur les utilise à ses risques et périls, sans garantie d'aucune sorte de la part de l'auteur. L'auteur n'est responsable d'aucun dommage subi par l'utilisateur pouvant résulter de l'utilisation ou de la distribution des codes sources de ce document.
De la même façon, l'auteur n'est en aucun cas responsable d'une quelconque perte de revenus ou de profits, ou de données, ou de tous dommages directs ou indirects, susceptibles de survenir du fait de l'utilisation des codes sources de ce document, quand bien même l'auteur aurait été averti de la possibilité de tels dommages. L'utilisation des codes sources de ce document vaut acceptation par l'utilisateur des termes de la licence ci-dessus.

Contacter le responsable de la rubrique C