Cours.
Type codice_1 en C.
Une liste simple est une collection d'objets accessibles les uns après les autres. Elle peut être
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.
L'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.
Cette 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 codice_3 car la documentation dit que le retour peut être codice_2 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 codice_1
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.
Ajout d'un élément en tête de liste.
L'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 codice_6 de la structure codice_1
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.
L'algorithme est relativement simple. Il consiste à rechercher le pointeur codice_2 dans la liste marquant sa fin. Une fois trouvé, il est modifié en allouant une nouvelle liste de 1 élément contenant codice_9. La difficulté principale est l'utilisation d'un pointeur de liste (un codice_10) 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.
List new_list=list_append(mylist,data);
Cas où la liste d'origine est vide.
 List *new_list=list_append(NULL,data);
Destructions d'éléments.
Destruction du premier élément.
Le 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.
La 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 codice_18 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 codice_19
Exemple, lors de la destruction de la liste codice_20 dans le code suivant, codice_20 n'est pas modifié.
list_destroy(mylist);
Lors de l'appel à codice_22, l'argument codice_23 prend la valeur de codice_20. Les deux pointeurs sont donc confondus
Dans la boucle, l'affectation de codice_23 ne modifie pas la valeur de codice_20 (bien que les structures de codice_1 n'existe plus (en rouge) en mémoire).
Longueur d'une liste.
Pour calculer la longueur d'une liste, il suffit de compter le nombre de pointeurs de type codice_1 différents du pointeur codice_2
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 codice_23 ne modifie pas la valeur de la liste de la fonction appelante.
Itérer sur les listes.
Il 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 codice_31 ne modifie en rien le pointeur original codice_23.
Un itérateur en C sur les listes est un pointeur de codice_33 soit un codice_10 (la raison essentielle est que la fonction codice_35 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 codice_36
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 codice_37
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.
Listes et ensembles.
Les éléments n'apparaissent qu'une seule fois dans un ensemble.

Novoflex
Leica
Photographie/Fabricants/Novoflex
Soufflets.
Les soufflets Novoflex sont destinés aux appareils d'autres constructeurs, sur lesquels ils se montent grâce à des bagues d'adaptation. Prévoir entre 40 et 200 € selon les modèles.

Pentax
Linhof
Photographie/Fabricants/Canon/Canon EF-S 60 mm f/2,8 Macro USM