Ecole Sup rieure de Technologie et dInformatique
Ann e universitaire : 2011-2012
Module : Programmation 2
TD N 3
Les listes cha n es
Mme BELKADHI CHELBI H.
1. G n ralit s sur les listes cha n es
Lorsque vous cr ez un algorithme utilisant des conteneurs, il existe diff rentes mani res de les
impl menter, la fa on la plus courante tant les tableaux, que vous connaissez tous. Lorsque vous
cr ez un tableau, les l ments de celui-ci sont plac s de fa on contigu en m moire. Pour pouvoir
le cr er, il vous faut conna tre sa taille. Si vous voulez supprimer un l ment au milieu du tableau,
il vous faut recopier les l ments temporairement, r -allouer de la m moire pour le tableau, puis
le remplir partir de l' l ment supprim . En bref, ce sont beaucoup de manipulations co teuses
en ressources.
Une liste cha n e est diff rente dans le sens o les l ments de votre liste sont r partis dans la
m moire et reli s entre eux par des pointeurs. Vous pouvez ajouter et enlever des l ments d'une
liste cha n e n'importe quel endroit, n'importe quel instant, sans devoir recr er la liste enti re.
Nous allons essayer de voir ceci plus en d tail sur ces sch mas :
la variable contiendra
Vous avez sur ce sch ma la repr sentation que l'on pourrait faire d'un tableau et d'une liste
cha n e. Chacune de ces repr sentations poss de ses avantages et inconv nients. C'est lors de
l' criture de votre programme que vous devez vous poser la question de savoir laquelle des deux
m thodes est la plus int ressante.
(cid:1) Dans un tableau, la taille est connue, l'adresse du premier l ment aussi. Lorsque vous d clarez
un tableau,
l'adresse du premier l ment de votre tableau.
Comme le stockage est contigu, et la taille de chacun des l ments connue, il est possible
d'atteindre directement la case i d'un tableau.
(cid:1) Pour d clarer un tableau, il faut conna tre sa taille.
(cid:1) Pour supprimer ou ajouter un l ment un tableau, il faut cr er un nouveau tableau et
supprimer l'ancien. Ce n'est en g n ral pas visible par l'utilisateur, mais c'est ce que realloc va
souvent faire. L'adresse du premier l ment d'un tableau peut changer apr s un realloc, ce qui
est tout fait logique puisque realloc n'aura pas forcement la possibilit de trouver en
m moire la place n cessaire et contigu pour allouer votre nouveau tableau. realloc va donc
chercher une place suffisante, recopier votre tableau, et supprimer l'ancien.
(cid:2) Dans une liste cha n e, la taille est inconnue au d part, la liste peut avoir autant d' l ments que
votre m moire le permet.
(cid:2) Il est en revanche impossible d'acc der directement l' l ment i de la liste chain e.
Pour ce faire, il vous faudra traverser les i-1 l ments pr c dents de la liste.
(cid:2) Pour d clarer une liste cha n e, il suffit de cr er le pointeur qui va pointer sur le premier
l ment de votre liste cha n e, aucune taille n'est donc sp cifier.
(cid:2) Il est possible d'ajouter, de supprimer, d'intervertir des l ments d'une liste cha n e sans avoir
recr er la liste en entier, mais en manipulant simplement leurs pointeurs.
Chaque l ment d'une liste cha n e est compos de deux parties :
-
-
la valeur que vous voulez stocker,
ladresse de l l ment suivant sil existe. S'il n'y a plus d' l ment suivant, alors l'adresse sera
NULL, et d signera le bout de la cha ne.
2. D claration en C d'une liste cha n e
Vous vous demandez s rement de quel type sera l' l ment de la liste cha n e. En effet, vous
pouvez cr er des listes cha n es de n'importe quel type d' l ments : entiers, caract res, structures,
tableaux, voir m me d'autres listes cha n es...
Il vous est m me possible de combiner plusieurs
types dans une m me
liste.
Voici la d claration dune liste simplement cha n e dentiers :
#include <stdlib.h>
typedef struct element element;
struct element
{
int val;
struct element *nxt;
};
typedef element* llist;
On cr e le type element qui est une structure contenant un entier (val) et un pointeur sur
l ment (nxt), qui contiendra l'adresse de l' l ment suivant. Ensuite, il nous faut cr er le type
llist (pour linked list = liste cha n e) qui est en fait un pointeur sur le type element. Lorsque
nous allons d clarer la liste cha n e, nous devrons d clarer un pointeur sur element, l'initialiser
NULL, pour pouvoir ensuite allouer le premier l ment. N'oubliez pas d'inclure stdlib.h afin de
pouvoir utiliser la macro NULL. Comme vous allez le constater, nous avons juste cr e le type
Advertisement
llist afin de simplifier la d claration.
Voil comment d clarer une liste cha n e (vide pour l'instant) :
#include <stdlib.h>
typedef struct element element;
struct element
{
int val;
struct element *nxt;
};
typedef element* llist;
int main()
{
//D clarons 3 listes cha n es de fa ons diff rentes mais quivalentes
llist ma_liste1 = NULL;
element *ma_liste2 = NULL;
struct element *ma_liste3 = NULL;
return 0;
}
Il est important de toujours initialiser la liste cha n e NULL.
3. Manipulation des listes cha n es
Maintenant que nous savons comment d clarer une liste cha n e, il serait int ressant d'apprendre
ajouter des l ments dans cette liste, ainsi que de lire ce qu'elle contient. C'est ce que nous
allons tudier dans cette premi re partie sur la manipulation des listes cha n es. Dans tous les cas
(ou presque), nous renverrons la nouvelle liste, c'est- -dire un pointeur sur element contenant
l'adresse du premier l ment de la liste.
3.1.
Ajouter un l ment
Lorsque nous voulons ajouter un l ment dans une liste cha n e, il faut savoir o l'ins rer. Les
deux ajouts g n riques des listes cha n es sont les ajouts en t te, et les ajouts en fin de liste. Nous
allons tudier ces deux moyens d'ajouter un l ment une liste.
3.1.1.
Ajouter en t te
Lors d'un ajout en t te, nous allons cr er un l ment, lui assigner la valeur que l'on veut ajouter,
puis pour terminer, raccorder cet l ment la liste pass e en param tre. Lors d'un ajout en t te,
on devra donc assigner nxt l'adresse du premier l ment de la liste pass en param tre.
Visualisons tout ceci sur un sch ma :
Le code C :
llist ajouterEnTete(llist liste, int valeur)
{
// On cr e un nouvel l ment
element* nouvelElement = malloc(sizeof(element));
// On assigne la valeur au nouvel l ment
nouvelElement->val = valeur;
// On assigne l'adresse de l' l ment suivant au nouvel l ment
nouvelElement->nxt = liste;
// On retourne la nouvelle liste : le pointeur sur le premier l ment
return nouvelElement;
}
C'est l'ajout le plus simple des deux. Il suffit de cr er un nouvel l ment puis de le relier au d but
de la liste originale. Si l'original est vide, c'est NULL qui sera assigne au champ nxt du
nouvelElement. La liste contiendra dans ce cas-l un seul l ment.
3.1.2.
Ajouter en fin de liste
Cette fois-ci, c'est un peu plus compliqu . Il nous faut tout d'abord cr er un nouvel l ment, lui
assigner sa valeur, et mettre l'adresse de l' l ment suivant NULL. En effet, comme cet l ment va
terminer la liste nous devons signaler qu'il n'y a plus d' l ment suivant. Ensuite, il faut faire
pointer le dernier l ment de liste originale sur le nouvel l ment que nous venons de cr er. Pour
ce faire, il faut cr er un pointeur temporaire sur element qui va se d placer d' l ment en
l ment, et regarder si cet l ment est le dernier de la liste. Un l ment sera forc ment le dernier
de la liste si NULL est assign son champ nxt.
Le code C :
llist ajouterEnFin(llist liste, int valeur)
{
// On cr e un nouvel l ment
element* nouvelElement = malloc(sizeof(element));
// On assigne la valeur au nouvel l ment
nouvelElement->val = valeur;
// On ajoute en fin, donc aucun l ment ne va suivre
nouvelElement->nxt = NULL;
if(liste == NULL)
{
// Si la liste est vide il suffit de renvoyer l' l ment cr
Advertisement
return nouvelElement;
}
else
{
// Sinon, on parcourt la liste l'aide d'un pointeur temporaire
// et on indique que le dernier l ment de la liste est reli au
//nouvel l ment
element* temp=liste;
while(temp->nxt != NULL)
{
temp = temp->nxt;
}
temp->nxt = nouvelElement;
return liste;
}
}
Comme vous pouvez le constater, nous nous d pla ons le long de la liste cha n e gr ce au
pointeur temp. Si l' l ment point par temp n'est pas le dernier (temp->nxt != NULL), on
avance d'un cran (temp = temp->nxt) en assignant temp l'adresse de l' l ment suivant. Une
fois que l'on est au dernier l ment, il ne reste plus qu' le relier au nouvel l ment.
3.2.
3.2.1.
Supprimer un l ment en t te
Supprimer un l ment en t te de liste
Il s'agit l de supprimer le premier l ment de la liste. Pour ce faire, il nous faudra utiliser la
fonction free que vous connaissez certainement. Si la liste n'est pas vide, on stocke l'adresse du
premier l ment de la liste apr s suppression (i.e. l'adresse du 2 me l ment de la liste originale),
on supprime le premier l ment, et on renvoie la nouvelle liste. Attention quand m me ne pas
lib rer le premier l ment avant d'avoir stock l'adresse du second, sans quoi il sera impossible de
la r cup rer.
Le code C :
llist supprimerElementEnTete(llist liste)
{
if(liste != NULL)
{
// Si la liste est non vide, on se pr pare renvoyer l'adresse de
// l' l ment en 2 me position
element* aRenvoyer = liste->nxt;
// On lib re le premier l ment
free(liste);
// On retourne le nouveau d but de la liste
return aRenvoyer;
}
else
return NULL;
}
3.2.2.
Supprimer un l ment en fin de liste
Cette fois-ci, il va falloir parcourir la liste jusqu' son dernier l ment, indiquer que l'avant-dernier
l ment va devenir le dernier de la liste et lib rer le dernier l ment pour enfin retourner le
pointeur sur le premier l ment de la liste d'origine.
Le code C :
llist supprimerElementEnFin(llist liste)
{
// Si la liste est vide, on retourne NULL
if(liste == NULL)
return NULL;
// Si la liste contient un seul l ment
if(liste->nxt == NULL)
{
// On le lib re et on retourne NULL (la liste est maintenant vide)
free(liste);
return NULL;
}
// Si la liste contient au moins deux l ments
element* tmp = liste;
element* ptmp = liste;
// Tant qu'on n'est pas au dernier l ment
while(tmp->nxt != NULL)
{
// ptmp stock l'adresse de tmp
ptmp = tmp;
Advertisement
// On d place tmp (mais ptmp garde l'ancienne valeur de tmp
tmp = tmp->nxt;
}
// A la sortie de la boucle, tmp pointe sur le dernier l ment, et
// ptmp sur l'avant-dernier. On indique que l'avant-dernier devient la
// fin de la liste et on supprime le dernier l ment
ptmp->nxt = NULL;
free(tmp);
return liste;
}
3.3. Rechercher un l ment dans une liste
Le but du jeu cette fois est de renvoyer l'adresse du premier l ment trouv ayant une certaine
valeur. Si aucun l ment n'est trouv , on renverra NULL. L'int r t est de pouvoir, une fois le
premier l ment trouv , chercher la prochaine occurrence en recherchant partir de
elementTrouve->nxt. On parcourt donc la liste jusqu'au bout, et d s qu'on trouve un l ment
qui correspond ce que l'on recherche, on renvoie son adresse.
Le code C :
llist rechercherElement(llist liste, int valeur)
{
element *tmp=liste;
// Tant que l'on n'est pas au bout de la liste
while(tmp != NULL)
{
if(tmp->val == valeur)
{
// Si l' l ment a la valeur recherch e, on renvoie son adresse
return tmp;
}
tmp = tmp->nxt;
}
return NULL;
}
3.4. Compter le nombre d'occurrences d'une valeur
Pour ce faire, nous allons utiliser la fonction pr c dente permettant de rechercher un l ment.
On cherche une premi re occurrence : si on la trouve, alors on continue la recherche partir de
l' l ment suivant, et ce tant qu'il reste des occurrences de la valeur recherch e. Il est aussi possible
d' crire cette fonction sans utiliser la pr c dente bien entendu, en parcourant l'ensemble de la
liste avec un compteur que l'on incr mente chaque fois que l'on passe sur un l ment ayant la
valeur recherch e. Cette fonction n'est pas beaucoup plus compliqu e, mais il est int ressant d'un
point de vue algorithmique de r utiliser des fonctions pour simplifier nos codes.
Le code C :
int nombreOccurences(llist liste, int valeur)
{
int i = 0;
// Si la liste est vide, on renvoie 0
if(liste == NULL)
return 0;
// Sinon, tant qu'il y a encore un l ment ayant la val = valeur
while((liste = rechercherElement(liste, valeur)) != NULL)
{
// On incr mente
liste = liste->nxt;
i++;
}
// Et on retourne le nombre d'occurrences
return i;
}
3.5. Recherche du i- me l ment
Pour le coup, c'est une fonction relativement simple. Il suffit de se d placer i fois l'aide du
pointeur tmp le long de la liste cha n e et de renvoyer l' l ment l'indice i. Si la liste contient
moins de i l ment(s), alors nous renverrons NULL.
Le code C :
llist element_i(llist liste, int indice)
{
int i;
// On se d place de i cases, tant que c'est possible
for(i=0; i<indice && liste != NULL; i++)
{
liste = liste->nxt;
}
// Si l' l ment est NULL, c'est que la liste contient moins de i
// l ments
Advertisement
if(liste == NULL)
{
return NULL;
}
else
{
// Sinon on renvoie l'adresse de l' l ment i
return liste;
}
}
3.6. Compter le nombre d' l ments d'une liste cha n e
C'est un algorithme vraiment simple. Vous parcourez la liste de bout en bout et incr mentez d'un
pour chaque nouvel l ment que vous trouvez.
Le code C (de la fonction it rative) :
int nombreElements(llist liste)
{
int nb=0;
element* tmp = liste ;
// On parcourt la liste
while(tmp != NULL)
{
nb++;
tmp = tmp->nxt ;
}
// On retourne le nombre d l ments parcourus
return nb;
}
Le code C (de la fonction r cursive) :
int nombreElements(llist liste)
{
// Si la liste est vide, il y a 0 l ment
if(liste == NULL)
return 0;
// Sinon, il y a un l ment (celui que l'on est en train de traiter)
// plus le nombre d' l ments contenus dans le reste de la liste
return nombreElements(liste->nxt)+1;
}
3.7. Effacer tous les l ments ayant une certaine valeur
Pour cette derni re fonction, nous allons encore une fois utiliser un algorithme r cursif. M me si
la r cursivit vous semble tre une notion complexe (et a l'est s rement), elle simplifie
grandement les algorithmes dans certains cas, et dans celui-ci tout particuli rement.
Le code C :
llist supprimerElement(llist liste, int valeur)
{
// Liste vide, il n'y a plus rien supprimer
if(liste == NULL)
return NULL;
// Si l' l ment en cours de traitement doit tre supprim
if(liste->val == valeur)
{
// On le supprime en prenant soin de m moriser
// l'adresse de l' l ment suivant
element* tmp = liste->nxt;
free(liste);
// L' l ment ayant t supprim , la liste commencera l' l ment
// suivant pointant sur une liste qui ne contient plus aucun
// l ment ayant la valeur recherch e
tmp = supprimerElement(tmp, valeur);
return tmp;
}
else
{
// Si l' lement en cours de traitement ne doit pas tre supprim ,
// alors la liste finale commencera par cet l ment et suivra une
// liste ne contenant plus d' l ment ayant la valeur recherch e
liste->nxt = supprimerElement(liste->nxt, valeur);
return liste;
}
}