c - 在我的编码器中双重释放或损坏(fasttop)

Question

我的程序涉及在队列中组合树列表，我的程序编译完美并且适用于大约一半的代码然后向我抛出这个错误。我已经将它缩小到涉及我的 freeTree 以及我如何在编码文件中调用它，对于一些背景故事，这是基于文本文件中字符频率的编码器，所以如果有一个包含 5 个不同字符的文本文件，那么这段代码将从队列中的 5 个不同节点开始。队列中的每个初始节点都包含字符和频率，优先级队列基于频率，以决胜局作为字符的数值。

malloc_printerr (action=3, str=0x7ffff7b98938 "double free or corruption (fasttop)", ptr=0x6034b0) at malloc.c:5027

结构体是这样的，符号代表字符，权重代表频率

struct treeNode
{
  unsigned char symbol;
  unsigned long weight;
  struct treeNode* left;
  struct treeNode* right;
  struct treeNode* next;
};

struct queue
{
  struct treeNode* first;
  struct treeNode* last;
};

这是我的 freeTree 方法

void freeTree( struct treeNode* root )
{
  if( root != NULL )
  {
    freeTree( root->left );
    freeTree( root->right );
    free( root );
  }
}

这些是我在代码的主要部分中使用的变量或树节点

  struct treeNode* newNode;
  struct treeNode* holder;

这就是所有被调用的地方，它应该通过我的队列将两个节点组合成一棵树，顶部的节点等于两个输入节点的权重，这应该继续直到队列只包含一棵大树

while( treeCount > 1 )
  {
    newNode = combineTwo( q->first, q->first->next );
    if( charCount == 2 )
    {
      holder = q->first;
      q->first = q->first->next;
      freeTree( holder );
      holder = q->first;
      q->first = newNode;
      freeTree( holder );
    }
    else
    {
      holder = q->first;
      q->first = q->first->next;
      freeTree( holder );
      holder = q->first;
      q->first = q->first->next;
      freeTree( holder );
      insertSortedNode( q, newNode );
    }
    charCount--;
    holder = NULL;
  }

这是我的 combineTwo 方法，它将使两个输入节点成为一个节点上的叶子

struct treeNode* combineTwo( struct treeNode* first, struct treeNode* second )
{
  struct treeNode* newNode = createNode( '\0', (first -> weight) + (second -> weight));
  if( first -> weight > second -> weight )
  {
    newNode -> right = first;
    newNode -> left = second;
  }
  if( first -> weight < second -> weight )
  {
    newNode -> left = first;
    newNode -> right = second;
  }
  if( first -> weight == second -> weight )
  {
    if( first -> symbol > second -> symbol )
    {
      newNode -> right = first;
      newNode -> left = second;
    }
    if( first -> symbol < second -> symbol )
    {
      newNode -> left = first;
      newNode -> right = second;
    }
  }
  return newNode;
}

如果需要更多信息，我会整天在这里回答任何问题

Answer 1

combineTwo 创建一个新节点，它(可能)将 newnode 的 left 和 right 指向 first 和 second 参数值。然后，您的 while 循环中的代码使用 freeTree 释放这些指针。

例如:

newNode = combineTwo( q->first, q->first->next ); // newNode->left = q->first (possibly)
if( charCount == 2 )
{
  holder = q->first;
  q->first = q->first->next;
  freeTree( holder );      // freeing the original q->first here. newNode still points to it.

需要判断新节点的left和right是应该指向原来的树节点，还是应该删除它们(原来的节点)。如果没有无效指针，您就无法同时执行这两项操作。