Manipuler les listes chainées
Cette fois, ça va monter d'un cran niveau difficulté. Nous allons voir tout un tas de fonctions, pour supprimer des éléments, rechercher un élément... Je vous conseille si vous n'avez pas tout compris de revenir un peu en arrière, de faire des essais avec votre compilateur préféré, parce que tout ce que nous allons voir fonctionne toujours sur le même principe. Je considèrerais ce que j'ai précédemment montré comme acquis. Cette partie va se dérouler comme ceci : j'explique l'algorithme général de la fonction puis je donne son code commenté.
Prêts ? On y va !
Supprimer un élément en tête
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.
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;
}
}
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.
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;
/* 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;
}
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.
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;
}
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.
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;
}
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.
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 */
if(liste == NULL)
{
return NULL;
}
else
{
/* Sinon on renvoie l'adresse de l'élément i */
return liste;
}
}
Récupérer la valeur d'un élément
C'est une fonction du même style que la fonction estVide. Elle sert à "masquer" le fonctionnement interne à l'utilisateur. Il suffit simplement de renvoyer à l'utilisateur la valeur d'un élément. Il faudra renvoyer un code d'erreur entier si l'élément n'existe pas (la liste est vide), c'est donc à vous de définir une macro selon l'utilisation que vous voulez faire des listes chaînées. Dans ce code, je considère qu'on ne travaille qu'avec des nombres entiers positifs, on renverra donc -1 pour une erreur. Vous pouvez mettre ici n'importe quelle valeur que vous êtes sûrs de ne pas utiliser dans votre liste. Une autre solution consiste à renvoyer un pointeur sur int au lieu d'un int, vous laissant donc la possibilité de renvoyer NULL.
#define ERREUR -1
int valeur(llist liste)
{
return ((liste == NULL)?ERREUR:(liste->val));
}
Compter le nombre d'éléments d'une liste chaîné
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. Cet algorithme n'ayant aucun intérêt au point où nous en sommes, je vais en profiter pour vous faire découvrir un nouveau type d'algorithme. Jusqu'à maintenant, nous n'avons utilisé que des algorithmes itératifs qui consistent à boucler tant que l'on n'est pas au bout. Nous allons voir qu'il existe des algorithmes que l'on appellent récursifs et qui consistent en fait à demander à une fonction de s'appeler elle-même. Attention : il faudrait un big-tuto complet pour tout expliquer à propos des algorithmes récursifs, ce n'est vraiment que pour vous montrer que ce genre de choses existe que je vais les utiliser dans les deux prochains codes.
Avant tout, je pense qu'un petit point d'explication s'impose.
Pour créer un algorithme récursif, il faut connaître la condition d'arrêt (ou condition de sortie) et la condition de récurrence. Il faut en fait vous imaginer que votre fonction a fait son office pour les n-1 éléments suivants, et qu'il ne reste plus qu'à traiter le dernier élément. Lisez le code suivant. N'ayez pas peur si ceci vous semble obscur, ce n'est pas essentiel pour utiliser les listes chaînées. Maintenant, je suis sûr que vous êtes au point et vous pouvez donc de manière itérative créer à peu près tout ce qui peut se faire.
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;
}
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. Je vous donne le code à titre indicatif, vous pourrez vous même recoder cette fonction avec un algorithme itératif si vous le voulez.
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;
}
}
fin.
ليست هناك تعليقات:
إرسال تعليق