c - 实现二叉树时出现Segmentation Fault (Core Dumped)

Question

我的代码在这里有段错误(核心转储)。我不太确定是哪一行引起的，因为我是 C 的新手。我在这里要做的是为文件中的每一行实现一个二叉搜索树(仅用于插入和搜索)。每行不超过 1000 字。

这是我的代码:

BST *bst_ins(BST *bst, char *key, void *value)
{
  BST* temp = NULL;
  int cmp = strcmp(bst->kvp.key, key);
  if(bst == NULL)
  { /* This for null node */
    temp = (BST*)malloc(sizeof(BST)); /* allocate the memory of struct for new node */
    temp->left = NULL;
    temp->right = NULL;
    temp->kvp.key = key;
    temp->kvp.value = value;
  }


  else if(cmp < 0) /* Current node less than input */
  {
    bst->right = bst_ins(bst->right,key,value);
  }

  else if(cmp > 0)
  {
    bst->left = bst_ins(bst->left,key,value);
  }

  return bst;
}


KVP *bst_get(BST *bst, char *key)
{
    KVP* return_this;
    if(bst!=NULL)
    {
        if(bst->kvp.key==key)
        {
            return return_this;
        }
        else if(strcmp(bst->kvp.key, key) < 0) /* Current node less than input */
        {
            return bst_get(bst->left, key);
        }
        else if(strcmp(bst->kvp.key,key) > 0)
        {
            return bst_get(bst->right,key);
        }
    }
    return 0;
}

下面是header.h

typedef struct {
    char *key;
    void *value;
} KVP;
typedef struct bst {
    struct bst *left;
    struct bst *right;
    KVP kvp;
} BST;

谁能帮我找出是哪条线引起的？谢谢。

编辑:

解决了!最后:D

这是主要功能。

int main()
{
char* str1=strdup("alokama");
char* str2=strdup("kokokoko");
BST *bst = NULL;
bst = bst_insert(bst,str1,NULL);
bst = bst_insert(bst,str2,NULL);
if(bst_get(bst,str1)){ printf ("yuhuu\n"); }
return 0;
}

Answer 1

当您调用bst_ins 时，bst 可能是NULL，因此您不能取消引用它。此外，您还定义了一个临时节点，它是 NULL。当您进行字符串比较时，

if (strcmp(temp->kvp.key, key) < 0) ...

您肯定会取消引用 NULL 指针。不好。下面的代码修复了这个问题，而且每次传递只调用一次 strcmp。请注意 temp 是如何仅在创建新节点的范围内定义的。

BST *bst_ins(BST * bst, char *key, void *value)
{
    int cmp;

    if (bst == NULL) {
        BST *temp = (BST *) malloc(sizeof(*temp));

        temp->left = NULL;
        temp->right = NULL;
        temp->kvp.key = key;
        temp->kvp.value = value;

        return temp;
    }

    cmp = strcmp(bst->kvp.key, key);

    if (cmp < 0) {
        bst->right = bst_ins(bst->right, key, value);
    } else if (cmp > 0) {
        bst->left = bst_ins(bst->left, key, value);
    }

    return bst;
}

您现在可以像这样插入新节点:

bst = bst_ins(bst, "plum", "1");
bst = bst_ins(bst, "apple", "2");
bst = bst_ins(bst, "orange", "3");
bst = bst_ins(bst, "kumquat", "4");

但这有点笨拙，因为你必须将结果分配给根节点，这是多余的并且容易忘记。您也失去了返回与 key 关联的(可能是新的)节点的有用可能性。

更好的方法可能是将根节点的地址传递给可能更改树的函数。如果你不害怕 (*bst) 符号和 poerator 的地址 &，这里是:

BST *bst_ins(BST **bst, char *key, void *value)
{
    int cmp;

    if (*bst == NULL) {
        *bst = (BST *) malloc(sizeof(**bst));

        (*bst)->left = NULL;
        (*bst)->right = NULL;
        (*bst)->kvp.key = key;
        (*bst)->kvp.value = value;

        return *bst;
    }

    cmp = strcmp((*bst)->kvp.key, key);

    if (cmp < 0)  return bst_ins(&(*bst)->right, key, value);    
    if (cmp > 0)  return bst_ins(&(*bst)->left, key, value);

    return *bst;
}

然后这样调用它:

bst_ins(&bst, "plum", "1");
bst_ins(&bst, "apple", "2");
bst_ins(&bst, "orange", "3");
bst_ins(&bst, "kumquat", "4");

该函数返回与键关联的节点，但您可以轻松忽略返回值。

最后，确保在完成后正确删除树。