[liste] Probleme d'insertion placée

**sorry60** · 29/04/2006, 17h00

Bonjour,

J'ai un enorme tp à faire sur les listes avec pas mal de fonctions.
Il y en a une qui depuis hier me pose probleme (surtout que je la re-utilise dans d'autres).
Il s'agit d'inserer un element au bon endroit dans une liste simplement chainée supposée etre triée dans l'ordre croissant.

Voici d'abord la structure :

Code :

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

1
2
3
4
5
typedef struct _un_element
{
    Tval elem_val;
    struct _un_element *suiv;
} Un_element, * P_un_element;

Et ma fonction qui donc ne marche pas bien...

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
/* fonction qui insere en place un element dans la liste */
void inserer_en_place (P_un_element *liste, P_un_element el )
{
    /* si la liste est vide */
    if ( !(*liste) )
        inserer_element_debut(liste,el);
    else
    {
        /* la liste est triee dans l'odre croissant */
        P_un_element prec = NULL;
        /* on garde en memoire la tete */
        P_un_element tete = *liste;
        /*Un_element tete = **liste;*/
        /* on se balade dans la liste tant que el->val plus grand que le chainon->val */
        /*while ( (cmpval(el->elem_val,(*liste)->elem_val)) > 0 )*/
        while ( ((*liste)->suiv != NULL) && (el->elem_val > (*liste)->elem_val) )
        {
            prec = *liste;
            *liste = (*liste)->suiv;
        }
        /* Si c'est en 1ere place */
        if ( !prec )
        {
            el->suiv = *liste;
            *liste = el;
        }
        /* si c'est en derniere place */
        else if ( !(*liste)->suiv )
        {
            el->suiv = NULL;
            (*liste)->suiv = el;
            /* on remet liste sur la tete */
            *liste = tete;
        }
        else
        {
            /* on insere la valeur */
            prec->suiv = el;
            el->suiv = *liste;    
            /* on remet liste sur la tete */
            *liste = tete;
        }
    }
}

Je l'avais pourtant testé :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Test de la fonction inserer_en_place */
    printf("Test de la fonction inserer_en_place\n");
    printf("On insere en place dans une liste vide :\n");
    inserer_en_place(&maListe5,creer_element(0));
    afficher_liste(maListe5);        
    printf("On insere en 1ere place d'une liste non vide :\n");
    inserer_en_place(&maListe,creer_element(1));
    afficher_liste(maListe);    
    printf("On insere en derniere place d'une liste non vide :\n");
    inserer_en_place(&maListe,creer_element(7));
    afficher_liste(maListe);
    printf("On insere au milieu d'une liste non vide :\n");
    inserer_en_place(&maListe,creer_element(5));
    afficher_liste(maListe);

Et c'etait ok..
Mais plus loin j'ai constaté son disfonctionnement..
Je la reutilise dans une autre fonction, qui insere un element au bonne endroit que si celui dernier n'est pas dans la liste :

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
/* fonction qui ajoute un element en place dans une liste triee si celui ci n'est pas present */
void inserer_en_place_si_unique (P_un_element *liste, P_un_element el )
{
    /* on test d'abord si el est deja dans la liste */
    P_un_element tmp = rechercher_element (*liste,el->elem_val);
    /* si il a ete trouve on ne fait rien */
    if ( tmp )
    {
        printf("Element deja dans la liste !\n");
        return;
    }
    /* sinon on l'insere en place */
    else
        inserer_en_place(liste,el);
}

Et cette derniere fonction me sert pour realiser l'intersection de deux ensembles (listes) :

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
/* Fonction qui cree un nouvelle liste qui est l'intersection de 2 listes passees en parametres, et qui renvoie cette nouvelle liste */
P_un_element intersection (P_un_element liste1, P_un_element liste2)
{
    P_un_element newListe = malloc(sizeof(Un_element));
 
    if ( newListe )
    {
        P_un_element tmp = NULL;
        newListe = NULL;
        /* on parcourt liste1 */
        while ( liste1 )
        {
            /* si l'element actuel de liste1 est dans liste2, on le rajoute a la nouvelle liste */
            if ( (tmp = rechercher_element(liste2,liste1->elem_val)) )
            {
                inserer_en_place_si_unique(&newListe,creer_element(liste1->elem_val));
            }
            liste1 = liste1->suiv;
        }
        return newListe;
    }
    else
        return NULL;
}

Et c'est là que je me suis apperçu qu'il y avait un probleme...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
/* Test de la fonction intersection */
    printf("Test de la fonction intersection\n");
    detruire_liste(&maListe3);
    printf("La liste1 :\n");
    afficher_liste(maListe);
    inserer_en_place(&maListe2,creer_element(2));
    inserer_en_place(&maListe2,creer_element(12));
    printf("La liste2 :\n");
    afficher_liste(maListe2);
    maListe3 = intersection(maListe,maListe2);
    printf("Leur intersection :\n");
    afficher_liste(maListe3);

Donne :

Test de la fonction intersection
La liste1 :
Valeur element : -1, pointeur suivant : 0x94d9008
Valeur element : 0, pointeur suivant : 0x94d9038
Valeur element : 1, pointeur suivant : 0x94d9048
Valeur element : 2, pointeur suivant : 0x94d9078
Valeur element : 3, pointeur suivant : 0x94d9018
Valeur element : 4, pointeur suivant : 0x94d9108
Valeur element : 5, pointeur suivant : 0x94d9148
Valeur element : 6, pointeur suivant : 0x94d9118
Valeur element : 7, pointeur suivant : 0x94d9128
Valeur element : 8, pointeur suivant : 0x94d91d8
Valeur element : 9, pointeur suivant : 0x94d91e8
Valeur element : 17, pointeur suivant : (nil)
La liste2 :
Valeur element : 1, pointeur suivant : 0x94d9218
Valeur element : 2, pointeur suivant : 0x94d9168
Valeur element : 3, pointeur suivant : 0x94d9158
Valeur element : 11, pointeur suivant : 0x94d90f8
Valeur element : 6, pointeur suivant : 0x94d9208
Valeur element : 12, pointeur suivant : (nil)
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
L'element n'est pas dans la liste !
Leur intersection :
Valeur element : 2, pointeur suivant : 0x94d90a8
Valeur element : 1, pointeur suivant : 0x94d9238
Valeur element : 3, pointeur suivant : 0x94d9248
Valeur element : 6, pointeur suivant : (nil)

L'intersection (nouvelle liste) est mal triée.. mais ça le fait que au debut, pour le 2, car apres le 3 et 6 sont bien triés..
Voila j'ai cherché pas mal de temps mais je ne vois plus rien

J'espere qu'un oeil exterieur y verra un peu plus clair.

Merci pour votre aide
Sorry

**diogene** · 29/04/2006, 18h17

Le problème se situe au moment de l'insertion d'un deuxième élément dans la liste.
Supposons que la liste comporte un seul élément. Au moment de l'insertion du deuxième :

Code :

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

1
2
3
4
5
6
7
        P_un_element prec = NULL;
        P_un_element tete = *liste
        while ( ((*liste)->suiv != NULL) && (el->elem_val > (*liste)->elem_val) )
        {
            prec = *liste;
            *liste = (*liste)->suiv;
        }

(*liste)->suiv vaut NULL et donc prec reste NULL

Code :

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

1
2
3
4
5
        if ( !prec )
        {
            el->suiv = *liste;
            *liste = el;
        }

Alors le deuxième élément est inséré en TETE même si il est plus grand que le premier. Le test sur prec est dans ce cas insuffisant pour choisir l'insertion en tête de la liste ou en queue.
Dans l'exemple d'intersection des listes, la liste résultante s'est construite de la façon suivante :
-1-
-2-1-
-2-1-3- etc

**sorry60** · 29/04/2006, 19h14

Ah en effet j'avais pas fait attention à ça...quel boulet..

Merci beaucoup de ton aide,
je vais corriger ça

[liste] Probleme d'insertion placée

C

Discussions similaires

Partager

Partager