C Указатель указателя на структуру и ссылку - PullRequest
Новая
       52

C Указатель указателя на структуру и ссылку

1 голос
/ 04 мая 2020

Я пытаюсь реализовать BST в C. Вот код: 

int main(int argc, char* argv[]) {
    int_bst_node_t * tree_p = NULL;
    test_insert(&tree_p, 40);
}

static void test_insert(int_bst_node_t ** t_p, int n) {
    printf("inserting %d into tree ", n);
    printf("\n");
    if (int_bst_insert(t_p, n)) {
        printf("result ");
        print_tree_elements(*t_p);
        printf("\n");
    }
    else {
       printf("insert failed\n");
    }
}

Код в другом файле: 

// Create a node, assign values
bool createNode(int n, int_bst_node_t *node) {
    int_bst_node_t *localNode = (struct int_bst_node*)malloc(sizeof(int_bst_node_t));
    if( localNode == NULL )
    {
        puts("\n Unable to allocate memory");
        return false;
    }
    localNode->data = n;
    localNode->left = NULL;
    localNode->right = NULL;

    node = localNode;
    //////    Prints right values 
    printf("\n LocalNode Data: %d  Node Data: %d", localNode->data, node->data);
    free(localNode);
    return true;
}

/* 
 * insert n into *t_p
 * does nothing if n is already in the tree
 * returns true if insertion succeeded (including the case where n is already
 * in the tree), false otherwise (e.g., malloc error)
*/
bool int_bst_insert(int_bst_node_t ** t_p, int n) {
    if (*t_p == NULL) {
        printf("*t_p %d IS null", *t_p);
        int_bst_node_t node;
        // Pass node as a ref, so data is updated
        if (createNode(n, &node) == false)
            return false;

        // Prints invalid data
        printf("\n Data of new node : %d", node.data);
        *t_p = &node;

        /*
          Need  to assign node to *t_p, so it is updated, and prints the values
          when calling next function in test_insert()

        int_bst_node_t *t = *t_p;
        printf("\n Data of *tp node : %d", t->data);  
        */     
     } else 
        printf("*t_p %d is NOT null", *t_p);

    printf("\n"); 
    return true;
 }

Я не могу установить значение / ref узла на t_p. Это только для узла root; дальше было бы больше узлов. Я не могу понять концепцию ** для обновления значения. Варианты пробовал, все терпит неудачу.

Буду рад, если кто-то поможет мне с этим.

Спасибо.

1 Ответ

1 голос
/ 05 мая 2020

Функция createNode не имеет смысла хотя бы потому, что принимает указатель на узел по значению. А после выделения памяти для узла вы сразу же освобождаете его, делая недействительным указатель, указывающий на выделенную память. 

int_bst_node_t *localNode = (struct int_bst_node*)malloc(sizeof(int_bst_node_t));
//...
node = localNode;
//...
free(localNode);

Функция int_bst_insert также не имеет смысла. Помимо подобных ошибок 

*t_p = &node;

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

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

Функции могут быть определены следующим образом. 

int_bst_node_t * createNode( int n ) 
{
    int_bst_node_t *localNode = malloc(sizeof(int_bst_node_t));

    if( localNode != NULL )
    {
        localNode->data = n;
        localNode->left = NULL;
        localNode->right = NULL;
    }

    return localNode;
}

и 

bool int_bst_insert( int_bst_node_t ** t_p, int n ) 
{
    while ( *t_p != NULL )
    {
        if ( n < ( *t_p )->data )
        {
            t_p = &( *t_p )->left;
        }
        else
        {
            t_p = &( *t_p )->right;
        }
    }

    *t_p = createNode( n );  

    return *t_p != NULL;
}
...