Structures de données en C/Les listes simples
Cours
modifierType List
en C
modifier
Une liste simple est une collection d'objets accessibles les uns après les autres. Elle peut être
- vide ; et la convention pour représenter la liste vide consiste à utiliser le pointeur
NULL
; - composé d'un élément et du reste de la liste.
Les déclarations nécessaires pour représenter le type des listes en langage C sont:
typedef struct s_List List;
struct s_List
{
List *next; /* pointeur sur le reste de la liste */
void *data; /* pointeur sur une donnée générique */
};
Initialisation
modifierL'utilisation primaire d'une liste consiste à la déclarer et à l'initialiser à la liste vide.
List *list = NULL;
Création d'une liste d'un élément
modifierCette fonction est très utile et pourra être modifiée par la suite lorsqu'il s'agira d'utiliser des allocateurs de mémoire intelligents.
La création d'une liste d'un élément demande d'allouer de la mémoire au gestionnaire de mémoire. Il convient de toujours tester le retour d'un malloc
car la documentation dit que le retour peut être NULL
si le système ne dispose plus de mémoire suffisante. Si l'allocation a réussi, il n'y a plus qu'à affecter les champs de la structure List
List *
list_create (void *data)
{
List *list = malloc(sizeof(list)); /* allocation (en vert sur le diagramme) et affectation à la variable list (en bleu) */
if (list) /* si l'allocation a réussi */
{
list->data = data; /* affectation du champ data (en rouge) */
list->next = NULL; /* affectation du champ next à la liste vide */
}
return list; /* retour de la liste (correctement allouée et affectée ou NULL) */
}
Ajouts d'éléments
modifierAjout d'un élément en tête de liste
modifierL'insertion d'un élément en tête de liste demande tout d'abord de créer une liste d'un élément. Si la création a réussi, il n'y a plus qu'à affecter le champ next
de la structure List
List *
list_prepend(List *old, void *data)
{
List *list = list_create(data); /* création et affectation d'une liste d'un élément (en vert sur le diagramme) */
if (list) /* si l'allocation mémoire a réussi */
list->next = old; /* accrochage de l'ancienne liste à la nouvelle (en bleu sur le diagramme) */
return list; /* retour de la nouvelle liste (ou NULL si l'allocation a échoué) */
}
Ajout d'un élément en fin de liste
modifierL'algorithme est relativement simple. Il consiste à rechercher le pointeur NULL
dans la liste marquant sa fin. Une fois trouvé, il est modifié en allouant une nouvelle liste de 1 élément contenant data
. La difficulté principale est l'utilisation d'un pointeur de liste (un List **
) permettant de traiter indifféremment le cas où la liste d'origine est vide et le cas où elle n'est pas vide.
List *
list_append(List *list, void *data)
{
List **plist = &list;
while (*plist)
plist = &(*plist)->next;
*plist = list_create(data);
if (*plist)
return list;
else
return NULL;
}
Cas où la liste d'origine n'est pas vide
modifier...
List new_list=list_append(mylist,data);
...
- instruction
List **plist = &list;
- instruction
plist = &(*plist)->next;
- instruction
*plist = list_create(data);
- instruction
return list;
Cas où la liste d'origine est vide
modifier ...
List *new_list=list_append(NULL,data);
...
- instruction
List **plist = &list;
- instruction
*plist = list_create(data);
- instruction
return list;
Destructions d'éléments
modifierDestruction du premier élément
modifierLe retrait du premier élément consiste à libérer le pointeur utilisé pour le premier élément et à retourner le reste de la liste
List *
list_remove_first(List *list)
{
List *first = list; /* conservation de la liste actuelle (opération en vert)*/
list = list->next; /* faire pointer list sur le reste (opération en bleu)*/
free(first); /* libérer la mémoire utilisée par la structure List précédente (opération en rouge) */
return list; /* retour de la nouvelle liste */
}
Lors d'un appel à list_remove_first la liste passée en argument n'est pas modifiée
...
List *new_list = list_remove_first(mylist);
...
Destruction de la liste entière
modifierLa destruction d'une liste concerne la libération de la mémoire préalablement réservée par le chainage de la liste. Je pense (et c'est discutable) que les bibliothèques ne doivent libérer que ce qu'elles ont alloué. Les données n'ont donc pas à être libérées. Elles peuvent être notamment des pointeurs vers des chaînes de caractères statiques, et je vous laisse imaginer les effets d'un free
sur ce genre de pointeur.
void
list_destroy(List *list)
{
while (list) /* tant que l'on n'est pas arrivé en fin de liste */
list = list_remove_first(list); /* retrait du premier élément de la liste */
}
Il est à noter que le pointeur original n'est pas modifié par la ligne list = list->next
Exemple, lors de la destruction de la liste mylist
dans le code suivant, mylist
n'est pas modifié.
...
list_destroy(mylist);
...
Lors de l'appel à list_destroy
, l'argument list
prend la valeur de mylist
. Les deux pointeurs sont donc confondus
Dans la boucle, l'affectation de list
ne modifie pas la valeur de mylist
(bien que les structures de List
n'existe plus (en rouge) en mémoire).
Longueur d'une liste
modifierPour calculer la longueur d'une liste, il suffit de compter le nombre de pointeurs de type List
différents du pointeur NULL
int
list_length(List *list)
{
int length = 0; /* initialisation de la longueur à 0 */
while (list) /* tant que la fin de la liste n'est pas atteinte */
{
length++; /* incrémenter la longueur */
list = list->next; /* passer à l'élément suivant */
}
return length; /* retourner la longueur calculée */
}
De même que pour la destruction, l'affectation de list
ne modifie pas la valeur de la liste de la fonction appelante.
Itérer sur les listes
modifierIl y a plusieurs moyens d'effectuer une itération sur les éléments d'une liste. Le plus simple étant présenté ici, mais j'enjoins les lecteurs à parcourir le chapitre consacré au concept d'itérateurs.
...
List *tmp=list; /* opération en vert sur le diagramme */
while (tmp)
{
/* traitement de tmp->data */
tmp = tmp->next; /* opération en bleu sur le diagramme */
}
...
Il est à noter que la modification du pointeur tmp
ne modifie en rien le pointeur original list
.
Un itérateur en C sur les listes est un pointeur de List *
soit un List **
(la raison essentielle est que la fonction list_iterator_next
modifie l'itérateur. La seule façon de procéder en C est d'utiliser en pointeur sur l'argument à modifier). Mais vu de l'extérieur des fonctions, il est préférable dans un soucis de généricité d'utiliser le pointeur void *
La fonction de création consiste à allouer un tel pointeur et à l'initialiser à la liste
Iterator *list_iterator_create(void *list)
{
return iterator_create(list, NULL, list_iterator_has_next, list_iterator_next);
}
La fonction pour savoir si il existe un élément suivant teste simplement la valeur de *iterator
static int list_iterator_has_next(const void *list)
{
return (int)list;
}
La fonction pour obtenir le prochain élément d'un itérateur de liste retourne la donnée et modifie l'itérateur en le faisant pointer sur la prochaine donnée.
static void *list_iterator_next(void *plist)
{
void *data = (*(List**)plist)->data; /* conservation de la donnée courante de l'itérateur */
*(List**)plist = (*(List**)plist)->next; /* modification de l'itérateur */
return data; /* retour de la donnée */
}
Le code classique pour parcourir une liste devient
...
Iterator *iterator = list_iterator_create(list);
if (iterator)
{
while (iterator_has_next(iterator))
{
void *data = iterator_next(iterator);
/* traitement de data */
}
iterator_destroy(iterator);
}
else
/* traitement de l'erreur d'allocation */
...
Exercices
modifierListes et ensembles
modifierLes éléments n'apparaissent qu'une seule fois dans un ensemble.
- Créer la fonction cardinal retournant le nombre d'éléments d'un ensemble
- Créer l'opérateur union
- Créer l'opérateur intersection