Liste ordonnee insertion

Version imprimable

Bonjour,

je suis en train de faire un petit programme avec des listes chainée, c'est une liste de mots, par ordre alphabétique. Je voudrais que dés lors de l'insertion cela soit trié directement.

Mon problème est que mon code ne fait pas ce que je desire, j'ai eu beau retourner le problème dans tout les sens je ne vois pas ce qui cloche dans mon code.
Si quelqu'un pouvait me donner son avis svp.

ci joint la fonction ajouter element

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
void ajouter(list *liste, char new_mot[100])
{
    int test=test_liste_null(liste);
    int i;
    Elem *new = (Element*)malloc(sizeof(struct Element));
    Element *act;
    int result=0;
 
 
    for(i_compt=0;i_compt<100;i_compt++)
    {
        new->chaine_caractere[i] = new_mot[i];//parcours le tableau (chaine de caractere) et copie caractere par caractere dans le tabeau du nouvel element
    }
 
    //si c'est le premiere élément
    if(test==0)
    {
        new->suivant = NULL;
        liste->premier=new;
 
    }
    else
    {
		//fonction qui renvoit un entier positif si l'element lue est avant (ordre alphabétique) le nouvel element 
		//sinon elle renvoit un entier negatif
        result=comparer_chaine(liste->premier->chaine_caractere,new->chaine_caractere);
		//comparaison avec le premier element de la pile
        if(result<0)
        {
            new->suivant=liste->premier;
            liste->premier=new;
        }
        else
        {
            act = liste->premier;
            while (act!= NULL && result>0)
            {
                result=comparer_chaine(act->chaine_caractere,new->chaine_caractere);
                act=act->suivant;
            }
            new->suivant=act->suivant;
            act->suivant=new;
        }
    }
}

cordialement

Bonjour,
Code:

1 2 3 4 5 6 7 8 act = liste->premier; while (act!= NULL && result>0) { result=comparer_chaine(act->chaine_caractere,new->chaine_caractere); act=act->suivant; } new->suivant=act->suivant; act->suivant=new;
Ici, après avoir fait la comparaison des deux chaines de caractères, tu avance dans la liste avant même de regarder si c'est le bon emplacement ou pas. De plus tu aura un segfault si tu dois insérer un élément à la fin de la liste car ton pointeur act sera sur NULL et tu essayera d'y écrire quelque chose.

Citation:

Mon problème est que mon code ne fait pas ce que je desire

Cad qu'il insère mais pas au bon endroit ? Qu'il n'insère rien du tout ? Le programme plante ? Que ce passe t-il ?

Des remarques sur le code :
Elem *new = (Element*)malloc(sizeof(struct Element)); --> Pointeur sur Elem pour Element ?
Code:

1 2 3 4 for(i_compt=0;i_compt<100;i_compt++) { new->chaine_caractere[i] = new_mot[i];//parcours le tableau (chaine de caractere) et copie caractere par caractere dans le tabeau du nouvel element }
--> pourquoi ne pas utiliser strcpy ?
d'ailleurs, la new->chaine_caractere est-elle correctement allouée ?
pourquoi comparer une fois puis comparer dans une boucle ? Tu ne peux pas directement faire une boucle ?
que fais la fonction comparer_chaine() ? Connais-tu la fonction strcmp() ?
Si tu donnes du code, il est mieux de créer un mini programme qu'on peut compiler et exécuter. Ton programme entier n'est pas nécessaire, juste extraire les parties qui posent problème ;)

