Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Bin tree, errore di segmentazione
Forum - C/C++ - Bin tree, errore di segmentazione

Avatar
Dante.cpp (Normal User)
Pro


Messaggi: 65
Iscritto: 23/11/2011

Segnala al moderatore
Postato alle 13:57
Lunedì, 21/01/2013

Compilo ed eseguo il seguente, in questa maniera:
Codice sorgente - presumibilmente C/C++
  1. $ cc main.c tree.c strg.c -o tree -g
  2. $ ./tree hello haw are you fine and you fine
  3. Errore di segmentazione (core dump creato)
  4. $


Codice sorgente - presumibilmente C/C++
  1. #include"tree.h"
  2.  
  3. /**
  4.  * La funzione tree_marge, crea un nuovo nodo t0, avente come figli
  5.  * i nodi t1 e t2. L'informazione della foglia(nodo) padre sarà il
  6.  * parametro s.
  7.  *
  8.  */
  9. Tree tree_merge( Str s, Tree t1, Tree t2 )
  10. {                                                  
  11.   Tree t0 = (Tree)malloc(sizeof(struct Tree))
  12.     ;
  13.   t0->left = t1;
  14.   t0->right = t2;
  15.  
  16.   str_cpy( t0->word, s);
  17.  
  18.   return t0;
  19. }
  20.  
  21. /**
  22.  * Se l'albero t è vuoto, allora crea una foglia, altrimenti vengono comparate le due
  23.  * informazioni "s" e "tree_word(t)". Se s è minore allora, si procede ricorsivamente con
  24.  * un'inserimento verso sinistra, mentre essendo s maggiore si procederà ricorsivamente
  25.  * verso il ramo destro.
  26.  * Questo metodo di inserimento genera un'albero avente le parole lessicograficamente
  27.  * minori, in basso a sinistra e quelle maggiori in basso a destra.
  28.  *
  29.  */
  30. Tree tree_insert( Str s, Tree t)
  31. {
  32.   if( tree_isvoid(t) )                                
  33.     return tree_new_leaf(s);
  34.  
  35.   int flag = str_cmp( tree_word(t), s);
  36.  
  37.   if (flag > 0)                                  
  38.     return tree_merge(tree_word(t), tree_insert(s, tree_left(t)), tree_right(t));
  39.    
  40.   else if (flag < 0)        
  41.     return tree_merge(tree_word(t), tree_left(t), tree_insert(s, tree_right(t)));
  42.  
  43.   else
  44.     return t;
  45. }
  46.  
  47.  
  48. int main(int argc, char **argv)
  49. {
  50.   Tree dizionario = NULL;  
  51.  
  52.   int i;
  53.   for(i=1;i<argc;i++)
  54.     dizionario = tree_insert( argv[i] , dizionario )
  55.       ;    
  56.   tree_show(dizionario);
  57.  
  58.   return 0;
  59. }


Analizzando con gdb non si ferma all'errore, inoltre anche se metto un break point in tree_insert(), l'esecuzione non si ferma appena lo incontra...

PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6403
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 14:33
Lunedì, 21/01/2013
Ci mostri il file

"tree.h"

?

Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti ( uno dei padri fondatori del moderno Calcolo delle probabilità ) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
Dante.cpp (Normal User)
Pro


Messaggi: 65
Iscritto: 23/11/2011

