Tri par insertion dans une liste chaînée

Signaler
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007
-
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007
-
Bonjour,

j'ai un problème avec une liste chaînée.
j'ai une liste d'element que j'arrive a récupéré mais je souhaiterai que lorsque je récupère un element il soit inséré directement dans la liste chainée et que se soit trié au fur et a mesur pour qu'à la fin je n'obtienne plus que la liste a affiché directement.

je développe en C++.

Si quelqu'un a un pti bout de code a me passer sa serait sympa.

A l'avance merci

19 réponses

Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Salut, ta liste chainée c'est <list> de la STL ?, un conteneur qui tri les objets insérés : <set> (comme les <map> : par defaut bool operator < a implemeter (std::less)  )

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

Oula, je souhaite pas faire un truc compliqué!
je veux juste que lorsque que j'ai un élément je parcours la liste afin de le placer au bonne endroit, je pense qu'avec une fonction ou mm pas sa doit fonctionné.

Merci quand même
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
il n'ya rien de complique :
#include <set>

class MaClasse
{
public :
....
    bool operator < (const MaClasse& maClasse)
    {
          return _identifiant < maClasse._identifiant;
    }
....
private
    int _identifaint;
};

typedef std::set<MaClasse> SetMaClasse; // optionnel bien sur....

A savoir par contre que tu ne peux pas insérer deux fois le meme objet

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

sa na va pas aller ta colution alors car il sepeut que j'ai plusieurs fois le mm numéro:

exemple de ma liste :
nom    code_erreur
titi         2
toto      2 
tutu      3

Donc voila ma liste et je veux classé par ordre croissant le code erreur avec le nom associé dans une liste chainée  .

Voila exactement ce que je veux faire.
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Pardon "deux fois le meme objet" au sens de l'operator <.   Si maClasse1._identifiant 3 et maClasse2._identifiant 3, un seul des deux objets pourra etre inséré.Si maClasse1._identifiant 3 on l'insere. maClasse1._identifiant2 et on l'insere, l'objet est insere 2 fois (mais ce ne sera pas le meme car copie de l'objet).

:D
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Ok, alors utilise les multimap.

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

Je pense qu'on doit pas bien se comprendre donc je ré explique :
j'ai une liste d'élement :
nom      code
titi            5
tutu         8
tata         4

ensuite je récupére chaque ligne et je voudrai l'insérer dans une liste chainée mais qui est trié à l'insertion de chaque nouveau objet.

et donc a la fin du dernier element je puisse ré afficher ma liste qui a été trié automatiquement

nom       code
tata         4
titi         5
tutu      8

Merci quand même
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
#include <map>

typedef std::multimap XXXXX; // ceci semble convenir pour ton exemple

les map sont triées sur la clé (ici int), et les multimap permettent d'avoir plusieurs fois la meme clé.

:D
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Désolé c'est parce que l'on poste en meme temps....

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

Mais je ne veux pas utiliser de map ni rien
juste prendre mon element le comparer a ceux qui sont déja dans la liste si mon
code <code suivant je l'insere dans la liste chainée c'est tout
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
et euh pardon il y a les multiset aussi, a toi de voir le conteneur qui te convient le mieux... (multiset c les set avec element multiple "autorisé")

:D
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Bon ben parcours ta liste et insère tes éléments....

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

ba justement je ne C pa comment faire C bien la le probleme.
je voudrai la parcourir et insérer ou il faut .

voila ce que je cherche a faire
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Oui bien justement la STL fourni toutes ces choses. Donc si ta liste chainée est une std::list, utilise la fonction std::sort sur les iterateurs de ta liste. Mais visiblement ce n'est pas le cas, donc je suppose que tu as tout redefini a ce moment la, poste les parties de ton code qu'il faut connaitre pour résoudre ton problème.

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

class element
{
   public : int code;
              char nom[20];
}

main()
{
   int count =10;
     element *list=NULL;
   element *elem;
   for (int i=0 ; i<count ; i++)
 {
      elem=new element;
   //C'est dans cette boucle que je voudrai insérer mon nouvelle élement dans ma liste chainée mais j'ai un gro problème avec ceux ci lol

   
 }
}

Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
ok et la définition de la liste chainée ?

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

C ma class element
Messages postés
326
Date d'inscription
vendredi 13 août 2004
Statut
Membre
Dernière intervention
2 novembre 2007
2
Tu veux dire qu'un élément a un pointeur sur le suivant et le précédent (doublement chainé ?) ?

:D
Messages postés
42
Date d'inscription
mardi 20 décembre 2005
Statut
Membre
Dernière intervention
30 mars 2007

Ba je pense qu'il va faloir que je fasse comme ceci car avec un pointeur je ne peux pas m'en sortir enfin je pense, la je suis perdue quand même.