C中的静态成员

问题描述 投票:1回答:2

我试图编写一个代码来确定树是否是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;
}
c static binary-search-tree
2个回答
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副本,每次重新初始化,并且不会在不同的调用之间共享。

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


0
投票

static会一次又一次地保留函数调用之间的变量值,因为它一次又一次地调用自身(递归)你需要保留prev变量的值

© www.soinside.com 2019 - 2024. All rights reserved.