Les listes chaînées en C

2 - Une liste chaînée triée

CGI

- Titre : Les listes chaînées en C

- Auteur : CGI

- Parution : 5 avril 2005

- Licence : Copyright 2002-2020 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.

Sommaire

- I. Introduction

- II. Un exemple concret

- III. Codes source de l'exemple

I - 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 - 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 tout 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. À 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é.

III - Codes source de l'exemple

Sortlist.h :

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

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