Insertion dans une liste chainée triée

Version imprimable

Bonjour,

J'ai un petit soucis d'insertion dans une liste chainée (on suppose qu'elle est déjà triée) :

Voici les structures de Element et de liste :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
//Element de la liste
 
typedef struct Element Element;
struct Element
{
    void * contenu;
    Element * suivant;
};
 
//La liste
 
typedef struct Liste Liste;
struct Liste
{
    Element *premier;
    Element *dernier;
};

Voici la fonction qui doit insérer :

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
 
int insertionOrdonnee(Liste *liste, int (*fct)(void * param1, void * param2), void * donnee){
 
     Element *elemp = liste->premier;
     Element *elem = malloc(sizeof(elem));
 
     if(elem == NULL){
        return 0;
     }
 
     if (liste ==NULL){
        return 0;
     }
 
     if(liste->premier==NULL && liste->dernier ==NULL){
        insertion(liste,donnee);
        return 1;
     }
 
     int ok = fct(elemp->contenu,donnee);
     while(elemp->suivant != NULL && (ok ==0 || ok < 0)){
        if (elemp == liste->premier && ok <0){
            printf("Insertion premier\n");
            insertion(liste,donnee);
            return 1;
        }else if(elemp == liste->dernier && ok <0){
            printf("Insertion dernier\n");
            insertionqueue(liste,donnee);
            return 1;
        }else{
            Element *el = elemp->suivant;
            elemp->suivant = el->suivant;
        }
    elemp = elemp->suivant;
    }
}

Voici le main :

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
 
int main(void){
 
    printf("Initialisation de la liste \n");
    Liste *liste=initialisation();
 
    int test = 4;
    int * var1 = &test;
        int test2 = 3;
    int * var2 = &test2;
    int test3 = 2;
    int *var3 = &test3;
 
    printf("Insertion en tête\n");
    insertion(liste,var1);
    afficherListe(liste);
 
    printf("\n");
 
    printf("Insertion en tête\n");
    insertion(liste,var2);
    afficherListe(liste);
 
        printf("\n");
 
    printf("Insertion en tete\n");
    insertion(liste,var3);
    afficherListe(liste);
 
    int comparaisonInt(void *p1, void *p2){
        if (p1 == p2){
            return 0;
        }else if (p1 > p2){
            return 1;
        }else{
            return -1;
        }
    }
 
    int  i = 2;
    printf("Insertion ordonnee\n");
    insertionOrdonnee(liste,&comparaisonInt,&i);
    afficherListe(liste);
 
 
    return 0;
}

ComparaisonInt est la fonction appele pour l'insertion, je pense que le problème vient de la, notamment avec la valeur retournée (toujours la même).

Merci de votre aide,

Cdtl,

25/11/2015, 00h06
stendhal666

Citation:

ComparaisonInt est la fonction appele pour l'insertion, je pense que le problème vient de la, notamment avec la valeur retournée (toujours la même).

En même temps tu compares deux pointeurs void entre eux, il y a peu de chance que cela compare des int... Il faudrait que ta fonction caste ses arguments en pointeur sur int puis les déréférence.

La première chose qui me saute aux yeux, c'est dans ta fonction "comparaisonInt()", tu compares la valeur des pointeurs passés en paramètre et non la valeur pointée par ceux-ci :
Code:

1 2 3 4 5 6 7 8 9 int comparaisonInt(void *p1, void *p2){ if ( (*p1) == (*p2) ){ return 0; }else if ( (*p1) > (*p2) ){ return 1; }else{ return -1; } }
(en passant, je ne définirai pas cette fonction dans le "main()", mais de façon plus global ..)

Ensuite, dans "insertionOrdonnee()", tu utilise le pointeur "Liste" avant de savoir s'il est NULL => ça peut t'amener à avoir un signal 11.
Et tu n'utilise pas ta variable "Element *elem", alors que dans le block "else" tu fais des trucs que je ne comprends pas bien, mais que peut-être elle pourrait servir à cet endroit, en tout cas, je dirais que tu casse (probablement) ta liste, là (tu sembles faire 2 fois "suivant") :

Si dans ta liste tu as : A -> qui a pour suivant -> B -> qui a pour suivant -> C, tu semble faire : A -> a pour suivant -> C, à mon sens tu perds B.

Et tu ne nous donnes pas le code de "insertion()", ni de "insertionqueue()"

DBRep

Merci de vos réponses, le problème est presque bon. J'arrive à inserer en tête si il le faut et en queue si il le faut mais je n'arrive pas à comprendre comment inserer "n'importe ou" dans la liste.
Voici le code de la fonction modifié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
 
int insertionOrdonnee(Liste *liste, int (*fct)(void * param1, void * param2), void * donnee){
 
     if (liste ==NULL){
        return 0;
     }
 
     Element *elemp = liste->premier;
     Element *elempf = liste->dernier;
     Element *elem = malloc(sizeof(elem));
 
     if(elem == NULL){
        return 0;
     }
 
     if(liste->premier==NULL && liste->dernier ==NULL){
        insertion(liste,donnee);
        return 1;
     }
 
        while(elemp->suivant != NULL ){
        int ok = fct(elemp->contenu,donnee);
        printf("Valeur ok %d\n", ok);
		if (elemp == liste->premier && ok >0){
            printf("Insertion premier\n");
            insertion(liste,donnee);
			return 1;
		}else if(elempf == liste->dernier && ok <0){
		    printf("Insertion dernier\n");
			insertionqueue(liste,donnee);
			return 1;
		}else{
		    printf("Insertion milieu\n");
			Element *el = elemp->suivant;
			elemp->suivant = el->suivant;
			return 1;
		}
    elemp = elemp->suivant;
	}
}

Et le code de la comparaison :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
    int comparaisonInt(void *p1, void *p2){
        int v1 = *((int *) p1);
        int v2 = *((int *) p2);
 
        if ( v1 == v2 ){
            return 0;
        }else if ( v1>v2 ){
            return 1;
        }else{
            return -1;
        }
    }

Merci de vos réponses,
Cdtl,

Une question en passant: lorsqu'on entretient une structure Liste avec un pointeur sur le dernier élément, c'est en général pcq c'est une liste doublement chaînée; si on ne peut pas traverser la liste dans le sens inverse, ce pointeur rajoute de la complexité de gestion sans rajouter grand chose. Pourquoi as-tu fait ce choix?

Je te propose d'abord une solution récursive, qui a l'avantage d'être plus claire:
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 struct Elem { void* donnee; Elem* next; }; struct Elem* new_element(void* donnee = NULL, struct Elem* next = NULL) { struct Elem* e = (struct Elem*) malloc(sizeof(struct Elem)); e->donnee = donnee; e->next = next; return e; } Elem* inserer(Elem* first, int (*compare)(void* a, void* b), void* value) { if (!first) return new_element(value); // on est arrivé au bout de la liste, on renvoie un element initialisé avec value et null int cmp = compare(first->donnee, value); if (cmp == 0) return first; // si l'élément est déjà présent pas besoin d'insertion if (cmp < 0) { first->next = inserer(first->next, compare, value); // si le nouvel élément est supérieur on poursuit dans la liste return first; } struct Elem* e = new_element(value, first); // s'il est inférieur on insère le nouvel élément return e; }
pour que tu voies bien la logique. Compare avec ton code et tu verras le problème (il y en a un autre qui vient de ce que tu n'initialises pas le membre "donnee" de ton nouvel élément).

25/11/2015, 12h52
breizhcola29

Au départ j'étais parti pour gérer les deux pointeurs mais en faite je me suis rendu compte que je suis pas assez à l'aise avec ça encore ^^
Du coup je suis resté sur un pointeur =)
Par contre ta redefinition de la structure Liste m'embete un peux , je trouve ça pas très clair et sa me force à changer toutes mes fonctions =)

Le principe c'est qu'il n'y a plus de structure liste, donc ça simplifie plutôt qu'autre chose mais bon, à toi de voir... La structure List { Elem* first; Elem Last; } est facultative puisqu'Elem suffit à former une liste.

De toute façon ce n'est pas vraiment la peine d'utiliser des fonctions comme inserer_au_debut ou inserer_a_la_fin dans une fonction comme celle-ci puisque le principe de son algorithme est de parcourir la chaîne jusqu'à l'endroit où insérer le nouvel élément:
Code:

1 2 3 4 5 6 7 8 9 10 void inserer(struct Elem** first, int (*compare)(void*, void*), void* value) { struct Elem *prev = NULL, *cur = *first; while ( cur && compare(cur->donnee, value) < 0 ) { prev = cur; cur = cur->next; } if (prev) // il y avait au moins un élement < value. Si on est à la fin de la liste, cur == NULL prev->next = new_element(value, cur); else *first = new_element(value, cur); }

25/11/2015, 17h41
breizhcola29

J'ai fini par trouver ^^ c'était une erreur au niveau de la comparaison et de l'insertion queue ^^