Bonjour,

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
void ajouter(list *liste, char new_mot[100])
{
    int test=test_liste_null(liste);
    int i;
    Elem *new = (Element*)malloc(sizeof(struct Element));
    Element *act;
    int result=0;

    //strncpy permet de le faire plus efficacement.
    for(i_compt=0;i_compt<100;i_compt++)
    {
        new->chaine_caractere[i] = new_mot[i];//parcours le tableau (chaine de caractere) et copie caractere par caractere dans le tabeau du nouvel element
    }

    //si c'est le premiere élément
    if(test==0)
    {
        new->suivant = NULL;
        liste->premier=new;

    }
    else
    {
		//fonction qui renvoit un entier positif si l'element lue est avant (ordre alphabétique) le nouvel element 
		//sinon elle renvoit un entier negatif
 //il existe aussi strcmpresult=comparer_chaine(liste->premier->chaine_caractere,new->chaine_caractere);
		//comparaison avec le premier element de la pile
        if(result<0)
        {
            new->suivant=liste->premier;
            liste->premier=new;
        }
        else
        {
            act = liste->premier;
            while (act!= NULL && result>0)
            {
                result=comparer_chaine(act->chaine_caractere,new->chaine_caractere);
                act=act->suivant;
            }
            new->suivant=act->suivant;
            act->suivant=new;
        }
    }
}

Tu peux aussi utiliser un parcours indirect :

Code:

1
2
3
4
5
6
7
8
9
Element ** ptr;
ptr = &liste;
while(*ptr != NULL && strcmp(newElement->chaine, (*ptr)->chaine ) > 0)
{
       ptr = &(*ptr->suivant);
}
 
newElement->suivant = *ptr->suivant;
*ptr = newElement;

EDIT : grillé par Bktero^^

22/08/2012, 16h09
thomaslouf

Merci pour toutes ces reactions alors je vais repondre dans l'ordre :

- MythOnirie je n'avais pas vu ce cas là merci
-Bktero element =elem c'est moi qui me suis trompé
comparer_chaine fait exactement la même chose que strcmp() (qui m'est interdit tout comme strcpy)
je fais deux test un sur le premier element et puis après sur ma boucle.
-Neckara je comprends pas trop ton parcours indirect? le double pointeur il te sert à quoi ici?
22/08/2012, 16h14
Neckara

Le parcours indirect te permet de traiter tous les éléments de ta liste sans distinctions qu'ils soient premier ou non.
22/08/2012, 16h20
thomaslouf

ah dac! je comprend pas trop les histoires avec les doubles pointeurs et tout ça.

Sinon lors de l'insertion ça ne se met pas du tout au bon endroit (en general ça le fait avec le premier element)
23/08/2012, 11h19
Bktero

Ne faisant jamais de liste, je me suis dit que ça serait un bon exercice de le faire et j'ai bien galéré :aie: Comme ta liste est simplement chainée (je présume ?), il faut trouver l'élément après lequel tu vas insérer et non l'élément avant lequel il faut insérer (si je ne m'abuse, le code de Neckara fait cela).

Il faut donc parcourir la liste et regarder si le nouveau mot peut s'insérer entre l’élément courant l'élément suivant. Si tu trouves un tel élément courant, tu arrêtes le parcours. Il se peut aussi que tu parcoures toute la liste sans rien trouver. Tu as donc un while, avec avec plus de conditions, qui s'arrête si on trouve un emplacement pour l'insertion ou si on arrive au bout de la liste. Après la boucle, tu testes si tu es à la fin ou pas pour savoir comment insérer le nouvel objet.

Deux cas particuliers : la liste est vide et l’élément doit s'insérer en tête de liste.

Avec une liste doublement chainée, tu aurais pu simplifier la chose et ne pas gérer la tête de liste séparément. En effet, avec un double chainage, tu peux trouver l’élément avant lequel il faut insérer ; en simple chainage, c'est forcément celui après lequel tu dois insérer et si le nouveau doit venir se mettre en tête de liste, il n'existe pas de tel élément.

Dans ton code, ta boucle s'arrête dés que : result=comparer_chaine(act->chaine_caractere,new->chaine_caractere); est inférieur ou égal à 0. Ta fonction pour comparer les chaines semblent marcher comme strcmp quant au code retour, c'est bien cela ? Ta boucle s'arrête dés le premier élément car le mot courant (= celui du premier élément) est avant le nouveau mot et ta fonction renvoie un nombre négatif. C'est cohérent avec ton dernier message où tu dis que ta fonction insère toujours après le premier élément.