-1

我已经使用堆栈以迭代方式编写了一个用于二叉搜索树的中序遍历的程序。但是，它正在中止并显示以下消息：

*** glibc detected *** ./a.out: double free or corruption (fasttop): 0x096c60d8 ***
======= Backtrace: =========
/lib/i386-linux-gnu/libc.so.6(+0x6cbe1)[0x63fbe1]
/lib/i386-linux-gnu/libc.so.6(+0x6e50b)[0x64150b]
/lib/i386-linux-gnu/libc.so.6(cfree+0x6d)[0x64469d]
./a.out[0x804854d]
./a.out[0x80486b4]
./a.out[0x80487d9]
/lib/i386-linux-gnu/libc.so.6(__libc_start_main+0xe7)[0x5e9e37]
./a.out[0x80483c1]
======= Memory map: ========
005d3000-0072f000 r-xp 00000000 08:01 802619     /lib/i386-linux-gnu/libc-2.13.so
0072f000-00731000 r--p 0015c000 08:01 802619     /lib/i386-linux-gnu/libc-2.13.so
00731000-00732000 rw-p 0015e000 08:01 802619     /lib/i386-linux-gnu/libc-2.13.so
00732000-00735000 rw-p 00000000 00:00 0 
0076c000-00788000 r-xp 00000000 08:01 802616     /lib/i386-linux-gnu/ld-2.13.so
00788000-00789000 r--p 0001b000 08:01 802616     /lib/i386-linux-gnu/ld-2.13.so
00789000-0078a000 rw-p 0001c000 08:01 802616     /lib/i386-linux-gnu/ld-2.13.so
00c03000-00c1d000 r-xp 00000000 08:01 787452     /lib/i386-linux-gnu/libgcc_s.so.1
00c1d000-00c1e000 r--p 00019000 08:01 787452     /lib/i386-linux-gnu/libgcc_s.so.1
00c1e000-00c1f000 rw-p 0001a000 08:01 787452     /lib/i386-linux-gnu/libgcc_s.so.1
00d02000-00d03000 r-xp 00000000 00:00 0          [vdso]
08048000-08049000 r-xp 00000000 08:01 802400     /home/akash/Code/Data_Structures  /Trees  /a.out
08049000-0804a000 r--p 00000000 08:01 802400     /home/akash/Code/Data_Structures/Trees/a.out
0804a000-0804b000 rw-p 00001000 08:01 802400     /home/akash/Code/Data_Structures/Trees/a.out
096c6000-096e7000 rw-p 00000000 00:00 0          [heap]
b7700000-b7721000 rw-p 00000000 00:00 0 
b7721000-b7800000 ---p 00000000 00:00 0 
b78b2000-b78b3000 rw-p 00000000 00:00 0 
b78c0000-b78c3000 rw-p 00000000 00:00 0 
bfd80000-bfda1000 rw-p 00000000 00:00 0          [stack]
2Aborted

这是我编写的代码：

typedef struct node
{
    struct node *left;
    int data;
    struct node *right;
} bTree;

typedef struct stack
{
    bTree *tPtr;
    struct stack *next;
} stack;

void Push_Stack (stack **sPtr , bTree *tPtrRef)
{
    if((*sPtr) == NULL)
    {
        (*sPtr) = (stack *)malloc(sizeof(stack));
        (*sPtr)->tPtr = tPtrRef;
        (*sPtr)->next = NULL;
        return;
    }
    else
    {
        stack *temp = *sPtr;
        stack *s;
        while((*sPtr)->next != NULL)
        {
            (*sPtr) = (*sPtr)->next;
        }

        s = (stack *)malloc(sizeof(stack));
        s->tPtr = tPtrRef;
        s->next = NULL;
        (*sPtr)->next = s;
        (*sPtr) = temp;
        return;
    }

}

bTree *Pop_Stack (stack **sPtr)
{
    if((*sPtr) == NULL)
        printf("\n Underflow");
    else
    {
        bTree *temp;
        stack *s = NULL;
        stack *tempPtr = (*sPtr);
        while((*sPtr)->next != NULL)
            (*sPtr) = (*sPtr)->next;
        temp = ((*sPtr)->tPtr);
        s = (*sPtr);
        free(s);
        s = NULL;
        (*sPtr) = tempPtr;
        return temp;

    }
}
void Process_BTreeNode (bTree *ptr)
{
    printf("%d",(ptr->data));
}

