Передать значения через дерево в C - PullRequest
1 голос
/ 06 марта 2019

Я пишу простой синтаксический анализатор на C, и я не уверен, что это лучший способ передать результаты в мое дерево, когда оно оценивается.

Вот мой текущий код, структура узла и функция ходьбы для оценки дерева.

typedef struct node {
    struct node* left;
    struct node* right;
    void* data;
    Symbol type;
} node;

void* walk(node* n) {
    if (n != NULL) {

        if (n->type == plus) {

            int x = 0;
            int a = *(int*)walk(n->left);
            int b = *(int*)walk(n->right);

            x = a + b;

            return &x;

        } else if (n->type == number) {
            return (int*)n->data;
        }
    }
    return NULL;
}

Из кода, который вы можете видеть, когда я добавляю два числа вместе, я сохраняю результат в локальной переменной и возвращаю адрес этой переменной, я знаю, что это неопределенное поведение, поэтому я подумал об использовании malloc и изменении своего кода на это:

int* x = malloc(1 * sizeof(int));
int a = *(int*)walk(n->left);
int b = *(int*)walk(n->right);

*x = a + b;

return x;

Но проблема с этим кодом в том, что я не уверен, каков наилучший способ освободить эту память, которую я только что использовал malloc.

Должен ли я пройти по дереву второй раз и освободить всю память таким образом, или это лучший способ освободить память, когда я закончу, или есть лучший способ распространения значений через мое дерево?

Ответы [ 2 ]

0 голосов
/ 06 марта 2019

Нет необходимости пересекать дерево во второй раз. Обратите внимание, что вам не нужны значения a и b после их суммирования в x. так что вы можете освободить их после добавления, что показано в ответе @ flu. Более того, вы можете сделать это без использования дополнительной памяти для флага.

Примечание: этот код будет из-за ошибки времени выполнения для неправильного ввода. чтобы обработать эти ошибки, проверьте NULL-указатели перед обращением к указателю.

void* walk(node* n) {
    if (n != NULL) {
        if (n->type == plus) {
            int * x = malloc(sizeof(int));
            int * a = (int*)walk(n->left);
            int * b = (int*)walk(n->right);
            *x = *a + *b;

            free(a);
            free(b);

            return x;
        } else if (n->type == number) {
            int * val = malloc(sizeof(int)); //allocate dynamic memory for the leaf node so that all nodes can be freed without checking.
            *val = n->data;
            return val;
        }
    }
    return NULL;
}
0 голосов
/ 06 марта 2019

Вы можете добавить дополнительный аргумент needToFree, чтобы сообщить вызывающей стороне освободить возвращенный указатель.

void* walk(node* n, bool* needToFree) {
    if (n != NULL) {
        if (n->type == plus) {
            bool needToFreeA;
            bool needToFreeB;
            int * x = malloc(sizeof(int));
            int * a = (int*)walk(n->left,  &needToFreeA);
            int * b = (int*)walk(n->right, &needToFreeB);
            *x = *a + *b;

            if( needToFreeA ) free(a);
            if( needToFreeB ) free(b);

            *needToFree = true;
            return x;
        } else if (n->type == number) {
            *needToFree = false;
            return (int*)n->data;
        }
    }
    *needToFree = false;
    return NULL;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...