意外的全局变量值;在C++中使用skewheap实现

Question

我正在尝试为我的数据结构讲座实现skewheap。忽略algotihm是否有效，我有代码本身的问题。在VS 2012代码运行但返回意外的结果。在调试过程中，全局变量的值（root）意外改变。在输入Insert(1)函数（第72行）之前，root的值是我期望它们的值（key=5,right=NULL,left=NULL）。但是当步进Insert()时，值域会随机更改。接着，在到达线45时：

node *p = &input; 

root变化值（input->key，null，null）。在Dev C++中，该程序被关闭，其中SIGSEV。一般sistuation看起来相似，但在Print()中，指向left和right的指针将值更改为某些意外值。这是什么原因？

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
using namespace std; 

struct node 
{ 
    int key; 
    node* right; 
    node* left; 
    node(int _key, node* _right, node* _left) 
    { 
     key = _key; 
     right = _right; 
     left = _left; 
    } 
}; 

node* root = NULL; 

node* Union(node* p1, node* p2) 
{ 
    node* p; 
    if (!p1) 
     return p2; 
    if (!p2) 
     return p1; 
    if (p1->key > p2->key) { 
     p = p1; 
     Union(p1->right, p2); 
    } else { 
     p = p2; 
     Union(p1, p2->right); 
    } 

    swap(p->left, p->right); 
    return p; 
} 


void Insert(int v) 
{ 
    node input = node(v, NULL, NULL); 
    node* p = &input; 
    root = Union(root, p); 
} 

void Print(node* v) 
{ 
    if (!v) { 
     return; 
    } 

    if (v->right) { 
     Print(v->right); 
    } 

    cout << v->key << endl; 

    if (v->left) { 
     Print(v->left); 
    } 
} 

int main() 
{ 
    Insert(5); 
    Insert(1); 
    cout << root->key; 

    system("pause"); 
    return 0; 
} 

Answer 1

input是本地的Insert()范围，因为它被声明为主体内部的自动变量。它没有像new所声明的对象那样具有动态存储持续时间。如果您的Union()方法返回p2（也就是说，如果它从input返回一个节点），那么root仍将指向在Insert()函数结束时仍然被销毁的对象。这被称为悬摆指针。

声明你的对象动态地防止这种情况发生：

node* input = new node(v, NULL, NULL); 
node* p = input; 
root = Union(root, p);