Segnala al moderatore
Postato alle 15:24
Lunedì, 21/01/2013
Codice sorgente - presumibilmente C++
  1. //tree.h
  2.  
  3. #define TREE
  4.  
  5. #ifndef STRG
  6.   #include"strg.h"
  7. #endif
  8.  
  9. #ifndef STDIO
  10.   #include<stdio.h>
  11. #endif
  12.  
  13. #ifndef STDLIB
  14.   #include<stdlib.h>
  15. #endif
  16.  
  17. #ifndef STDBOOL
  18.   #include<stdbool.h>
  19. #endif
  20.  
  21.  
  22. struct Tree
  23. {                                        
  24.   Str word;                                    
  25.   struct Tree *left, *right;                                                                                
  26. };
  27.  
  28. typedef struct Tree * Tree;
  29.  
  30.  
  31. /**
  32.  * Unisce due alberi.
  33.  *
  34.  */
  35. extern Tree tree_merge( Str, Tree, Tree );
  36.  
  37.  
  38. /**
  39.  * Alloca una nuova foglia, priva di figli.
  40.  *
  41.  */
  42. extern Tree tree_new_leaf( Str );  
  43.  
  44.  
  45. /**
  46.  * Verifica che l'albero sia vuoto.
  47.  *
  48.  */
  49. extern int tree_isvoid(Tree );
  50.  
  51.  
  52. /**
  53.  * Restituiscono rispettivamente il figlio sinistro
  54.  * e destro di t.
  55.  *
  56.  */
  57. extern Tree tree_left( Tree );
  58.  
  59. extern Tree tree_right( Tree );
  60.  
  61.  
  62. /**
  63.  * Restituisce l'informazione del nodo t
  64.  *
  65.  */
  66. extern Str tree_word( Tree );
  67.  
  68. /**
  69.  * Inserisce nell'albero t, la parola s in maniera ordinata.
  70.  *
  71.  */
  72. extern Tree tree_insert( Str , Tree );
  73.  
  74. /**
  75.  * Restituiscono rispettivamente le stringhe lessicografficamente
  76.  * ninore e maggiore.
  77.  *
  78.  */
  79. extern Str tree_min( Tree );
  80.  
  81. extern Str tree_max( Tree );
  82.  
  83.  
  84. /**
  85.  * Stampa sul terminane l'albero t.
  86.  *
  87.  */
  88. extern void tree_show( Tree );


Posto anche il file con le definizioni?

Ultima modifica effettuata da Dante.cpp il 21/01/2013 alle 15:32
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6403
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 16:08
Lunedì, 21/01/2013
Devi postare tutto il sorgente in modo che possa essere ricompilato *senza errori* per poterlo provare.

Altrimenti ci si sta più tempo a capire il problema e non hai risposte.

In particolare, comunque, queste linee

Codice sorgente - presumibilmente C/C++
  1. struct Tree
  2. {                                        
  3.   Str word;                                    
  4.   struct Tree *left, *right;                                                                                
  5. };
  6.  
  7. typedef struct Tree * Tree;


mi sembrano assurde ... che senso ha chiamare la struttura e il nuovo tipo con lo stesso nome (Tree) ?

Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti ( uno dei padri fondatori del moderno Calcolo delle probabilità ) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
Dante.cpp (Normal User)
Pro


Messaggi: 65
Iscritto: 23/11/2011

Segnala al moderatore
Postato alle 16:19
Lunedì, 21/01/2013
mmm, non hai torto, cosi è più bellino:
Codice sorgente - presumibilmente C/C++
  1. struct Leaf
  2. {                                        
  3.   Str word;                                    
  4.   struct Leaf *left, *right;                                                                                
  5. };
  6.  
  7. typedef struct Leaf * Tree;


