Как qsort массив указателей на символ в C?

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 в этой функции? Я совсем не понимаю. Почему двойной указатель? Почему не работала моя оригинальная функция?

Спасибо, Бода Чидо.

Answer 1

Если это помогает держать вещи прямо в голове, тип, к которому вы должны привести указатели в компараторе, совпадает с исходным типом указателя данных, который вы передаете в qsort (который qsort docs вызывает base). Но для того, чтобы qsort был общим, он просто обрабатывает все как void*, независимо от того, что это «на самом деле».

Итак, если вы сортируете массив целых чисел, вы передадите int* (преобразованное в void*). qsort вернет вам два void* указателя на компаратор, который вы конвертируете в int*, и разыменование для получения значений int, которые вы фактически сравниваете.

Теперь замените int на char*:

если вы сортируете массив char*, тогда вы передадите char** (преобразованное в void*). qsort вернет вам два void* указателя на компаратор, который вы конвертируете в char**, и разыменование для получения значений char*, которые вы фактически сравниваете.

В вашем примере, поскольку вы используете массив, передаваемый вами char** является результатом того, что массив char* "затухает" до указателя на его первый элемент. Поскольку первый элемент - char*, указатель на него - char**.

Answer 2

Представьте, что ваши данные были double data[5].

Ваш метод сравнения будет получать указатели (double *, переданные как void *) на элементы (double).
Теперь замените double на char * снова.

Answer 3

Функция сравнения берет указатели на тип объекта в массиве, который вы хотите отсортировать.Поскольку массив содержит char *, ваша функция сравнения принимает указатели на char *, или char **.

Answer 4

qsort достаточно для сортировки массивов, состоящих из других вещей, а не указателей.Вот почему параметр размера есть.Он не может напрямую передавать элементы массива в функцию сравнения, поскольку во время компиляции не знает, насколько они велики.Поэтому он проходит указатели.В вашем случае вы получаете указатели на char *, char **.

Answer 5

Может быть, мне проще дать вам пример кода от меня. Я пытаюсь отсортировать массив TreeNodes, и первые несколько строк моего компаратора выглядят так:

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

После этого вы проводите сравнение, используя t1 и t2.

Answer 6

@ 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 );
}

Answer 7

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

- это оператор, запрашивающий у компилятора массив символов размером 5 символов. Вы инициализировали эти указатели для строковых литералов, но для компилятора это все еще массив из пяти указателей.

Когда вы передаете этот массив в qsort, массив указателей превращается в указатель, указывающий на первый элемент, в соответствии с правилами передачи параметров массива C.

Следовательно, вы должны обработать один уровень косвенности, прежде чем сможете перейти к массивам символов, содержащих константы.

Answer 8

из 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 ** (то есть указатель на указатель на символ).