Trier un arbre

[Rockleader]

Bon, je n'ai plus d'erreurs sur mes structures et fonctions à la compilation; et à l'exécution cela semble bien se passer; en revanche je prend une erreur de segmentation sur un affichage O_o

Je ne m'explique pas pourquoi.
Les printf OK et EMPILE ne sont là que pour servir de trace.

En ce qui concerne l'algo j'espère que je ne me suis pas planté

Code: Tout sélectionner

void triIteratifGRD(GRD a)
{
   PILE p=initpile();
   if(a!=NULL)
   {
      printf("OK\n");
      p=empile(p,&a);
   }
   while(!pilevide(p))
   {
      printf("OK2\n");
      a=(depile(&p));
      if(estVideGRD(a))
      {
         printf("OK3\n");
         if(!pilevide(p))
         {
            printf("OK4\n");
            a=depile(&p);
            printf("OK5\n");
            printf("%d\n",a->val); /*erreur de segmentation*/
            printf("OK6\n");
         }
      }
      else
      {
         printf("EMPILE\n");
         p=empile(p,&((a)->gauche));
         p=empile(p,&(a));
         p=empile(p,&((a)->droite));
      }
   }
}

Une idée de ce qui cloche ?


Pour rappel voici les structures

Code: Tout sélectionner

typedef struct unfeuille {
   int val;
   struct unfeuille *gauche;
   struct unfeuille *droite;
}feuille;
typedef struct unfeuille * GRD;

typedef struct elpile {
  GRD* feuille;
  struct elpile* suivant; //pointeur sur la feuille suivante
 }pile;

typedef struct elpile* PILE;

a est bien de type GRD donc a->val est bien un int pour moi. Du coup je vois pas d'où ça vient...


Au niveau de la pile il doit pas y avoir de problème sinon je ne passerais pas les fonctions.

[fatal_error]

en tout cas,

Code: Tout sélectionner

         p=empile(p,&((a)->gauche));
         p=empile(p,&(a));

c est pas coherent
Déjà:
pourquoi utiliser &a->gauche et pas tout simplement a->gauche
de même pourquoi mettre dans la pile des pointeurs de pointeurs de struct...
Par ailleurs, unfeuille, ca veut rien dire, et normalement en plus feuille c est reserve pour les terminaux idem les noeuds qui ont pas de fils, donc voire unfeuille avec noeud gauche et noeud droite non NULL, c est quelque peu tiquant!

Par ailleurs, reecrire sur la valeur "(GRD) a" passe en argument, cest un peu moyen..., generalement on fait ca si on veut modifier la valeur qui est passee en argument, mais ca devrait pas etre le cas ici.

Bref, comme d hab tu nous mets une mine d'erreurs potentielles en demandant de trouver c 'est quoi qui passe pas!

[Rockleader]

pourquoi utiliser &a->gauche et pas tout simplement a->gauche
de même pourquoi mettre dans la pile des pointeurs de pointeurs de struct...

Et bien il me semble que pour l'algo tourne bien il faut modifier le GRD et donc on est obligé de passer par pointeurs sachant que je ne peux pas récupérer et la pile et le GRD.

Mais tu as raison il y a un truc pas logique dans mon algo, le code est dégueu mais les fonctions marchent; du moins elles ont l'air de marcher. Mais l'algo que j'ai produit n'est pas correct je pense.

[fatal_error]

ya pas besoin de passer l'adresse d'un pointeur pour modifier le contenu pointé par ce pointeur.
Passer le pointeur suffit

[Rockleader]

ya pas besoin de passer l'adresse d'un pointeur pour modifier le contenu pointé par ce pointeur.
Passer le pointeur suffit

Moui c'est pas faux.

Je fais une pause là dessus j'essaierais de le reprendre plus tard.


EN attendant, je m'attaque à un autre type de structure, un itérateur sur un arbre GRD.

Cet itérateur permet un sens de parcours par défaut croissant; mais qui peut aussi être décroissant.
Il contient un pointeur de fonction retournant l'itérateur dont l'arbre courant est le suivant. L'affectation de ce pointeur se fera en fonction du sens de parcours.

