c - 在 C 中搜索递归数据结构

Question

我想帮忙写一个递归搜索函数。

我有一个如下所示的数据结构:

struct node_t {
    char       name[16];    
    int        num_children;
    node_t**   children;
};

我在一个深树状结构中有很多节点，每个节点可以有很多 child 。

为了找到树中某处的节点，我目前将根节点传递给此函数:

node_search(node_t* parent, const char* node_name) {

    if(strcmp(parent->name, node_name) == 0) {
        return parent;
    } 
    else {
        for(int i = 0; i < parent->num_children; ++i) {
            node_t* node_found = node_search(parent->children[i], node_name);

            if(strcmp(node_found->name, node_name) == 0) {
                return node_found;
            }           
        }
    }
}

这似乎可行，但我观察到的两件事让我担心这不是最佳/正确的方法:

1. 当在树中很深的地方找到所需的节点时，strcmp 会在递归结束时为调用堆栈中的每个帧完成。

   <

2. 当遍历树中没有所需节点的分支时，循环内的 strcmp 最终对垃圾值进行比较，感觉不太好坚实。

有人知道这种递归搜索可以用更好的方式完成吗？

Answer 1

您需要所有路径上的返回值，解决您的编译器应该给您的警告将使您理解NULL是唯一合乎逻辑的选择找到了。

有了它，您可以在修复此问题时通过消除冗余检查来显着减少代码。这里不需要两个 strcmp。您在项目符号列表中提到:“...循环内的 strcmp...” - 您已经在循环中 strcmp；它是在对那个 child 的递归调用中完成的。没有意义再做一次。

node_t* node_search(node_t* parent, const char* node_name)
{
    if(strcmp(parent->name, node_name) == 0)
        return parent;

    node_t *node_found = NULL;
    for(int i = 0; !node_found && i < parent->num_children; ++i)
        node_found = node_search(parent->children[i], node_name);

    return node_found;
}

如果未找到该元素，则应返回 NULL，并中断循环，一旦找到节点 就返回链中。

最后，根据此代码的位置，您可能希望在打开取消引用之前确保 parent 不为 NULL。此代码假定在没有 parent 的有效非空指针的情况下永远不会调用它。这是否是一个有效的假设(显然是在您发布的代码中)我留给您决定。