如何在C语言中对指向字符的指针数组进行qsort排序？

Question

假设我在C语言中有一个指向字符指针的数组：

char *data[5] = { "boda", "cydo", "washington", "dc", "obama" };

我希望使用qsort对这个数组进行排序:

qsort(data, 5, sizeof(char *), compare_function);

我无法想出比较函数。由于某些原因，以下代码不起作用：

int compare_function(const void *name1, const void *name2)
{
    const char *name1_ = (const char *)name1;
    const char *name2_ = (const char *)name2;
    return strcmp(name1_, name2_);
}

我进行了大量的搜索，并发现在qsort内部必须使用**：

int compare_function(const void *name1, const void *name2)
{
    const char *name1_ = *(const char **)name1;
    const char *name2_ = *(const char **)name2;
    return strcmp(name1_, name2_);
}

这个很好用。

有人能解释一下这个函数中*(const char **)name1的用途吗？我完全不理解。为什么要双指针？为什么我的原始函数不起作用？

谢谢，Boda Cydo。

- bodacydo

---

data 应该声明为 const。 - Billy ONeal

Billy，如果它是const，它仍然可以被排序吗？ - bodacydo

可以的。数组可以是非const的，但是其中包含的指针应该是const类型的。你不能修改编译时常量文字（这样做是未定义的行为）。如果你想要达到这个目的，你需要使用 const char *data[5]。如果你想让整个数组都是常量，那么你需要使用 const char * const data[5]。 - Billy ONeal

Answer 1

如果有助于在您的头脑中保持清晰，那么您应该将指针强制转换为比较器中的类型与您传递给qsort的数据指针的原始类型相同（qsort文档称之为“base”）。但是为了使qsort成为通用函数，它只是处理所有东西都作为void*，而不管它实际上是什么。

因此，如果您要对int数组进行排序，则将传入一个int*（转换为void*）。qsort将向您返回两个void*指向比较器，您将其转换为int *，并取消引用以获取实际比较的int值。

现在将int替换为char*：

如果您要对char*数组进行排序，则将传入一个char**（转换为void*）。qsort将向您返回两个void*指向比较器，您将其转换为char **，并取消引用以获取实际比较的char*值。

在您的示例中，因为您使用的是数组，所以传入的char**是char*数组“衰减”为指向其第一个元素的指针的结果。由于第一个元素是char*，指向它的指针是char**。

- Steve Jessop

Answer 2

想象一下你的数据是 double data[5]。

现在，您的比较方法将接收指向元素（double）的指针（作为void*）。
现在再次用char*替换double。

- H H

Answer 3

qsort 能够对指针以外的其他类型数组进行排序，这也是为什么需要有 size 参数的原因。由于在编译时无法确定数组元素的大小，因此无法直接将它们传递给比较函数。因此，qsort 传递指向 char *、char ** 的指针。在您的情况下，您会得到指向 char * 和 char ** 的指针。

- jilles

---

我不明白，抱歉。qsort的第一个参数是一个*。我传递了一个**。这意味着我实际上只传递了一个*。但是一个*恰好是一个char *。明白了吗？这就是为什么我感到困惑。 - bodacydo

重要的是比较函数使用指向数组元素的指针。由于数组的每个元素都是指向char的指针，因此比较函数操作指向指向char的指针的指针。 - jamesdlin

Answer 4

比较函数需要指向你想要排序的数组中对象类型的指针。由于数组包含 char *，因此你的比较函数需要指向char *，即char **的指针。

- R.. GitHub STOP HELPING ICE

Answer 5

也许给你一个我的代码示例会更容易理解。我正在尝试对一个 TreeNode 数组进行排序，我的比较器的前几行如下：

int compareTreeNode(const void* tt1, const void* tt2) {
   const TreeNode *t1, *t2;
   t1=*(const TreeNode**)tt1;
   t2=*(const TreeNode**)tt2;

之后使用t1和t2进行比较。

- Kemin Zhou

Answer 6

从man qsort中：

The  contents of the array are sorted in ascending 
order according to a comparison function pointed to by
compar, which is called with two arguments that **point**
to the objects being compared.

听起来比较函数会得到指向数组元素的指针。现在，指向char *的指针是char **（即指向字符的指针的指针）。

- Andre Holzner

Answer 7

char *data[5] = { "boda", "cydo", "washington", "dc", "obama" };

这是一条语句，请求编译器为字符指针的大小分配一个长度为5的数组。您已将这些指针初始化为字符串字面量，但对于编译器来说，它仍然是一个包含五个指针的数组。

当您将该数组传递到qsort中时，指针数组会按照C数组参数传递规则衰减为指向第一个元素的指针。

因此，在访问实际包含常量的字符数组之前，您必须处理一级间接寻址。

- Billy ONeal

Answer 8

qsort() 会传递一个指向用户定义比较函数的指针，由于你有一个 char *（指向字符数组的指针），因此你的比较函数应该从指向指针的指针中解引用，因此是 char **。

- Curiosity

Answer 9

@bodacydo 这里有一个程序，可能可以解释其他程序员试图传达的内容，但这只适用于“整数”的情况下。

#include <stdio.h>


int main()
{
    int i , j;
    int *x[2] = {&i, &j};

    i = 10; j = 20;

    printf("in main() address of i = %p, address of j = %p \r\n", &i, &j);

    fun(x);
    fun(x + 1);

    return 0;
}


void fun(int **ptr)
{
    printf("value(it would be an address) of decayed element received = %p, double dereferenced value is %d \r\n",*ptr, **ptr);
    printf("the decayed value can also be printed as *(int **)ptr = %p \r\n", *(int **)ptr );
}

- linuxstack