Je voudrais savoir si la structure que j'ai proposé est correcte ou pas. Ma structure d'arbre est OK; j'ai juste un doute sur celle de l'itérateur, je ne suis pas sûr que cela corresponde bien à ce qui est demandé.

Code: Tout sélectionner

#define CROISSANT 0
#define DECROISSANT 1


typedef struct unfeuille {
   int val;
   struct unfeuille *filsG;
   struct unfeuille *filsD;
   struct unfeuille *pere;
}feuille;

typedef struct unfeuille * arbreGRD;


typedef struct sIterGRD {
   int sens;/*sens de parcours de l'arbre*/
   arbreGRD courant;
   struct sIterGRD* (* prochainIterateur)(struct sIterGRD *);
}arbre;

typedef struct sIterGRD *iterGRD;

[fatal_error]

struct sIterGRD* (* prochainIterateur)(struct sIterGRD *);

Je sais pas pourquoi tu enquilles un pointeur de fonction oO, mais le comportement d'un itérateur c'est qu'on puisse faire

Code: Tout sélectionner

Iterateur it (Arbre*);
Iterateur itSuivant = it.next();
Arbre* arbre = itSuivant.getArbre();

Qui globalement se traduit en C par

Code: Tout sélectionner

struct Iterateur{
 int sens; //devrait etre un enum
 struct unfeuille* noeud;
}
struct Iterateur iterateur_suivant(struct Iterateur courant){
 Iterateur retour;
 retour.sens = courant.sens;
 retour.noeud = courant.noeud->gauche;
 return retour;
}

Dans les grosses lignes

[Rockleader]

Je sais pas pourquoi tu enquilles un pointeur de fonction oO, mais le comportement d'un itérateur c'est qu'on puisse faire

Par rapport à la consigne;

Cet itérateur permet un sens de parcours par défaut croissant; mais qui peut aussi être décroissant.
Il contient un pointeur de fonction retournant l'itérateur dont l'arbre courant est le suivant. L'affectation de ce pointeur se fera en fonction du sens de parcours.

J'ai cru comprendre dans cet énoncé que l'on me demandait un pointeur de fonction. A tord peut être ?

[fatal_error]

Faut dire, ton énoncé c'est dla mxxxxx aussi.

J'ai cru comprendre dans cet énoncé que l'on me demandait un pointeur de fonction. A tord peut être ?

au temps pour moi, j'ai lu trop hâtivement.

Ben déjà, tu as pas besoin de stocker sens, parce que comme le dit l'énoncé (...), c'est le pointeur de fonction qui connait le sens de parcours.

Enfin bref,
tu peux garder un iterateur classique et lui adjoindre le pointeur de fonction..

struct iterator{
Arbre* a;
struct iterator (* nextIterator)(struct Arbre*);
};

cela dit j'aime pas du tout ce design, parce que l'utilisateur doit fournir nextIterator alors qu'il s'en tape d'écrire des machins pour manipuler les iterators, lui tout ce qu'il veut c'est pouvoir manipuler le prochain élément...
Mais bon, plus rien me surprend avec ton prof =D

[Rockleader]

Ok; donc au final

Code: Tout sélectionner

#define CROISSANT 0
#define DECROISSANT 1


typedef struct unfeuille {
   int val;
   struct unfeuille *filsG;
   struct unfeuille *filsD;
   struct unfeuille *pere;
}feuille;

typedef struct unfeuille * arbreGRD;


typedef struct sIterGRD {
   int sens;/*sens de parcours de l'arbre*/
   arbreGRD* courant;
   struct sIterGRD(* prochainIterateur)(struct sIterGRD *);
}arbre;

typedef struct sIterGRD *iterGRD;


sens est useless d'après toi, mais je me rappelle qu'en cours le prof nous as demandé de le spécifier quand même dans la structure donc je vais garder, peut être que ça servira à moment donné.





