вернуть локальный указатель

Question

struct node
{
  Item item; node *l, *r;
  node(Item x) {item = x; l = 0; r = 0;}
};

typedef node* link;
link max(Item a[], int l, int r)
{
    int m = (l+r)/2;
    link x = new node(a[m]);
    if (l==r) return x; // return a local pointer
    x->l = max(a, l, m);
    x-r = max(a, m+1, r);
    Item u = x->l->item, v = x->r->item;
    if (u>v) x->item = u;
    else x->item=v;

    return x;    // return a local pointer
}

Это фрагмент кода из «Алгоритма в c ++» Роберта Седжвика, стр. 252, Программа 5.19. А в функции max() возвращаемая переменная является указателем, который создается внутри функции.

По моему мнению, возвращение локального указателя не разрешено в c / c ++. Итак, мой вопрос: «Это нормально, чтобы написать такую ​​функцию»? Я не могу поверить, что такая классическая книга ошибается, как эта. Или я неправильно понял принцип? Пожалуйста помоги. Спасибо.

Answer 1

x не является «локальным указателем», то есть указателем на локальную переменную.*x было выделено с использованием new.x указывает на динамически распределенную память, и возвращать этот указатель просто отлично.Так что да, можно написать такую ​​функцию, и в книге нет ошибок.

Answer 2

Ошибка возвращать указатель на локальную переменную.x указывает на переменную, выделенную в куче:

link x = new node(a[m]);

Таким образом, x не указывает на локальную переменную.

Причина, по которой возвращается указатель на локальную переменнуюОшибка заключается в том, что такая переменная существует только до тех пор, пока функция активна (то есть между тем, как она вводится и выходит).Переменные, выделенные в куче (например, с использованием оператора new), существуют до тех пор, пока они не будут освобождены (например, с помощью оператора delete).

Answer 3

Это прекрасно, потому что содержимое x размещается в куче, а не в стеке. Вы можете быть сбиты с толку, так как там есть typedef node* link;, что делает его похожим на распределение в стеке, поскольку маскирует тот факт, что x на самом деле node *.