在二叉树中删除数据时自由段错误 [英] segfault in free while deleting data in binary tree

问题描述

我在二进制搜索树中删除一些数据时可以免费获得段错误。

来自gdb的后退跟踪如下。



＃1 0x0036fe30 in raise（）from /lib/libc.so.6

（gdb）up

＃2 0x00371741 in / from /lib/libc.so.6

（gdb）up / /
＃3 0x003a88cb in __libc_message（）from /lib/libc.so.6 br />
（gdb）up

＃4 0x003b0c65 in _int_free（）from /lib/libc.so.6

（gdb）up

＃5 0x003b4c59 in free（）from /lib/libc.so.6

（gdb）up

＃6 0x0804a014 in Delete_Node（dest = 4854128） ，del_trav_node = 0x1804e158，dest_std = 4854128）at src / smsc_bintree_operation.c：297

297 src / smsc_bintree_operation.c：没有这样的文件或目录。
src / smsc_bintree_operation中的
.c

（gdb）p del_trav_node-> left

$ 1 =（struct bst *）0x0

（gdb）p del_trav_node-> ;对吧

$ 2 =（struct bst *）0xebb000



如需参考，删除代码如下

 NODE Delete_Node（U32bit dest，NODE del_trav_node，U32bit dest_std）
 {
 NODE del_trav_temp，del_trav_prev; 
 
  if （del_trav_node == NULL）
 {
 LOG（   \ notlement not found \\\
）; 
} 
  else  
 {
  if （dest < del_trav_node-> key_val）
 {
 del_trav_prev = del_trav_node; 
 del_trav_node-> left = Delete_Node（dest，del_trav_node-> left，dest_std）; 
 
} 
 其他  if （dest> del_trav_node-> ; key_val）
 {
 del_trav_prev = del_trav_node; 
 del_trav_node-> right = Delete_Node（dest，del_trav_node-> right，dest_std）; 
 
} 
 其他  //  如果要删除的节点是根节点 
 {
  if （（del_trav_node-> left = = NULL）&&（del_trav_node-> right == NULL））
 {
 
 free（del_trav_node）; 
 
  return （NULL）; 
} 
  else   if （（del_trav_node-> left！= NULL） &&（del_trav_node-> right！= NULL））
 {
 
 del_trav_temp = Find_Min（del_trav_node-> right）; 
 del_trav_node-> key_val = del_trav_temp-> key_val; 
 memcpy（& del_trav_node-> value，& del_trav_temp-> value， sizeof （SMSC_DATA_ARRAY））; 
 del_trav_node-> right = Delete_Node（del_trav_node-> key_val，del_trav_node-> right，dest_std）; 
 
 
 
} 
  else   if （del_trav_node-> left == NULL）
 {
 del_trav_temp = del_trav_node; 
 
 del_trav_node = del_trav_node-> right; 
 
  if （del_trav_temp！= NULL）
 free（del_trav_temp）;行号---  297  
 
} 
  else   if （del_trav_node-> right == NULL）
 {
 
 
 del_trav_temp = del_trav_node; 
 
 del_trav_node = del_trav_node-> left; 
 
  if （del_trav_temp！= NULL）
 free（del_trav_temp）; 
 
} 
  else ; 
} 
} 
  return  del_trav_node; 
}; 

任何帮助将不胜感激。



谢谢

SP



代码块添加 - OriginalGriff [/ edit]

解决方案

1 =（struct bst *）0x0

（gdb）p del_trav_node-> right

2 =（struct bst *）0xebb000



