Probleme de tri suivant 2 paramètresRésolu

Question

Bonsoir, je vous appelle &#224; l'aide parce que je n'arrive pas &#224; trier ma liste chain&#233;e correctement; je n'ai pas trouv&#233; de solution &#224; mon probl&#232;me sur le site. Ce serai sympa de votre part si vous pouviez m'aider.

voila comment est d&#233;finie ma structure:

struct point {
 int indiceligne;
 int indicecolonne;
 int F; // F = G + H
 int G; // distance du point de depart au point courant
 int H; // distance Manhattan pour aller jusqu'au point destination
 int traite;// 0 si non trait&#233; et 1 si trait&#233;
 struct point *suivant;
};


struct point *ListeOuverte = NULL;

mon prog de tri :
// On trie en meme temps qu'on ajoute des points
void AjoutePointListeOuverte (int i, int j, float G, float H) {
 struct point *p;


 p = (struct point *) malloc(sizeof(struct point));
 (*p).indiceligne = i;
 (*p).indicecolonne = j;
 (*p).F = G + H;
 (*p).G = G;
 (*p).H = H;
 (*p).suivant = NULL;


 if (ListeOuverte == NULL)
  ListeOuverte = p;
 else {
  struct point *pcourant = ListeOuverte;
  struct point *pprecedent = ListeOuverte;
  while (((*pcourant).suivant != NULL) && ((*pcourant).F <= (*p).F))  {
   pprecedent = pcourant;
   pcourant = (*pcourant).suivant;
  }
  if ((*pcourant).suivant == NULL) {
   if ((*p).F >= (*pcourant).F)
    (*pcourant).suivant = p; // fin de liste
   else
    if ((pprecedent == ListeOuverte) && ((*p).F < (*ListeOuverte).F)){
     (*p).suivant = ListeOuverte; // debut de liste
     ListeOuverte = p;
    }
    else {
     (*pprecedent).suivant = p;
     (*p).suivant = pcourant;
    }  }
  else {
   if ((pprecedent == ListeOuverte) && ((*p).F < (*ListeOuverte).F)) {
    (*p).suivant = ListeOuverte; // debut de liste
    ListeOuverte = p;
   }
   else {
    (*pprecedent).suivant = p;
    (*p).suivant = pcourant;
   }  } }}

Le probl&#232;me est que dans mon tri, quand j'ai deux F &#233;gaux, je voudrais trier ces elements par valeur de int traite, les '0' en premier.
(je travaille sous visual c++6 et je suis d&#233;butant en c et c++)
 pouvez vous m'aider? merci d'avance

luhtor · Accepted Answer

Bon deja, remplace ca  (*p).H par ca: p->H, ca sera bcp plus lisible dans ton programme.



Et ca veut dire quoi ca: "je voudrais trier ces elements par valeur de int traite".

En enfin, soit explique mieux, soit commente ton programme, car c'est illisible la :)

Gam_z64 · Answer

// On trie en meme temps qu'on ajoute des points void AjoutePointListeOuverte (int i, int j, float G, float H) { struct point *p; p = (struct point *) malloc(sizeof(struct point)); (*p).indiceligne = i; (*p).indicecolonne = j; (*p).F = G + H; (*p).G = G; (*p).H = H; (*p).traite=0; (*p).suivant = NULL; if (ListeOuverte == NULL) ListeOuverte = p; else { struct point *pcourant = ListeOuverte; struct point *pprecedent = ListeOuverte; while ((pcourant -> suivant != NULL) && (pcourant -> F <= p -> F)) { pprecedent = pcourant; pcourant = pcourant -> suivant; } if (pcourant -> suivant == NULL) { if (p -> F >= pcourant -> F) pcourant -> suivant = p; // range en fin de liste else if ((pprecedent == ListeOuverte) && (p -> F < ListeOuverte -> F)){ p -> suivant = ListeOuverte; // range en debut de liste ListeOuverte = p; } else { pprecedent -> suivant = p; p -> suivant = pcourant; } } else { if ((pprecedent == ListeOuverte) && (p -> F < ListeOuverte -> F)) { p -> suivant = ListeOuverte; // range en debut de liste ListeOuverte = p; } else { pprecedent -> suivant = p; p -> suivant = pcourant; } } } } Je voudrais que la liste soit rangée de telle sorte que les elements ayant int traite=0 soent en haut (trié par F croissant) et les elements avec int traite=1 en bas de la liste (trié par F croissant) Merci

luhtor · Answer

Le pb, c'est que tu veux tout faire en meme temps. Cr&#233;er une fonction
qui permute deux &#233;l&#233;ments, ca permettra d'avoir une fonction de tri
plus lisible. Ou peut etre une fonction qui permet de d&#233;placer un
&#233;l&#233;ment de ta liste chainer.



Apres, c'est plus simple pour ton tri, t'as juste a maintenir deux
compteurs pour le d&#233;but, et la fin de la liste. Quand tu rajoutes des
&#233;l&#233;ments, tu as juste a les ajouter apr&#232;s/avant le compteur.

Gam_z64 · Answer

Ok merci, quelqu'un m'a dit la meme chose de faire une fonction qui compare deux &#233;lements et de trier ; j'essaie de le faire.
Un grand merci encore

Probleme de tri suivant 2 paramètres

4 réponses

Votre réponse

Discussions similaires