IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Liste ordonnee insertion


Sujet :

C

  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Janvier 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2012
    Messages : 33
    Par défaut Liste ordonnee insertion
    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 : 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
    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

  2. #2
    Membre émérite Avatar de MythOnirie
    Homme Profil pro
    Développeur décisionnel
    Inscrit en
    Juin 2012
    Messages
    376
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : Développeur décisionnel

    Informations forums :
    Inscription : Juin 2012
    Messages : 376
    Par défaut
    Bonjour,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  3. #3
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2009
    Messages
    4 491
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2009
    Messages : 4 491
    Billets dans le blog
    1
    Par défaut
    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 :
    1. Elem *new = (Element*)malloc(sizeof(struct Element)); --> Pointeur sur Elem pour Element ?
    2. Code : Sélectionner tout - Visualiser dans une fenêtre à part
      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 ?
    3. d'ailleurs, la new->chaine_caractere est-elle correctement allouée ?
    4. pourquoi comparer une fois puis comparer dans une boucle ? Tu ne peux pas directement faire une boucle ?
    5. 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

  4. #4
    Inactif  


    Homme Profil pro
    Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Inscrit en
    Décembre 2011
    Messages
    9 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 9 026
    Par défaut
    Bonjour,

    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
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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^^

  5. #5
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Janvier 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2012
    Messages : 33
    Par défaut
    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?

  6. #6
    Inactif  


    Homme Profil pro
    Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Inscrit en
    Décembre 2011
    Messages
    9 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Doctorant sécurité informatique — Diplômé master Droit/Économie/Gestion
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 9 026
    Par défaut
    Le parcours indirect te permet de traiter tous les éléments de ta liste sans distinctions qu'ils soient premier ou non.

  7. #7
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Janvier 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2012
    Messages : 33
    Par défaut
    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)

  8. #8
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2009
    Messages
    4 491
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2009
    Messages : 4 491
    Billets dans le blog
    1
    Par défaut
    Ne faisant jamais de liste, je me suis dit que ça serait un bon exercice de le faire et j'ai bien galéré 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.

Discussions similaires

  1. Programme todo list -erreur insert
    Par SkimCelul dans le forum PHP & Base de données
    Réponses: 3
    Dernier message: 15/02/2013, 08h19
  2. Réponses: 1
    Dernier message: 08/10/2011, 05h16
  3. [PHP 5.2] Liste des insert par page
    Par ptiteuf dans le forum Langage
    Réponses: 3
    Dernier message: 14/07/2010, 21h33
  4. [LG]Tri par insertion dans une liste chainée
    Par mister_dsg dans le forum Langage
    Réponses: 4
    Dernier message: 18/12/2003, 22h34

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo