4

在 C 编程方面，我几乎是个菜鸟。

几天来一直在尝试从以下形式的表达式创建二叉树：

A(B,C(D,$))

每个字母都是节点。

'('在我的树中下降一个级别（向右）。

','去我树的左边树枝

'$'插入一个 NULL 节点。

')'意味着上升一个层次。

这是我在编码 2-3 天后得出的结论：

#define SUCCESS 0

typedef struct BinaryTree
{
char info;
BinaryTree *left,*right,*father;
}BinaryTree;



int create(BinaryTree*nodeBT, const char *expression)
{   
    nodeBT *aux;
    nodeBT *root;
    nodeBT *parent;
    nodeBT=(BinaryTree*) malloc (sizeof(BinaryTree));         
        nodeBT->info=*expression;
    nodeBT->right=nodeBT->left=NULL;
    nodeBT->father = NULL;

    ++expression;   
    parent=nodeBT;                                                 
    root=nodeBT;

    while (*expression)
        {if (isalpha (*expression))
            {aux=(BinaryTree*) malloc (sizeof(BinaryTree));
             aux->info=*expression;
             aux->dr=nodeBT->st=NULL;
             aux->father= parent;
             nodeBT=aux;}

        if (*expression== '(')
            {parent=nodeBT;
            nodeBT=nodeBT->dr;}

        if (*expression== ',')
            {nodeBT=nodeBT->father;
            nodeBT=nodeBT->dr;}

        if (*expression== ')')
            {nodeBT=nodeBT->father;
            parent= nodeBT->nodeBT;}

        if (*expression== '$')
            ++expression;

        ++expression;
    }

nodeBT=root;
return SUCCESS;
}

最后，在尝试访问新创建的树时，我不断收到“内存不可读 0xCCCCCC”。而且我没有丝毫暗示我在哪里弄错了。

任何想法 ？

4

1 回答 1

8

几个问题：

  1. 您没有向我们展示 type 的定义nodeBT，但您已经声明aux,root和parentto 是指向该类型的指针。

  2. 然后，即使它被声明为指向 a ，您也将其分配aux给指向a 。BinaryTreenodeBT

  3. 您分配给aux->dr，这不是 的一部分BinaryTree，所以我不能只假设您输入nodeBT了您的意思BinaryTree。您分配给nodeBT->st，那不是BinaryTree两者的一部分。

  4. 您尝试通过分配返回解析树nodeBT=root。问题在于 C 是一种“按值调用”的语言。这意味着当您的create函数分配给 时nodeBT，它只是更改其局部变量的值。的调用者create没有看到这种变化。所以调用者没有收到根节点。这可能就是您收到“内存不可读”错误的原因；调用者正在访问一些随机内存，而不是包含根节点的内存。

如果您使用称为“递归下降”的标准技术编写解析器，您的代码实际上会更容易理解。就是这样。

让我们编写一个函数，从表达式字符串中解析一个节点。天真地，它应该有这样的签名：

