Discussion :

[Tziboun]

Bonjour à tous,

Je dois faire un programme qui trie une liste chainée double selont différents criteres. Pour commencer j'ai décidé de ne classer la liste chainnée que par nom.

Malheureusement je n'ai pas le résultat escompté.
Au moment de l'affichage, cela m'affiche le une ligne à l'infini.

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
 
 
LISTE *tri_insertion(LISTE *liste,char choix)
{
        LISTE *liste_triee; //liste toujours triée
        ENTREE *tmp;
        ENTREE *courant;
        liste_triee=creer_liste();
        while((liste->t)>1)
        {
            tmp=liste->first->next;
            courant=liste->first;
            while(courant!=NULL)
            {
                if(strcmp(courant->nom,tmp->nom)<0)
                {
                    tmp=courant;
                }
                courant=courant->next;
            }
 
            if(tmp->previous==NULL)
            {
                liste->first=tmp->next;
            }
            else
            {
                if(tmp->next==NULL)
                {
                    tmp->previous->next=NULL;
                }
                else
                {
                    tmp->previous->next=tmp->next;
                    tmp->next->previous=tmp->previous;
                }
            }
            ajoute_entree(tmp,liste_triee);
            liste->t--;
        }
        ajoute_entree(liste->first,liste_triee);
        return liste_triee;
}

et la fonction ajoute_entree :

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
 
void ajoute_entree(ENTREE *entree, LISTE *liste) // ajoute une entree à la fin d'une liste initialisee ou existante (cfr. creer_liste())
{
    //  (ne manipule pas les donnees).
    entree->previous=NULL;
    entree->next=NULL;
    if(liste->t==0)
    {
        liste->first=entree;
        entree->previous=NULL;
    }
    else
    {
        ENTREE *courant;
        ENTREE *previous;
        courant=liste->first;
        previous=liste->first;
        while(courant->next!=NULL)
        {
            courant=courant->next;
            if(courant->next==NULL)
            {
                previous=courant;
            }
        }
        courant->next=entree;
        entree->previous=previous;
    }
    liste->t++;
}

J'ai refait l'exercice en algorithme sur une feuille et ca m'a l'air bon donc je comprends pas où est mon érreur...
merci de votre aide...

[Neckara]

Bonjour,

Ligne 27 : entree->previous=courant; ?

[Tziboun]

C'est vrai que j'ai mis une condition pour rien ..^^

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
 
void ajoute_entree(ENTREE *entree, LISTE *liste) // ajoute une entree à la fin d'une liste initialisee ou existante (cfr. creer_liste())
{
    //  (ne manipule pas les donnees).
    entree->previous=NULL;
    entree->next=NULL;
    if(liste->t==0)
    {
        liste->first=entree;
        entree->previous=NULL;
    }
    else
    {
        ENTREE *courant;
        courant=liste->first;
        while(courant->next!=NULL)
        {
            courant=courant->next;
        }
        courant->next=entree;
        entree->previous=courant;
    }
    liste->t++;
}

.. C'est mieux comme ca , mais ca ne résout pas mon problème

[Tziboun]

Personne ne peut m'aider ?

[fred1599]

J'ai du mal à voir l'intérêt de choix.

il est difficile de donner des explications sans tes structures.

[Tziboun]

Sorry ce n'est pas très clair, en fait le parrametre choix ne sert à rien , je comptais l'implémenter après.

En fait les structures ont peu d'importance ici car je ne travaille qu'avec entree->nom pour commencer.

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
 
typedef struct entree
{
    char nom[30];
    char prenom[20];
    char initiales[6];
    char mail[30];
    char tel[20];
    char classe[20];
    struct entree *next;
    struct entree *previous;
} ENTREE;
 
typedef struct liste
{
    int t;
    struct entree *first;
} LISTE;

[fred1599]

Ok, il y a une fonction géniale permettant de faire cela assez rapidement.

1) Tu crées une fonction de comparaison

Quelquechose du genre

Code :

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

1
2
3
4
5
6
7
8
9
10
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   char const *const *pa = a;
   char const *const *pb = b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (*pa, *pb);
}

2) Tu utilises qsort dont le prototype est :

Code :

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

