C- BST中的分割故障误差

Question

我在主机中调用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: %dn",k);
    strcpy(l,"x");
    k = add_word(l);
    printf("add_word(%s): %dn",l,k);
    strcpy(l,"x");
    k = find_word(l);
    printf("find_word(%s): %dn",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): %dn", w, k);
    k = find_word(w);
    printf("find_word(%s): %dn", 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;
}