如需参考，删除代码如下

 NODE Delete_Node（U32bit dest，NODE del_trav_node，U32bit dest_std）
 {
 NODE del_trav_temp，del_trav_prev; 
 
  if （del_trav_node == NULL）
 {
 LOG（   \ notlement not found \\\
）; 
} 
  else  
 {
  if （dest < del_trav_node-> key_val）
 {
 del_trav_prev = del_trav_node; 
 del_trav_node-> left = Delete_Node（dest，del_trav_node-> left，dest_std）; 
 
} 
 其他  if （dest> del_trav_node-> ; key_val）
 {
 del_trav_prev = del_trav_node; 
 del_trav_node-> right = Delete_Node（dest，del_trav_node-> right，dest_std）; 
 
} 
 其他  //  如果要删除的节点是根节点 
 {
  if （（del_trav_node-> left = = NULL）&&（del_trav_node-> right == NULL））
 {
 
 free（del_trav_node）; 
 
  return （NULL）; 
} 
  else   if （（del_trav_node-> left！= NULL） &&（del_trav_node-> right！= NULL））
 {
 
 del_trav_temp = Find_Min（del_trav_node-> right）; 
 del_trav_node-> key_val = del_trav_temp-> key_val; 
 memcpy（& del_trav_node-> value，& del_trav_temp-> value， sizeof （SMSC_DATA_ARRAY））; 
 del_trav_node-> right = Delete_Node（del_trav_node-> key_val，del_trav_node-> right，dest_std）; 
 
 
 
} 
  else   if （del_trav_node-> left == NULL）
 {
 del_trav_temp = del_trav_node; 
 
 del_trav_node = del_trav_node-> right; 
 
  if （del_trav_temp！= NULL）
 free（del_trav_temp）;行号---  297  
 
} 
  else   if （del_trav_node-> right == NULL）
 {
 
 
 del_trav_temp = del_trav_node; 
 
 del_trav_node = del_trav_node-> left; 
 
  if （del_trav_temp！= NULL）
 free（del_trav_temp）; 
 
} 
  else ; 
} 
} 
  return  del_trav_node; 
}; 

任何帮助将不胜感激。



谢谢

SP



已添加代码块 - OriginalGriff [/ edit]

首先，你用 del_trav_prev 做什么？你可能想要用它做一些事情，但你分配一个值，然后完全忽略它。不知道这是否相关，但要么你需要做些什么，要么摆脱它。



其次，这取决于你的数据在很大程度上 - 可能是一个分支或另一个是问题，或者可能是您设置树的代码有问题。在任何一种情况下我都说不清楚，因为我无法访问你已完成的树。



所以，它取决于你。

在函数的第一行放置一个断点，并通过调试器运行代码。然后查看您的代码，并查看您的数据并找出手动应该发生的事情。然后单步执行每一行检查您预期发生的情况正是如此。如果不是，那就是当你遇到问题时，你可以回溯（或者再次运行并仔细观察）以找出原因。


对不起，但我们不能为你做到这一点 - 时间让你倾向于一种新的（非常非常有用的）技能：调试！

Hi ,
I am getting segfault on free while deleting some data in binary search tree.
The back trace from gdb is as follows.

#1 0x0036fe30 in raise () from /lib/libc.so.6
(gdb) up
#2 0x00371741 in abort () from /lib/libc.so.6
(gdb) up
#3 0x003a88cb in __libc_message () from /lib/libc.so.6
(gdb) up
#4 0x003b0c65 in _int_free () from /lib/libc.so.6
(gdb) up
#5 0x003b4c59 in free () from /lib/libc.so.6
(gdb) up
#6 0x0804a014 in Delete_Node (dest=4854128, del_trav_node=0x1804e158, dest_std=4854128) at src/smsc_bintree_operation.c:297
297 src/smsc_bintree_operation.c: No such file or directory.
in src/smsc_bintree_operation.c
(gdb) p del_trav_node->left
$1 = (struct bst *) 0x0
(gdb) p del_trav_node->right
$2 = (struct bst *) 0xebb000

For a reference the code for deletion is as follows