int IsEmpty_Stack (stack *sPtr)
{
    if(sPtr == NULL)
        return 0;
    else
        return 1;
}
void Inorder_BTree_Itr (bTree *rootRef)
{
  bTree *tempRoot = rootRef;
  stack *tempStack = NULL;
  int isDone = 1;
  while(isDone)
  {
      while(tempRoot)
      {
          Push_Stack (&tempStack , tempRoot);
          tempRoot = tempRoot->left;
      }

      if(IsEmpty_Stack(tempStack))
      {
          bTree *temp = Pop_Stack (&tempStack);
          Process_BTreeNode (temp);
              tempRoot = temp->right;
      }
      else
          isDone = 0;
  }
}

int main()
{
    bTree *head = NULL;
    Insert_BTree (&head , 10);
    Insert_BTree (&head , 8);
    Insert_BTree (&head , 13);
    Insert_BTree (&head , 4);
    Insert_BTree (&head , 9);
    Insert_BTree (&head , 15);
    Insert_BTree (&head , 18);
    Insert_BTree (&head , 11);
    Insert_BTree (&head , 2);
    Insert_BTree (&head , 5);
    /*Inorder_BTree_Rec (head);*/ //Checked the Insert_Btree func using Recursive Preorder
    printf("\n");
    Inorder_BTree_Itr(head);

    return 0;
}

我也尝试使用 Valgrind 来查找内存损坏的位置，但我无法分析 Valgrind 日志：

==26857== ERROR SUMMARY: 89088 errors from 3 contexts (suppressed: 11 from 6)
==26857== 
==26857== 29696 errors in context 1 of 3:
==26857== Invalid free() / delete / delete[]
==26857==    at 0x4025BF0: free (vg_replace_malloc.c:366)
==26857==    by 0x804854C: Pop_Stack (BinaryTree.c:59)
==26857==    by 0x80486B3: Inorder_BTree_Itr (BinaryTree.c:133)
==26857==    by 0x80487D8: main (BinaryTree.c:159)
==26857==  Address 0x419e350 is 0 bytes inside a block of size 8 free'd
==26857==    at 0x4025BF0: free (vg_replace_malloc.c:366)
==26857==    by 0x804854C: Pop_Stack (BinaryTree.c:59)
==26857==    by 0x80486B3: Inorder_BTree_Itr (BinaryTree.c:133)
==26857==    by 0x80487D8: main (BinaryTree.c:159)
==26857== 
==26857== 
==26857== 29696 errors in context 2 of 3:
==26857== Invalid read of size 4
==26857==    at 0x8048535: Pop_Stack (BinaryTree.c:57)
==26857==    by 0x80486B3: Inorder_BTree_Itr (BinaryTree.c:133)
==26857==    by 0x80487D8: main (BinaryTree.c:159)
==26857==  Address 0x419e350 is 0 bytes inside a block of size 8 free'd
==26857==    at 0x4025BF0: free (vg_replace_malloc.c:366)
==26857==    by 0x804854C: Pop_Stack (BinaryTree.c:59)
==26857==    by 0x80486B3: Inorder_BTree_Itr (BinaryTree.c:133)
==26857==    by 0x80487D8: main (BinaryTree.c:159)
==26857== 
==26857== 
==26857== 29696 errors in context 3 of 3:
==26857== Invalid read of size 4
==26857==    at 0x8048529: Pop_Stack (BinaryTree.c:55)
==26857==    by 0x80486B3: Inorder_BTree_Itr (BinaryTree.c:133)
==26857==    by 0x80487D8: main (BinaryTree.c:159)
==26857==  Address 0x419e354 is 4 bytes inside a block of size 8 free'd
==26857==    at 0x4025BF0: free (vg_replace_malloc.c:366)
==26857==    by 0x804854C: Pop_Stack (BinaryTree.c:59)
==26857==    by 0x80486B3: Inorder_BTree_Itr (BinaryTree.c:133)
==26857==    by 0x80487D8: main (BinaryTree.c:159)
==26857== 
--26857-- 
--26857-- used_suppression:     11 U1004-ARM-_dl_relocate_object
==26857== 
==26857== ERROR SUMMARY: 89088 errors from 3 contexts (suppressed: 11 from 6)

有人可以给我任何有关如何分析内存映射或 Valgrind 日志的指示，以便我可以调试此错误。谢谢。

4

1 回答 1

1 
while((*sPtr)->next != NULL)
    (*sPtr) = (*sPtr)->next;

temp = ((*sPtr)->tPtr);
s = (*sPtr);
free(s);

在上述链表操作期间，您删除了最后一个元素，但不存储被释放的元素的下一个元素。在链表中删除时，您还应该保留前一个指针。您可以尝试以下方法：

stack *prev = NULL;  
while((*sPtr)->next != NULL) {  
   prev = *sPtr;  
   (*sPtr) = (*sPtr)->next;  
}

if (prev) {  
    prev->next = NULL;  
}
于 2012-05-20T05:08:29.717 回答