1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : septembre 2017
    Messages : 39
    Points : 24
    Points
    24

    Par défaut 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 : 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.

  2. #2
    Membre expert
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    décembre 2015
    Messages
    750
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2015
    Messages : 750
    Points : 3 757
    Points
    3 757

    Par défaut

    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 : 52
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 : 54
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 );

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 340
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 340
    Points : 17 802
    Points
    17 802
    Billets dans le blog
    1

    Par défaut

    Bonjour
    Citation Envoyé par Cisman Voir le message
    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...

    Citation Envoyé par Cisman Voir le message
    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


    Citation Envoyé par Cisman Voir le message
    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...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  4. #4
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : septembre 2017
    Messages : 39
    Points : 24
    Points
    24

    Par défaut

    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?

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : septembre 2017
    Messages : 39
    Points : 24
    Points
    24

    Par défaut

    Citation Envoyé par Sve@r Voir le message
    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?

  6. #6
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 340
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 340
    Points : 17 802
    Points
    17 802
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Cisman Voir le message
    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...

    Citation Envoyé par Cisman Voir le message
    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é...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  7. #7
    Membre expert
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    décembre 2015
    Messages
    750
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2015
    Messages : 750
    Points : 3 757
    Points
    3 757

    Par défaut

    Citation Envoyé par Cisman Voir le message
    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 : 33
Taille : 2,7 Ko
    On doit passer en paramètre, non pas une variable pointant sur le 1er élément, mais l'adresse de ce qui effectivement pointe sur le 1er élément. La fonction dispose alors de tout le nécessaire pour échanger les 2 éléments.

  8. #8
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : septembre 2017
    Messages : 39
    Points : 24
    Points
    24

    Par défaut

    Citation Envoyé par Sve@r Voir le message
    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().

  9. #9
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : septembre 2017
    Messages : 39
    Points : 24
    Points
    24

    Par défaut

    Citation Envoyé par dalfab Voir le message
    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).

  10. #10
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 340
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 340
    Points : 17 802
    Points
    17 802
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Cisman Voir le message
    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...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  11. #11
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : septembre 2017
    Messages : 39
    Points : 24
    Points
    24

    Par défaut

    Citation Envoyé par Sve@r Voir le message
    Hé oui, pas facile facile tout ça...
    Effectivement pas facile!
    Mais tes explications très bien expliquées, me permettent d'y voir plus clair dans la manipulation de listes chainées.
    ça m'ouvre les yeux

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Tri à bulle avec liste chainée
    Par Shol4891 dans le forum Algorithmes et structures de données
    Réponses: 12
    Dernier message: 14/02/2018, 12h23
  2. Comparaison sur liste chainée
    Par calagan dans le forum C
    Réponses: 9
    Dernier message: 24/07/2007, 21h58
  3. Tri sur liste chainée
    Par SevSof dans le forum C
    Réponses: 16
    Dernier message: 27/05/2007, 00h45
  4. Tri rapide de liste chainée
    Par A_B dans le forum C
    Réponses: 7
    Dernier message: 16/04/2007, 23h26
  5. [Débutant] Pointeur sur liste chainée
    Par HaTnuX dans le forum C
    Réponses: 2
    Dernier message: 02/12/2006, 17h53

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo