Creare albero di stringhe

di il
9 risposte

Creare albero di stringhe

Ciao a tutti...a breve ho un esame e la maggior parte delle tracce richiede di creare un albero binario di stringhe...guardando per il forum ho visto delle richieste simili ma non ho trovato qualcosa che facesse al caso mio.

vi posto il mio codice....quando eseguo appena inserisco la prima stringa da inserire nell'albero mi da segmentation fault.
non capisco dove sia lo sbaglio nella funzione insert...potete darmi una mano?? grazie in anticipo dell'aiuto!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef struct _node{

  char *key;

  struct _node *left;

  struct _node *right;

} node;

node* insertRec(node *tree, char *input){

  if(tree==NULL){

    node *new=(node*) malloc(sizeof(node));

    new->key=input;

    new->left=NULL;

    new->right=NULL;

    return new;

  }

  if((strcmp(tree->key, input)>=0)) tree->left=insertRec(tree->left, input);

  else tree->right=insertRec(tree->right, input);

  return tree;

}


main(){

  int i, n; node *tree; char *input;

  scanf("%d", &n);

  for(i=0; i<n; i++){

    input=(char*) malloc(101*sizeof(char));

    scanf("%s", input);

    tree=insertRec(tree, input);

  }

}

9 Risposte

  • Re: Creare albero di stringhe

    A me funziona però devo dire che sto usando MS Visual Studio C++.

    Stai usando mingw o gcc su linux?

    In questo caso ti converrebbe compilare con l'opzione -g e provare a fare il debug. in alcuni casi mi ha aiutato.
  • Re: Creare albero di stringhe

    C'era qualche errore nel codice. Questa versione dovrebbe essere corretta: osserva bene le differenze.
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct _node
    {
    	char *key;
    	struct _node *left;
    	struct _node *right;
    } node;
    
    node* insertRec(node *tree, char *input)
    {
    	node *new=(node*) malloc(sizeof(node));
    	
    	/* ATTENZIONE!!! */
    	new->key = malloc(100 * sizeof(char));
    	strcpy(new->key, input);
    	
    	new->left=NULL;
    	new->right=NULL;
    
    	if(tree==NULL)
    	{
    		return new;
    	}
    
    	if((strcmp(tree->key, input)>=0)) tree->left=insertRec(tree->left, input);
    
    	else tree->right=insertRec(tree->right, input);
    
    	return tree;
    }
    
    
    void stampa_albero(node* tree)
    {
    	if(tree == NULL)
    		return;
    
    	stampa_albero(tree->left);
    	printf("%s  ", tree->key);
    	stampa_albero(tree->right);
    }
    
    
    int main()
    {
    	int i, n;
    	node *tree = NULL;
    	char *input;
    	input = (char*) malloc(101*sizeof(char));
    
    	printf("Numero di stringhe: ");
    	scanf("%d", &n);
    
    	for(i=0; i<n; i++)
    	{
    		scanf("%s", input);
    		tree=insertRec(tree, input);
    	}
    
    	stampa_albero(tree);
    	printf("\n");
    
    	return 0;
    }
    
  • Re: Creare albero di stringhe

    mentat ha scritto:


    devo dire che sto usando MS Visual Studio C++.
    Veramente anche io e compilando ho un warning su

    tree=insertRec(tree, input);

    warning C4700: variabile locale "tree" utilizzata senza inizializzazione

    e quindi non continuerei ad eseguirlo ...
  • Re: Creare albero di stringhe

    Esatto, poi non c'era l'allocazione per il campo "key" di un nodo e le stringhe venivano copiate con l'operatore =, anziché con l'apposita funzione strcpy.
    Infine c'era la malloc dentro al ciclo for che era inutile: basta eseguirla una volta sola all'inizio. Altrimenti si poteva utilizzare anche l'allocazione statica...

    Penso di aver detto tutto. In caso contrario sono certo che ci penserà oregon.
  • Re: Creare albero di stringhe

    Intanto grazie mille del tempo e delle risposte!
    A me funziona però devo dire che sto usando MS Visual Studio C++.
    io sto usando gcc su linux...quando compilo non mi da alcun errore

    ho provato anche a sostituire
    new->key=input;
    
    con
    new->key=(char*) malloc(101*sizeof(char));
    
    strcpy(new->key, input);
    ma mi da sempre segmentation fault quando eseguo.
  • Re: Creare albero di stringhe

    Per prima cosa i programmi andrebbero compilati con
    gcc -Wall ...
    che ti dà anche tutti i warning.
    Poi mi sembra strano che non ti funzioni: io ho provato a compilarlo con gcc su linux e non ho problemi.



    Hai fatto copia-incolla del codice che ti avevo postato? Per sicurezza lo rimetto:
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct _node
    {
    	char *key;
    	struct _node *left;
    	struct _node *right;
    } node;
    
    node* insertRec(node *tree, char *input)
    {
    	node *new=(node*) malloc(sizeof(node));
    	
    	/* ATTENZIONE!!! */
    	new->key = malloc(100 * sizeof(char));
    	strcpy(new->key, input);
    	
    	new->left=NULL;
    	new->right=NULL;
    
    	if(tree==NULL)
    	{
    		return new;
    	}
    
    	if((strcmp(tree->key, input)>=0)) tree->left=insertRec(tree->left, input);
    
    	else tree->right=insertRec(tree->right, input);
    
    	return tree;
    }
    
    
    void stampa_albero(node* tree)
    {
    	if(tree == NULL)
    		return;
    
    	stampa_albero(tree->left);
    	printf("%s  ", tree->key);
    	stampa_albero(tree->right);
    }
    
    
    int main()
    {
    	int i, n;
    	node *tree = NULL;
    	char *input;
    	input = (char*) malloc(101*sizeof(char));
    
    	printf("Numero di stringhe: ");
    	scanf("%d", &n);
    
    	for(i=0; i<n; i++)
    	{
    		scanf("%s", input);
    		tree=insertRec(tree, input);
    	}
    
    	stampa_albero(tree);
    	printf("\n");
    
    	return 0;
    }
    
  • Re: Creare albero di stringhe

    Ok scusa adesso con il tuo codice mi funziona...però a questo punto mi sorge un dubbio:

    non capisco perchè la riga di codice
    tree->key=input;
    non funzioni negli alberi ma quando la chiamo su una lista il programma fila liscio.

    non capisco quale sia la differenza.
    typedef struct _item{
    
      char *key;
    
      struct _item *next;
    
    } item;
    
    item* create_list(char *input){
    
      item *l=(item*) malloc(sizeof(item));
    
      l->key=input;
    
      l->next=NULL;
    
      return l;
    
    }
    
    void insert(item *l, char *input){
    
      item *t=l;
    
      while(t->next!=NULL) t=t->next;
    
      t->next=(item*) malloc(sizeof(item));
    
      t=t->next;
    
      t->key=input;
    
      t->next=NULL;
    
    }
    
  • Re: Creare albero di stringhe

    Quello che so è che non puoi copiare o assegnare una stringa con l'operatore =. Ad esempio
    nuova_stringa = vecchia_stringa;
    è sbagliato. Per questa operazione c'è l'apposita funzione strcpy e il codice corretto è
    strcpy(nuova_stringa, vecchia_stringa);
    Per il resto non saprei perché con le liste ti funzionasse. Evidentemente c'era qualcosa di diverso, però questa tienila come regola: copia di stringhe ==> strcpy.
  • Re: Creare albero di stringhe

    Ooook thanks!
Devi accedere o registrarti per scrivere nel forum
9 risposte