Tri à bulle sur liste chainée
Bonjour,
j'essaie depuis ce matin d'exécuter un tri à bulle sur une liste simplement chainée.
Ce matin, je croyais que ça fonctionnais, mais en fait, je déplaçais d'un élément vers un autre la donné qui m'intéressait (à la bourrin), ce qui n'est pas le but avec une liste chainée.
Je voudrais arriver à déplacer les pointeurs vers les éléments (maillon). D'autant plus que la structure qui compose ma liste chainée contient différents types de variables (nom, prénom, année, section, côtes, etc...).
mon programme plante et je crois que ça viens de la fonction permut, mais sans certitudes.
Voici mon code:
enum.h
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
|
#ifndef ENUM_H
#define ENUM_H
typedef struct Etudiant Etudiant;
struct Etudiant
{
char nom[25];
int total;
Etudiant * next;//pointeur vers la structure Etudiant suivante
};
//insertion dans l'ordre alphabétique
Etudiant * ajoutAlpha(Etudiant * tete,char inom[], int *nb);
//Fct permutation de deux élt d'une liste
void permut(Etudiant *elt1, Etudiant *elt2);
//Fct tri à bulle sur liste chainée
void triBulle(Etudiant *tete);
//lire liste
void lireList(Etudiant * tete);
//libère mémoire
void freeList(Etudiant * tete);
#endif // ENUM_H |
Fct.c
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "enum.h"
//insertion dans l'ordre alphabétique
Etudiant * ajoutAlpha(Etudiant * tete,char inom[], int *nb)
{
Etudiant *temp = tete;
Etudiant *elt = NULL;
elt = malloc(sizeof(Etudiant));
if (elt == NULL)//test si allocation a fonctionné
{
printf("Mémoire insuffisante");
exit(99);
}
strcpy(elt->nom,inom);
elt->total = *nb;
if (temp == NULL) // si la liste est vide on renvoie elt
{
elt->next = NULL;
return elt;
}
else if( stricmp(temp->nom,inom) > 0 ) // si l'élément est a insérer en premier
{
elt->next=tete;
return elt;
}
else // si l'élément est a insérer au milieu ou a la fin
{
while ( temp->next != NULL && stricmp(temp->next->nom,inom) < 0 ) // on trouve l'endroit
{
temp = temp->next;
}
elt->next = temp->next;
temp->next = elt;
}
return tete;
}
//Fct permutation de deux élt d'une liste
void permut(Etudiant *elt1, Etudiant *elt2)
{
Etudiant *eltTemp = elt1->next;
elt1->next = elt2->next;
elt2->next = eltTemp;
}
//Fct tri à bulle sur liste chainée (décroissant)
void triBulle(Etudiant *tete)
{
int permutation;//variable booleen
Etudiant *elt = tete;
Etudiant *eltTemp = NULL;
/* test si liste est vide? */
if (elt == NULL)
return;
do
{
permutation = 0;//booleen init à 0
elt = tete;
while (elt->next != eltTemp)
{
if (elt->total < elt->next->total)//décroissant
{
permut(elt, elt->next);//appel Fct permut
permutation = 1;//si permut alors permutation à 1
}
elt = elt->next;
}
eltTemp = elt;
}
while (permutation);//tant qu'il y a permutation je boucle
}
//lire et afficher liste
void lireList(Etudiant * tete)
{
while (tete != NULL){
printf("%s - %d\n", tete->nom, tete->total);
tete = tete->next;
}
printf("---------------\n");
}
//libère la mémoire
void freeList(Etudiant * tete)
{
Etudiant * temp = NULL;
while (tete != NULL)
{
temp = tete;
tete = tete->next;
printf("free(%s %d)\n", temp->nom, temp->total);
free(temp);
}
printf("---------------\n");
} |
Et enfin mon main.c
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
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "enum.h"
int main()
{
Etudiant *teteListe = NULL;
int nb1=15,nb2=20,nb3=30,nb4=2,nb5=12,nb6=40;
int *ptnb1=&nb1, *ptnb2=&nb2, *ptnb3=&nb3, *ptnb4=&nb4, *ptnb5=&nb5, *ptnb6=&nb6;
teteListe = ajoutAlpha(teteListe,"Zoe", ptnb1);
lireList(teteListe);
teteListe = ajoutAlpha(teteListe,"Anne", ptnb2);
lireList(teteListe);
teteListe = ajoutAlpha(teteListe,"Luc", ptnb3);
lireList(teteListe);
teteListe = ajoutAlpha(teteListe,"Frederic", ptnb4);
teteListe = ajoutAlpha(teteListe,"Jean", ptnb5);
lireList(teteListe);
teteListe = ajoutAlpha(teteListe,"Sandrine", ptnb6);
lireList(teteListe);
triBulle(teteListe);
lireList(teteListe);
freeList(teteListe);
return 0;
} |
Voilà, si un œil plus expert que le mien trouvera peut-être mon erreur.
Encore une chose, je sais que le tri à bulle n'est pas optimal pour les listes chainées, mais je n'ai vu que celui-là et le tri par insertion.
