0

二分探索木のコードを実装しようとしていました。問題は次のコードが機能しないことですが、insert(struct bst** node, data) のような挿入関数にダブル ポインターを渡すと機能します。単一のポインターを渡すことでも機能するはずだと思います。ここでエラーが何であるかを誰でも説明できますか?

void insert(struct bst* node, int data )
{
    if (node == NULL)
    {
        printf("here with %d\n",data);
        node = (struct bst*)malloc(sizeof(struct bst));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    if(data < node->data)
    {
        insert(node->left,data);
    }
    else if(data > node->data)
    {
        insert(node->right,data);
    }
}
4

3 に答える 3

1

関数に渡されたポインターの値を変更したい場合は、ポインターへのポインターとして渡す必要があります。

void alloc_int(int** p)
{
  *p = malloc(sizeof(int));
}

int main()
{
  int* p = NULL;
  alloc_int(&p);
  *p = 10; // here memory for p is allocated so you can use it
  free(p);
  return 0;
}

あなたの例でも同じです。値を変更するには、ポインターのアドレスを渡す必要があります (ポインターの値は実際のデータのアドレスです)。

于 2013-11-15T02:14:20.977 に答える
1

の親になるポインタを変更できる必要がありますnode。再帰呼び出しを行うときinsert(node->left,data)、node(新しいノードの親) に左の子 ( left==null) がない場合は、 を呼び出してinsert(null,data)います。最初のifステートメントは新しいノードを作成し、そのデータを割り当てますが、そのノードをツリーにフックする方法はありません。また、insertは新しいノードを返さないため、ノードは永久に失われます。

これを修正するための簡単なハックは、新しいノードを返すことです:

struct bst *insert(struct bst* node, int data, struct bst* parent )
{ /// Note new return value
    if (node == NULL)
    {
        printf("here with %d\n",data);
        node = (struct bst*)malloc(sizeof(struct bst));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        return node; /// NEW - send it back to the parent
    }

    if(data < node->data)
    {
        node->left = insert(node->left,data); /// save the new child if there wasn't one
        return node; /// otherwise, send back the node so the tree doesn't change.
    }
    else //if(data > node->data) /// On equal keys, add to the right
    {
        node->right = insert(node->right,data);
        return node;
    }
}

(免責事項: コードはまだテストされていません)

于 2013-11-15T02:14:52.693 に答える
1

ポインターの値を変更したい場合は、ポインターのアドレスを (as としてstruct node **) 渡す必要があります。

あなたのコードで：

node = (struct bst*)malloc(sizeof(struct bst));

の値は関数内でnode変更されinsertますが、呼び出し元の関数内の変数は変更されません。

于 2013-11-15T02:11:15.150 に答える