带指针的嵌套结构
#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; }
以上是一个简化的程序,给出了一些定义代码,因此我无法更改基本结构,如表,表,节点,tree_ptr,而其他可以更改。 我想要实现的是拼写检查,表存储树的头部和树的一些其他属性(这里省略),树被实现为有序二叉树。
我发现,在(* ptr)=(* ptr) – > right之后,insert()最多可以工作两次; t->头也改变了。 因此,在使用它两次之后,我失去了树的头部。
如何修改我的insert()?
要将节点插入树中,首先必须搜索空叶。 除此之外,你不要修改t
,所以不需要通过返回值写回:
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; }
使用此递归function,您可以打印您的树:
void printTree( tree_ptr ptr ) { if ( ptr == NULL ) return; printTree( ptr->left ); printf( "%s\n", ptr->element ); printTree( ptr->right ); } printTree( t->head );
使用这个,您可以free
树的所有节点:
void deleteTree( tree_ptr ptr ) { if ( ptr == NULL ) return; deleteTree( ptr->left ); deleteTree( ptr->right ); free( ptr ); } deleteTree( t->head ); t->head = NULL;
问题是ptr
指向结构节点的指针的地址,而不是直接指向结构节点:
tree_ptr *ptr = &(t->head);
然后在while循环中迭代时,你不是在改变指针ptr
,而是指向它指向的指针,即t->head
:
(*ptr) = (*ptr)->left;
这会在每次迭代时覆盖指针t->head
,有效地擦除指针指向的节点,并泄漏内存。
而是使用指向struct节点的普通指针:
struct node* iter = t->head; ... if ( strcmp(insert_key, iter->element)<0 ){ ... } else{ iter = iter->left; ....
我强烈建议删除隐藏指针的那些typedef,因为它们使代码难以阅读并模糊类型,这在这种情况下是不可取的:
typedef struct node *tree_ptr; typedef struct table * Table;
另请注意,如果循环发现重复,则不会释放分配的节点,从而泄漏内存。