c - qsort() 中使用的比较函数是否有任何限制

Question

我编写了这段代码片段来将字符串数组排序为最小化它们的连接的顺序:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int cmpstr(const void* p1, const void* p2){
    int p1l = strlen((const char*)p1);
    int p2l = strlen((const char*)p2);
    int r = strncmp((const char*)p1, (const char*)p2, p1l<p2l?p1l:p2l);
    if(r == 0 && p1l != p2l){
        if(p1l < p2l){
            return cmpstr(p1, (const char*)p2 + p1l);
        }
        return cmpstr((const char*)p1 + p2l, p2);
    }
    return r;
}

int main(){
    const char* arrstr[] = {"93", "936", "15", "152", "946"};
    int num = sizeof(arrstr) / sizeof(char*);
    qsort(arrstr, num, sizeof(char*), cmpstr);
    for(int i = 0; i < num; i++){
        printf("%s\n", arrstr[i]);
    }
}

这些字符串应按顺序 15 152 936 93 946 排序。我们希望 93 介于 936 和 946 之间，因为 936 93 <93 936和 93 946 <946 93(为清楚起见忽略添加的空格)。

但是代码没有按预期工作。该数组根本没有排序，尽管我对 cmpstr() 的测试完全符合我的预期。

我做错了什么？

我注意到，当我将 cmpstr() 的强制转换部分从 *(char* const*) 更改为 (char*)，qsort() 也不起作用。这是为什么？

Answer 1

传递给qsort 的比较函数接收要比较的两个数组元素的地址。由于每个数组元素都是一个 char *，因此每个元素的地址都是一个 char **。所以你缺少一级间接。

您需要将每个参数转换为 char * const *，然后取消引用以获取指向字符串的指针:

int cmpstr(const void* p1p, const void* p2p){
    char *p1 = *(char * const *)p1p;
    char *p2 = *(char * const *)p2p;
    ...
}

编辑:

因为你想递归地调用这个函数，你需要一个非递归包装函数来包围你的递归函数，因为它们采用的参数是不一样的:

// internal recursive function that takes two strings
static int cmpstr_int(const char* p1, const char* p2){
    int p1l = strlen(p1);
    int p2l = strlen(p2);
    int r = strncmp(p1, p2, p1l<p2l?p1l:p2l);
    if(r == 0 && p1l != p2l){
        if(p1l < p2l){
            return cmpstr_int(p1, p2 + p1l);
        }
        return cmpstr_int(p1 + p2l, p2);
    }
    return r;
}

// comparison function that extracts desired datatype from void * params
// and passes them to recursive function
static int cmpstr(const void* p1p, const void* p2p){
    const char *p1 = *(char * const *)p1p;
    const char *p2 = *(char * const *)p2p;
    return cmpstr_int(p1, p2);
}