Codice sorgente - presumibilmente C/C++
  1. //tree.c
  2.  
  3. #ifndef TREE
  4.  #include"tree.h"
  5. #endif
  6.  
  7. /**
  8.  * La funzione tree_marge, crea un nuovo nodo t0, avente come figli
  9.  * i nodi t1 e t2. L'informazione della foglia(nodo) padre sarà il
  10.  * parametro s.
  11.  *
  12.  */
  13. Tree tree_merge( Str s, Tree t1, Tree t2 )
  14. {                                                  
  15.   Tree t0 = (Tree)malloc(sizeof(struct Leaf))
  16.     ;
  17.   t0->left = t1;
  18.   t0->right = t2;
  19.  
  20.   str_cpy( t0->word, s);
  21.  
  22.   return t0;
  23. }
  24.  
  25. /**
  26.  * Alloca una nuova foglia, priva di figli.
  27.  *
  28.  */
  29. Tree tree_new_leaf( Str s )
  30. {
  31.   return tree_merge( s, NULL, NULL )
  32.     ;  
  33. }
  34.  
  35. /**
  36.  * Verifica che l'albero sia vuoto.
  37.  *
  38.  */
  39. int tree_isvoid(Tree t)
  40. {
  41.   if (t == NULL)                                                                  
  42.     return true;
  43.   else
  44.     return false;
  45. }
  46.  
  47.  
  48. /**
  49.  * Restituiscono rispettivamente il figlio sinistro
  50.  * e destro di t.
  51.  *
  52.  */
  53. Tree tree_left( Tree t ){ return t->left; }
  54.  
  55. Tree tree_right( Tree t ){ return t->right; }
  56.  
  57.  
  58. /**
  59.  * Restituisce l'informazione del nodo t
  60.  *
  61.  */
  62. Str tree_word( Tree t ){ return t->word; }
  63.  
  64.  
  65. /**
  66.  * Se l'albero t è vuoto, allora crea una foglia, altrimnti vengono comparete le due
  67.  * informazioni s e tree_word(t). Se s è minore allora, si procede ricorsivamente con
  68.  * un'inserimento verso sinistra, mentre essendo s maggiore si procederà ricorsivamente
  69.  * verso il ramo destro.
  70.  * Questo metodo di inserimento genera un'albero avente le parole lessicografficamente
  71.  * minori in basso a sinistra e quelle maggiori in basso a destra.
  72.  *
  73.  */
  74. Tree tree_insert( Str s, Tree t)
  75. {
  76.   if( tree_isvoid(t) )                                
  77.     return tree_new_leaf(s);
  78.  
  79.   int flag = str_cmp( tree_word(t), s);
  80.  
  81.   if (flag > 0)                                  
  82.     return tree_merge(tree_word(t), tree_insert(s, tree_left(t)), tree_right(t));
  83.    
  84.   else if (flag < 0)        
  85.     return tree_merge(tree_word(t), tree_left(t), tree_insert(s, tree_right(t)));
  86.  
  87.   else
  88.     return t;
  89. }
  90.  
  91. /**
  92.  * Scorre l'albero dall'alto verso il basso a sinistra
  93.  * cosi trovando l'informazione minore.
  94.  * La funzione tree_max funzione in maniera analoga.
  95.  *
  96.  */
  97. Str tree_min( Tree t )
  98. {                  
  99.   if(tree_isvoid(tree_left(t)))
  100.     return tree_word(t);        
  101.   else
  102.     return tree_min(tree_left(t));                  
  103. }
  104.  
  105.  
  106. Str tree_max( Tree t )
  107. {
  108.   if(tree_isvoid(tree_right(t)))
  109.     return tree_word(t);  
  110.   else
  111.     return tree_max(tree_right(t));
  112. }
  113.  
  114.  
  115. /**
  116.  * Stampa sul terminane l'albero t.
  117.  *
  118.  */
  119. void tree_show( Tree t )
  120. {
  121.   if (tree_isvoid(t) == false)
  122.   {
  123.     tree_show(tree_left(t));
  124.     printf("%s ", tree_word(t));
  125.     tree_show(tree_right(t));
  126.   }
  127. }


