Wikilivres

« Structures de données en C/Les listes simples » : différence entre les versions

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Ortho
balise source
Ligne 8 :
[[Image:Structures_de_données_en_C-list.png|140 px|Représentation graphique du type <code>List</code>]]
 
Les déclarations nécessaires pour représenter le type des listes en langage C sont:
<source lang="c">
<font color="blue">typedef</font> <font color="blue">struct</font> _List List;
typedef struct s_List List;
<font color="blue">struct</font> _List
struct s_List
{
{
List *next; <font color="green">/* pointeur sur le reste de la liste */</font>
<font color="blue">void</font>List *datanext; <font color="green">/* pointeur sur unele donnéereste génériquede la liste */</font>
void *data; /* pointeur sur une donnée générique */
};
};
</source>
 
=== Initialisation ===
L'utilisation primaire d'une liste consiste à la déclarer et à l'initialiser à la liste vide.
<source lang="c">
List *list = <b>NULL</b>;
List *list = NULL;
</source>
 
=== Création d'une liste d'un élément ===
Ligne 25 ⟶ 29 :
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 <code>malloc</code> car la documentation dit que le retour peut être <code>NULL</code> 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 <code>List</code>
 
<source lang="c">
List *
List *
list_create (<font color="blue">void</font> *data)
list_create (void *data)
{
{
List *list = <b>malloc</b> (<font color="blue">sizeof</font> (*list)); <font color="green">/* allocation (en vert sur le diagramme) et affectation à la variable list (en bleu) */</font>
List *list = malloc(sizeof(*list)); /* allocation (en vert sur le diagramme) et affectation à la variable list (en bleu) */
<font color="blue">if</font> (list) <font color="green">/* si l'allocation a réussi */</font>
if (list) /* si l'allocation a réussi */
{
{
list->data = data; <font color="green">/* affectation du champ data (en rouge) */</font>
list->nextdata = <b>NULL</b>data; <font color="green">/* affectation du champ nextdata à(en la liste viderouge) */</font>
list->next = <b>NULL</b>; /* affectation du champ next à la liste vide */
}
}
<font color="blue">return</font> list; <font color="green">/* retour de la liste (correctement allouée et affectée ou NULL) */</font>
return list; /* retour de la liste (correctement allouée et affectée ou NULL) */
}
</source>
[[Image:Structures_de_données_en_C-list_create.png|108 px|Création d'une liste d'un élément]]
 
Ligne 44 ⟶ 50 :
[[Image:Structures_de_données_en_C-list_prepend.png|334 px|Ajout d'un élément en tête de liste]]
 
<source lang="c">
List *
List *
list_prepend(List *old, <font color="blue">void</font> *data)
list_prepend(List *old, void *data)
{
{
List *list = list_create(data); <font color="green">/* création et affectation d'une liste d'un élément (en vert sur le diagramme) */</font>
List *list = list_create(data); /* création et affectation d'une liste d'un élément (en vert sur le diagramme) */
<font color="blue">if</font> (list) <font color="green">/* si l'allocation mémoire a réussi */</font>
if (list->next) = old; <font color="green">/* accrochage de /* si l'ancienneallocation listemémoire àa la nouvelle (en bleu sur le diagramme)réussi */</font>
<font color="blue">return</font list->next list= old; /* accrochage de <fontl'ancienne color="green">/*liste retour deà la nouvelle liste (ouen NULLbleu si l'allocationsur ale échouédiagramme) */</font>
return list; /* retour de la nouvelle liste (ou NULL si l'allocation a échoué) */
}
}
</source>
 
==== Ajout d'un élément en fin de liste ====
L'algorithme est relativement simple. Il consiste à rechercher le pointeur <code>NULL</code> dans la liste marquant sa fin. Une fois trouvé, il est modifié en allouant une nouvelle liste de 1 élément contenant <code>data</code>. La difficulté principale est l'utilisation d'un pointeur de liste (un <code>List **</code>) permettant de traiter indifféremment le cas où la liste d'origine est vide et le cas où elle n'est pas vide.
 
List *
<source lang="c">
list_append(List *list, <font color="blue">void</font> *data)
List *
{
list_append(List **plistlist, =void &list;*data)
{
<font color="blue">while</font> (*plist)
List **plist = &(*plist)->nextlist;
while (*plist)
*plist = list_create(data);
<font color plist ="blue">if</font> &(*plist)->next;
*plist = list_create(data);
<font color="blue">return</font> list;
if (*plist)
<font color="blue">else</font>
<font color="blue"> return</font> <b>NULL</b>list;
else
}
return NULL;
}
</source>
 
===== Cas où la liste d'origine n'est pas vide =====
<source lang="c">
<pre>
...
List new_list=list_append(mylist,data);
...
</presource>
 
* instruction <code>List **plist = &list;</code>
Ligne 86 ⟶ 98 :
 
===== Cas où la liste d'origine est vide =====
<source lang="c">
...
List *new_list=list_append(<b>NULL</b>,data);
...
</source>
 
* instruction <code>List **plist = &list;</code>
Ligne 101 ⟶ 115 :
Le retrait du premier élément consiste à libérer le pointeur utilisé pour le premier élément et à retourner le reste de la liste
 
<source lang="c">
List *
List *
list_remove_first(List *list)
{
List *first = list; <font color="green">/* conservation de la liste actuelle (opération en vert)*/</font>
list = list->next; <font color="green">/* faire pointer list sur le reste (opération en bleu)*/</font>
<b> free</b>(first); <font color="green">/* libérer la mémoire utilisée par la structure List précédente (opération en rouge) */</font>
<font color="blue">return</font> list; <font color="green">/* retour de la nouvelle liste */</font>
}
</source>
Lors d'un appel à list_remove_first la liste passée en argument n'est pas modifiée
Ligne 114 ⟶ 130 :
[[Image:Structures_de_données_en_C-list_remove_first.png|336 px|Résultat de la ligne <code>List *new_list = list_remove_first(mylist);</code>]]
 
<source lang="c">
<pre>
...
List *new_list = list_remove_first(mylist);
...
</presource>
 
==== 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 <code>free</code> sur ce genre de pointeur.
 
<source lang="c">
<font color="blue">void</font>
void
list_destroy(List *list)
list_destroy(List *list)
{
{
<font color="blue">while</font> (list) <font color="green">/* tant que l'on n'est pas arrivé en fin de liste */</font>
while list = list_remove_first(list); <font color="green"> /* tant que l'on n'est retraitpas duarrivé premieren élémentfin de la liste */</font>
list = list_remove_first(list); /* retrait du premier élément de la liste */
}
}
</source>
Il est à noter que le pointeur original n'est pas modifié par la ligne <code>list = list->next</code>
 
Exemple, lors de la destruction de la liste <code>mylist</code> dans le code suivant, <code>mylist</code> n'est pas modifié.
 
<pre>
<source lang="c">
...
list_destroy(mylist);
...
</presource>
 
Lors de l'appel à <code>list_destroy</code>, l'argument <code>list</code> prend la valeur de <code>mylist</code>. Les deux pointeurs sont donc confondus
 
Ligne 148 ⟶ 168 :
=== Longueur d'une liste ===
Pour calculer la longueur d'une liste, il suffit de compter le nombre de pointeurs de type <code>List</code> différents du pointeur <code>NULL</code>
 
<font color="blue">int</font>
<source lang="c">
list_length(List *list)
int
{
list_length(List *list)
<font color="blue">int</font> length = <font color="red">0</font>; <font color="green">/* initialisation de la longueur à 0 */</font>
{
<font color="blue">while</font> (list) <font color="green">/* tant que la fin de la liste d'est pas atteinte */</font>
int length = 0; /* initialisation de la longueur à 0 */
while (list) /* tant que la fin de la liste d'est pas atteinte */
{
length++; <font color="green">/* incrémenter la longueur */</font>
list = list->next; <font color="green">/* passer à l'élément suivant */</font>
}
<font color="blue"> return</font> length; <font color="green">/* retourner la longueur calculée */</font>
}
</source>
De même que pour la destruction, l'affectation de <code>list</code> 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'[[Structures de données en C/Les itérateurs|itérateurs]].
 
...
<source lang="c">
List *tmp=list; <font color="green">/* opération en vert sur le diagramme */</font>
...
<font color="blue">while</font> (tmp)
List *tmp=list; /* opération en vert sur le diagramme */
{
while (tmp)
<font color="green">/* traitement de tmp-&gt;data */</font>
{
tmp = tmp->next; <font color="green">/* opération en bleu sur le diagramme */</font>
/* traitement de tmp-&gt;data */
}
tmp = tmp->next; /* opération en bleu sur le diagramme */
...
}
...
</source>
[[Image:Structures_de_données_en_C-list_iteration_1.png|300 px|Début de l'itération</code>]]
 
Ligne 181 ⟶ 207 :
 
La fonction de création consiste à allouer un tel pointeur et à l'initialiser à la liste
 
<pre>
<source lang="c">
Iterator *list_iterator_create(void *list)
{
return iterator_create(list, NULL, list_iterator_has_next, list_iterator_next);
}
</presource>
 
La fonction pour savoir si il existe un élément suivant teste simplement la valeur de <code>*iterator</code>
 
<pre>
<source lang="c">
static int list_iterator_has_next(const void *list)
{
return (int)list;
}
</presource>
 
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.
 
<pre>
<source lang="c">
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 */
}
</presource>
 
Le code classique pour parcourir une liste devient
 
<pre>
<source lang="c">
...
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 */
...
</presource>
 
== Exercices ==
Récupérée de « https://fr.wikibooks.org/wiki/Structures_de_données_en_C/Les_listes_simples »