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 :

Une fonction d'ajout par tri


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Inscrit en
    Novembre 2009
    Messages
    63
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 63
    Par défaut Une fonction d'ajout par tri
    Salut tous,

    J'avais passé trois jours à essayer de coder une fonction d'ajout par tri sur un structure de tableau de pointeur (char * tableau[50]) sans vraiment arriver à pointer du doigt le problème.

    Bref j'ai fait quelques tests et ça ne semble pas trop aboutir, mais du moins je tombe sur des choses plus ou moins bonnes maintenant...

    Voilà je vous montre d'abord le code :

    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
     
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    ///déclarer la chaîne masse qui servira de 'fin/stop' pour tableau
    char * masse="\0";
     
    ///Création d'une liste
    //cette fonction nous permettra de créer une liste vide et de mettre la masse sur le premier élément
    // cette manipulation nous aidera sur les autres fonctions notamment l'ajout par tri
    void Create(char * Pnt[])
    {
        Pnt[0]=masse;
    }
     
    ///fonction longueur de la liste
    //fonction qui peut toujours être utile et pas trop compliqué au codage
    int Length(char * p[])
    {
        int i;
        for(i=0;strcmp(p[i],masse)!=0;i++);
        return i;
    }
     
    ///Affichage simple
    void Show(char * Pnt[])
    {
        int i;
        for(i=0;strcmp(Pnt[i],masse)!=0;i++)
        {
            puts(Pnt[i]);
        }
    }
     
    //Ajout par tri
    //cette fonction suppose aussi la création d'une liste vide qui se remplit en se triant en même temps, autrement dit
    // on déclare simplement la listre (char * Pnt[];) après quoi elle la remplit une par une (Add_sort("premier"); Add_sort("deuxième");...).
     
     
     
    void Add_sort(char * Pnt[],char * Ch)
    {
        if(Length(Pnt)==0)
        {
            Pnt[0]=Ch;
            Pnt[1]=masse;
        }//après test ça marche !
        //Pnt[0]=Ch;
        else
        {
            int i;
            int j;
            for(i=0;strcmp(Pnt[i],Ch)<0 && strcmp(Pnt[i],masse)!=0;i++);
            for(j=0;j<i;j++)
            {
                Pnt[Length(Pnt)+1-j]=Pnt[Length(Pnt)-j];
            }
            Pnt[i]=Ch;
            for(i=0;strcmp(Pnt[i],masse)!=0;i++);
            Pnt[i+1]=masse;
        }
    }
     
    int main()
    {
    char * p[50];
    Create(p);
    Add_sort(p,"a");
    Add_sort(p,"c");
    Add_sort(p,"b");
     
    Show(p);
     
    return 0;
    }
    Les fonctions Show, Length et Create marchent donc on s'en soucie pas.
    J'espère que vous pourriez au moins m'indiquer le problème

    Remarque :
    En compilation, j'ai remarqué que si l'on rajoute des chaînes ordonnées, tout va pour le mieux, et même que ça trie après le quatrième rajout, mais c'est pas toujours évident et des fois ça trie, des fois ça écrase...

  2. #2
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 833
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 833
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par bounadalvidal Voir le message
    Salut tous,

    J'avais passé trois jours à essayer de coder une fonction d'ajout par tri sur un structure de tableau de pointeur (char * tableau[50]) sans vraiment arriver à pointer du doigt le problème.

    Bref j'ai fait quelques tests et ça ne semble pas trop aboutir, mais du moins je tombe sur des choses plus ou moins bonnes maintenant...

    Voilà je vous montre d'abord le code :

    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
     
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    ///déclarer la chaîne masse qui servira de 'fin/stop' pour tableau
    char * masse="\0";
     
    ///Création d'une liste
    //cette fonction nous permettra de créer une liste vide et de mettre la masse sur le premier élément
    // cette manipulation nous aidera sur les autres fonctions notamment l'ajout par tri
    void Create(char * Pnt[])
    {
        Pnt[0]=masse;
    }
     
    ///fonction longueur de la liste
    //fonction qui peut toujours être utile et pas trop compliqué au codage
    int Length(char * p[])
    {
        int i;
        for(i=0;strcmp(p[i],masse)!=0;i++);
        return i;
    }
     
    ///Affichage simple
    void Show(char * Pnt[])
    {
        int i;
        for(i=0;strcmp(Pnt[i],masse)!=0;i++)
        {
            puts(Pnt[i]);
        }
    }
     
    //Ajout par tri
    //cette fonction suppose aussi la création d'une liste vide qui se remplit en se triant en même temps, autrement dit
    // on déclare simplement la listre (char * Pnt[];) après quoi elle la remplit une par une (Add_sort("premier"); Add_sort("deuxième");...).
     
     
     
    void Add_sort(char * Pnt[],char * Ch)
    {
        if(Length(Pnt)==0)
        {
            Pnt[0]=Ch;
            Pnt[1]=masse;
        }//après test ça marche !
        //Pnt[0]=Ch;
        else
        {
            int i;
            int j;
            for(i=0;strcmp(Pnt[i],Ch)<0 && strcmp(Pnt[i],masse)!=0;i++);
            for(j=0;j<i;j++)
            {
                Pnt[Length(Pnt)+1-j]=Pnt[Length(Pnt)-j];
            }
            Pnt[i]=Ch;
            for(i=0;strcmp(Pnt[i],masse)!=0;i++);
            Pnt[i+1]=masse;
        }
    }
     
    int main()
    {
    char * p[50];
    Create(p);
    Add_sort(p,"a");
    Add_sort(p,"c");
    Add_sort(p,"b");
     
    Show(p);
     
    return 0;
    }
    Les fonctions Show, Length et Create marchent donc on s'en soucie pas.
    J'espère que vous pourriez au moins m'indiquer le problème

    Remarque :
    En compilation, j'ai remarqué que si l'on rajoute des chaînes ordonnées, tout va pour le mieux, et même que ça trie après le quatrième rajout, mais c'est pas toujours évident et des fois ça trie, des fois ça écrase...
    Salut

    Je ne pige pas trop ce char *masse="\0".
    Si tu désires créer un pointeur pointant vers une chaine vide, alors c'est char*masse="" qu'il faut écrire. La chaine "" étant automatiquement terminée par un caractère '\0".
    Si tu désires créer un pointeur sentinelle, alors char *masse=NULL. Dans ce dernier cas, utiliser NULL ira aussi bien. Ca permettra de comparer directement tab[i] == NULL au lieu de passer via strcmp(). Surtout que parfois tu écris strcmp(Pnt[i], masse) donc tu as très bien compris que tu compares des chaines et qu'on ne manipule pas des chaines comme des éléments simples (une chaine est d'abord un tableau et tu n'as en main que l'adresse de début) mais par ailleurs, tu écris Pnt[i]=masse alors qu'il faudrait passer par strcpy().

    Ce qui m'amène d'ailleurs au final: quand tu écris Pnt[i]=ch; tu ne fais que copier dans Pnt[i] l'adresse de la variable ch ; cette variable étant l'adresse de la chaine saisie. Bref en fait tu ne copies et ne tries pas des chaines mais simplement des adresses. Dans ton cas présent ça peut marcher puisque tu appelles ta fonction en lui passant diverses chaines statiques donc des adresses différentes mais imaginons que tu lui passes une même chaine chaque fois remplie différemment, comme ça
    Code c : 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
    int main()
    {
    char * p[50];
    Create(p);
    char chaine[10];
     
    strcpy(chaine, "a");
    Add_sort(p,chaine);
     
    strcpy(chaine, "b");
    Add_sort(p,chaine);
     
    strcpy(chaine, "c");
    Add_sort(p,chaine);
     
    Show(p);
     
    return 0;
    }
    Alors ça marchera encore moins bien.

    Donc si j'ai bien compris, tu voudrais un tableau de chaines triées. Donc si on entre toto, titi, tata, le tableau qui en résultera sera tata, titi, toto.
    Déjà, une remarque générale: on ne trie jamais un tableau lors de son remplissage, car dans le pire des cas, pour 50 éléments tu auras alors 50 tris (on entre le premier et on tri le tableau puis on entre le second et on trie les deux puis on entre le 3° et on trie les 3 etc etc) soit 50 * 51 / 2 = 1275 manipulations. Donc s'il faut un tableau trié, on remplit le tableau puis on le trie une fois en final.

    Mais admettons que tu aies besoin d'un tableau trié à chaque insert. Alors dans ce cas, la meilleure solution est de créer une liste. Chaque élément ayant l'adresse du suivant. Et quand on entre un nouvel élément, alors il va s'insérer à sa bonne place. Ce ne sont alors que 2 pointeurs à modifier au lieu de tout décaler (accessoirement, ton décalage est horrible car tu aurais pu faire simplement strcpy(tab[i+1], tab[i]) mais passons).

    Donc voilà. Maintenant, s'il s'agit juste d'un amusement perso pour t'apprendre à manipuler pointeurs et tableaux, alors voilà ce qu'il faut faire
    1) tu ne déclares non pas un tableau de 50 pointeurs mais un tableau char[50][10] (en admettant que chaque chaine ne fasse pas plus de 9 lettres => sinon à toi de définir ta limite mais il en faut une pour que ton tableau puisse stocker des vraies chaines et non de bêtes pointeurs)
    2) tu utilises strcpy() pour remplir chaque tab[i] d'écrire tab[i]=ch
    3) dans ce cas, tu peux éviter d'avoir une "masse" en mémorisant le nb d'éléments utiles mais ça t'oblige à garder une variable en plus. A voir ce que tu préfères. Sinon, si tu préfères une masse (ce qui est d'ailleurs plus conseillé mais on appelle alors ce type d'élément une "sentinelle"), alors tu peux utiliser simplement ""

    4) et si vraiment tu deviens à l'aise, alors tu peux revenir à ton tableau de pointeurs mais alors chaque strcpy() devra être précédé d'un malloc pour allouer la taille. Dans ce cas, ta sentinelle peut alors devenir la macro NULL

    Dernière remarque: la fonction create() ressemble plus à une initialisation qu'à une création. Mais c'est très subsidiaire...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  3. #3
    Membre confirmé
    Inscrit en
    Novembre 2009
    Messages
    63
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 63
    Par défaut
    Salut,
    D'abord merci d'avoir pris le temps de mettre une réponse aussi détaillée
    Ensuite : pour ce qui est du choix de la structure, je ne voulais pas mettre une matrice char car, comme vous l'aviez mentionné, il faut avoir une taille maximale en tête, et disons que je préfère encore laisser à l'utilisateur la liberté de saisir des chaînes "follement" longue...

    L'usage de strcpy ça je peux comprendre, même si j'en vois pas la nécessité : ne suffit-il pas de passer l'adresse d'une chaîne à une case du tableau-pointeurs pour que je puisse la consulter à volonté, n'est-ce-pas tout le "génie" des pointeurs ?

    Pour le tri répétitif : c'est plus consommateur, mais je veux qu'à chaque fois que je fasse un affichage, j'ai une liste triée, m'importe peu si pour cela je dois trier 50 fois ou une...

    La chaîne masse est mal faite peut-être, j'aurai pu mettre un "" ou *masse=NULL, mais je préfère masse="\0" pour le symbolique de la chose...

    En conclusion je crois que le problème se résume en l'usage de Pnt[i]=Ch au lieu de strcpy(Pnt[i],Ch), je saisis pourquoi strcpy peut fonctionner mais pas pourquoi une affectation ne fera pas l'affaire...

  4. #4
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 833
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 833
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par bounadalvidal Voir le message
    Ensuite : pour ce qui est du choix de la structure, je ne voulais pas mettre une matrice char car, comme vous l'aviez mentionné, il faut avoir une taille maximale en tête, et disons que je préfère encore laisser à l'utilisateur la liberté de saisir des chaînes "follement" longue...
    Pas de problème. C'est faisable.

    Citation Envoyé par bounadalvidal Voir le message
    L'usage de strcpy ça je peux comprendre, même si j'en vois pas la nécessité : ne suffit-il pas de passer l'adresse d'une chaîne à une case du tableau-pointeurs pour que je puisse la consulter à volonté, n'est-ce-pas tout le "génie" des pointeurs ?
    Tout à fait. Mais alors il faut que chaque pointeur du tableau pointe vers une adresse différente et valide et contenant ladite chaine.
    Là, il s'agit maintenant qu'on soit d'accord sur la façon de faire. Actuellement ton code fonctionne presque bien pour une seule raison: tu lui passes des pointeurs pointant vers des chaines en dur dans la mémoire. 3 chaines différentes donc 3 pointeurs différents. Ok, ça marche (presque). Mais je présume qu'il s'agit simplement d'un test de bon fonctionnement et que l'utilisateur, lui, aura à la place un outil de saisie de chaine et que cet outil remplira donc une chaine unique que tu enverras à la fonction. Donc tu passeras toujours la même adresse à la fonction.
    Et dans ce cas, la variable contenant la chaine saisie étant la même, tu stockeras la même adresse plusieurs fois.

    Il faut imaginer la mémoire comme une suite de casiers. Tu as le casier 1 qui contient "a", puis le casier 2 qui contient "b" et le casier 3 qui contient "c". Et toi, tu stockes 1, 2 et 3 => ok.

    Mais ensuite tu remplaces tout ça par un unique casier n° 500 que l'utilisateur remplit. Là, si tu stockes 500 à chaque fois ce ne sera plus bon (d'où mon exemple de démo)...

    Citation Envoyé par bounadalvidal Voir le message
    La chaîne masse est mal faite peut-être, j'aurai pu mettre un "" ou *masse=NULL, mais je préfère masse="\0" pour le symbolique de la chose...
    Si tu veux (bien que mon exemple ci-dessous te démontrera que c'est inutile). Attention quand-même à ne pas confondre "\0" et '\0' car ce n'est pas tout à fait pareil...

    Citation Envoyé par bounadalvidal Voir le message
    En conclusion je crois que le problème se résume en l'usage de Pnt[i]=Ch au lieu de strcpy(Pnt[i],Ch), je saisis pourquoi strcpy peut fonctionner mais pas pourquoi une affectation ne fera pas l'affaire...
    Pas du tout. En dehors de tout ce que je t'ai dit, le problème principal de ton code d'origine se situe au niveau du décalage. Tu oublies de décaler le dernier élément.

    Tu trouveras ci-dessous ton code corrigé. Accessoirement, j'ai optimisé la fonction d'insertion (éviter autant que possible l'appel à length()). Et étant donné que tu te sers de masse comme d'un pointeur, on peut alors remplacer tous les strcmp par des simples != (on compare juste les pointeurs). Et donc puisque la masse devient un simple pointeur, autant utiliser le pointeur NULL fait pour ça ; ce qui donne en final
    Code c : 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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    ///Création d'une liste
    //cette fonction nous permettra de créer une liste vide et de mettre la NULL sur le premier élément
    // cette manipulation nous aidera sur les autres fonctions notamment l'ajout par tri
    void Create(char * Pnt[])
    {
        Pnt[0]=NULL;
    }
     
    ///fonction longueur de la liste
    //fonction qui peut toujours être utile et pas trop compliqué au codage
    int Length(char * p[])
    {
        int i;
        for(i=0;p[i] != NULL;i++);
        return i;
    }
     
    ///Affichage simple
    void Show(char * Pnt[])
    {
        int i;
        for(i=0;Pnt[i] != NULL;i++)
        {
            puts(Pnt[i]);
        }
    }
     
    //Ajout par tri
    //cette fonction suppose aussi la création d'une liste vide qui se remplit en se triant en même temps, autrement dit
    // on déclare simplement la listre (char * Pnt[];) après quoi elle la remplit une par une (Add_sort("premier"); Add_sort("deuxième");...).
     
    void Add_sort(char * Pnt[],char * Ch)
    {
        if(Length(Pnt)==0)
        {
            Pnt[0]=Ch;
            Pnt[1]=NULL;
            return;
        }
         int i;
         int j;
         // Puisqu'on ajoute un élément, alors NULL décalera
         // Autant mettre de suite le nouveau - Il y en a alors 2
         // mais c'est pas grave, l'ancien sautera au décalage
         Pnt[Length(Pnt) + 1]=NULL;
     
         // On cherche la position du nouvel élément
         for(i=0;Pnt[i] != NULL && strcmp(Pnt[i],Ch)<0;i++);
     
         // On décale tous ceux qui sont après
         for (j=Length(Pnt); j > i; j--)
             Pnt[j]=Pnt[j - 1];
     
         // On positionne l'élément qui vient d'arriver
         Pnt[i]=Ch;
    }
     
    int main()
    {
    char * p[50];
    Create(p);
    Add_sort(p,"a");
    Add_sort(p,"c");
    Add_sort(p,"b");
     
    Show(p);
     
    return 0;
    }

    En dehors des modifs de style (éviter un else si on quitte la fonction dans le if), Tu remarqueras une modif importante: lors de la recherche de la position, on commence par tester NULL avant de comparer.

    Bien entendu, ce code fonctionne pour toi mais si tu remplaces ton main par le mien du post précédent, alors tu n'auras plus rien de cohérent (toujours cette histoire d'adresse unique). Mais je te laisse réfléchir...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  5. #5
    Membre confirmé
    Inscrit en
    Novembre 2009
    Messages
    63
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 63
    Par défaut
    Salut,
    Je vois maintenant où il était le problème, il semble que c'était d'ordre algorithmique et non syntactique ou conceptuelle, bref...Merci énormément

  6. #6
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 833
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 833
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par bounadalvidal Voir le message
    Salut,
    Je vois maintenant où il était le problème, il semble que c'était d'ordre algorithmique et non syntactique ou conceptuelle, bref...Merci énormément
    Pas de soucis. J'ai même optimisé encore un peu plus la fonction Add_sort en enlevant ce cas particulier du premier élément vu qu'il marche aussi dans le cas général et en incluant le NULL dans le décalage lui-même

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void Add_sort(char * Pnt[],char * Ch)
    {
        int i;
        int j;
     
        // On cherche la position du nouvel élément
        for(i=0;Pnt[i] != NULL && strcmp(Pnt[i],Ch)<0;i++);
     
        // On décale tous ceux qui sont après (le NULL est inclus) en partant de la fin
        for (j=Length(Pnt); j >= i; j--)
            Pnt[j + 1]=Pnt[j];
     
        // On positionne l'élément
        Pnt[i]=Ch;
    }
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [PHP 5.0] Appliquer une fonction à plusieurs valeurs par référence
    Par gui80 dans le forum Langage
    Réponses: 12
    Dernier message: 09/03/2010, 13h42
  2. Réponses: 1
    Dernier message: 02/11/2009, 13h23
  3. Réponses: 0
    Dernier message: 26/07/2007, 15h22
  4. Réponses: 2
    Dernier message: 08/10/2006, 11h44
  5. Appel d'une fonction en C par un noyau en asm (link)
    Par julson dans le forum Programmation d'OS
    Réponses: 7
    Dernier message: 22/03/2005, 15h14

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