Discussion :

[Nicotyrox]

Bonjour,

J'aimerais de l'aide sur une gestion de pointeur.
Je dois gerer une equation (avec ses priorité opératoires etc) dans un arbre binaire de façon à pouvoir l'enregistrer, l'affiher et la calculer. Seulement j'ai un problème lors de la création de mon arbre. La boucle If avec "arbrefct->droite" dans ce code ne fonctionne pas (plantage du programme) Le code présenté içi est une partie de la fonction et du programme, mais le message "premier élement ne s'affiche pas alors que ceux d'avant s'affiche. Comment corriger ?

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
77
78
79
80
81
82
83
84
85
86
87
 
noeud *creerArbre(char *t)
{
    noeud *s = malloc(sizeof(noeud));
    int i=2,taille=0,nbPOuv=0,nbP=0,tolerance=0; // i initialisé à 2 pour sauté le =
    taille=strlen(t);
 
    s->valeur = t[0]; // implicitement, le caractère est transformé en Code ASCII
    s->oper = "=";  // permet de dire que nous sommes bien dans le premier élement pour la fonction d'affichage
    s->gauche = NULL;
    s->droite = NULL;
 
    //maintenant on doit en fonction des parenthèse établir une hierarchie
    //Utilisation d'une variable de tolérance, permettant de refaire des test de aractères tant que le nombre de parenthèse tolérée <= nombre de parenthèse dans la fonction
    while (tolerance <= nbP)
    {
        while (i<= taille)
        {
            //gestion du nombre de parenthèse
            if (t[i] == '(')
            {
                nbPOuv++;
                nbP++;
            }
 
            if ((t[i] == ')') && (nbPOuv != 0)) // même si ça ne devrait jamais arriver, simple sécurité
                nbPOuv--;
 
            if (((t[i] == '+') || (t[i] == '-') || (t[i] == '*')) && (nbPOuv == tolerance))  //Si t est soit +, soit -, soit * et qu'en plus, le nombre de parenthèse ouverte est identique au nombre de parenthèse tolérée
            {
                printf("Caractère entrant : %c\n",t[i]);
                ajouterNoeud(s,t[i],0);
                //On ajoute à la suite les caractères précedants et suivant celui traité uniquement si on a pas de parenthése aant et après l'opérateur
                if ((estTuUnChiffre(t[i-1])) && (estTuUnChiffre(t[i+1])))
                {
                //Ne pas oublier de faire une conversion en nombre à 2 digits si on le doit
                    if (estTuUnChiffre(t[i-2]))
                        ajouterNoeud(s,nombre(t[i-2],t[i-1]),1);
                    else
                        ajouterNoeud(s,t[i-1],1);
 
                    if (estTuUnChiffre(t[i+2]))
                        ajouterNoeud(s,nombre(t[i+1],t[i+2]),0);
                    else
                        ajouterNoeud(s,t[i+1],0);
                }
            }
            i++;
        }
        //reinitialisation des paramètres
        tolerance++;
        i=2;
    }while (tolerance <= nbP);
 
    return s;
}
 
