时间戳

首页 > 解决方案 > C中的静态成员

c - C中的静态成员

问题描述

我试图编写一个代码来确定一棵树是否是 BST。
我从网站上搜索了解决方案以供参考。
解决方案之一如下：
我真的不明白静态指针在这个函数中的作用。
谁能给我解释一下？太感谢了！

这是代码片段。

int isBSTtree(treeNode *T)
{
    static treeNode *prev=NULL;
    if(T)
    {
        if(!isBSTtree(T->left))
        {
            return 0;
        }
        if(prev!=NULL && T->value<=prev->value)
        {
            return 0;
        }
        prev=T;
        return isBST(T->right);
    }
    return 1;
}

标签： cstaticbinary-search-tree

解决方案

静态变量在函数调用之间保留它们的值。如果它们作为声明的一部分被初始化，如 中 static treeNode *prev=NULL;，则初始化只发生一次。

例如，如果你有 f：

void f(int n) {
    static int x = 4;

    if (!n) {
        printf(" : ");
        return;
    }

    x += 2;
    printf("%d ", x);
    f(n - 1);
    printf("(%d) ", x); 
}

然后f(3)会打印6 8 10 (10) (10) (10)。静态变量用于将值传递给递归调用并返回值。在 BST 检查的情况下，它被用来查找左子树最右边元素的值。

但是这样做有几个问题。

f(3); putchar('\n'); f(3);印刷

6 8 10 (10) (10) (10)
12 14 16 (16) (16) (16)

因为我们忘记在非递归调用之间重置静态变量。如果我们f(3)同时从两个不同的线程调用，那么两个调用都会使用同一个静态变量，并且不知道数字会以什么顺序出现。

isBSTtree 背后的逻辑是进行从左到右的遍历，跟踪迄今为止看到的最大元素，如果在节点左侧看到的最大元素大于节点的值，则表明失败。因此，更好的方法是：

int isBSTaux(treeNode *T, treeNode **prev) {
    if(!T) return 1;

    if (!isBSTaux(T->left, prev)) return 0;
    if (*prev && (*prev)->value > T->value) return 0;
    *prev = T;
    return isBSTaux(T->right, prev);
}

int isBSTtree(treeNode *root) {
   treeNode *prev = NULL;
   return isBSTaux(root, &prev);
}

对 isBSTtree 的每次调用都会获得自己的 prev 副本，每次都会重新初始化，并且不会在不同调用之间共享。

（这并不是说静态局部变量没有它们的用途；它们只是在这种特殊情况下不是正确的选择。）

推荐阅读