C(初学者): Why won't my qsort work? 编辑:从一个错误到另一个错误

Question

我正在进行 K&R 练习 6-4，即:

6-4. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.

我决定做的是创建一个名为 dstncFreqNode6_4 的结构:

struct dstncFreqNode6_4
{
   char *word;
   int count;
   struct dstncFreqNode6_4 *left;
   struct dstncFreqNode6_4 *right;
};

然后我解析输入的单词，并为每个不同的单词创建一个“dstncFreqNode6_4”节点和两个指向它的指针:一个插入 BST(添加新单词/更新已经遇到的单词的计数)，和一个插入到“dsntFredNode6_4”指针的全局数组中。

这样做是为了让我可以通过遍历 BST(它包含指向目前遇到的所有单词的指针)来更新单词(节点)的计数。整个输入被解析后，指针数组将按成员的“计数”变量排序，然后打印。由于

添加新词/更新计数的代码在这里:(我不认为它有什么问题，因为 BST 和数组似乎被正确填充，所以你可以忽略它):

//"wordCounts" is originally a global dstncFreqNode6_4** declared outside the function, numWords is the current length of the array

struct dstncFreqNode6_4 *addFreqNode6_4(struct dstncFreqNode6_4 *root, char *word)
{

    if(root == NULL)
    {

       root = (struct dstncFreqNode6_4 *) malloc(sizeof(struct dstncFreqNode6_4));
       root -> word = word;
       root -> count = 1;

       root -> left = NULL;
       root -> right = NULL;


       struct dstncFreqNode6_4 **p;

       wordCounts = (struct dstncFreqNode6_4 **) realloc(wordCounts, sizeof(struct dstncFreqNode6_4*) * (numWords +1));
       p = wordCounts + numWords++;

       (*p) = root;

    }
    else if(strcmp(word, root -> word) < 0)
        root -> left = addFreqNode6_4(root -> left, word);
    else if(strcmp(word, root -> word) > 0)
        root -> right = addFreqNode6_4(root -> right, word);
    else
        root -> count++;

return root;

所以除了排序之外，我的一切都正常工作；它根本不会对数组进行排序。也就是说... 元素的顺序保持不变 编辑:我得到一个段错误。 编辑＃2: 现在没有段错误；原来的问题依然存在。

我正在使用 STLib.h 的 qsort 方法；我使用的比较函数是:

int qcmp6_4(const void *a, const void *b)
{
    return (*(struct dstncFreqNode6_4 **)a) -> count - (*(struct dstncFreqNode6_4 **)b) -> count;
}

我似乎无法弄清楚为什么它不能正确排序。我实际上实现了自己的快速排序算法并得到了相同的结果。我现在真的不知道。

如果能得到一些新鲜的、专家的眼光为我指明正确的方向，那就太好了。谢谢。

编辑

抱歉，这是对 qsort 的调用:

qsort(wordCounts, numWords, sizeof(struct dstncFreqNode6_4 *), qcmp6_4);

编辑#2:

按照建议，我将“wordCounts”设为节点指针数组(本文中的所有代码都已更新以反射(reflect)这一点)。所以从本质上讲，BST和数组包含的信息是一样的(实际上数组指针被初始化为BST中对应的指针)，只是用途不同。 BST 用于添加新词/更新已遇到词的计数，数组在末尾排序(按每个词的计数)并打印。但是，我遇到了与最初遇到的相同问题:调用 qsort 后数组的顺序保持不变。

Answer 1

在我看来，您正在尝试对节点数组进行排序，每个节点都包含指向数组中其他节点的指针。排序后，这些指针当然会指向错误的数组元素。也许这是你的问题？

顺便说一下，我看到您正在使用 realloc。每当它必须将分配的数组移动到新位置以满足新的大小要求时，指向数组元素的指针也会出现同样的问题，更糟糕的是:节点指针现在将全部指向到无效地址并使用它们将导致未定义的行为。

一个可能的解决方案是永远不要修改您的原始节点数组，而是制作第二个指向节点的指针数组，并使用比较它们指向的节点的比较函数对该指针数组进行排序到。