Salut
Toutes les réponses de ce forum ne seront pas grand chose face à un vrai tuto comme on peut en trouver de partout.
Une liste chainée c'est un concept informatique permettant de garder un ensemble trié tout en facilitant une insertion ultérieure.
Déjà ici il faut bien se dire que si l'ensemble n'a pas besoin de tri, alors il n'est pas nécessaire d'utiliser une liste chainée et un simple tableau (bien plus rapide) suffit.
Donc une liste se caractérise par ce qu'on appelle un "maillon" ou "noeud". C'est l'entité qui permet de stocker un élément de l'ensemble.
De plus, ce maillon possède un lien vers le maillon suivant (la notion "suivant" est totalement liée à l'idée que s'en fait le programmeur)
Exemple: maillon pour une liste permettant de gérer des gens (nom, prenom)
Code :
- struct s_elem {
- char nom[10];
- char prenom[10];
- struct s_elem *next;
- } t_elem;
|
Le dernier maillon de la liste ayant sa valeur "next" positionnée à NULL par convention.
Une fois qu'on maitrise bien le maillon, et qu'on arrive à bien conceptualiser le truc, le reste n'est que de la logique.
Donc pour swapper 2 maillons A et B il suffit de
1) se placer sur le maillon précédant A (on va le nommer pA)
2) se placer sur le maillon précédant B (on va le nommer pB)
3) positionner pA->next sur B et positionner pB->next sur A
4) positionner A->next sur b->next et b->next sur a->next
Accessoirement swapper 2 maillons cela ne se fait jamais puisque cela veut dire que la liste n'est pas triée ce qui signifie qu'on n'a pas besoin de liste
Pour accéder à un élément de la liste, il suffit de faire une boucle
Code :
- t_elem *cur;
- for (cur=premier; cur->next != NULL; cur=cur->next)
- {
- if (cur->... == valeur attendue)
- faire ce qu'on doit
- }
|
Dernier détail: pour tenir une liste il suffit de tenir son premier maillon. Toutefois, l'expérience montre qu'il peut être judicieux de créer une structure dédiée
Code :
- struct {
- struct t_elem *prem;
- } t_liste;
|
Ca peut paraitre idiot de créer une structure pour juste un seul élément mais cela a des avantages qu'on comprend quand on se met à manipuler des listes. Par exemple on peut ensuite rajouter facilement d'autres outils comme un compteur d'éléments, un pointeur vers l'élément courant, un pointeur vers le dernier, etc...
