# Structures de données en C/Les listes simples

* Les itérateurs
* Les listes simples
Annexes
* Les itérateurs
* Les listes simples
Annexes
[ Modifier le sommaire ]

## Cours
### Type List en C

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:

### Initialisation

L'utilisation primaire d'une liste consiste à la déclarer et à l'initialiser à la liste vide.

### 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 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

### 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 next de la structure List

#### Ajout d'un élément en fin de liste

L'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.

##### Cas où la liste d'origine n'est pas vide

* instruction List **plist = &list;
* instruction plist = &(*plist)->next;
* instruction *plist = list_create(data);
* instruction return list;

##### Cas où la liste d'origine est vide

* instruction List **plist = &list;
* instruction *plist = list_create(data);
* instruction return list;

### 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
Lors d'un appel à list_remove_first la liste passée en argument n'est pas modifiée

#### 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 free sur ce genre de pointeur.
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é.
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

Pour calculer la longueur d'une liste, il suffit de compter le nombre de pointeurs de type List différents du pointeur NULL
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

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.
Il est à noter que la modification du pointeur tmp ne modifie en rien le pointeur original list.
Cette page est en travaux. Tant que cet avis n'aura pas disparu, veuillez en considérer le plan et le contenu encore incomplets, temporaires et sujets à caution. Si vous souhaitez participer, il vous est recommandé de consulter sa page de discussion au préalable, où des informations peuvent être données sur l'avancement des travaux.
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
La fonction pour savoir si il existe un élément suivant teste simplement la valeur de *iterator
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.
Le code classique pour parcourir une liste devient

## Exercices
### Listes et ensembles

Les é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