[Cours #8] Listes chainées

AlexMog

Bonjour à tous,
Dans ce cours, nous allons voir ce qu'est une liste chainées, et comment elle fonctionne.
 
I- Liste chainée? WTF?
D'après Wikipedia: "Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type".
Pour résumer, il s'agit d'une collection de données (comme un tableau, sisi), qui a une taille variable, donc on a pas besoin de connaitre la taille de la liste à l'avance (un peu comme dans le cours sur les allocations dynamiques ). Les éléments sont enregistrés les uns après les autres.
C'est donc une grosse liste de données. Le premier élément pointe vers le second, le second vers le troisième, le troisième vers le quatrième etc...
Comme le montre le schéma ci-dessous:
(Source: Openclassroom)
<img alt="39595.jpg" src="http://uploads.siteduzero.com/files/39001_40000/39595.jpg"/>
C'est une liste chainée simple, et nous ne verrons que celle-ci. Pour la liste chainée circulaire, ou encore double, je vous laisse chercher par vous mêmes 
 
II- Créons notre structure de données!
Une liste chainées à pour but de contenir des données (c'est logique...), il faut donc créer une structure pour stocker lesdites données.
Pour ma part de vais créer une liste pour stocker l'age et la taille d'un certain nombre d'utilisateurs.
<pre class="ipsCode prettyprint">
typedef struct s_list
{
int taille;
int age;
struct s_list *next;
}t_list;
</pre>
Oh! c'est étrange, qu'est-ce que la variable "next" vient faire ici? Comme je l'ai dit plus haut, il s'agit du pointeur sur le prochain élément de notre liste chainée. Il va falloir penser à le mettre à NULL pour connaitre la fin de notre liste chainée! En effet, lorsqu'on sera au dernier élément, on le sera grâce au NULL.
Dans ce cours, je vais uniquement vous apprendre à ajouter des éléments à votre liste, à parcourir votre liste, et enfin à supprimer votre liste. C'est à vous d'utiliser votre tête pour la suite!
 
III- Ajouter un élément à la liste.
Maintenant que notre structure est crée, nous allons créer plusieurs fonctions, pour gérer notre liste chainée.
Créons tout d'abord une fonction pour ajouter un élément à la liste:
<pre class="ipsCode prettyprint">
int add_to_list(t_list **list, t_list *datas)
{
t_list *next;

next = NULL;
if (*list != NULL)
next = *list;
if ((*list = malloc(sizeof(t_list))) == NULL)
return (1);
(*list)->taille = datas->taille;
(*list)->age = datas->age;
(*list)->next =next;
return (0);
}
</pre>
Voici un exemple d'utilisation de la fonciton:
<pre class="ipsCode prettyprint">
int main(void)
{
t_list *list;
t_list datas;

*list = NULL;
datas.age = 10;
datas.taille = 180;
// On ajoute à notre liste
if (add_to_list(&list, &datas))
return (1);
// On récupère le premier noeud pour voir ce qu'il contient
printf("Age: %d, Taille: %d\n", list->age, list->taille);
return (0);
}
</pre>
III- Parcourons notre liste!
Nous allons à présent parcourir notre liste.
<pre class="ipsCode prettyprint">
int main(void)
{
t_list *list;
t_list datas;
int i;

i = -1;
// On remplis notre liste avec 10 éléments
while (++i < 10)
{
datas.age = i;
datas.taille = 180 + i;
if (add_to_list(&list, &datas))
return (1);
}
// On parcours et on affiche notre liste!
while (list != NULL)
{
printf("Age: %d, Taille: %d\n", list->age, list->taille);
list = list->next;
}
return (0);
}
</pre>
IV- Vidons notre liste! (C'est important de vider la mémoire!)
Pour cela, créons une fonction de vidage.
<pre class="ipsCode prettyprint">
void clear_list(t_list **list)
{
t_list *elem;
t_list *next;

elem = *list;
while (elem)
{
next = elem->next;
free(elem);
elem = next;
}
*list = NULL;
}
</pre>
Exemple d'utilisation:
<pre class="ipsCode prettyprint">
int main(void)
{
t_list *list;
t_list datas;
int i;

i = -1;
// On remplis notre liste avec 10 éléments
while (++i < 10)
{
datas.age = i;
datas.taille = 180 + i;
if (add_to_list(&list, &datas))
return (1);
}
// On parcours et on affiche notre liste! (on utilise un pointeur annexe pour ne pas perdre le noeud mère)
list *elem = list;
while (elem != NULL)
{
printf("Age: %d, Taille: %d\n", elem->age, elem->taille);
elem = elem->next;
}
clear_list(&list);
return (0);
}
</pre>
Je vous laisse la joie d'analyser le code, à ce stade des cours (et si vous avez bien tout suivi) vous savez analyser le code, je vous laisse donc le comprendre par vous mêmes! Je reste disponible pour répondre à vos questions!
 
A bientôt pour un prochain cours!

davydavek

Choses que j'ai remarquer:
-Il manque une parenthèse dans la fonction add_to_list, après le sizeof(t_list) dans le second if.
-La variable next dans la fonction add_to_list n'est pas utilisée.
-Dans l'exemple, la liste ne contient qu'un élément. (au lieu de 10), je pense qu'il y a un problème dans la fonction add_to_list.

AlexMog

<blockquote class="ipsQuote" data-cite="davydavek" data-ipsquote="" data-ipsquote-contentclass="forums_Topic" data-ipsquote-contentcommentid="8323" data-ipsquote-contentid="783" data-ipsquote-contenttype="forums" data-ipsquote-timestamp="1401822414" data-ipsquote-username="davydavek"><div>
<div>
Choses que j'ai remarquer:
-Il manque une parasynthèse dans la fonction add_to_list, après le sizeof(t_list) dans le second if.
-La variable next dans la fonction add_to_list n'est pas utilisée.
-Dans l'exemple, la liste ne contient qu'un élément. (au lieu de 10), je pense qu'il y a un problème dans la fonction add_to_list.
</div>
</div></blockquote>
Réparé, merci pour l'info. Effectivement, j'ai tout codé directement sur Meli, donc j'ai pas pu tester ^^'

Azad

Merci du cours, c'est pratique la continuité linéraire des différents tutoriels. (Haaaan, Alex fait des fautes dans ces cours !)

+1 rep

AlexMog

EDIT: correction de quelques erreurs.

Azad

Thanks, lesquels ?

AlexMog

Une petite erreur dans le dernier code qui faisait que seul le dernier élément de la liste était free.

NodeBB

[Cours #8] Listes chainées