[C] Swaper les maillons d'une liste chainees ! Help

Swaper les maillons d'une liste chainees ! Help [C] - C - Programmation

Marsh Posté le 08-01-2012 à 16:32:41    

Bonjour,
 
J'aimerai une petite explication sur les listes chainees, notion que je ne maitrise pas tres bien.
 
Je voudrai swapper deux elements de ma liste, comment faire ?
 
Comment je peux acceder a tel ou tel maillon de ma liste ?
 
Merci d'avances pour vos reponses.

Reply

Marsh Posté le 08-01-2012 à 16:32:41   

Reply

Marsh Posté le 08-01-2012 à 17:42:10    

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 :
  1. struct s_elem {
  2.     char nom[10];
  3.     char prenom[10];
  4.     struct s_elem *next;
  5. } 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 :
  1. t_elem *cur;
  2. for (cur=premier; cur->next != NULL; cur=cur->next)
  3. {
  4.     if (cur->... == valeur attendue)
  5.         faire ce qu'on doit
  6. }


 
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 :
  1. struct {
  2.     struct t_elem *prem;
  3. } 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...

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed