c - Qsort 与哈夫曼树

Question

我有一个问题，我必须构建一个哈夫曼树，我理解这个问题背后的概念并且我知道如何去做。但是，我发现我的代码出错的原因与我的排序功能有关。每次我在列表中输入一个新节点时，我都想对列表进行排序。我有一个结构，其中有频率，我制作了一个结构数组，字符存储在文件中。

我的问题在于创建节点，创建了一个新节点并指向数组中的两个字符。但是，当我对这个列表进行排序时，指针会更改为其他字符。每一步都会发生这种情况，并导致它完全错误。

我在 main 中的 qsort 调用是这样的:

qsort(list, n, sizeof(Node), intcompare);

我的 intcompare 函数是这样的:

int intcompare(const void *a, const void *b)
{
int freq1 = ((Node*)a)->frequency;
int freq2 = ((Node*)b)->frequency;

   if (freq1 == freq2){
      return 0;
   }
   else if (freq1 < freq2){
      return 1;
   }
   else{
      return -1;
   }

}

我的结构是这样的:

typedef struct node{
   char character;
   int frequency;
   struct node *left;
   struct node *right;
}Node;

每次调用 qsort 时，我的列表都会按频率正确排序。为什么这会改变我的结构中的指针指向的位置？提前致谢!!

Answer 1

qsort 移动数组中的结构。因此，如果存在一个指向数组中索引 3 处的字符 X 的 left 指针，并且 qsort 移动 X 到索引 16，然后 left 指针将不再指向 X。它将指向索引 3 处的任何 qsort。长话短说，您需要在每次之后重新计算所有 left 和 right 指针种类。