代码之家 › 专栏 › 技术社区 › Kevin

C(初学者):为什么我的排序不起作用?编辑:从一个错误到另一个错误

qsort struct algorithm c

1

Kevin · 技术社区 · 14 年前

我在做K&R练习6-4,它是:

我决定创建一个名为dstncferqnode6_4的结构:

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

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

这样做是为了通过遍历BST(它包含指向到目前为止遇到的所有单词的指针)来更新单词(节点)的计数。分析完整个输入后,指针数组将按成员的“count”变量排序,然后打印出来。自从

添加新词/更新计数的代码如下:( 我认为没有什么问题,因为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”作为指向节点的指针数组( ). 因此,本质上,BST和数组包含相同的信息(实际上数组指针被初始化为BST中相应的指针),但它们的用途不同。BST用于添加新单词/更新已遇到单词的计数,数组在末尾(按每个单词的计数)排序并打印。但是,我遇到了与最初运行时相同的问题:在调用qsort之后,数组的顺序保持不变。

2 回复 | 直到 14 年前

1

0

R.. GitHub STOP HELPING ICE 14 年前

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

顺便说一下,我知道你在用 realloc 重新分配 每当它必须将分配的数组移动到一个新位置以满足新的大小要求时,只会更糟:节点指针现在都指向无效地址,使用它们将导致未定义的行为。

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

2

0

Kevin 14 年前

所以我设法用自己的quicksort实现对它进行排序。stlib.h的版本仍然没有排序我的数组。它只能用于基元类型的数组吗?因为这是我能看到的阻止它工作的唯一原因。

void swapFreq6_4(struct dstncFreqNode6_4 **a, struct dstncFreqNode6_4 **b)
{
   struct dstncFreqNode6_4 *t=*a; *a=*b; *b=t;
}

void **sortFreq6_4(struct dstncFreqNode6_4 **arr, int beg, int end)
{

   if (end > beg + 1)
   {
      struct dstncFreqNode6_4 *piv = *(arr + beg);
      int l = beg + 1;
      int r = end;


     while (l < r)
     {
         if ( (*(arr + l))-> count <= piv -> count)
             l++;
         else
             swapFreq6_4((arr + l), (arr + --r));
     }



     swapFreq6_4((arr + --l), (arr + beg));
     sortFreq6_4(arr, beg, l);
     sortFreq6_4(arr, r, end);

  }
}

有人知道为什么stdlib的qsort代码不能与我的结构一起工作吗?我用错了吗(我对它的调用,以及比较函数都在原来的post中)?