tri et liste chainée double

Version imprimable

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:

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:

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

07/11/2012, 22h11
Neckara

Bonjour,

Ligne 27 : entree->previous=courant; ?

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

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

08/11/2012, 15h04
Tziboun

help

Personne ne peut m'aider ? :calim2:
08/11/2012, 15h24
fred1599

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

il est difficile de donner des explications sans tes structures.

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:

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;

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:

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:

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:

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

08/11/2012, 17h13
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 ,...)

résolu !

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:

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:

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:

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:

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