2

我是一名计算机科学学院的学生。昨天，我有一个关于使用 C++ 的二叉搜索树的课程。我们是由那个班的实验室助理教的。

他们将树中的节点定义为这样的结构：

struct Data{
    char name[15];
    int age;
    Data *left,*right;
};

他们给了我们一个在 BST 中搜索的代码，如下所示：

// temp is current node, name is the value of the node to be searched for.
Data* search(Data *temp,char name[]) {
    if(strcmp(temp->name,name)>0)
        search(temp->left,name);
    else if(strcmp(temp->name,name)<0)
        search(temp->right,name);
    else
        return temp;
}

我注意到代码是错误的。如果函数进入第一个或第二个 if 块，它不会执行任何 return 语句。

但是当实验室助手运行代码时，它工作得很好。

我想也许这种行为是特定于编译器的。但是当我在 gcc 上尝试该代码时，该功能也可以正常工作。（我们大学使用microsoft visual c++编译器）

谁能解释发生了什么？为什么这段代码有效？

PS：忽略节点为空、找不到值等其他错误。

4

2 回答 2

8

这只是未定义的行为。

它似乎有效，因为有一个寄存器保存返回值。在递归树的最深路径中，temp被移动到该寄存器中，之后永远不会被清除或更改，因此该寄存器将包含正确的节点，直到第一次调用返回。

当第一个调用返回时，调用上下文检查该寄存器的返回值，这恰好是正确的。但你不应该依赖这个。假设它总是有效是不安全的。

于 2012-05-11T09:29:55.440 回答
1

通常，您有一个用于从函数返回值的硬件寄存器（例如，在 i686 上是 %EAX）。如果您在函数中所做的最后一件事是调用另一个函数并且预期的返回值是该函数的结果，则可能会发生 %EAX 值没有被丢弃并且被调用者很好地检索到的情况。

但是，这取决于许多假设，您不应该期望它以任何方式可靠。首先，编译器可以检测到您没有使用 的返回值search()，因此如果它暗示search()没有副作用，它可能会决定优化该调用。如果它能够内联搜索调用，它可以部分优化它。

可能还有其他架构（iirc，IA64 就是这种情况），其中调用约定更加微妙，并且用于在一个函数中返回值的寄存器与调用函数中的不同。所以你的代码依赖于平台相关的细节来工作，而它应该是一种高级（和可移植的）语言。

于 2012-05-11T09:32:01.617 回答