Discussion :

[badack]

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 :

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

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 :

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

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
Avez vous quelques idées pour me sortir de ce gouffre?

Code :

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

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,

[souviron34]

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...

[Emmanuel Delahaye]

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.

[badack]

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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

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 :

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

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

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

Code :

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

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

Je fais ma comparaison.

Code :

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

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 :

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

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 :

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

1
2
 
pePremier = pePremier->suivant;

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

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

[Emmanuel Delahaye]

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 :

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

struct node *tri (struct node *p);

et ça s'utilise :

Code :

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

   list = tri (list);

[badack]

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.

[badack]

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

Code :

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

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;
}