return local pointer

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 *.