Discussion :

[zequiche]

Bonjour,
je cherche à coder un arbre en C avec des valeurs entières. Mon but est de pouvoir parcourir chaque branche de l'arbre (n-uplets d'entiers où n est la profondeur de la branche).

J'ai codé la chose suivante, qui semble marcher pour la première branche, mais me renvoit un segmentation fault lors de la construction de la deuxième branche.

J'ai pris une profondeur de 5 et les deux quintuplets suivants :
{ 7 2 3 4 5 }
et
{ 7 3 2 4 5 }
Mes deux branches se séparent donc au deuxième niveau de récursion et c'est là que la bât blesse.

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
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
  struct node *sn;
  int v;
  size_t s_sn;
} n_t;
 
int add_branch(int* branch, size_t s_branch, n_t** tree, size_t *s_tree) {
 
  int i=0;
  int* p=branch;
  size_t s_p=s_branch;
  n_t* new_tree;
  fprintf(stderr,"s_tree : %d\n",*s_tree);
 
  while (i < *s_tree && tree[i]->v!=*branch) { i++; }
 
  if (i==(*s_tree)) { /* ajout d un noeud */
    fprintf(stderr,"nouvelle val %d au niveau %d\n",*branch,s_branch);
    (*s_tree)++;
    fprintf(stderr,"allocating sizeof(n_t)*%d\n",*s_tree);
    if ( ( new_tree=realloc(*tree,sizeof(n_t)*(*s_tree) )) == NULL ) {
      fprintf(stderr,"error... could not realloc...\n");
      exit(1);
    }
    else {
      *tree=new_tree;
      tree[i]->sn=NULL;
      tree[i]->s_sn=0;
      tree[i]->v=*branch;
    }
  }
  else {
    fprintf(stderr,"val %d deja trouvee au niveau %d\n",*branch,s_branch);
  }
 
  // recursivite
  s_p--;
  if ( s_p > 0) {
    p++;
    add_branch(p,s_p,&(tree[i]->sn),&(tree[i]->s_sn));
  }
 
  return 0;
 
}
 
int main(int argc, char* argv[]) {
 
n_t* t=NULL;
size_t s_t=0;
int b[5]={7,2,3,4,5};
 
fprintf(stderr,"ajout de :");
for (int i=0 ; i< sizeof(b)/sizeof(int) ; i++)
  fprintf(stderr," %d",b[i]);
fprintf(stderr,"\n");
 
add_branch(b,sizeof(b)/sizeof(int),&t,&s_t);
 
b[2]=2;b[1]=3; /* 1 3 2 4 5 */
 
fprintf(stderr,"ajout de :");
for (int i=0 ; i< sizeof(b)/sizeof(int) ; i++)
  fprintf(stderr," %d",b[i]);
fprintf(stderr,"\n");
 
add_branch(b,sizeof(b)/sizeof(int),&t,&s_t);
 
}

Merci de votre aide, et pardon d'avance si le sujet a déjà été traité ou si c'est moi qui ai maltraité mon code...
J'ai tenté avec gdb, mais ça ne m'a pas avancé (je ne sais pas très bien l'utiliser, j'ai fait quelques breakpoints et affiché tree, mais bof)
L'erreur survient lorsque j'initialise le membre sn de tree[1] à NULL : tree[i]->sn=NULL. En fait tree[1] semble ne pas pointer vers un n_t, malgré mon realloc

[dalfab]

Bonjour,
Ligne 30, on a *tree qui reçoit une allocation d'un tableau de n_t.
Donc pour accéder à un élément de ce tableau on doit faire (*tree)[i] qui est de type n_t.
Et ligne 31 on accède à un champ de cet élément par (*tree)[i].sn = NULL;.
tree est un pointeur et tree[1] ne correspond pas à une adresse valide.

[zequiche]

Super, merci, voici mon code qui marche :

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
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
  struct node *sn;
  int v;
  size_t s_sn;
} n_t;
 
int add_branch(int* branch, size_t s_branch, n_t** tree, size_t *s_tree) {
 
  int i=0;
  int* p=branch;
  size_t s_p=s_branch;
  n_t* new_tree;
  //fprintf(stderr,"s_tree : %d\n",*s_tree);
 
  while (i < *s_tree && (*tree)[i].v!=*branch) { i++; }
 
  if (i==(*s_tree)) { /* ajout d un noeud */
    fprintf(stderr,"nouvelle val %d au niveau %d\n",*branch,s_branch);
    (*s_tree)++;
    fprintf(stderr,"allocating sizeof(n_t)*%d\n",*s_tree);
    if ( ( new_tree=realloc(*tree,sizeof(n_t)*(*s_tree) )) == NULL ) {
      fprintf(stderr,"error... could not realloc...\n");
      exit(1);
    }
    else {
      *tree=new_tree;
      (*tree)[i].sn=NULL;
      (*tree)[i].s_sn=0;
      (*tree)[i].v=*branch;
    }
  }
  else {
    fprintf(stderr,"val %d deja trouvee au niveau %d\n",*branch,s_branch);
  }
 
  // recursivite
  s_p--;
  if ( s_p > 0) {
    p++;
    fprintf(stderr,"recursion profondeur %d\n",s_p);
    add_branch(p,s_p,&((*tree)[i].sn),&((*tree)[i].s_sn));
  }
 
  return 0;
 
}
 
int main(int argc, char* argv[]) {
 
n_t* t=NULL;
size_t s_t=0;
int b[5]={7,2,3,4,5};
 
fprintf(stderr,"ajout de :");
for (int i=0 ; i< sizeof(b)/sizeof(int) ; i++)
  fprintf(stderr," %d",b[i]);
fprintf(stderr,"\n");
add_branch(b,sizeof(b)/sizeof(int),&t,&s_t);
 
b[2]=2;b[1]=3; /* 1 3 2 4 5 */
fprintf(stderr,"ajout de :");
for (int i=0 ; i< sizeof(b)/sizeof(int) ; i++)
  fprintf(stderr," %d",b[i]);
fprintf(stderr,"\n");
add_branch(b,sizeof(b)/sizeof(int),&t,&s_t);
 
}

avec des fuites de mémoire forcément puisque je n'ai pas encore écrit le code pour la libérer.
Merci !