c - 使用 C 中的 qsort 按频率将单词排序到哈希表中

Question

我的任务是改进将 .txt 文件中的所有单词排序到哈希表中的程序的运行时间。这个三重嵌套的 for 循环排序算法就是问题所在:

// Sort hash table elements and save as pointers in 'array'
for (i = 0; i < tsize; i++)
   for (ele = htable[i]; ele != NULL; ele = ele->next) {
    if (ele->freq == 1)
    scnt++;

    for (j = cnt; j > 0 && ele->freq > array[j-1]->freq; j--)
      array[j] = array[j-1];

    array[j] = ele;
    cnt++;
}

我想做的是使用 qsort()，但我不知道应该从哪里开始。任何建议都会有所帮助，谢谢。

更新:我将上面的代码片段修改如下:

// Sort hash table elements and save as pointers in 'array'
for (i = 0; i < tsize; i++)
   for (ele = htable[i]; ele != NULL; ele = ele->next) {
    if (ele->freq == 1)
    scnt++;

    array[cnt] = ele;
    qsort(array, tsize, sizeof(h_ptr), (int (*) (const void *, const void *))compare_ele);
    cnt++;
}

并添加了这个比较功能:

// Compare function for qsort
int compare_ele (h_ptr *a, h_ptr *b)
{
    if (a->freq < b->freq)
        return + 1;
    if (a->freq > b->freq)
        return - 1;
    return 0;
}

h_ptr 的结构是:

typedef struct HELE {
    char *word;
    int freq;
    struct HELE *next;
} h_rec, *h_ptr;

当我编译时，我收到此错误:

analysis.c: In function ‘compare_ele’:
analysis.c:137:10: error: request for member ‘freq’ in something not a structure or union
 if (a->freq < b->freq)
      ^
analysis.c:137:20: error: request for member ‘freq’ in something not a structure or union
 if (a->freq < b->freq)
                ^
analysis.c:139:10: error: request for member ‘freq’ in something not a structure or union
 if (a->freq > b->freq)
      ^
analysis.c:139:20: error: request for member ‘freq’ in something not a structure or union
 if (a->freq > b->freq)

Answer 1

更新后的代码中的两个 for 循环正在创建一个未排序的数组，同时跟踪变量 cnt 中数组中的项目数。您应该在这些 for 循环完成后调用 qsort，并将 cnt 作为第二个参数传递给 qsort。

比较函数应始终遵循qsort指定的函数原型(prototype)。定义一个在用作 qsort 的第四个参数时需要强制转换的比较器函数是不好的做法。请参阅wikipedia article有关如何编写正确的比较器函数的示例。

在您的情况下，比较器函数的前两行应该是

h_rec *a = *(const h_rec **)p;
h_rec *b = *(const h_rec **)q;

请注意，我总是避免将 * 放入 typedef 中。这是错误消息的来源，您没有正确考虑到代码中的 a 和 b 实际上是指针到指针类型的事实-构造-HELE。