una struttura annidata con puntatori

#include  #include  #include  typedef struct node *tree_ptr; typedef struct table * Table; struct node { char* element; tree_ptr left, right; }; typedef struct table { tree_ptr head; int tree_h; }table; char* key = NULL; Table insert(char* insert_key,Table t) { int height = 0; //tree_ptr ptr = t->head; tree_ptr *ptr = &(t->head); key = strdup(insert_key); tree_ptr new_node = malloc(sizeof(struct node)); new_node->element = key; new_node->left = NULL; new_node->right = NULL; if ( t->head==NULL ){ *ptr = new_node; t->tree_h = 0; printf("head:%s\n",t->head->element); return t; } while(1){ if ( strcmp(insert_key, (*ptr)->element)left ==NULL ){ (*ptr)->left = new_node; height++; if ( height > t->tree_h) t->tree_h = height; break; } else{ (*ptr) = (*ptr)->left; height++; } } else if ( strcmp(insert_key, (*ptr)->element)>0 ){ if ( (*ptr)->right ==NULL ){ (*ptr)->right = new_node; height++; if ( height > t->tree_h) t->tree_h = height; break; } else{ (*ptr) = (*ptr)->right; height++; } } else break; } return t; } int main() { Table t = malloc(sizeof(table)); t->head = NULL; t = insert("one", t); t = insert("two", t); t = insert("three", t); printf("%s\n",t->head->element); return 0; } 

Quanto sopra è un programma semplificato, viene dato un codice di definizione, quindi non ho potuto modificare la struttura di base, come la tabella, la tabella, il nodo, tree_ptr, mentre altri potrebbero essere modificati. Quello che sto cercando di implementare è un controllo ortografico, la tabella memorizza la testa dell’albero e alcune altre proprietà dell’albero (che qui viene omesso), l’albero è implementato come un albero binario ordinato.

Trovo che insert () funzioni bene fino a due volte, dopo il (* ptr) = (* ptr) -> right; anche la t-> head viene modificata. Quindi, dopo averlo usato due volte, ho perso la testa dell’albero.

Come modificare il mio insert ()?

Per inserire un nodo in un albero devi prima cercare una foglia vuota. Oltre a questo non si modifica t , quindi non c’è bisogno di scriverlo indietro per valore di ritorno:

 void insert( char* insert_key, Table t ) { // serach empty leaf, where to insert the new node tree_ptr *ptr = &(t->head); // start at head while ( *ptr != NULL ) // end if empty leaf is found { int cmpRes = strcmp( insert_key, (*ptr)->element ); if ( cmpRes == 0 ) return; // insert_key already is member of tree if ( cmpRes < 0 ) ptr = &((*ptr)->left); // step down to left child else ptr = &((*ptr)->right); // step down to right child } // create new node tree_ptr new_node = malloc( sizeof(struct node) ); new_node->element = strdup( insert_key ); new_node->left = NULL; new_node->right = NULL; // place new node at empty leaf *ptr = new_node; } 

Con questa funzione ricorsiva puoi stampare il tuo albero:

 void printTree( tree_ptr ptr ) { if ( ptr == NULL ) return; printTree( ptr->left ); printf( "%s\n", ptr->element ); printTree( ptr->right ); } printTree( t->head ); 

E con questo puoi free tutti i nodes del tuo albero:

 void deleteTree( tree_ptr ptr ) { if ( ptr == NULL ) return; deleteTree( ptr->left ); deleteTree( ptr->right ); free( ptr ); } deleteTree( t->head ); t->head = NULL; 

Il problema è che ptr sta puntando l’indirizzo del puntatore a un nodo struct, invece di puntare direttamente a un nodo struct:

 tree_ptr *ptr = &(t->head); 

Quindi, durante l’iterazione del ciclo while, non si modifica il puntatore ptr , ma il puntatore a cui punta, che è t->head :

  (*ptr) = (*ptr)->left; 

Questo sovrascrive il puntatore, t->head ogni iterazione, cancellando efficacemente i nodes puntati dal puntatore e perdendo memoria.

Utilizzare invece un puntatore normale al nodo struct:

 struct node* iter = t->head; ... if ( strcmp(insert_key, iter->element)<0 ){ ... } else{ iter = iter->left; .... 

E suggerirei vivamente di rimuovere quei typedef che nascondono il puntatore, perché rendono il codice difficile da leggere e offuscare i tipi, cosa non desiderabile in questo contesto:

 typedef struct node *tree_ptr; typedef struct table * Table; 

Si noti inoltre che se il loop trova un duplicato, il nodo allocato non viene liberato, perdendo la memoria.