AlexMog Posté(e) June 3, 2014 Signaler Share Posté(e) June 3, 2014 (modifié) 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) 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. typedef struct s_list { int taille; int age; struct s_list *next; }t_list; 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: 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); } Voici un exemple d'utilisation de la fonciton: 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); } III- Parcourons notre liste! Nous allons à présent parcourir notre liste. 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); } IV- Vidons notre liste! (C'est important de vider la mémoire!) Pour cela, créons une fonction de vidage. 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; } Exemple d'utilisation: 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); } 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! Modifié July 10, 2014 par AlexMog 3 Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
davydavek Posté(e) June 3, 2014 Signaler Share Posté(e) June 3, 2014 (modifié) 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. Modifié June 4, 2014 par davydavek Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
AlexMog Posté(e) June 3, 2014 Auteur Signaler Share Posté(e) June 3, 2014 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. Réparé, merci pour l'info. Effectivement, j'ai tout codé directement sur Meli, donc j'ai pas pu tester ^^' Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
Azad Posté(e) June 4, 2014 Signaler Share Posté(e) June 4, 2014 Merci du cours, c'est pratique la continuité linéraire des différents tutoriels.(Haaaan, Alex fait des fautes dans ces cours !) +1 rep Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
AlexMog Posté(e) July 10, 2014 Auteur Signaler Share Posté(e) July 10, 2014 EDIT: correction de quelques erreurs. Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
Azad Posté(e) July 11, 2014 Signaler Share Posté(e) July 11, 2014 Thanks, lesquels ? Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
AlexMog Posté(e) July 11, 2014 Auteur Signaler Share Posté(e) July 11, 2014 Une petite erreur dans le dernier code qui faisait que seul le dernier élément de la liste était free. Citer Lien vers le commentaire Partager sur d’autres sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.