比较指针和NULL时程序崩溃了

Question

比较指针和NULL时程序崩溃了

3

 template<class item_type>
 struct node{
     item_type x;
     node<item_type> *left;
     node<item_type> *right;
     //functions
 };

 template<class item_type, class param>
 class Tree{
        node<item_type> *root;
    public:
        item_type Get_Item(param item);
        void Add_Item(item_type item);
        void Delete_Item(item_type item);

        //more functions

        Tree();
};


template<class item_type, class param>
Tree<item_type, param>::Tree()
{
    this->root = new node<item_type>;

    this->root->left=NULL;
    this->root->right=NULL;

}

添加项目：

void Tree<item_type, param>::Add_Item(item_type item)
{

    node<item_type> newItem;
    newItem.x = item;
    node<item_type> *cur = root;
    node<item_type> *prev;

    if(cur->x==NULL)
        cur->x=item;

    int ifGreater;
    while(cur->left!=NULL || cur->right!=NULL)
    {
        if(item<cur->x)
        {
            ifGreater = 0;
            prev = cur;
            cur = cur->left;
        }
        else
        {
            ifGreater = 1;
            prev = cur;
            cur = cur->right;
        }
    }
    if(ifGreater==1)
        prev->right = &newItem;
    if(ifGreater==0)
        prev->left = &newItem;
}

在这个函数中的cout<<1处出现了问题。

template<class item_type, class param>
    void Tree<item_type, param>::Delete_Item(item_type item)
    {
        node<item_type> *cur = root;
        node<item_type> *prev;

        int ifGreater;
        if(cur==NULL)
        {
            cout<<"Not found"<<endl;
            return;
        }

        while(cur!= NULL && (cur->left!=NULL || cur->right!=NULL))
        {   
            cout<<1; //crash occurs RIGHT before here as 1 is never printed
            if(item<cur->x)
            {
                //do something   
            }                              
        }

问题出现在cout<<1之前和int ifGreater;声明之后。 cout仅用于测试运行位置和停止运行位置。我使用调用来运行此函数。

int main()
{
     Tree<int,int> theTree;
     theTree.Add_Item(1); //so the tree isn't empty
     theTree.Delete_Item(1);
}

注意：该程序甚至无法通过第一次迭代，内存的不当处理（已经被修复）并不是该特定错误的原因。

- SemicolonExpected

3

至少在删除当前节点 cur 后，你需要跳出循环。你很可能还需要在删除之前修补指向该节点的指针。 - Dietmar Kühl

最好拿一张纸坐下来，思考它应该如何工作。你应该处理 root == NULL 的情况，并且除了 Dietmar 的建议之外，当“未找到”时你应该退出（break/return）。 - Tony Delroy

它没有达到那个点，但是谢谢@DietmarKühl修复 :) - SemicolonExpected

1

我认为如果没有提供最小完整示例，或者至少是一个完整的示例，我们将无法帮助您。 - Beta

@ali @santa 我已经检查过了，在 while(cur!= NULL && (cur->left!=NULL || cur->right!=NULL))。此外，在调用此函数之前，我还确保它不是空的，因为另一个函数在将值放入根节点之前进行了操作。 - SemicolonExpected

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- greatwolf · Accepted Answer

以下代码存在未定义行为：

template <class item_type, class param>
void Tree<item_type, param>::Add_Item(item_type item)
{
    node<item_type> newItem;
    // ...
    if (ifGreater == 1)
        prev->right = &newItem;
    if (ifGreater == 0)
        prev->left = &newItem;       
}

在上面的代码中，newItem 是一个本地变量，而当 Add_Item 退出后，您仍然保留了指向该本地变量的指针，这很可能是崩溃的原因。

此外，您从未初始化 ifGreater 或 node<item_type> *prev;。同样，当执行以下操作时，这将导致更多未定义的行为：

    if (ifGreater == 1)
        prev->right = &newItem;
    if (ifGreater == 0)
        prev->left = &newItem;

您很可能会引用一些随机的内存。这是因为不能保证您的while循环被执行，例如考虑left和right都是NULL的情况。