Tri d'une structure avec ptr sur void

Bonjour à tous,

je vous expose mon problème:

voici une fonction qui recoit en paramètre une liste doublement chainée (bornes*).

Cette liste comprend des elements définit comme suit:

Code:

---

1 2 3 4 5 6 7

struct element { void* type; element* suivant; element* precedent }; element* PElement;

---

Le pointeur sur void type recoit une structure définit comme suit:

Code:

---

1 2 3 4 5 6

struct participant{ ...... int pointsQualif; ..... };

---

Mon problème est que je n'arrive pas à trier cette liste donné en paramètre en fonction des pointsQualif. J'ai voulu implémenter un tri à bulle mais je dois me planter quelques part et je ne vois pas où.
Pour être complet, la liste passé en paramètre est correctement constituée.
Mon idée est de trier cette liste sur les pointsQualif, donc je pensais pouvoir, une fois comparé, juste échanger les adresses présentes dans les variables type. Mais ca coince 8O
Avez vous quelques idées pour me sortir de ce gouffre?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

bornes* triPtsQualification(bornes* lst){ int cpt, courant, debug; int inversion,longueur;   longueur = NombreDElements(lst);   participant* paPremier = (participant*) malloc (sizeof(participant)); participant* paSecond = (participant*) malloc (sizeof(participant));   PElement pePremier = (PElement) malloc (sizeof(element)); PElement peSecond = (PElement) malloc (sizeof(element)); PElement peTampon = (PElement) malloc (sizeof(element));   pePremier = lst->premier; //peSecond = pePremier->suivant; debug = 0; do{ inversion = 0; debug++; for(courant = 0; courant<longueur-1; courant++){ paPremier = (participant*) pePremier->type; paSecond = (participant*) pePremier->suivant->type; if(paPremier->pointsQualif > paSecond->pointsQualif){ peTampon->type = pePremier->type; pePremier->type = peSecond->type; peSecond->type = peTampon->type; inversion = 1; } paPremier = (participant*) malloc (sizeof(participant)); paSecond = (participant*) malloc (sizeof(participant)); pePremier = pePremier->suivant; longueur--; }   }while(inversion == 1); return lst; }

---

Merci à tous,

je crois qu'il faut activement que tu révises les cours de tri.... Et d'algorithmie,..

Ecris en clair, sur du papier, ce que tu veux faire, et ça t'apparaîtra tout simplement.

Là tu fais du gros n'importe quoi, avec des allocations etc...

Tu veux faire du tri.. Il n'y a pas d'allocations. Juste un ré-arrangement des choses...

Citation:

---

Envoyé par souviron34

Tu veux faire du tri.. Il n'y a pas d'allocations. Juste un ré-arrangement des choses...

---

Ca dépend des algorithmes...

EDIT : Ah, liste chainée. OK. Pas d'allocation.

Je m'étais représenté le problème comme suis:

- Ma liste (bornes) comprend des cellules (element)
- Chaque cellules à un pointeur sur void
- Ce pointeur sur void contient l'adresse d'une structure de type participant
- Mon tri doit se baser sur la variable PointsQualif se trouvant dans ma structure participant
- Je compare donc pour 2 cellules les variables PointsQualif se trouvant dans les structures participant resectif.

Code:

---

1 2	paPremier->pointsQualif > paSecond->pointsQualif

---

- Si échange il doit avoir, alors j'inverse les adresses présentent dans mes pointeurs sur void (type) de mes cellules.

L'algorithme que j'ai utilisé ici est un tri à bulle.

Au niveau de mes allocations mémoires, elles sont peut être mauvaise, mais voici ce que je comprend de mon implémentation:

Code:

---

1 2 3

participant* paPremier = (participant*) malloc (sizeof(participant)); participant* paSecond = (participant*) malloc (sizeof(participant));

---

Ici, je crée 2 variables de type participant pointant vers une structure participant.

Code:

---

1 2 3 4

PElement pePremier = (PElement) malloc (sizeof(element)); PElement peSecond = (PElement) malloc (sizeof(element)); PElement peTampon = (PElement) malloc (sizeof(element));

---

Ici, je crée 3 variables de type element pointant vers une structure element. C'est avec ces structures et leur variable type que je vais réaliser l'échange.

Code:

---

1 2	pePremier = lst->premier;

---

Je prend le premier élément de ma liste et je l'assigne à ma variable de type élément pePRemier.

Code:

---

1 2	for(courant = 0; courant<longueur-1; courant++){

---

Je vais compter jusque quand j'arrive aux nombre d'éléments de ma liste -1.

Code:

---

1 2	paPremier = (participant*) pePremier->type;

---

De pePremier, je cast ce qui est dans ma variable type en participant et je l'assigne paPremier. Je peux donc travailler sur ma structure participant et ses variables.

Code:

---

1 2	paSecond = (participant*) pePremier->suivant->type;

---

Je vais caster dans paSecond, l'élément suivant de pePremier.

Code:

---

1 2	if(paPremier->pointsQualif > paSecond->pointsQualif){

---

Je fais ma comparaison.

Code:

---

1 2 3 4 5 6

peTampon->type = pePremier->type; pePremier->type = peSecond->type; peSecond->type = peTampon->type; inversion = 1;

---

Si paPremier->pointsQualif est plus gand que paSecond->pointsQualif, alors je permutte les adresses présentent dans pePremier->type et peSecond->Type.

Code:

---

1 2 3

paPremier = (participant*) malloc (sizeof(participant)); paSecond = (participant*) malloc (sizeof(participant));

---

Ici, je réinitialise mes 2 variables paPremier et paSecond en allouant une nouvelle adresse mémoire.

Code:

---

1 2	pePremier = pePremier->suivant;

---

Je passe à l'élément suivant de ma liste.

Voilà, où est ce que ma logique coince :oops:
Merci de votre patience.

Citation:

---

Envoyé par badack

Je m'étais représenté le problème comme suis:

---

Bzzt... Pour trier une liste chainée, tu définis un nouvelle 'tête' (un pointeur du même type que les éléments de la liste) pointant sur NULL (liste vide) et tu fais un déplacement ordonné dans la nouvelle liste. C'est tout. Les listes ne se traitent pas comme les tableaux.

Voici ce qui va se passer :

liste > a > c > b > NIL
temp > NIL

liste > c > b > NIL
temp > a > NIL

liste > b > NIL
temp > a > c > NIL

liste > NIL
temp > a > b > c > NIL

liste > a > b > c > NIL
temp > NIL

terminé.

A toi d'écrire la fonction qui parcours l'ancienne liste, retire ses éléments un à un et le place au bon endroit dans la nouvelle liste. Quand c'est terminé, il suffit que le pointeur de tête de l'ancienne liste pointe sur la nouvelle et on a plus besoin du pointeur de la nouvelle liste.

Code:

---

struct node *tri (struct node *p);

---

et ça s'utilise :

Code:

---

list = tri (list);

---

Merci Emmanuel,

les remises en questions ne sont pas toujours évidente quand on a le nez dans le mur, mais ton explication ma permis de comprendre mon erreur de logique.

J'ai donc écris une fonction extraireElement et une autre InsereElement. Je n'ai plus qu'à les emboiter dans la logique de tri.

8-) Voilà, j'ai revus mon code et ca fonctionne à merveille. Voici pour ceux que ca intéresse et tout commentaire est le bienvenu.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

bornes* triPtsQualification(bornes* lst){   int insere; bornes* lstTrie = (bornes*) malloc (sizeof(bornes)); PElement curseur_lst = NULL; PElement curseur_lstTrie = NULL;   Init(lstTrie);   while(ListeVide(lst) != 1){ curseur_lst = lst->premier; if(ListeVide(lstTrie)){ //Si la liste des éléments triés est vide AjouterEnDebutDeListe(lstTrie,ExtraireElement(lst,curseur_lst)); }else if(NombreDElements(lstTrie) == 1){ //Si la liste des éléments triès ne comporte qu'un seul élément curseur_lstTrie = lstTrie->premier; if(((participant*)curseur_lst->type)->pointsQualif < ((participant*)curseur_lstTrie->type)->pointsQualif){ AjouterDansListeAvant(lstTrie,curseur_lstTrie,ExtraireElement(lst,curseur_lst)); }else{ AjouterDansListeApres(lstTrie,curseur_lstTrie,ExtraireElement(lst,curseur_lst)); } }else{ //Si la liste des éléments triès comporte plusieurs éléments curseur_lstTrie = lstTrie->premier; insere = false; while(insere == false){ if(((participant*)curseur_lst->type)->pointsQualif < ((participant*)curseur_lstTrie->type)->pointsQualif){ AjouterDansListeAvant(lstTrie,curseur_lstTrie,ExtraireElement(lst,curseur_lst)); insere = true; }else if (curseur_lstTrie->suivant == NULL){ //Si c'est le dernier élément de la liste triée AjouterDansListeApres(lstTrie,curseur_lstTrie,ExtraireElement(lst,curseur_lst)); insere = true; }else{ curseur_lstTrie = curseur_lstTrie->suivant; } } } }   return lstTrie; }

---