Статический член в C - PullRequest
Новая
       14

Статический член в C

1 голос
/ 12 апреля 2019

Я пытался написать код, чтобы определить, является ли дерево 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;
}

Ответы [ 2 ]

1 голос
/ 12 апреля 2019

Статические переменные сохраняют свои значения между вызовами функций. Если они инициализированы как часть декларации, как в 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 голосов
/ 12 апреля 2019

static будет сохранять значение переменных между вызовами функций снова и снова, так как оно вызывает себя снова и снова (рекурсия), вам нужно сохранить значение переменной prev

...