1
2
3
4
void qsort (void *tableau
            , size_t nb_elem
            , size_t taille_elem
            , int (*compare) (void const *a, void const *b));

qsort est une fonction qui permet de tout trier, y compris les chaînes de caractères.

En continuant sur l'exemple ça donnerait

Code :

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

qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);

[Tziboun]

Ca c'est une solution avec des tableaux, je dois garder ma liste chainée.
Il s'agit d'un exercice pour lécole etje dois le faire à l'aide de liste chainée, dailleurs après je vais implémenter un choix de critere selon lequel on veut effectuer le tri (nom, prenom ,...)

[Tziboun]

J'ai fini par refaire entrièrement la fonction de tri en la sous-divisant en sous-fonctions pour être sur de ne pas me tromper et pour faciliter un éventuel débugage et ...miracle , cela tourne très bien.

Voiçi le code si ca intéresse quelqu'un :


Les structures :

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
 
typedef struct entree
{
    char nom[30];
    char prenom[20];
    char initiales[6];
    char mail[30];
    char tel[20];
    char classe[20];
    struct entree *next;
    struct entree *previous;
} ENTREE;
 
typedef struct liste
{
    int t;
    struct entree *first;
} LISTE;

Code :

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

1
2
3
4
5
6
7
8
 
LISTE *creer_liste()
{
    LISTE *n_liste = malloc(sizeof(LISTE));
    n_liste->t=0;
    n_liste->first=NULL;
    return n_liste;
}

La fonction ajoute_entree -> qui n'a pas bougé (cela fonctionnait déjà avant)

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
 
void ajoute_entree(ENTREE *entree, LISTE *liste) // ajoute une entree à la fin d'une liste initialisee ou existante (cfr. creer_liste())
{
    //  (ne manipule pas les donnees).
    entree->previous=NULL;
    entree->next=NULL;
    if(liste->t==0)
    {
        liste->first=entree;
        entree->previous=NULL;
    }
    else
    {
        ENTREE *courant;
        courant=liste->first;
        while(courant->next!=NULL)
        {
            courant=courant->next;
        }
        courant->next=entree;
        entree->previous=courant;
    }
    liste->t++;
}

La fonction tri_insertion qui fait maintenant appel à des sous-fonctions
1- La premiere renvoie la plus petite entree de la liste (ordre alphabetique)
2- La seconde délie l'entrée de la liste où elle se trouvait (en réajustant les ponteurs)
3- Enfin , la troisièmme fonction ajoute l'entrée préalablement déliée à une nouvelle liste (la liste triée)

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
 
LISTE *tri_insertion(LISTE *liste,char choix)
{
    LISTE *liste_triee;
    liste_triee=creer_liste();
    ENTREE *plus_petit;
    plus_petit=NULL;
    while(liste->t>0)
    {
        plus_petit=plus_petite_entree(liste,choix);
        delier_entree(plus_petit,liste);
        ajoute_entree(plus_petit,liste_triee);
    }
free(liste);
return liste_triee;
}
 
ENTREE *plus_petite_entree(LISTE *liste,char choix)
{
    if(liste->t<2)
    {
        return(liste->first);
    }
    else
    {
        ENTREE *courant;
        ENTREE *plus_petit;
        courant=liste->first;
        plus_petit=liste->first;
        while(courant!=NULL)
        {
           if(choix=='n')
           {
            if(strcmp(courant->nom,plus_petit->nom)<0)
            {
                plus_petit=courant;
            }
           }
 
           if(choix=='p')
           {
            if(strcmp(courant->prenom,plus_petit->prenom)<0)
            {
                plus_petit=courant;
            }
           }
 
           if(choix=='c')
           {
            if(strcmp(courant->classe,plus_petit->classe)<0)
            {
                plus_petit=courant;
            }
           }
            courant=courant->next;
        }
        return plus_petit;
    }
}
 
void delier_entree(ENTREE *entree,LISTE *liste)
{
   if(liste->t<2)
   {
 
   }
   else if(entree->previous==NULL)
   {
      liste->first=entree->next;
      entree->next->previous=NULL;
   }
   else if(entree->next==NULL)
   {
      entree->previous->next=NULL;
   }
   else
   {
      entree->previous->next=entree->next;
      entree->next->previous=entree->previous;
   }
   liste->t--;
}