BST中的分段错误错误

Question

当我在main中调用find_word函数时，我总是收到分段错误错误。 当一个单词被添加我想返回1，当它发现这个词，我想它返回1.所以我也不确定我的插入方法是否正确。

#include <string.h> 
#include <stdlib.h> 
#include <stdio.h> 

struct node { 
    char *word; 
    struct node *left; 
    struct node *right; 
}; 
static struct node *root; 


int init(void) 
{ 
    struct node *new_node = malloc (sizeof(struct node)); 
    if(new_node==NULL){ 
     return 0; 
    } 

    else{ 
     root = new_node; 
     new_node->left = NULL; 
     new_node->right = NULL; 
     return 1; 
    } 
} 

static int insert(struct node *newnode, char *word) 
{ 
    struct node *temp = NULL; 
    if(!(newnode)) 
     { 
      temp = (struct node *)malloc(sizeof(struct node)); 
      temp->left =NULL; 
      temp->right = NULL; 
      temp->word = word; 
      newnode = temp; 
      return 0; 
     } 

    if(word < (newnode)->word) 
     { 
      insert((newnode)->left, word); 
     } 
    else if(word > (newnode)->word) 
     { 
      insert((newnode)->right, word); 
     } 
    return 1; 
} 

int add_word(char *word) 
{ 
    return insert(root,word); 

} 
static int find(char *word, struct node *newnode){ 
    if(newnode==NULL){ 
     return 0; 
    } 
    else if(strcmp(word,newnode->word)>0){ 
     find(word,newnode->left); 
    } 

    else if(strcmp(newnode->word,word)<0){ 
     find(word,newnode->right); 
    } 
    else{ 

     return 1; 

    } 
    return 0; 
} 


int find_word(char *word) 
{ 
    return find(word,root); 
} 




int main(int argc,char *argv[]) 
{ 
    int k; 
    char l[5]; 


    k = init(); 
    printf("init: %d\n",k); 

    strcpy(l,"x"); 
    k = add_word(l); 
    printf("add_word(%s): %d\n",l,k); 

    strcpy(l,"x"); 
    k = find_word(l); 
    printf("find_word(%s): %d\n",l,k); 



    return 0; 
} 

Answer 1

解决这样

#include <string.h> 
#include <stdlib.h> 
#include <stdio.h> 

struct node { 
    char *word; 
    struct node *left; 
    struct node *right; 
}; 

static struct node *root = NULL; 

static int insert(struct node **newnode, char *word){ 
    struct node *temp = NULL; 
    int cmp; 

    if(!*newnode){ 
     temp = (struct node *)malloc(sizeof(struct node)); 
     temp->left =NULL; 
     temp->right = NULL; 
     temp->word = strdup(word); 
     *newnode = temp; 
     return 0; 
    } 

    if((cmp=strcmp(word, (*newnode)->word)) < 0) 
     return insert(&(*newnode)->left, word); 
    if(cmp > 0) 
     return insert(&(*newnode)->right, word); 
    return 1; 
} 

int add_word(char *word){ 
    return insert(&root, word); 
} 

static int find(char *word, struct node *newnode){ 
    int cmp; 
    if(newnode==NULL) 
     return 0; 
    if((cmp=strcmp(word, newnode->word)) == 0) 
     return 1; 
    if(cmp < 0) 
     return find(word, newnode->left); 
    return find(word, newnode->right); 
} 

int find_word(char *word){ 
    return find(word, root); 
} 

int main(int argc,char *argv[]){ 
    int k; 
    char *w; 

    k = add_word(w="x"); 
    printf("add_word(%s): %d\n", w, k); 

    k = find_word(w); 
    printf("find_word(%s): %d\n", w, k); 

    return 0; 
} 

Answer 2

如果newnode->word为NULL，你应该在当前节点插入单词，处理空根节点。

static int insert(struct node *newnode, char *word) 
{ 
    struct node *temp = NULL; 
    if(!(newnode)) 
     { 
      temp = (struct node *)malloc(sizeof(struct node)); 
      temp->left =NULL; 
      temp->right = NULL; 
      temp->word = malloc(strlen(word)+1); 
      strcpy(temp->word, word); 
      newnode = temp; 
      return 0; 
     } 

    if (newnode->word == NULL) { 
     newnode->word = malloc(strlen(word)+1); 
     strcpy(newnode->word, word); 
     return 1; 
    } 

    if(strcmp(word,(newnode)->word) < 0) 
     { 
      insert((newnode)->left, word); 
     } 
    else if(strcmp(word,(newnode)->word) > 0) 
     { 
      insert((newnode)->right, word); 
     } 
    return 1; 
} 

在你find功能，你叫strcmp两次。您交换参数的顺序，但您也将> 0更改为< 0。这些互相抵消，所以两者都在测试同样的事情。你需要改变一个或另一个，但不是两个。您还应该检查newnode->word == NULL。

static int find(char *word, struct node *newnode){ 
    if(newnode==NULL || newnode->word == NULL){ 
     return 0; 
    } 
    else if(strcmp(word,newnode->word)>0){ 
     find(word,newnode->left); 
    } 

    else if(strcmp(word,newnode->word)<0){ 
     find(word,newnode->right); 
    } 
    else{ 

     return 1; 

    } 
    return 0; 
}