Tri à bulle sur liste chainée

**Cisman** · 05/04/2018, 19h17

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 :

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
 
#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 :

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

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

**dalfab** · 05/04/2018, 22h30

Bonjour,

Je ne sais pas si la fonction permut() plante, mais une chose sûre c'est qu'elle ne permute pas.
Avec les pointeurs, il faut toujours faire un dessin
Nom : avant.png
Affichages : 3694
Taille : 2,7 Ko

Nom : avant.png
Affichages : 3694
Taille : 2,7 Ko

Avec ces deux pointeurs elt1 et elt2, comment arriver à un échange des éléments? En jaune les pointeurs qui ont dus être modifiés pour arriver à la permutation.
Nom : apres.png
Affichages : 3563
Taille : 4,2 Ko

Nom : apres.png
Affichages : 3563
Taille : 4,2 Ko

Je ne vois aucune possibilité. On pourrais utiliser à la place une interface à un seul paramètre pour permut()!

Code :

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

void echanger2EtudiantsSuccessifs( Etudiant **adrPtrPremEtud );

**Sve@r** · 06/04/2018, 00h10

Bonjour

Envoyé par Cisman

ce qui n'est pas le but avec une liste chainée.

Ben surtout le but d'une liste chainée est d'être toujours triée (tout nouvel élément venant s'insérer à sa bonne place dans la liste). Surtout que face à un tableau, c'est son seul avantage...

Envoyé par Cisman

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

Il est tout à fait possible d'avoir une liste chainée sur n critères, chaque critère géré par un pointeur différent. Ensuite, lors de l'insertion, on passe l'algorithme d'insertion pour chaque pointeur selon le critère du pointeur traité
Ainsi les (par exemple) items suivants

0x10 Victor Hugo 60
0x20 Amadéus Mozart 40
0x30 Arthur Rimbaud 35

Seraient chainés selon les critères suivants

le nom: 0x10 - 0x20 - 0x30
le prénom: 0x20 - 0x30 - 0x10
l'age: 0x30 - 0x20 - 0x10

Cela donnerait alors la liste suivante

tete_nom=0x10 tete_prenom=0x20 tete_age=0x30
0x10 Victor Hugo 60 next_nom=0x20 next_prenom=NULL next_age=NULL
0x20 Amadéus Mozart 40 next_nom=0x30 next_prenom=0x30 next_age=0x10
0x30 Arthur Rimbaud 35 next_nom=NULL next_prenom=0x10 next_age=0x20

Envoyé par Cisman

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.

Il est moins qu'optimal, il est totalement inutile...

**Cisman** · 06/04/2018, 14h32

Bonjour

Je ne vois aucune possibilité. On pourrais utiliser à la place une interface à un seul paramètre pour permut()!

C'est pour ça que je crée un élément temporaire.
Dans tes dessins, tu n'utilises que 2 éléments passé en paramètre?

**Cisman** · 06/04/2018, 14h52

Envoyé par Sve@r

Il est moins qu'optimal, il est totalement inutile...

C'est vrai que avec ce système, le tri deviens totalement inutile. Mes consignes sont:
Afficher les étudiants d'une section déterminée

par ordre Alphabétique
par ordre en Fct des résultats
les échecs
mes réussite

Maintenant je crois que mon prof s'en fou de la façon dont c'est trié, du moment que j'arrive à les afficher correctement.

Que je comprenne bien ton résonnement, les 0x10, 0x20 et 0x30 représente des pointeurs?

**Sve@r** · 06/04/2018, 17h39

Envoyé par Cisman

Que je comprenne bien ton résonnement, les 0x10, 0x20 et 0x30 représente des pointeurs?

Soyons précis. Un pointeur est un type en C permettant de stocker une adresse. 0x10, 0x20 et 0x30 ne sont pas des pointeurs, ce sont des adresses. Et elles représentent effectivement les adresses mémoire de mes 3 personnages.
Et si tu pars de chaque tête (tete_nom, tete_prenom et tete_age) et que tu suis chaque adresse qui est indiquée, en passant ensuite à la next de sa catégorie, tu retrouves les 3 personnages triés par le nom, le prénom ou l'age...

Envoyé par Cisman

Mes consignes sont:
Afficher les étudiants d'une section déterminée

par ordre Alphabétique
par ordre en Fct des résultats
les échecs
mes réussite

Maintenant je crois que mon prof s'en fou de la façon dont c'est trié, du moment que j'arrive à les afficher correctement.

Je ne vois même pas qu'il soit imposé une liste chainée là dedans.

Donc si tu n'es pas imposé aux listes chainées ; et si tu as le droit d'utiliser des outils déjà existants comme qsort(), alors tu n'as même plus à t'enquiquiner pour le tri. Tu génères un tableau d'étudiants (chaque étudiant encapsulé dans une structure adaptée) et tu passes ce tableau à qsort() à chaque fois que tu veux un tri spécifique. Faut juste que tu programmes les fonctions comparer deux noms, comparer deux résultats, comparer deux échecs, comparer deux réussites) et à chaque tri spécifique, tu passes à qsort() la fonction de comparaison dédiée au critère associé...

**dalfab** · 06/04/2018, 17h50

Envoyé par Cisman

Dans tes dessins, tu n'utilises que 2 éléments passé en paramètre?

C'est ce qui correspond à ton code. On voit qu'il n'est pas possible d'échanger les deux éléments.
L'interface de fonction que je propose se dessine comme cela :
Nom : avant2.png
Affichages : 3430
Taille : 2,7 Ko

Nom : avant2.png
Affichages : 3430
Taille : 2,7 Ko

On doit passer en paramètre, non pas une variable pointant sur le 1^er élément, mais l'adresse de ce qui effectivement pointe sur le 1^er élément. La fonction dispose alors de tout le nécessaire pour échanger les 2 éléments.

**Cisman** · 06/04/2018, 18h56

Envoyé par Sve@r

Je ne vois même pas qu'il soit imposé une liste chainée là dedans.

Disons qu'il ne nous a pas imposé les listes chainées, pour ne pas mettre en échec celui qui ne les maitrise pas, ça lui laisse une chance.
Je trouve les listes chainées mieux adapté a une gestion d'étudiant dans une école, et c'est comme ça que cela nous à été présenté au cours, ajout facile, mémoire géré de façons plus dynamique et sans pour autant devoir mettre mes structures étudiants dans un tableau de manière contigüe dans la mémoire (s'il y a 2000 élèves dans l'école!)
Maintenant, je peux utiliser les outils existants et donc c'est vrai que pour trier une section ou une classe par résultat ou autre, j'aurai plus facile de tout mettre dans un tableau, en plus c'est quelque chose que j'ai déjà fait.
Et pour le moment, je maitrise mieux les tableaux que les listes, Je crois que je vais utilisé les deux, j'insère mes noms dans la liste par ordre alphabétique (fonctionne déjà) et pour le tri, j'utiliserai un tableau et qsort().

**Cisman** · 06/04/2018, 19h00

Envoyé par dalfab

C'est ce qui correspond à ton code. On voit qu'il n'est pas possible d'échanger les deux éléments.

Quand je regarde ma fonction permut, je lui passe bien deux paramètres, mais dans la fonction, j'en déclare et initialise un troisième (temp).

**Sve@r** · 06/04/2018, 19h22

Envoyé par Cisman

Code c :

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

1
2
3
4
5
6
void permut(Etudiant *elt1, Etudiant *elt2)
{
    Etudiant *eltTemp = elt1->next;
    elt1->next = elt2->next;
    elt2->next = eltTemp;
}

Quand je regarde ma fonction permut, je lui passe bien deux paramètres, mais dans la fonction, j'en déclare et initialise un troisième (temp).

Euh... ça ne peut pas fonctionner. Une permutation de deux éléments met en jeu 3 éléments !!! Tu oublies l'élément précédent le premier à permuter.

Imaginons par exemple 4 items Pierre (0x10), Paul (0x20), Jacques (0x30) et Amélie (0x40); avec le chainage suivant

tete=0x10
0x10 Pierre, next=0x20
0x20 Paul, next=0x30
0x30 Jacques, next=0x40
0x40 Amélie, next=NULL

(comme ça, au-moins, le chainage n'est pas compliqué à suivre et cela ne change rien à la démo).

Maintenant, tu veux échanger Paul et Jacques. Tu appelles donc permut(0x20, 0x30). La fonction échange chaque next de l'un par l'autre. Le next de Paul passe à 0x40 (Amélie, ce qui est correct) mais le next de Jacques passe 0x30 donc lui-même !!!
Par ailleurs, le next de Pierre, lui, il n'a pas changé (alors qu'il aurait dû !!!). Et tu te retrouves avec le chainage suivant

tete=0x10
0x10 Pierre, next=0x20
0x20 Paul, next=0x40
0x30 Jacques, next=0x30
0x40 Amélie, next=NULL

Là, tu remarqueras que l'adresse 0x30 n'étant plus dans aucun next, on a perdu Jacques ; sauf pour lui-même qui se fait sa propre liste autobouclante mais qu'on ne peut jamais atteindre (petite île perdue dans la RAM).
Hé oui, pas facile facile tout ça...