Si j'ai bien compris; la première fonction que je dois réaliser va correspondre au proto suivant

Code: Tout sélectionner

IterGRD creerIterGRD(arbreGRD a)

La création ça va donc être

Code: Tout sélectionner

IterGRD creerIterGRD(arbreGRD a)

iterGRD itA=malloc(sizeof(arbreGRD));
//vérification du malloc puis
itA->sens=CROISSANT; //valeur par défaut
itA->courant=(*a); //ici j'ai un doute courant est de type arbreGRD* et a est de type arbreGRD
/*et pour le troisième champ de structure qui est le pointeur de fonction, je vois
pas vraiment comment le mettre à jour si j'ai bien compris ce que l'on veut
 stocker là c'est l'itérateur suivant. Or à la création il n'y en as pas si je ne m'abuse.
Donc on retourne NULL pour ce champ ? Dans tous les cas je vois pas vraiment comment faire.*/

return itA;


[fatal_error]

IterGRD creerIterGRD(arbreGRD a)

lorsque tu crèes ton itérateur, tu t'attends à pouvoir avoir accéder à l'itérateur suivant. Donc il faut pour qu'il soit valide, que tu puisses pouvoir itérer.

Idem, l'itérateur retourné doit contenir le pointeur de fonction.

Code: Tout sélectionner

IterGRD creeIterGRD(arbreGRD a, machin*(nextFunction)(Arbre*)){
 IterGRD it;
 it.prochainIterateur = nextFunction;
 return it;
}

sens est useless d'après toi, mais je me rappelle qu'en cours le prof nous as demandé de le spécifier quand même dans la structure donc je vais garder, peut être que ça servira à moment donné.

une parenthèse: si le prof dit de le mettre tu le mets.
Mais ne le mets pas parce qu'hypothétiquement ca va servir. Sinon, fais du java :lol3:

[Rockleader]

Par contre, mon prototype est donné et il s'agit bien de

IterGRD creerIterGRD(arbreGRD a)

et non de

IterGRD creerIterGRD(arbreGRD a, machin)

[...]

EN fait on positionne l'itérateur sur l'arbre qui va contenir la plus petite valeur.

[fatal_error]

ben dans ce cas là mets un setter.
C'est nul, mais ca a l'air d'être ce que veux ton prof :x

[Rockleader]

ben dans ce cas là mets un setter.
C'est nul, mais ca a l'air d'être ce que veux ton prof

Je sens que tu l'aimes bien mon prof :d


C'est quoi un setter ?

J'ai trouvé des infos là dessus seulement sur ce topic mais je n'ai vraiment pas compris: http://www.developpez.net/forums/d1211973/java/general-java/debuter/quoi-servent-getter-setter/

(et ça parle java donc --')

[fatal_error]

Code: Tout sélectionner

//what users see
struct Arbre{
 Private* data;
}
void set_arbre_value(Arbre* arbre, int value);//a setter
int get_arbre_value(Arbre* arbre);//a getter

//implementation
struct Private{
 int value;
}
void set_arbre_value(Arbre* arbre, int value){
  arbre->data->value = value;
}
int get_arbre_value(Arbre* arbre){
  return arbre->data->value;
}

Dans ton cas ca change rien parce que tout est publique...
mais dans l'idée, si les données étaient masquées à l'utilisateur, ben c'est à ca que serve les getter et setter

[Rockleader]

Dans ton cas ca change rien parce que tout est publique...
mais dans l'idée, si les données étaient masquées à l'utilisateur, ben c'est à ca que serve les getter et setter

Ok; ça serait dans le cas ou j'aurais fait de la protection de donnée alors.



Mais je ne vois toujours pas ce que ça va donner en partant de ma structure à cause de ce fameux champ de pointeur de fonction. Je dois vraiment être lent à la détente, désolé !!!

[fatal_error]

Ok; ça serait dans le cas ou j'aurais fait de la protection de donnée alors.

1) Rien ne t'empêche de mettre tes setters/getters
2) Tu devrais protéger tes données, spécialement ton pointeur de fonction. Parce que ca serait ballo que ton utilisateur décide de changer le pointeur alors que t'es déjà entrain d'itérer... c'est un peu un workaround pour le fait que celui-ci ne soit pas donné dans le constructeur/initialisation forcée de ta structure...