BinaryTree *nodeFromExpression(char const *expression) {

要解析节点，我们首先需要获取节点的info：

    char info = expression[0];

接下来，我们需要查看节点是否应该有子节点。

    BinaryTree *leftChild = NULL;
    BinaryTree *rightChild = NULL;
    if (expression[1] == '(') {

如果它应该有孩子，我们需要解析它们。这就是我们将“递归”放在“递归下降”中的地方：我们只是nodeFromExpression再次调用来解析每个孩子。要解析左孩子，我们需要跳过 中的前两个字符，因为它们是当前节点expression的 info 和 the ：(

        leftChild = nodeFromExpression(expression + 2);

但是我们跳过多少来解析正确的孩子？我们需要跳过我们在解析左孩子时使用的所有字符......</p> 

        rightChild = nodeFromExpression(expression + ???

我们不知道那是多少个字符！事实证明，我们不仅需要nodeFromExpression返回它解析的节点，还需要返回它消耗了多少字符的一些指示。所以我们需要改变签名nodeFromExpression来允许它。如果我们在解析时遇到错误怎么办？让我们定义一个结构，它nodeFromExpression可以用来返回它解析的节点、它消耗的字符数以及它遇到的错误（如果有的话）：

typedef struct {
    BinaryTree *node;
    char const *error;
    int offset;
} ParseResult;

我们会说 iferror是非 null 的，thennode是 null 并且offset是我们发现错误的字符串中的偏移量。否则，offset只是过去用于 parse 的最后一个字符node。

所以，重新开始，我们将nodeFromExpressionreturn a ParseResult。它将把整个表达式字符串作为输入，它会采用该字符串中开始解析的偏移量：

ParseResult nodeFromExpression(char const *expression, int offset) {

现在我们有了报告错误的方法，让我们做一些错误检查：

    if (!expression[offset]) {
        return (ParseResult){
            .error = "end of string where info expected",
            .offset = offset
        };
    }
    char info = expression[offset++];

我第一次没有提到这一点，但我们应该$在这里处理你的 NULL 令牌：

    if (info == '$') {
        return (ParseResult){  
            .node = NULL,
            .offset = offset   
        };
    }

现在我们可以回到解析孩子的问题了。

    BinaryTree *leftChild = NULL;
    BinaryTree *rightChild = NULL;
    if (expression[offset] == '(') {

因此，要解析左孩子，我们只需再次递归调用自己。如果递归调用出错，我们返回相同的结果：

        ParseResult leftResult = nodeFromExpression(expression, offset);
        if (leftResult->error)
            return leftResult;

OK，我们成功解析了左孩子。现在我们需要检查并使用孩子之间的逗号：

        offset = leftResult.offset;
        if (expression[offset] != ',') {
            return (ParseResult){
                .error = "comma expected",
                .offset = offset
            };
        }
        ++offset;

现在我们可以递归调用nodeFromExpression来解析右孩子：

        ParseResult rightResult = nodeFromExpression(expression, offset);

如果我们不想泄漏内存，那么现在的错误情况会稍微复杂一些。我们需要在返回错误之前释放左孩子：

        if (rightResult.error) {
            free(leftResult.node);
            return rightResult;
        }

请注意，free如果您通过它，它什么也不NULL做，所以我们不需要明确地检查它。

现在我们需要检查并消费)after子元素：

        offset = rightResult.offset;
        if (expression[offset] != ')') {
            free(leftResult.node);
            free(rightResult.node);
            return (ParseResult){
                .error = "right parenthesis expected",
                .offset = offset
            };
        }
        ++offset;

我们需要在and变量仍在作用域内时设置局部变量leftChild和变量：rightChildleftResultrightResult

        leftChild = leftResult.node;
        rightChild = rightResult.node;
    }

如果需要，我们已经解析了两个子节点，所以现在我们准备构建需要返回的节点：

    BinaryTree *node = (BinaryTree *)calloc(1, sizeof *node);
    node->info = info;
    node->left = leftChild;
    node->right = rightChild;

我们还有最后一件事要做：我们需要设置father孩子的指针：

    if (leftChild) {
        leftChild->father = node;
    }
    if (rightChild) {
        rightChild->father = node;
    }

最后，我们可以返回一个成功的ParseResult：

    return (ParseResult){
        .node = node,
        .offset = offset
    };
}

我已将所有代码放在此要点中，以便于复制粘贴。

更新

如果您的编译器不喜欢该(ParseResult){ ... }语法，您应该寻找更好的编译器。该语法自 1999 年以来一直是标准的（§6.5.2.5 复合文字）。当您正在寻找更好的编译器时，您可以像这样解决它。

首先，添加两个静态函数：

static ParseResult ParseResultMakeWithNode(BinaryTree *node, int offset) {
    ParseResult result;
    memset(&result, 0, sizeof result);
    result.node = node;
    result.offset = offset;
    return result;
}

static ParseResult ParseResultMakeWithError(char const *error, int offset) {
    ParseResult result;
    memset(&result, 0, sizeof result);
    result.error = error;
    result.offset = offset;
    return result;
}

然后，用对这些函数的调用替换有问题的语法。例子：

    if (!expression[offset]) {
        return ParseResultMakeWithError("end of string where info expected",
            offset);
    }


    if (info == '$') {
        return ParseResultMakeWithNode(NULL, offset);
    }
于 2012-12-29T20:56:09.127 回答