[liste] Probleme d'insertion placée
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:
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:
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:
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:
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:
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:
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 :
Citation:
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 :aie:
J'espere qu'un oeil exterieur y verra un peu plus clair.
Merci pour votre aide
Sorry
