Опускание амперсанда в вызове функции

Question

Я пытаюсь реализовать двоичное дерево ADT в C, и я хотел бы использовать API, функции которого имеют форму foo (объект, значение). Насколько я написал рабочее дерево для значения int, но когда я вызываю функцию BinTree_insert, я должен использовать оператор "&", чтобы получить адрес объекта. Можно ли изменить эту функцию, чтобы пропустить &?

typedef struct __bintree_node_t
{
    int data;
    struct __bintree_node_t* left;
    struct __bintree_node_t* right;
}bintree_node_t;

static void __BinTree_insert(bintree_node_t** node, int value)
{
    if(!(*node))
    {
        *node = __BinTree_newNode();
        (*node)->data = value;
    }
    else if((*node)->data < value)
        __BinTree_insert(&(*node)->left, value);
    else if((*node)->data > value)
        __BinTree_insert(&(*node)->right, value);
}

void BinTree_insert(bintree_node_t* node, int value)
{
    //??????
}

int main(void)
{
    bintree_node_t* root = 0;

    BinTree_insert(root, 2); //sth like this
    __BinTree_insert(&root, 1); //instead of this
}

Answer 1

У вас есть следующие варианты:

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

  static void BinTree_insert(bintree_node_t* node, int value)
  {
      if (!node)
      {
          node = __BinTree_newNode();
          node->data = value;
      }
      else if (node->data < value)
          node->left = __BinTree_insert(node->left, value);
      else if (node->data > value)
          node->right = __BinTree_insert(node->right, value);
  }
  
  int main(void)
  {
      bintree_node_t* root = 0;
  
      root = BinTree_insert(root, 2);
  }
  

• Или, если вы просто хотите изменить начальный вызов, вы можете самостоятельно поддерживать указатель на указатель:

  int main(void)
  {
      bintree_node_t* root = 0;
      bintree_node_t** rootPtr = 0;
  
      __BinTree_insert(rootPtr, 2);
  }
  

• Или вы можете определить тип, который дополнительно инкапсулирует указатель, но добавляет немного больше кода и выделения памяти.

Не уверен, в чем же смысл?

Answer 2

Вы реализовали функцию insert (), чтобы она изменяла свой первый параметр. Чтобы сделать это, вы должны передать корень по указателю; если вы передадите его по значению (a bintree_node_t*), изменение корня внутри BinTree_insert() не будет отражено вне функции (хотя изменения к корневому узлу будут).

Например, если дерево пустое (корень равен NULL), ваша функция вставки создает новый узел и имеет корневую точку указателя на этом узле; это невозможно сделать, если вы хотите сохранить исходный корневой указатель, который по-прежнему будет равен NULL.

То, что вы можете сделать, это заставить функцию вставки вернуть новый корень. Тогда вы могли бы передать старый корень как bintree_node_t* (т.е. по значению).