c - C 程序中的内存损坏/双重释放问题

Question

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

*** 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 日志的指示，以便我可以调试此错误。谢谢。

Answer 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;  
}