c - C 中的静态成员

Question

我正在尝试编写代码来确定一棵树是否是 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;
}

Answer 1

静态变量在函数调用之间保留它们的值。如果它们作为声明的一部分被初始化，如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 副本，每次都会重新初始化，并且不会在不同的调用之间共享。

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