C ++ - Проблемы с пониманием модификации / назначения указателя и ссылок на указатель - PullRequest
Новая
       118

C ++ - Проблемы с пониманием модификации / назначения указателя и ссылок на указатель

0 голосов
/ 25 февраля 2020

У меня есть двоичное дерево, которое выглядит следующим образом 

struct Node 
{
  int key;
  double data;
  Node* right;
  Node* left;
};

, и у меня есть эта функция "вставки" для вставки новых узлов и построения дерева 

void insert(Node*& p, int key, double to_be_inserted) 
{
  if (p == nullptr) 
  {
    p = new Node;
    p->key = key;
    p->data = to_be_inserted;
    p->left = nullptr;
    p->right = nullptr;
  }
  else 
  {
    if (p->key == key) 
    {
      p->data = to_be_inserted;
    }
    else 
    {
      Node*& child = (p->key > key) ? p->left : p->right;
      insert(child, key, to_be_inserted);
    }
  }
}

и основная функция это выглядит так 

int main(int argc, char ** argv) 
{
  Node* root = nullptr;
  insert(root, 11, 11);
  insert(root, 6, 6);
  insert(root, 4, 4);
  insert(root, 5, 5);
  insert(root, 8, 8);
  insert(root, 10, 10);
  insert(root, 19, 19);
  insert(root, 17, 17);
  insert(root, 43, 43);
  insert(root, 31, 31);
  insert(root, 49, 49);

  printTree(root, 0);
  return 0;
}

Окончательное «распечатанное» дерево выглядит так:

enter image description here

(This) print- out "предназначен для чтения слева направо, а не сверху вниз)

Мои вопросы:

  1. Как функция insert знает, что такое дерево в настоящее время выглядит, когда он вызывается во второй (или более) раз? root в main - это всего лишь один узел (с двумя дочерними элементами), который не меняется (согласно моему отладчику), и вы используете один и тот же root в качестве аргумента несколько раз. Как он узнает, где остановился, когда insert вызывается снова? Что на самом деле делает строка p = new Node (в insert). Мне кажется, что он просто перезаписывает root, снова и снова? В основном, где хранится память о том, как выглядит (текущее) полное дерево?

  2. Будет ли функция insert вести себя иначе, если она будет объявлена ​​как Node * insert(Node * p, int key, double value);?

  3. Есть ли конкретная c причина, по которой p является указателем ссылка вместо обычного указателя? Какая разница?

Извините, за длинные (и, возможно, глупые) вопросы. Я новичок в C ++. Я понимаю основы указателей и ссылок, но, по-видимому, я не могу понять, что на самом деле происходит в функции insert (и в основной функции, когда insert вызывается несколько раз с помощью одного и того же root параметр).

Спасибо!

1 Ответ

3 голосов
/ 25 февраля 2020

Как функция вставки узнает, как выглядит дерево в данный момент, когда оно вызывается второй (или более) раз?

Поскольку узел root сохраняет память своих двух потомки и его потомки сохраняют память о каждом из своих потомков, и ...

Функция вставки начинается с узла и в этом блоке 

    else 
    {
      Node*& child = (p->key > key) ? p->left : p->right;
      insert(child, key, to_be_inserted);
    }

Определяет, какая ветвь должна быть "развернута" вниз в ", чтобы найти пустой узел для вставки. Каждая вставка значения в узле проходит по дереву, пока не найдет правильное местоположение вставки.

Будет ли функция вставки вести себя по-разному, если она будет объявлена ​​как Node * insert (Node * p, int key, двойное значение);?

Да, если бы оно было объявлено, как указано выше в вашем вопросе, значение p типа Node * было бы скопировано из main в функцию insert как локальная переменная. Любые изменения в p во вставке будут локальными и не повлияют на значение root в main. Когда вы переходите по ссылке, любые изменения, сделанные в p в insert, влияют на root в основном. Если вы не перейдете по ссылке, root всегда будет nullptr, а insert будет выполнять только эту ветку: 

  if (p == nullptr) 
  {
    p = new Node;
    p->key = key;
    p->data = to_be_inserted;
    p->left = nullptr;
    p->right = nullptr;
  }

, что приведет к утечке памяти.

Есть ли конкретная c причина, по которой p является ссылкой на указатель вместо обычного указателя? Какая разница?

см. Выше

...