Bien programmer en langage C
Date de publication : 28 mai 2008
X. Les listes chaînées
X-A. Introduction
X-B. Implémentation d'une liste chaînée simple
X-B-1. Implémentation avec structure.
X. Les listes chaînées
X-A. Introduction
Les listes chaînées constituent une alternative intéressante aux tableaux. En dehors du fait qu'elles
sont souples par nature, elles permettent d'insérer et de supprimer facilement un élément. Par contre,
le parcours est séquentiel (mais rien n'empêche de gérer un 'index', c'est à dire un tableau de
pointeurs, séparément).
X-B. Implémentation d'une liste chaînée simple
Le principe est très simple. Il suffit de définir dans l'élément un champ 'pointeur sur le suivant' qui
contient l'adresse de l'élément suivant. Il suffit alors de connaître le début de la liste, et on
peut alors la parcourir séquentiellement en allant chercher l'élément suivant, jusqu'au dernier
qui pointe sur NULL (fin de liste).
On commence par définir un 'maillon' ou noeud' (node) :
struct node
{
int x;
struct node *p_next;
};
|
Ensuite, on définit le pointeur de tête. Il a le même type qu'un maillon et il contient soit NULL (chaîne
vide), soit l'adresse du premier noeud :
int main (void)
{
struct node *p_head = NULL;
return 0;
}
|
Il est primordial que cette valeur soit maintenue à jour et qu'elle ne soit pas perdue.
Ensuite, on crée une fonction qui permet, par exemple, d'ajouter en fin de liste. Pour ça, on distingue
le cas de la liste vide et les autres cas. Si la liste est vide, on retourne simplement l'adresse
du nouveau noeud qui est par définition, le premier, sinon, on cherche le dernier noeud existant
et on y 'accroche' le nouveau.
struct node *add_end (struct node *p_head, int value)
{
struct node *p_new = malloc (sizeof *p_new);
if (p_new != NULL)
{
p_new->x = value;
p_new->p_next = NULL;
if (p_head == NULL)
{
p_head = p_new;
}
else
{
struct node *p = p_head;
while (p->p_next != NULL)
{
p = p->p_next;
}
p->p_next = p_new;
}
}
return p_head;
}
|
Afin de pouvoir tout de suite vérifier si tout s'est bien passé, on définit dans la foulée, une fonction
de visualisation de la liste chaînée :
void display (struct node *p_head)
{
struct node *p = p_head;
while (p != NULL)
{
printf ("%d > ", p->x);
p = p->p_next;
}
printf ("NIL\n");
}
|
Avec ce petit fichier de test :
int main (void)
{
struct node *p_head = NULL;
p_head = add_end (p_head, 1);
p_head = add_end (p_head, 2);
p_head = add_end (p_head, 3);
display (p_head);
return 0;
}
|
ça donne :
1 > 2 > 3 > NIL
Press ENTER to continue.
|
Je laisse au lecteur le soin de réaliser la fonction de libération de l'ensemble de la liste, l'ajout
d'un noeud en tête (add_top()), l'insertion (insert()), la suppression d'un noeud (suppress()) etc.
[1]
X-B-1. Implémentation avec structure.
Afin de simplifier la gestion de la liste, il est possible de regrouper, dans une structure 'liste',
les éléments intéressants de celle-ci, comme l'inévitable pointeur sur la tête de liste, mais aussi
le pointeur sur la fin de la liste, ce qui permet un ajout en queue très rapide. D'autres informations
(nombre d'éléments etc.) peuvent aussi accélérer les traitements.
struct list
{
struct node *p_head;
struct node *p_tail;
};
|
L'interface de la fonction d'ajout à la fin se trouve alors modifiée de la façon suivante :
void add_end (struct list *p_list, int value);
|
et l'usage s'en trouve simplifié :
int main (void)
{
struct list list = {0};
add_end (&list, 1);
add_end (&list, 2);
add_end (&list, 3);
display (&list);
return 0;
}
|
Je laisse au lecteur le soin de réaliser les fonctions list_add_end(), list_display(), list_add_top()
selon ce principe.[1]
Il est aussi évidemment possible de rendre la structure opaque (
TAD)
typedef struct list list_s;
|
#include "list.h"
struct node
{
int x;
struct node *p_next;
};
struct list
{
struct node *p_head;
struct node *p_tail;
};
|
[1] Vous pouvez poster vos tentatives sur le forum en cas de difficultés.
Copyright © 2008 Emmanuel Delahaye.
Aucune reproduction, même partielle, ne peut être faite
de ce site ni de l'ensemble de son contenu : textes, documents, images, etc.
sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à
trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.
