在c中的函数中通过指针传递参数值

Question

我是学习c的新手..... 所以我正在尝试从以下输入创建树结构：

(2, 50) (4, 30) (9, 30) (10, 400) (-5, -40)
(7, 20) (19, 200) (20, 50) (-18, -200) (-2, 29)
(2, 67) (4, 35) (9, 45) (-18, 100)

首先，我定义了一些数据结构和辅助函数如下：

typedef struct AVLTreeNode
{
    int key;                    //key of this item
    int value;                  //value (int) of this item
    int height;                 //height of the subtree rooted at this node
    struct AVLTreeNode *parent; //pointer to parent
    struct AVLTreeNode *left;   //pointer to left child
    struct AVLTreeNode *right;  //pointer to right child
} AVLTreeNode;

//data type for AVL trees
typedef struct AVLTree
{
    int size;          // count of items in avl tree
    AVLTreeNode *root; // root
} AVLTree;

// create a new AVLTreeNode
AVLTreeNode *newAVLTreeNode(int k, int v)
{
    AVLTreeNode *newNode;
    newNode = malloc(sizeof(AVLTreeNode));
    assert(newNode != NULL);
    newNode->key = k;
    newNode->value = v;
    newNode->height = 0;  // height of this new node is set to 0
    newNode->left = NULL; // this node has no child
    newNode->right = NULL;
    newNode->parent = NULL; // no parent
    return newNode;
}

// create a new empty avl tree
AVLTree *newAVLTree()
{
    AVLTree *T;
    T = malloc(sizeof(AVLTree));
    assert(T != NULL);
    T->size = 0;
    T->root = NULL;
    return T;
}

然后我写了一个函数将每对数据插入到树中：

int InsertNode(AVLTree *T, int k, int v)
{
    AVLTreeNode *currentNode = T->root;
    AVLTreeNode *parent;
    //if the tree/subtree is empty
    if (currentNode == NULL)
    {
        currentNode = newAVLTreeNode(k, v);
    }
    //keys are equal
    else
    {
        while (currentNode != NULL)
        {
            parent = currentNode;
            if (k == currentNode->key)
            {
                if (v == currentNode->value)
                {
                    return 0;
                }
                else if (v < currentNode->value)
                {
                    currentNode = currentNode->left;
                }
                else if (v > currentNode->value)
                {
                    currentNode = currentNode->right;
                }
            }
            else if (k < currentNode->key)
            {
                currentNode = currentNode->left;
            }
            else if (k > currentNode->key)
            {
                currentNode = currentNode->right;
            }
        }

        currentNode = newAVLTreeNode(k, v);
        currentNode->parent = parent;
    }
    T->size++;
    return 1;
}

我原以为函数参数中的值 k 和 v 会分别传递给 T->root->key 和 T->root->value，但它不起作用..... 可以有人帮我更正代码并向我解释我的代码错误的原因吗？

Answer 1

主要问题是您的 InsertNode() 函数根本没有。它确实构造了一个AVLTreeNode，遍历树到新节点的插入点，并设置它的父指针，但它从不更新父节点的子指针，也不会更新树的根指针。最初是空的。特别是，分配给 currentNode 没有这种效果。

但是，您可以通过将 currentNode 调整为双指针 (AVLTreeNode **) 来使此代码工作，以便您可以通过它间接分配给所需的根指针或子指针.

AVLTreeNode **currentNode = &T->root;

// ...

currentNode = &(*currentNode)->left;

// ...

// So that you can ultimately do this:
*currentNode = newAVLTreeNode(k, v);

在c中的函数中通过指针传递参数值

Pass argument value by pointer in function in c

c

tree

pointers

function-pointers