c - 为什么我在 C 中使用指针的递归会崩溃？

Question

我目前正在学习计算机科学，我们开始使用指针。我有一种感觉，我开始理解指针，但我遇到了问题，无法弄清楚出了什么问题。

我们定义了这样的树:

typedef struct node *tree;
struct node {int key; tree left, right;}; 

现在我们应该编写一个函数来创建具有三个参数的节点:节点的键、左节点和应该位于该节点“下方”的右节点。我这样做了，它似乎有效:

tree createNode(int n, tree l, tree r){
    tree node = (tree) malloc(sizeof(tree));
    node->key = n;
    node->left = l;
    node->right = r;
    return node;
}

最后我们应该编写一个函数来将树的所有叶子相乘，我认为最简单的方法是从根开始并通过递归搜索叶子，然后将它们相乘。但是当我调用该函数时，程序似乎在函数中间崩溃了。我的函数如下所示:

int leafprod(tree t){
    printf("%d\n", t->key);

    if (t->left == NULL){
        if (t->right == NULL){
            printf("$1\n\n");
            return t->key;
        }
        printf("$2\n\n");
        return leafprod(t->right);
    }
    if (t->right == NULL){
        printf("$3\n\n");
        return leafprod(t->left);
    }
    printf("$4\n\n");
    return leafprod(t->left) * leafprod(t->right);
}

我在主函数中调用该函数，如下所示:

int main(){
    tree a = createNode(1, NULL, NULL);
    tree b = createNode(2, NULL, NULL);
    tree c = createNode(3, a, NULL);
    tree d = createNode(4, b, c);

    int n = leafprod(d);

    printf("end: %d", n);

    free(a);
    free(b);
    free(c);
    free(d);

    return 0;
}

我使用打印语句来跟踪程序并尝试找到错误，但在大多数情况下它什么也不打印。然后有时会打印:

4
$4

2
$2

程序只执行了整个代码两次。我相信我可能错误地使用了 malloc 函数，但我无法判断。

Answer 1

问题出在这一行:

tree node = (tree) malloc(sizeof(tree));

tree 是指向结构节点 的指针的类型定义。 因此 sizeof(tree) 只是指针的大小。

您应该改为以下之一:

tree node = malloc(sizeof(*l));

或者:

tree node = malloc(sizeof(*r));

*l 和 *r 的类型为 struct node (不是指针)，这是您要创建的元素。

@IanAbbott 评论的另一个选项是:

tree node = malloc(sizeof(*node));

请注意，这里的node是变量的名称，而不是类型(在C中需要以struct为前缀，即struct node)。 这种方法的优点是语句不依赖于其他变量。

旁注:

1. 您不应该强制转换 malloc 的结果。参见这里:Do I cast the result of malloc? .
2. 用 typedef 隐藏指针类型并不是一个好习惯。您可以考虑避免它(如果您想省去到处使用 struct 关键字的麻烦，可以使用 typedef struct node Node)。