NODE Delete_Node(U32bit dest,NODE del_trav_node, U32bit dest_std)
{
        NODE del_trav_temp,del_trav_prev;

        if(del_trav_node == NULL)
        {
                LOG("\nelement not found\n");
        }
        else
        {
                if(dest < del_trav_node->key_val)
                {
                        del_trav_prev = del_trav_node;
                        del_trav_node->left = Delete_Node(dest,del_trav_node->left,dest_std);

                }
                else if(dest > del_trav_node->key_val)
                {
                        del_trav_prev = del_trav_node;
                        del_trav_node->right = Delete_Node(dest,del_trav_node->right,dest_std);

                }
                else //if the node to be deleted is the root node
                {
                        if((del_trav_node->left == NULL) && (del_trav_node->right == NULL))
                        {
                               
                                free(del_trav_node);
                               
                          return(NULL);
                      }
                      else if((del_trav_node->left != NULL) &&(del_trav_node->right != NULL))
                      {
                             
                        del_trav_temp = Find_Min(del_trav_node->right);
                        del_trav_node->key_val = del_trav_temp->key_val;
                        memcpy(&del_trav_node->value,&del_trav_temp->value,sizeof(SMSC_DATA_ARRAY));
del_trav_node->right = Delete_Node(del_trav_node->key_val,del_trav_node->right,dest_std);
                            
                            

                      }
                      else if(del_trav_node->left == NULL)
                      {
                             del_trav_temp = del_trav_node;

                              del_trav_node = del_trav_node->right;

                              if(del_trav_temp != NULL)
                                      free(del_trav_temp);  line no  ---297
                              
                      }
                       else if(del_trav_node->right == NULL)
                        {
                               

                                del_trav_temp = del_trav_node;

                                del_trav_node = del_trav_node->left;

                                if(del_trav_temp != NULL)
                                        free(del_trav_temp);
                            
                        }
                        else;
                }
        }
        return del_trav_node;
};

Any help will be appreciated .

Thanks
SP

[edit]Code block added - OriginalGriff[/edit]

解决方案

1 = (struct bst *) 0x0
(gdb) p del_trav_node->right

2 = (struct bst *) 0xebb000

For a reference the code for deletion is as follows

NODE Delete_Node(U32bit dest,NODE del_trav_node, U32bit dest_std)
{
        NODE del_trav_temp,del_trav_prev;

        if(del_trav_node == NULL)
        {
                LOG("\nelement not found\n");
        }
        else
        {
                if(dest < del_trav_node->key_val)
                {
                        del_trav_prev = del_trav_node;
                        del_trav_node->left = Delete_Node(dest,del_trav_node->left,dest_std);

                }
                else if(dest > del_trav_node->key_val)
                {
                        del_trav_prev = del_trav_node;
                        del_trav_node->right = Delete_Node(dest,del_trav_node->right,dest_std);

                }
                else //if the node to be deleted is the root node
                {
                        if((del_trav_node->left == NULL) && (del_trav_node->right == NULL))
                        {
                               
                                free(del_trav_node);
                               
                          return(NULL);
                      }
                      else if((del_trav_node->left != NULL) &&(del_trav_node->right != NULL))
                      {
                             
                        del_trav_temp = Find_Min(del_trav_node->right);
                        del_trav_node->key_val = del_trav_temp->key_val;
                        memcpy(&del_trav_node->value,&del_trav_temp->value,sizeof(SMSC_DATA_ARRAY));
del_trav_node->right = Delete_Node(del_trav_node->key_val,del_trav_node->right,dest_std);
                            
                            

                      }
                      else if(del_trav_node->left == NULL)
                      {
                             del_trav_temp = del_trav_node;

                              del_trav_node = del_trav_node->right;

                              if(del_trav_temp != NULL)
                                      free(del_trav_temp);  line no  ---297
                              
                      }
                       else if(del_trav_node->right == NULL)
                        {
                               

                                del_trav_temp = del_trav_node;

                                del_trav_node = del_trav_node->left;

                                if(del_trav_temp != NULL)
                                        free(del_trav_temp);
                            
                        }
                        else;
                }
        }
        return del_trav_node;
};

Any help will be appreciated .

Thanks
SP

[edit]Code block added - OriginalGriff[/edit]

First off, what are you doing with del_trav_prev? You presumably meant to do something with it, but you assign a value, and then ignore it completely. Don't know if that is relevant, but either you need to do something with it, or get rid off it.

Secondly, this is going to depend on your data to a large extent - it may be that one "branch" or the other is the problem, or it may be that your code to set up the tree is faulty. I can't tell in either case, because I don't have access to your completed tree.

So, its going to be up to you.
Put a breakpoint on the first line in the function, and run your code through the debugger. Then look at your code, and at your data and work out what should happen manually. Then single step each line checking that what you expected to happen is exactly what did. When it isn't, that's when you have a problem, and you can back-track (or run it again and look more closely) to find out why.

Sorry, but we can't do that for you - time for you to leans a new (and very, very useful) skill: debugging!

这篇关于在二叉树中删除数据时自由段错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！