Discussion :

[GLDavid]

Bonjour à tous

Je travaille sur une liste chaînée. Or, je veux faire un premier tri de cette liste chaînée pour ne retenir que les maillons qui répondent à un critère. Ainsi, je voudrais recréer une autre liste chaînée résultat qui contiendrait tous les éléments qui ont passé avec succès le test. Je ne cherche pas du code, mais plutôt les idées maîtresses pour réaliser une fonction de ce genre, cela fait un bail que j'ai plus fait de liste chaînée

Merci d'avance de votre aide.

@++

[Biosox]

Moi je ferais comme ça:

Tu parcours ta première liste chainée dans l'ordre, en créant une deuxième liste mais dans laquelle tu ne mets que les éléments qui répondent au critère:

1) tu parcours la liste 1 à la recherche du premier élément qui répond au critère. Des qu'il est trouvé,tu le copie (sauf la valeur du pointeur vers le suivant puisqu'on ne connait pas encore le suivant. donc cette valeur doit pour l'instant etre NULL, car peut-etre qu'il n'y aura aucun suivant), et la copie devient la "racine" de ta liste 2.

rappel: chaque élément contient un pointeur vers le suivant. (ou 2 pointeurs, un vers le suivant un vers le précédent) Si un pointeur vaut NULL, on considère qu'on est à la fin de la liste (c'est une façon de faire)

2) maintenant tu boucles jusqu'à la fin de liste 1:
l'element que tu vient de crée lors d'une copie devient "elemPrecedent"
- cherche dans la liste 1 le prochain élément répondant au critère
- une fois trouvé, tu le copies en créant un "elemActuel" (ne copie pas le pointeur vers le suivant, init le é NULL de nouveau)
- tu peux enfin initialiser la valeur du "pointeur vers élément suivant" de "elemPrecedant" en lui mettant l'adresse de "elemActuel"


et voila. j'espère avoir été assez clair.

[gege2061]

Salut

Moi je ferais comme ça:

ça me parrai bien compliqué!

Un p'tit bout de code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
while (list)
{
  if (test (list->data))
  {
    list2->add (list->data);
  }
  list = list->next;
}

Avec bien sur list la liste à triée et list2 la nouvelle liste contenant uniquement les maillons dont test (list->data) est vérifier.

Ta question a surement plus sa place dans le forum algo, non ?

[GLDavid]

Salut

Merci à tous de vos réponses. Je vais tenter celle de Gégé.
Merci encore

@++