указатели и значения

Question

Я написал следующий код, и он правильно печатает корневое значение, но не значение ret. Здесь потенциально печатается адрес памяти (1707388). Я считаю, что ret теперь может быть изменен, и результат будет замечен в основном. Любая помощь приветствуется.

#include <stdlib.h> 

struct node{ 
int value; 
    int order; 
    struct node *left; 
    struct node *right; 
}; 

typedef struct node node_t; 

node_t array[10]; 

void createTree(node_t *p, int order){ 
    p->value = rand()%10; 
    p->order = order; 
    printf("%i", p->value); 
    printf(" "); 
    printf("%i\n", p->order); 
    if (!order){ 
     p->left = NULL; 
     p->right = NULL; 
     return; 
    } 
    order--; 
    createTree(&p->left, order); 
    createTree(&p->right, order); 
} 

void traverse(node_t *current, node_t *ret, int size){ 
    printf("%i\n", current->value); 
    if (current->value > size){ 
     ret = current; 
     traverse(&current->left, &ret, size); 
     traverse(&current->right, &ret, size); 
    } 
    return; 
} 

int main(void){ 
    node_t *root = &array[0]; 
    node_t *ret; 
    srand(time(NULL)); 
    createTree(root, 4); 
    int i = 3; 
    printf("%s", "root-value: "); 
    printf("%i\n", root->value); 
    traverse(root, ret, i); 
    printf("%s", "root-value: "); 
    printf("%i\n", root->value); 
    printf("%i\n", ret->value); 
    return 1; 
} 

Answer 1

Вы передаете ret по значению

void traverse(node_t *current, node_t *ret, int size){ 

Когда функция изменения ret, изменения не распространяются обратно вызывающему.

Это означает, что ret в main() остается неинициализированным, а поведение вашего кода не определено.

Чтобы исправить это, сделайте traverse либо возвратом ret, либо возьмите его как node_t**.

Answer 2

Это:

void createTree(node_t *p, int order) 

Должно быть

void createTree(node_t **p, int order) 

В противном случае вы изменяете указатель местныйnode_t, вместо одного вне функции. Ваше дерево тоже не построено должным образом.

Answer 3

С кодом есть несколько проблем.

Во-первых, вы неправильно распределите память для узлов. В вашем коде вы используете неправильный тип указателя, более того, указатель на неинициализированную область.

Здесь, как его можно использовать по-разному:

node_t *createTree(int order) 
{ 
    node_t *result = malloc(sizeof(*result)); 
    result->value = rand() % 10; 
    result->order = order; 
    if (order) 
    { 
     result->left = createTree(order - 1); 
     result->right = createTree(order - 1); 
    } 
    else 
    { 
     result->left = result->right = 0; 
    } 
    return result; 
} 

Тогда ваш траверс функции нужен блок для ограничения Agains не удался поиск:

node_t *traverse(node_t *current, int size) 
{ 
    node_t *ret = NULL; 

    if (current->value > size) 
    { 
     // assuming current node fit - stops the search 
     ret = current; 
    } 

    if (!ret && current->left) 
    { 
     // try left node 
     ret = traverse(current->left, size); 
    } 
    if (!ret && current->right) 
    { 
     // try right node 
     ret = traverse(current->right, size); 
    } 
    return ret; 
} 

В случае, если вам нужно (как правило, вы делаете) , вот destroyTree:

void destroyTree(node_t *node) 
{ 
    if (!node) return; // we treat NULL as a valid pointer for simplicity 

    destroyTree(node->left); 
    destroyTree(node->right); 
    free(node); 
} 

А вот пример использования:

node_t *root, *found; 

root = createTree(4); 
found = traverse(root, 3); 
if (found) 
{ 
    printf("Found!"); 
} 
destroyTree(root); 

Answer 4

В traverse(node_t *current, node_t *ret, int size), ret является переменной стека. Другими словами, вы передаете указатель по значению, а не передаете его по ссылке.

Что вы сделали на данный момент, по существу, такой же, как:

int f(int i) { 
    ... 
    i = <any value>; 
    ... 
} 

В этом случае изменяемого только копию значения.

В вашей программе вы также изменяете копию указателя. Вне функции указатель остается не измененным.

Если вы хотите изменить его, вам необходимо передать указатель на него:

void traverse(node_t *current, node_t **ret, int size){ 
    ... 
    *ret = current; 
    ... 
    return; 
} 

То же самое для createTree().