void ajouterNoeud(noeud **arbre, char valeur, int dir)
{
    noeud *noeudfct;
    noeud *arbrefct = *arbre;
 
    noeud *elem = malloc(sizeof(noeud));
    //Définition de l'élement que l'on ajoute
    if (estTuUnChiffre(valeur))
    {
        elem->valeur = conversionEntier(valeur);
        elem->oper = NULL;
        elem->gauche = NULL;
        elem->droite = NULL;
    }
    else
    {
        elem->valeur = NULL;
        elem->oper = valeur;
        elem->gauche = NULL;
        elem->droite = NULL;
    }
    noeudfct = arbrefct;
    printf("Hey\n");
    //Maintenant, si c'est le premier élement de calcul de l'équation, il viendra forcément se placer à droite, et on aura forcément NULL
    if (arbrefct->droite == NULL)
    {
        printf("Premier élement\n");
        noeudfct->droite = elem;
        return;
    }

Je joins également la structure noeud utilisée, au cas où :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
typedef struct noeud
{
    int valeur;
    char oper;
    struct noeud *gauche;
    struct noeud *droite;
} noeud ;

J'ai déjà essayer de remplacer la condition IF par :

if (arbrefct != NULL && arbrefct->droite == NULL)Et voiçi ce que le debugger me dit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
#0 774015DE ntdll!LdrQueryProcessModuleInformation() (C:\Windows\system32\ntdll.dll:??)
#1 774015DE ntdll!LdrQueryProcessModuleInformation() (C:\Windows\system32\ntdll.dll:??)
#2 773F014E ntdll!LdrFindResource_U() (C:\Windows\system32\ntdll.dll:??)
#3 0028F9CC ?? () (??:??)
#4 004014EA creerArbre(t=0x404070 <_Jv_RegisterClasses+4210800> "A=1+2") (F:\ProjetAA\AlgoA\main.c:70)
#5 00401A35 main() (F:\ProjetAA\AlgoA\main.c:243)

A SAVOIR :

- Le message Hey s'affiche, mais le programme plante avant le message "premier element", preuve que c'est bien la condition qui a un problème.
- Je commence à 2 car cette fonction sert pour ce qui sera après le =/ En gros l'équation est de la forme a=1+(2*(3+6)) et lorsque je fais la création de l'arbre, je crée le premier élement comme forcément le nom de l'équation et pour opérateur =.

[gerald3d]

Bonjour.

Sans trop regarder en profondeur ton code il serait bon que tu limites l'accès à certaines des variables transmises. Par exemple dans le fonction noeud *creerArbre(char *t) j'aurais tendance à transmettre t en tant que const : noeud *creerArbre(const char *t) tu peux appliquer ceci à toutes les entêtes de tes fonctions. Toute variable transmise qui ne doit pas être modifiée dans la fonction doit être transmise en tant que const.

Ensuite, dans la fonction void ajouterNoeud(noeud **arbre, char valeur, int dir); tu écris par exemple : elem->valeur = NULL;. valeur est un int. Bien que NULL soit définit à priori pour l'instant à la valeur 0 je ne suis pas sûr que ton code fonctionne bien longtemps. Imagines que NULL soit redéfinit ca risque de poser des problèmes (exemple du C++ avec nullptr).

Enfin, lorsque tu fais appel à la fonction void ajouterNoeud(noeud **arbre, char valeur, int dir); dans la fonction noeud *creerArbre(char *t); tu transmets le pointeur s alors que tu dois envoyer l'adresse du pointeur s : &s

[Nicotyrox]

Merci ! J'ai réussi à avancer du coup. Mais je me retrouve confronter à un autre problème de pointeur.
Du coup, j'ai crée une fonction créeoeudPlusLoin pour le crer au plus loin possible :

Voilà les mdoification :

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
 
void ajoutNoeudPlusLoin(noeud **arbre, noeud **elem)
{
    noeud *noeudfct;
    noeud *arbrefct = *arbre;
 
    noeudfct = arbrefct->gauche;
 
    //Maintenant, tout se placera en fonction de la position
    if (arbrefct->oper == NULL)
        return;
 
    if (noeudfct == NULL)
    {
        arbrefct->gauche = elem;
        return;
    }
 
    noeudfct = arbrefct->droite;
 
    if (noeudfct == NULL)
    {
        arbrefct->droite = elem;
        return;
    }
 
    if(arbrefct->gauche != NULL)
    {
        ajoutNoeudPlusLoin(&arbrefct->gauche, &elem);
        return;
    }
    if(arbrefct->droite != NULL)
    {
        ajoutNoeudPlusLoin(&arbrefct->droite, &elem);
        return;
    }
}
 
void ajouterNoeud(noeud **arbre, char valeur, int nb, int dir)
{
    printf("Entrée dans la fonction ajouté noeud du caractère %c et nombre %d\n",valeur,nb);
    noeud *noeudfct;
    noeud *arbrefct = *arbre;
 
    noeud *elem = malloc(sizeof(noeud));
 
    //Définition de l'élement que l'on ajoute
    if (valeur == NULL)
    {
        elem->valeur = conversionEntier(valeur);
        elem->oper = NULL;
        elem->gauche = NULL;
        elem->droite = NULL;
    }
    else
    {
        elem->valeur = NULL;
        elem->oper = valeur;
        elem->gauche = NULL;
        elem->droite = NULL;
    }
    noeudfct = arbrefct;
    //Maintenant, si c'est le premier élement de calcul de l'équation, il viendra forcément se placer à droite, et on aura forcément NULL
    if ((arbrefct != NULL) && (arbrefct->droite == NULL))
    {
        noeudfct->droite = elem;
        return;
    }
    printf("Pas le premier element !\n");
    //sinon, pas de sortie de fonction, on peut sauter cet élement
    //maintenant, on ajoute au plus loin dèsqu'on peut
    ajoutNoeudPlusLoin(&arbrefct, &elem);
 
 
}

Les fonction étant forcément récursive, je n'arrive pas à la définir pour qu'elle parcourt l'arbre en profondeur pour ajouter les elements. Que faire ?

[gerald3d]

Une fonction récursive, avec les pointeurs transmis qui changent à chaque appel, j'en ai mal à la tête rien que d'y penser . Je ne comprends pas bien la démarche. À quoi doit servir cette nouvelle fonction exactement ?

[Nicotyrox]

Moi en la faisant elle a explosée
En fait chaque element transmis sont transmis de gauche a droite et chaque niveau représente un niveau de priorité. Plus c'est en bas, plus c'est prioritaire. Et du coup je doit classer une équation dans,un arbre binaire de cette façon. C'est pas le plus pratique on est bien d'accord hein, mais c'est une priorité imposée par mon prof, et ça m'embete depuis le début de la semaine.

Du coup, la fonction ajouter noeud doit transmettre de gauche a droite les informations. Et j'avais créer une fonction plus loin pour faire l'ajout au plus loin possible. Mais ça plante replante et rereplante.
Si tu reusis a corriger ou si tu trouve une autre méthode d'insertion du noeud je suis preneur ^^

[Sve@r]

Si tu reusis a corriger ou si tu trouve une autre méthode d'insertion du noeud je suis preneur ^^

Bonjour

Je ne comprends pas trop non plus ce que tu entends par "plus loin". Est-ce "le plus loin possible" ? Ou bien "le plus en profondeur possible" ?

Toutefois, devant un truc qui commence à devenir conséquent, je commencerais moi par avoir de bonnes bases bien solides. C'est très bien d'avoir défini ton type "noeud" (tu l'aurais normalisé en l'appelant "t_noeud" ça aurait été le must mais on ne peut pas tout avoir) mais pourquoi n'as-tu pas défini aussi un type dédié pour l'arbre ???
Ca peut-être un truc même super simple, du style

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
typedef struct {
    t_noeud *racine;
} t_arbre;

Mais ce type débile avec un simple pointeur aura les avantages suivants

• tu n'es plus obligé de passer un noeud **arbre à tes fonctions quand lesdites fonctions doivent modifier l'arbre. Tu peux leur passer un simple t_arbre *arbre. Les fonctions pourront à loisir taper dans arbre->racine ou dans un noeud en profondeur (gauche/droite) même pour le modifier.
• si un jour tu veux enrichir ton arbre d'infos complémentaires (par exemple la profondeur maximale, etc), tu les rajoutes dans le type et hop, toutes tes fonctions y auront immédiatement accès

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
void ajoutNoeudPlusLoin(noeud **arbre, noeud **elem)
{
    ... 
    if(arbrefct->gauche != NULL)
    {
        ajoutNoeudPlusLoin(&arbrefct->gauche, &elem);
        return;
    }
    if(arbrefct->droite != NULL)
    {
        ajoutNoeudPlusLoin(&arbrefct->droite, &elem);
        return;
    }
}

Tu vois ton erreur ? elem étant déjà un noeud **, et ta fonction attendant un noeud **, faut lui passer elem et non &elem. Une erreur que tu n'aurais pas fait si tu avais eu un type t_arbre disponible. Comme je dis souvent, on peut tenir une chemise par le col mais ça va mieux si on la place sur un cintre.

Les fonction étant forcément récursive, je n'arrive pas à la définir pour qu'elle parcourt l'arbre en profondeur pour ajouter les elements. Que faire ?

Perso moi je modulerais un peu plus en séparant la phase "recherche de l'endroit où poser un noeud" (fonction très probablement récursive mais ne modifiant rien et donc n'ayant pas besoin de recevoir des noeud** à la c..) et "positionnement du nouveau noeud" (fonction recevant certainenement un pointeur à modifier mais ne faisant aucune récursivité).
Par exemple un truc de ce style

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
t_noeud *cherche_emplacement_tres_tres_loin_au_pays_de_shrek(t_noeud *noeud)
{
    t_noeud *find;
 
    // Fin récursivité
    if (noeud == NULL) return NULL;
    if (trouvé_emplacement) return noeud;
 
    // Recherche branche gauche
    if ((find=cherche_emplacement_tres_tres_loin_au_pays_de_shrek(noeud->gauche)) != NULL) return find;
 
    // Recherche branche droite
    if ((find=cherche_emplacement_tres_tres_loin_au_pays_de_shrek(noeud->droite)) != NULL) return find;
 
   // Pas trouvé (mais normalement ça ne doit pas arriver)
   return NULL;
}
 
t_noeud *ajouter_noeud(t_arbre *arbre)
{
    t_noeud *find;
    t_noeud *new;
 
    if ((new=malloc(sizeof(t_noeud))) == NULL) return NULL;
 
    new->oper=...
    new->valeur=...
    new->gauche=NULL;
    new->droite=NULL;
 
    if ((find=cherche_emplacement_tres_tres_loin_au_pays_de_shrek(arbre->racine)) == NULL)
    {
         // Placement à la racine
         arbre->racine=new;
         return new;
    }
 
    // Placement dans le noeud trouvé
    if (...test qui indique si le nouveau noeud doit aller à gauche ou à droite...) find->gauche=new;
    else find->droite=new;
    return new;
}

Bon c'est peut-être pas encore parfait mais c'est déjà l'idée. Il te faut en effet avoir des fonctions très très réduites que tu peux appeler quand tu en as besoin et à plusieurs endroits plutôt que des fonctions moyennes que tu ne peux appeler qu'une seule fois et où tu dois reproduire une partie du code dans une autre fonction quand tu as cette autre fonction qui fait presque pareil que la première (ajouter_noeud, ajouter_noeud_plus_loin, etc...)

Et surtout tout faire pour éviter ces putains de noeud** qui élèvent la probabilité de bug non pas au carré (une probabilité étant inférieure à 1, la mettre au carré la réduira au lieu de l'augmenter) mais à la puissance 1/2²...

[Médinoc]

Pour le coup d'éviter les Noeud**, je ne suis pas forcément d'accord, car beaucoup de fonctions liées aux arbres agissent sur des sous-arbres. Donc, à moins de mettre une structure t_arbre dans chaque nœud...

Par contre, quand on joue beaucoup avec des pointeurs et double-pointeurs, c'est là que la notation hongroise aide à éviter de trop s'emmêler les pinceaux.

[Sve@r]

Pour le coup d'éviter les Noeud**, je ne suis pas forcément d'accord, car beaucoup de fonctions liées aux arbres agissent sur des sous-arbres. Donc, à moins de mettre une structure t_arbre dans chaque nœud...

Oui effectivement si une fonction "simple" a besoin de modifier l'adresse d'un noeud, il n'y a pas de mal à lui passer un Noeud**. La fonction fait sa petite boucle, modifie le pointeur et basta. D'ailleurs on peut faire une petite modif à ma fonction "cherche_emplacement_tres_tres_loin_au_pays_de_shrek" et lui faire renvoyer directement l'adresse du pointeur où créer le nouveau noeud (plutôt que lui faire renvoyer le noeud père). Ce qui évitera à la fonction "ajouter_noeud" de devoir chercher s'il faut l'ajouter à gauche ou à droite.

Mais là t'as vu ? Ca se passe en récursif quoi. Bon peut-être qu'en rectifiant l'erreur que j'ai relevée, ça marchera mais j'avais même pas envie de dérouler sa fonction sur papier pour vérifier tellement j'avais déjà mal aux cheveux rien qu'en la regardant. Tu avoueras que ce genre de truc c'est comme se recouvrir d'essence et jongler avec des torches enflamées...

[Médinoc]

Généralement, je fais une fonction de recherche récursive qui retourne l'emplacement où insérer (pointeur de pointeur), plus un wrapper non-const sur la première et une fonction de recherche récursive const. L'insertion elle-même, une fois l'emplacement trouvé, n'est alors pas récursive.

[Nicotyrox]

Excusez moi du retard de ma réponse, j'ai pas vraiment eu de temps cette semaine ^^

Merci beaucoup pour vos aides, j'ai pu avancer mon travail