Lists: Implementation and Manipulation in C

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 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éé 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; // 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 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; } }