Codice sorgente - presumibilmente C++
  1. //strg.h
  2.  
  3. #define STRG
  4.  
  5. #ifndef STDIO
  6.   #include<stdio.h>
  7. #endif
  8.  
  9. #ifndef STDLIB
  10.   #include<stdlib.h>
  11. #endif
  12.  
  13. #ifndef STRING
  14.   #include<string.h>
  15. #endif
  16.  
  17.  
  18. typedef  char * Str;
  19.  
  20.  
  21. /**
  22.  * Dimensione massima delle stringhe gestite; se l'input
  23.  * supera il limite la stringa viene tagliata, evitando
  24.  * di invadere zone di memoria adiacenti.
  25.  *
  26.  */
  27. #define MAX_CH 1024
  28.  
  29.  
  30. /**
  31.  * Alloca una vettore di MAX_CH+1 char, che potra contenere
  32.  * una stringa di MAX_CH carateri, piu un byte per il caratere
  33.  * di fine stringa.
  34.  *
  35.  */
  36. extern Str str_new_max();
  37.  
  38. /**
  39.  * Alloca una vettore di nchar+1 char, che potra contenere
  40.  * una stringa di nchar carateri, piu il fine stringa. Se
  41.  * cerchiamo di allocare stringhe di lunghezza maggiore di MAX_CH,
  42.  * verrà restituito NULL.
  43.  *
  44.  */
  45. extern Str str_new( int );
  46.  
  47. /**
  48.  * Copia la stringa s2 in s1, sino a un massiamo di MAX_CH
  49.  * carateri, se la stringa di destinazione è troppo picola
  50.  * restituisce -1 altrimenti 0
  51.  *
  52.  */
  53. extern int str_cpy( Str, Str );
  54.  
  55. /**
  56.  * Crea una coppia identica del parametro passato; se
  57.  * l'input è maggiore di MAX_CH restiruisce NULL.
  58.  *
  59.  */
  60. extern Str str_twix( Str );
  61.  
  62. /**
  63.  * Compara lesicografficamente due stringhe prive di spazzi. Restiruisce
  64.  * un valore negativo se s1< s2, 0 se s1 == s2 e un intero positivo se s1>s2.
  65.  *
  66.  */
  67. extern int str_cmp( Str, Str );


Codice sorgente - presumibilmente C++
  1. //strg.c
  2.  
  3. #ifndef STRG
  4.   #include"strg.h"
  5. #endif
  6.  
  7. /**
  8.  * Alloca una vettore di MAX_CH+1 char, che potra contenere
  9.  * una stringa di MAX_CH carateri, piu un byte per il caratere
  10.  * di fine stringa.
  11.  *
  12.  */
  13. Str str_new_max()
  14. {
  15.   return (Str) calloc( MAX_CH+1, sizeof(char))
  16.     ;
  17. }
  18.  
  19. /**
  20.  * Alloca una vettore di nchar+1 char, che potra contenere
  21.  * una stringa di nchar carateri, piu il fine stringa. Se
  22.  * cerchiamo di allocare stringhe di lunghezza maggiore di MAX_CH,
  23.  * verrà restituito NULL.
  24.  *
  25.  */
  26. Str str_new( int nchar )
  27. {
  28.   Str out
  29.     =
  30.   nchar <= MAX_CH
  31.     ?  
  32.   (Str) calloc( nchar+1, sizeof(char))
  33.     :
  34.   (Str) NULL
  35.     ;
  36.    
  37.   return out;
  38. }
  39.  
  40. /**
  41.  * Copia la stringa s2 in s1, sino a un massiamo di MAX_CH
  42.  * carateri, se la stringa di sestinazione è troppo picola
  43.  * restituisce -1 altrimenti 0.
  44.  *
  45.  */
  46. int str_cpy( Str s1, Str s2)
  47. {
  48.   int flag
  49.     =
  50.   strlen(s2) <= strlen(s1)
  51.     ?
  52.   0 : -1
  53.     ;
  54.    
  55.   strncpy( s1, s2, MAX_CH);
  56.  
  57.   return flag;
  58. }
  59.  
  60.  
  61. /**
  62.  * Crea una coppia identica del parametro passato; se l'input è maggiore di MAX_CH restiruisce NULL.
  63.  * In questo caso non ha senso controllare le ecezzioni di str_cpy, dal momento che allocchiamo la
  64.  * stringa c, in funzione di strlen(s).
  65.  *
  66.  */
  67. Str str_twix( Str s )
  68. {
  69.   Str c = str_new( strlen(s) );
  70.  
  71.   if( c != NULL )
  72.     str_cpy(c,s);
  73.    
  74.   return c;
  75. }
  76.  
  77.  
  78. /**
  79.  * Compara lesicografficamente due stringhe prive di spazzi. Restiruisce un valore negativo se s1< s2,
  80.  * 0 se s1 == s2 e un intero positivo se s1>s2.
  81.  *
  82.  */
  83. int str_cmp( Str s1, Str s2 )
  84. {
  85.   return strncmp( s1, s2, MAX_CH )
  86.     ;
  87. }


Scusate la ridondanza dai commenti...

Ultima modifica effettuata da Dante.cpp il 21/01/2013 alle 16:22
PM Quote