3) Tu devrais toujours protéger tes données si elles sont pas triviales.. mais je vais pas te faire un cours, alors documentes toi sur les POD.

Mais je ne vois toujours pas ce que ça va donner en partant de ma structure à cause de ce fameux champ de pointeur de fonction. Je dois vraiment être lent à la détente, désolé !!!

Faut dire en un quart d'heure, ca fait ptet un peu court.
Qu'aimerais-tu écrire du côté utilisateur?
Si je te dis d'itérer sur tout l'arbre, tu aimerais écrire quoi? (on s'en tape des erreurs de syntaxe, juste les grandes lignes en C)

[Rockleader]

Ben,

si on a un arbreGRD

Je serais tenté de faire une boucle sur chaque sous arbre avec appel récursif; un peu comme j'avais fais précédemment

Code: Tout sélectionner

void triGRD(arbreGRD a)
{
   if(!estVidearbreGRD(a))
   {
      triGRD(a->filsG);
      printf("%d\n",a->val);
      triGRD(a->filsD);
   }
}

Sa c'est ce que je ferais pour avoir tout l'arbre

Ici, on cherche à retourner l'itérateur en positionnant sur l'arbre ayant la plus petite valeur.

Donc il faudrait prendre le premier résultat retourner par triGRD ?

[joel76]

Code: Tout sélectionner

int tri(Tree* t){
 if(t==NULL) return 0;
 printf("%d",t->value);
 int sum = tri(t->left);
 printf("%d",sum);
 int sum2 = tri(t->right);
 int total = sum+sum2+t->value;
 printf("%d",total);
 return total;
}


Pour revenir à ce problème, j'ai réussi à dérécursiver ce bout de prog (légérement modifié pour afficher le nom de la branche dont on vient de calculer la somme).
Je donne le code C, pour ceux que ça intéresse :

Code: Tout sélectionner

typedef enum {RACINE, GAUCHE, DROITE} type_arbre;
typedef struct
{
   int p[1024];
   type_arbre t[1024];
   int ind;
} pile_valeur;

typedef struct
{
   GRD *p[1024];
   type_arbre t[1024];
   int ind;
} pile_arbre;


// gestion des piles de valeurs
void init_pile_valeur(pile_valeur *p)
{
   p->ind = 0;
}

int pile_valeur_vide(pile_valeur *p)
{
   return p->ind == 0;
}

int depile_pile_valeur(pile_valeur *p, type_arbre *type)
{
   p->ind--;
   *type = p->t[p->ind];
   return p->p[p->ind];
}

void empile_pile_valeur(pile_valeur *p, int v, type_arbre type)
{
   p->t[p->ind] = type;
   p->p[p->ind++] = v;
}

// gestion des piles de feuilles
void init_pile_arbre(pile_arbre *p)
{
   p->ind = 0;
}

int pile_arbre_vide(pile_arbre *p)
{
   return p->ind == 0;
}

GRD *depile_pile_arbre(pile_arbre *p, type_arbre *type)
{
   p->ind--;
   *type = p->t[p->ind];
   return p->p[p->ind];
}

void empile_pile_arbre(pile_arbre *p, GRD *arbre, type_arbre type)
{
   p->t[p->ind] = type;
   p->p[p->ind++] = arbre;
}


// le code de la dérécursivation
int itere_somme(GRD *arbre)
{
   pile_valeur p_v;
   pile_arbre p_a;
   GRD *pred = NULL;
   int v = 0;
   int tl = 0;
   int i, j, k;

   init_pile_valeur(&p_v);
   init_pile_arbre(&p_a);
   empile_pile_arbre(&p_a, arbre, RACINE);

   
   while(! pile_arbre_vide(&p_a))
   {
      type_arbre t_a;
      GRD *feuille = depile_pile_arbre(&p_a, &t_a);

      if (feuille == NULL)
      {
         empile_pile_valeur(&p_v, 0, t_a);

         if (t_a == GAUCHE)
         {
            puts("Sous arbre gauche 0");
         }
         else
         {
            type_arbre t;
            puts("Sous arbre droit 0");
            // ici on depile trois valeurs
            // on affiche la somme
            // puis on empile la somme
            do
            {
               v = 0;
               v += depile_pile_valeur(&p_v, &t);
               v += depile_pile_valeur(&p_v, &t);
               v += depile_pile_valeur(&p_v, &t);
               empile_pile_valeur(&p_v, v, t);
               printf("Total %d\n", v);
               switch(t)
               {
               case RACINE :
                  
                  break;
               case GAUCHE :
                  printf("Sous arbre gauche %d\n", v);
                  break;
               case DROITE :
                  printf("Sous arbre droit %d\n", v);
                  break;
               }
            }
            while (t == DROITE);            
         }
      }
      else
      {
         printf("Noeud %d\n", feuille->val);
         empile_pile_valeur(&p_v, feuille->val, t_a);
         empile_pile_arbre(&p_a, feuille->droite, DROITE);
         empile_pile_arbre(&p_a, feuille->gauche, GAUCHE);
      }
   }
   return v;
}


le code récursif que j'ai dérécursivé (inspiré de delui de fatal_error):

Code: Tout sélectionner

int tri(GRD * t)
{
   int sum1 , sum2, total;
   if(t==NULL)
      return 0;
      
   printf("noeud %d\n",t->val);
 
   sum1 = tri(t->gauche);
   printf("sous arbre gauche %d\n",sum1);

   sum2 = tri(t->droite);
   printf("sous arbre droit %d\n",sum2);

   total = sum1+sum2+t->val;
   printf("total %d\n",total);
   
   return total;
}

[fatal_error]

un peu plus verbeux mais plus naturel (subjectif) et généralisable:

Code: Tout sélectionner

#include
#include
struct Tree{
  Tree():left(NULL),right(NULL),val(0){}
  ~Tree(){
    if(left){
      delete left;
    }
    if(right){
      delete right;
    }
  }
  Tree* left;
  Tree* right;
  int val;
};
Tree* initTree(){
/*
    root
  a     d
b   c e   f
*/
  Tree* root = new Tree;
  Tree* a = new Tree;
  Tree* b = new Tree;
  Tree* c = new Tree;
  Tree* d = new Tree;
  Tree* e = new Tree;
  root->left = a;root->right=d;
  a->left = b;
  a->right = c;
  a->val = 10;
  d->val = 20;
  d->left = e;
  b->val = 2;
  c->val = 4;
  e->val = 6;
  return root;
}
typedef enum {MAIN, EXPLORE_LEFT, EXPLORE_RIGHT} ExploreType;
struct ContextMethod{
  Tree* t;
  int sum1;
  int sum2;
};
struct ReturnValue{
  ReturnValue(int v=-1):value(v){}
  int value;
};

int main(){
  Tree* root = initTree();
  std::list > stack;
  ReturnValue returnValue;
 
  ContextMethod rootContext;  rootContext.t = root;
  stack.push_front(std::pair(rootContext, MAIN));
  while(stack.size()){
    //restore context
    std::pair context = stack.front();
    stack.pop_front();
    if(context.second == MAIN){
      if(context.first.t == NULL){
        returnValue = ReturnValue(0);
      }else{
        std::coutvalleft;
        stack.push_front(context);
      }
    }else if(context.second == EXPLORE_LEFT){
      context.first.sum1 = returnValue.value;
      std::coutright;
      stack.push_front(context);
    }else if(context.second == EXPLORE_RIGHT){
      context.first.sum2 = returnValue.value;
      std::coutval;
       std::cout<<"total "<<total<<std::endl;
       returnValue = ReturnValue(total);
    }
  }
  delete root;
   return 0;
}


edit: c'est du c++, mais bon, le code reste compréhensible